## 12/21/2015

### cryptography12

Cryptography 12

RSA

RSA is a block cipher, the block size must be less than or equal .$\log_{2}(n)+1$, if block size =i bits $2^{i}<n<2^{i}+1$
The encryption and decryption are on the following form
$C = M^{e} mod(n)$
$M = C^{d} mod(n) = (M^{e})^d mod(n) = M^{ed} mod(n)$
The relationship between e and d are multiplicative inverse modulo Q(n) as in Euler Totient Function   ed mod(Q(n))=1
d is relatively prime to Q(n) and e also.

Now let us look at RSA ingredients

1- q and p two prime numbers
2- n=q*p
3- e by using gcd(Q(n),e)=1   1<e<Q(n)
4- d mod(Q(n)) = $e^{-1}$

Example:

1- Two prime numbers p=17 q=11
2- n=q*p= 17*11=187
3- Q(n) = (p-1)*(q-1)= 16*10=160
4- Select e such that e is relatively prime to Q(n)=160 and less than Q(n) ,,, We choose e=7
5- Determine d such that ed mod(Q(n)) = 1 ,,, d=23   (23*7 mod(160) =1)

Choosing q and p:

1- q and p should be differ in length by only a few digits, in 1024 bit key (309+ decimal digits) both q and p should be on the order of magnitude of $10^{75}$ to $10^{100}$.
2- (q-1) and (p-1) should contain a large prime factor.
3- gcd((q-1),(p-1)) should be small.

Note: gcd stands for Greater common divisor http://en.wikipedia.org/wiki/Greatest_common_divisor
Note: If e < n and d < $n^{1/4}$ then d can be easily determined.

Miller-Rabin Algorithm :

Miller-Rabin Algorithm is a primality test, an algorithm which determines whether a given number is prime or not.
In practice, we implement the Miller-Rabin test as follows:

1- Given n, find s so that n1=2sq for some odd q.
2- Pick a random a{1,...,n1}
3- If aq=1 then n passes (Prime).
4- For i=0,...,s1 see if a2iq=1. If so, n passes (Prime).
5- Otherwise n is composite.

The pseudocode Of Miller-Rabin Algorithm :
Input: n > 2, an odd integer to be tested for primality;
k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·q with q odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
pick a randomly in the range [2, n − 1]
x ← aq mod n
if x = 1 or x = n − 1 then do next LOOP
for r = 1 .. s − 1
x ← x2 mod n
if x = 1 then return composite
if x = n − 1 then do next LOOP
return composite
return probably prime

Note: You can use this python code to try Miller-Rabin algorithm https://github.com/Hamza-Megahed/miller-rabin-test/blob/master/miller-rabin.py