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 which d is relatively prime to Q(n) and e also.

• q and p two prime numbers
• n=q*p
• e by using gcd(Q(n),e)=1  1<e<Q(n)
• 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)

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 1: GCD stands for Greater common divisor
Note 2: If e < n and d < \(n^{1/4}\) then d can be easily determined.

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 = (2^{s}.q)\) for some odd \(q\).
2- Pick a random \(a\in\{1,…,n−1\}\)
3- If \(a^{q}=1\) then \(n\) passes (Prime).
4- For \(i=0,…,s-1\) if \(a^{2i.q}=-1\) If so, \(n\) passes (Prime).
5- Otherwise \(n\) is composite.

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 3: You can use this python code to try Miller-Rabin algorithm