Tag: cryptography

Arytmetyka modulo + Ruboto + Ruby + Android

W związku z zajęciami z kryptografii, potrzebowałem mieć pod ręką trochę narzędzi umożliwiających obliczenie fi (funkcji Eulera), odwrotności modulo, rozkładu liczby na czynniki pierwsze, wyznaczanie odwrotności modulo macierzy 2x2 oraz mnożenie macierzy 2x2 razy 1x2 oraz obliczenia modulo z duuuuuużych liczb przedstawionych jako potęg. Dlatego też powstał kod działający na Androidzie. Jedyne wymaganie to Ruboto - do znalezienia na Markecie. Jest to JRuby dla Androida, umożliwiający odpalanie prostych skryptów na telefonie. Idealne kiedy trzeba napisać coś na szybko. Zaczniemy od potęgowania. Spróbuj dokonać takiego obliczenia modulo: 12345^12345 mod126 w kalkulatorze na Windows. Chyba się nie udało ;) A ten oto poniższy kod, świetnie sobie z tym radzi:

liczba = 12345
power = 12345
n = 126
#--------------------------------------
def mod(liczba, power, n)
  val = 1

  power.times do |i|
    val *= liczba
    val %= n
  end
  val
end

puts "#{liczba}^#{power}(mod#{n})= #{mod(liczba, power, n)}"

A wynikiem jest: 99 Następnie mamy funkcję Eulera (fi):

liczba = 30
#--------------------------------------
def phi(m)
  r = (2..m)
  primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}
  primes.inject(m){|e, p| e%p==0 ? e/p*(p-1) : e}
end

puts "fi dla #{liczba} wynosi: #{phi(liczba)}"

Która też działa niczego sobie :) - oczywiście to obliczenie dla zbyt dużych liczb na telefonie komórkowym nie będzie przebiegać zbyt szybko, więc używajcie z rozwagą ;) Kolejnym kawałkiem kodu jest kod obliczający odwrotność zadanej liczby w sensie modulo:

liczba = 315
n = 676
#--------------------------------------

class Integer
  def to_ba(size=128)
    a=[]
    (size-1).downto(0) do |i|
      a<<< 2**index
  }

  val = 1
  powers.each { |pow|
    pow.times do |i|
      val *= liczba
      val %= n
    end
  }
  val
end

def check(liczba, odw, n)
  (liczba*odw)%n == 1
end

odw = odwrotnosc(liczba, n)

if odw == 0
  puts "Odwrotnosc nie istnieje NWD(#{liczba}, #{n}) != 1"
else

  if check(liczba, odw, n)
    puts "#{liczba}^-1 (mod#{n})= #{odw}"
  else
    puts "NWD(#{liczba}, #{n}) != 1"
  end
end

Rozkład liczby na czynniki pierwsze:

liczba = 2

# -----------------------------------------------------------------------------
def factorize(orig)
    factors = {}
    factors.default = 0
    n = orig
    i = 2
    sqi = 4
    while sqi <= n do
        while n.modulo(i) == 0 do
            n /= i
            factors[i] += 1
        end
        sqi += 2 * i + 1
        i += 1
    end

    if (n != 1) && (n != orig)
        factors[n] += 1
    end
    factors
end

def printfactorhash(orig, factorcount)
    print format("%-10d ", orig)
    if factorcount.length == 0
        print "Liczba pierwsza"
    else
        factorcount.sort.each { |factor,exponent|
            print factor
            if exponent > 1
                print "^", exponent
            end
            print " "
        }
    end
    puts
end

n = liczba.to_i
mfactors = factorize(n)
printfactorhash(n, mfactors)

Odwrotność macierzy (w sensie modulo):

MATRIX = [[0,11],
          [17,0]]

#[a, b]
#[c, d]

n = 29

#--------------------------------------

class Integer
  def to_ba(size=128)
    a=[]
    (size-1).downto(0) do |i|
      a<<self[i]
    end
    a
  end
end

def phi(m)
  r = (2..m)
  primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}
  primes.inject(m){|e, p| e%p==0 ? e/p*(p-1) : e}
end

def odwrotnosc(liczba, n)
  fi = phi(n)

  powers = []
  (fi-1).to_ba.reverse.each_with_index { |b, index|
    next if b == 0
    powers << 2**index
  }

  val = 1
  powers.each { |pow|
    pow.times do |i|
      val *= liczba
      val %= n
    end
  }
  val
end

def nwd(a,b)
  if a > b then a -= b else b -= a end while a != b; return a
end

def det(m)
  m[0][0].to_i*m[1][1].to_i-m[0][1].to_i*m[1][0].to_i
end

def inverse(m, n)

  det = det(m)
  det = det%n

  if nwd(det, n) != 1
    puts "NWD(m, n) != 1"
    exit
  end

  puts "det= #{det}"
  odw_a = odwrotnosc(det, n)
  puts "det^-1mod(#{n})= #{odw_a}"

  w = []
  w << [odw_a*m[1][1]%n, -odw_a*m[0][1]%n ]
  w << [-odw_a*m[1][0]%n, odw_a*m[0][0]%n ]
  w
