ElGamal

  • Taher Elgamal, 1985
  • Creation of keys:
    • Choose prime p and two random numbeers g and x which both are smaller than p
    • Calculate
      \qquad y=g^{x}\: mod\: p
    • Public key is \{y,g,p\}
    • Private key is x

Signing message M with ElGamal

  • Choose random number k so that gcd(k,p-1)=1
  • Calculate a=g^{k}\: mod\: p
  • Solve b from equation M=(xa+xb)\: mod\:(p-1)
  • Signature pair is \{a,b\}, random number k stays secret
  • To verify signature calculate that y^{a}a^{b}\: mod\: p=g^{M}\: mod\: p (verifier do not know private key x)
  • Every new signature requires new random k
    • If k is revealed it is possible to solve the secret key
  • DSA (Digital signature algorithm) is based on ElGamal algorithm

Encryption with ElGamal

  • Choose random number k so that gcd(k,p-1)=1
  • Calculate
    \qquad a=g^{k}mod\: p
    \qquad b=y^{k}M\: mod\: p
  • Secret message is pair \{a,b\}, which is twice as long as original message

Decryption with ElGamal

  • Calculate M=\frac{b}{a^{x}}mod\: p
  • Proof: a^{x}\equiv_{p}g^{kx} and b*a^{-x}\equiv_{p}y^{k}M*a^{-x}\equiv_{p}g^{xk}M*g^{-xk}\equiv_{p}M
    • ElGamal is just slightly modified diffie-hellman key-exchange protocol
    • Security relies on the hardness of computing Discrete logarithms instead of factoring big integer like in RSA.
  • In order to find secret key x by knowing public key \{y,g,p\} attacker has to solve discrete logarithm y=g^{x}\: mod\: p

Knapsacks

  • Idea is to gather different weights in the sack and inform the total weight
  • Merkle-Hellman knapsack (first knapsack problem based cipher 1978)
    • Super-Increasing set. E.g.: A\{1,3,7,12,30\}
    • Choose pair \{n,m\}, where m>SUM(A) and has no common factors with m e.g. their gcd is 1.
      • For example: \{13,55\}
      • gcd(13,55) and SUM(A)=53
    • Public key is A_{i}*n\: mod\: m \Rightarrow J\{13,39,36,46,5\}
  • Encryption with public key
    • Divide the message in blocks which size in bits are same as the terms in sack (in this case 5)
    • Add the values in sack on the position of 1-bits of message together
    • For example if block is 01101: 0 1 1 0 1 = 0*13+1*39+1*36+0*46+1*5=80
  • To decrypt the key owner calculates n^{-1}\: mod\: m\:\Rightarrow13^{-1}mod\:55=17
  • The cipher text is then multiplied with inverse of n with modulus m.
  • During the decryption of the message the encrypted message is multiplied with the inverse of n and modulus m is taken from result. From the result, bit values are found out by using the secret key A.
    • J=A*n\: mod\: m\:\Rightarrow\: A=J*n^{-1}mod\: m \Rightarrow A\{1,3,7,12,30\}
  • 80*17\: mod\:55=40 \Rightarrow\:40-30=10,12>10,10-7=3,3-3=0,1>0\:\Rightarrow01101
  • Security of knapsacks:
  • All known knapsack problem based algorithms have been broken.
Last modified: 2013/07/01 14:42