# Secured Communications

Asymmetric Cryptography

## Asymmetric cryptography

• Relies on use of two keys: Public and private
• Sometimes called Public key systems
• Idea of publickey cryptosystem was first publicly suggested by Whitfield Diffie and Martin Hellman
• Encryption is conducted with the recipients public key, decryption with corresponding private key (secret key)
• After encryption only the recipient (or who ever knows the secret key) may decrypt the message
• Some algorithms can be used also for digital signatures
• encryption with the signers secret key. (more on digital signatures lecture)
• Different kind of mathematical approaches have been developed to accomplish the result
• every approach relies on modular algebra e.g. calulcating in fields
• RSA, ElGamal, DSA (only for signing), ECC

## RSA

• Key generation for RSA
1. Generate two big primes p and q, which are roughly the same size. (Has same amount of digits)
2. Calculate $n=pq$and $\phi=(p-1)(q-1)$
3. Select random key e, $1so that $gcd(e,\phi)=1$. (Thus e and $\phi$ are relatively prime)
4. Calculate key d, $1, so that $ed\equiv_{\phi}1$ i.e. $d=e^{-1}mod(\phi)$ (for example using extended euclidean algorithm on formula $ed-\phi k=1$)
5. Public key is (n,e), private key is d.
• p , q and $\phi$ should be kept secret.

## Encrypting and decrypting with RSA