end

def print_res(w)
  puts "[#{w[0][0]}, #{w[0][1]}]"
  puts "[#{w[1][0]}, #{w[1][1]}]"
end

print_res(inverse(MATRIX, n))

Mnożenie macierzy 2x2 przez 1x2 (w sensie modulo n)

MATRIX1 = [
          [21,19],
          [22,18]]

MATRIX2 = [15, 24]

n = 29

def multiply(m1, m2, n)
  w = [(m1[0][0]*m2[0]+m1[0][1]*m2[1])%n, (m1[1][0]*m2[0]+m1[1][1]*m2[1])%n ]
end

def print_res(res)
  puts "[ #{res[0]}, #{res[1]}]"
end

print_res(multiply(MATRIX1, MATRIX2, n))

Podsumowując: powyżej zamieściłem kod który wykonuje następujące czynności:

  • Obliczanie modulo dużych liczb przedstawionych w postaci potęg
  • Funkcja Eulera - algorytm obliczenia wartości funkcji fi
  • Obliczanie odwrotności liczby w sensie modulo
  • Rozkład liczby na czynniki pierwsze

Mam nadzieję że się przyda :) A tutaj: źródełko

Why should I always use salt in hashes

Most people already heard that, however it's worth mentioning (via wiki):

A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the (cryptographic) hash value, such that an accidental or intentional change to the data will change the hash value. The data to be encoded is often called the "message," and the hash value is sometimes called the message digest or simply digest.

But, what does it really mean? It's quite simple - we have and input string (or some other data), we "insert" it into our algorithm and on output we will have a new "shortcuted" string. This operation is one-sided, so you cannot turn it back (to be honest you can but it is really hard). If you use SHA-2 hash function, the output looks similar to this:

4e2ecff8f8be5a7d4d8821266d956d844aa5b8eebd5983edbaaa6fa7fc9bc9e21
de42d443f50d8608a79f6507b7e95c6d4a913615c85710f86a40bc23cdc5d5d

When we store users passwords in our systems (databases, files, etc), they should be safe. If we get hacked and our database will get stolen, passwords should be protected. No one should be able to read them. Most users have one password for all their web-activities, so if this password get stolen, probably cracker will be able to log in into victim Facebook, Twitter and any other web accounts.

If we store not a pure password but its hash shortcut - even if it get stolen, cracker will not be able to use it to authorize into any type of account.

When using cryptographic hash function, we must remember about some rules:

  • MD5 should not be used for critical functions such as hashing passwords
  • Every hash function with "open" algorithm can be "broken" using brute-force attack
  • Every brute-force attack can be speeded up by using rainbow tables
  • Allowing users to create simple passwords is also not recommended

Remember this and you will be safe.

First of all, lets select one of hash functions. MD5 is old (and weak), also SHA1 has some vulnerabilities. The most common safe hash function is SHA2 and it is recommended when hashing password.

But what about brute-force attacks? Any password should be validated before use. They should not be to short or two simple. We can do it by using regular expression like this one:

^(?=.*\d)(?=.*([a-z]|[A-Z]))([\x20-\x7E]){8,40}$

Regexp presented above will ensure has minimum 8 chars, minimum one big letter and minimum one digit. Using this type of regular expressions will ensure that none user will have password like "abc" or any similar. But still, if we have rainbow tables and a lot of password hashes, we can extract at least some of them. How to protect ourself against attacks based on rainbow tables? Use salt.

What is salt? Salt consists of random bits, creating one of the inputs to a one-way hash function.In a typical usage for password authentication, the salt is stored along with the output of the one-way function, sometimes along with the number of iterations to be used in generating the output (for key stretching). After mixing salt into password any rainbow table will be meaningless.

How tu generate and use salt? The easiest way is to use one, global salt. Example:

# only small letters and digits
Password: "123qwerty"
# small and big letters, special chars and digits
Salt: "%^&amp;*(#@$@K:JKBJVCHKB@QRU)+{KMF  er23"
# password+salt
Hash: sha2

As you can see above - using salt will dramatically increase password power. One global salt has one major and really big disadvantage. If two users have same password they will also have same output hash. So, if we have a lot of users and some of them have same hashed password, we need to figure out only one hash and we will have access to accounts of the rest of users with same hash. We can also generate our own rainbow table dedicated for our cryptographic hash function and salt.

To protect against such behaviours we should use uniq per user salt. How to generate such salt? Combine some per user data and some random stuff. Example:

salt = user.login+user.created_at+rand(10**5)+'65241770q_  E9089u(&amp;'

We store salt with password hash. Don't worry - it is safe. Since each user has his own uniq hash, there does not exist any general rainbow table. Mix password, dynamic and static salt and you will be safe. Furthermore, when mixing salts and password in a uniq way - until cracker steals database and source codes, he will not know how to generate rainbow tables. Example:

hashed_pass = SHA2(user.login+user.password+salt+static_salt)

Copyright © 2024 Closer to Code

Theme by Anders NorenUp ↑