Cryptography 12

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)\)

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.

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 n−1=2sq for some odd q .

2- Pick a randoma∈{1,...,n−1}

2- Pick a random

3- If aq=1 then n passes (Prime).

4- Fori=0,...,s−1 see if a2iq=−1 . If so, n passes (Prime).

5- Otherwisen is composite.

4- For

5- Otherwise

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 testOutput:compositeifnis composite, otherwiseprobably primewriten− 1 as 2^{s}·qwithqodd by factoring powers of 2 fromn− 1 LOOP:repeatktimes: pickarandomly in the range [2,n− 1]x←a^{q}modnifx= 1 orx=n− 1thendonextLOOPforr= 1 ..s− 1x←x^{2}modnifx= 1thenreturncompositeifx=n− 1thendonextLOOPreturncompositereturnprobably 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`