• Divide message M in blocks that are smaller than n (i.e. is size of n is the block size should be 64 bits on maximum.
• Encrypt the blocks using formula
$c_{i}=M_{i}^{e}mod\: n$ , where i is the block number
• Decryption is done with formula $M_{i}=c_{i}^{d}mod\: n$
• Proof: $c_{i}^{d}=(M_{i}^{e})^{d}=M_{i}^{ed}=M_{i}^{k*\phi+1}=M_{i}M_{i}^{k\phi}=M_{i}*1\,(\,mod\, n\,)$
• from key generation: $ed-\phi k=1\rightarrow ed=1+\phi k$
• Remember the Euler's theorem $a^{\phi(p)}\equiv_{p}1$ if gcd (a,p) = 1
• RSA operations are interchangeable
• Encryption can be done with either public or private key. Decryption is thus done with the key not used in encryption.

## RSA example

• let $p=47\; q=71\Rightarrow n=p*q=3337$
• e cannot have common divisor with $(p-1)(q-1)=46*70=3220$ .
• Choose $e=79$ ; $gcd(79,3220)=1$
• Calculate $d=79^{-1}mod\:3220=1019$
• Let the message be 1010110000 which is same as integer 688
• Encryption: $688^{79}mod\:3337=1570$ , which in binary form (11000100010) is the encrypted message
• Decryption: $1570^{1019}mod\:3337=688$

## Speeding up RSA

• Choosing e cleverly can speed up the RSA calculations, Common choices are 3, 17 ja 65537
• $65537=2^{16}+1$,has only two 1 bits in binary form (first and last bit), which speeds up calculations.
• Note! : There are risks on using small e (see RSA security)
• If p and q has been stored it is possible to speed up operations done with private key by using chinese remainder theorem

## RSA security

• The security is presumed to rely on the hardness of factoring
• Try to factor n in order to find p and q, to be able to calculate d
• Current factorization methods base on quadratic sieve method.
• In 1994 a number with 129 digits (~428 bits) was factorized with Quadratic sieve. In 2005 number with 200 digits was factorized (663 bits), with lattice sieve algorithm
• There is no mathematical proof that n has to be factored in order to find out decryption key d and message m. (no-one just don't know any other way.)
• Attack against value $\phi$ is not easier than factoring n. ( $\phi$ is about the size of n, factoring is as hard)
• Trying all possible d's has also the same complexity.
• Brute force attack
• Try all possible decryption keys d to find message
• when d is big enough this is at least as slow as factoring n
• Timing attacks
• measuring the time how long it takes to decrypt a message to determine the private key
• counter measure: Blinding e.g. multiple the cipher text with random number that is also encrypted before decrypting the message

## Attacks against RSA implementation or use

• Common modulus attack
• Let's assume implementation of RSA gives same modulus to all users.
• Same message is encrypted with two different keys that has same modulus (due to bad RSA implementation)
• $c_{1}=m^{e_{1}}\: mod\: n$ $c_{2}=m^{e_{2}}\: mod\: n$
• Cryptoanalyst now knows values n,$e_{1}$,$e_{2}$,$c_{1}$,$c_{2}$
• If $gcd(e_{1},e_{2})=1$, which is very likely, the analyst can use extended euclidean algorithm to calculate r and s so that $re_{1}+se_{2}=1$
• Let's presume r is in this case negative (one of the values has to be)
• Using extended euclideaan algorithm calculate $c_{1}^{-1}$, after which you can calculate the original message $(c_{1}^{-1})^{-r}*c_{2}^{s}=m\: mod\: n$
• Attacks when RSA is used for both encrypting and making digital signatures will be discussed on signatures lectures.
• Notes on using small encryption exponent
• If $\frac{e(e+1)}{2}$ linearly dependant messages are encrypted with different public keys, which have same e there is an attack against the system.
• If the messages are identical it is enough to have e messages to make the attack.
• Menezes et al. p.288 for more details to those interested.
• It is good idea to pad messages with random characters , to prevent such attacks

## Elliptic curves

• Elliptic curve is $y^{2}=x^{3}+ax+b$, where x, y, a and b are real numbers.
• if $x^{3}+ax+b$ has no repeated factors (or if $4a^{3}+27b^{2}\neq0$) the curve can be used to form a group for elliptic curve cryptography (ECC)
• Adding points in elliptic curve group.
• Draw a line between points and calculate the 3rd point in curve that the line crosses. Then take reflection in the x axis of this point to get the result.
• If there is no third point crossed, the result is called point of infinity.
• Let's calculate P + Q = R where P = (xP,yP) and Q = (xQ,yQ) and P,Q are not negative of each other e.g. R $\neq0$
• $s=\frac{P_{y}-Q_{y}}{P_{x}-Q_{x}}$ e.g. (slope of the line through P and Q)
• $R_{x}= s^{2}-P_{x}-Q_{x}$ and $R_{y}=-P_{y}+s(P_{x}-R_{x})$
• Adding point to itself (e.g. P+P=2P)
• Draw a tangent for the selected point P in curve, calculate where the tangent crosses the curve. Then take reflection in the x axis of this point to get the result i.e. 2P
• to calculate with higher multipliers: 3P=2P+P, 4P=2(2P) and so on.
• Calculate R when 2P = R $\neq0$
• $s=\frac{3P_{x}^{2}+a}{2P_{Y}}$
• $R_{X}=s^{2}-2P_{x}$ and $R_{y}=s(P_{x}-R_{x})-P_{y}$

## Elliptic curve mod p

• Reducing the area on which the points may be on some field p
• let's assume curve: $y^{2}\equiv_{5}x^{3}+4x+4$
• in mod 5 the values for x can be 0,1,2,3,4 and point of infinity

$x\equiv_{5}0\Rightarrow y^{2}\equiv_{5}0+4*0+4=4\Rightarrow y\equiv2,-2\rightarrow y\equiv_{5}2,3$ $(5-2=3)$$( 2^{2}=4\, and\,3^{2}=9\Rightarrow9\, mod\,5=4)$
$x\equiv_{5}1\Rightarrow y^{2}\equiv_{5}4\Rightarrow y\equiv_{5}2,3$ $x\equiv_{5}2\Rightarrow y^{2}\equiv_{5}0\Rightarrow y\equiv_{5}0$
$x\equiv_{5}3\Rightarrow y^{2}\equiv_{5}3$ No solution $x\equiv_{5}4\Rightarrow y^{2}\equiv_{5}4\Rightarrow y\equiv_{5}2,3$
$x=\infty\Rightarrow y=\infty$

• Thus the points for curve in mod 5 are (0,2),(0,3),(1,2),(1,3),(2,0),(4,2),(4,3) and ($\infty,\infty$)
• Adding points is done as normal though remember $\frac{a}{b}=a*b^{-1}$
• adding points (1,2) and (4,3) in above curve together
slope $m\equiv_{5}\frac{3-2}{4-1}\equiv\frac{1}{3}\equiv2$, $(3*2\equiv_{5}1)$
$x_{3}\equiv_{5}m^{2}-x_{1}-x_{2}\equiv_{5}2^{2}-1-4\equiv_{5}4$
$y_{3}\equiv_{5}m(x_{1}-x_{3})-y_{1}\equiv_{5}2(1-4)-2\equiv_{5}2$
• Thus: (1,2) + (4,3) = (4,2)

## Elliptic curve discrete logarithm problem(ECDLP)

• Given two points G and Y on an elliptic curve such that Y = kG (that is, Y is G added to itself k times), find the integer k.
• In discrete logarithm we have to try all possible powers, in elliptic curve we have to try all k
• Like in discrete logarithms the calculations can be done much faster when the multiplier k is known

## Elliptic curve cryptography (ECC) principles

• Let's first define the curve $y^{2}\equiv_{5}x^{3}+ax+b\,\, mod\, p$ e.g. $E_{p}(a,b)$
• Generation of keys:
• First select base point B in the curve
• Pick random integer k, which is the secret key
• Compute point K by scalar multiplication K=k*B
• Public key is [K,B,a,b,p] secret key [k,B,a,b,p]
• Encryption
• First Message is described as point M on curve
• Select randon integer r and compute $C_{0}=r*B$ and $C_{1}=M+r*K$
• The cipher text is point pair $[C_{0}\,\, C_{1} ]$
• Decryption
• calculate: $C_{1}-k*C_{2}=M$
• Proof:
• $C_{1}=M+rK$ , $C_{0}=r*B$ and K=k*B
• thus: $M+rK-k(r*B)\rightarrow M+r(k*B)-k(r*B)=M$

## Data as point in curve

• Simple method (Koblitz)
• use m (in integer) as an x-coordinate of a point in curve.
• It is possible that there is no valid y for the given x-coordinate
• Add few bits at the end of m and change them until you find a proper point
• all messages should have equal amount of these additional bits

## Elliptic curve uses

• ECIES (Elliptic Curve Integrated Encryption Scheme)
• The actual message is encrypted with symmetric algorithm, but with use of elliptic curves the symmetric key can be transmitted to the receiver along with the encrypted message
• PSEC (Provable Secure Encryption Curve scheme)
• Like ECIES
• ECDSA (Elliptic curve digital signature algorithm)
• Signatures with Elliptic curves can be done in similar fashion than DSA (which is related to ElGamal)
• Will be talked more on signature lectures

## Diffie-hellman type key exchange with elliptic curves

• First decide elliptic curve and choose point P
• A chooses random number k and calculates multiplied P i.e. kP and sends this to B
• B chooses random number l and calculates multiplied P i.e. lP and sends this to A
• Now A can calculate shared key by multiplying the received lP with k i.e. k(lP).
• B gets the same point by multiplying the gained results from a with his own secret i.e. l(kP)
• The shared key is point lkP==klP

## Elliptic curve in action

• Elliptic curves can have smaller key size than RSA or other discrete logarithm based asymmetric systems. (224 bit ECC key is equivalent to 2048 bit RSA key from security point of view)
• ECC is overall a bit faster than RSA (ECC with 160 bit key vs RSA 1024 bit key)
• ECC is faster in decryption (and signing) while slower in encryption (and verifying) than RSA.
• Standards define the curves used.
• Elliptic curves have several patent issues, which has slowed down their use