## 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.