Transcript RSA cryptosystem with large key length

Wanjiang Qian
 RSA background
 Totient function φ(n)
 RSA algorithm
 RSA example
 Three algorithms
 Miller-Rabin primality test algorithm
 Euclidean algorithm
 Modular exponentiation
 Two Keys
 Private key known only to individual;
 Public key available to anyone.
 Idea
 Confidentiality: encipher using public key, decipher using private key;
 Integrity/authentication: encipher using private key, decipher using public key.
 Requirements
 It must be computationally easy to encipher or decipher a message given the appropriate
key;
 It must be computationally infeasible to derive the private key from the public key;
 It must be computationally infeasible to determine the private key from a chosen plaintext
attack.
 Totient function φ(n)
 Number of positive integers less than n and relatively prime to n.
 Relatively prime means with no factors in common with n.
 Example: φ(10) = 4
 1, 3, 7, 9 are relatively prime to 10.
 Algorithm
 Choose two large prime numbers p, q
 Let n = pq; then φ(n) = (p–1)(q–1)
 Choose e < n such that e is relatively prime to φ(n).
 Compute d such that ed mod φ(n) = 1
 Public key: (e, n); private key: (d, n)
 Encipher: c = me mod n
 Decipher: m = cd mod n
 Take p = 7, q = 11, so n = 77 and φ(n) = 60
 Alice chooses e = 17, making d = 53
 Bob wants to send Alice secret message HELLO (07 04 11 11 14)
 0717 mod 77 = 28
 0417 mod 77 = 16
 1117 mod 77 = 44
 1117 mod 77 = 44
 1417 mod 77 = 42
 Bob sends 28 16 44 44 42, Alice receives 28 16 44 44 42
 Alice uses private key, d = 53, to decrypt message.
 No one else could read it, as only Alice knows her private key and that is needed for
decryption
 Miller-Rabin Primality test
 an algorithm to determine whether the
number is prime or not.
 Input:
 n is the number needs to have
primality test, k is the number of
witnesses used to test primality of n.
 O(n + min{n-4, k}*n + min{n-4,k}*J +
min{n-4,k}*n*J)
 O(n + k*n + k*J + k*n*J)
 Euclidean algorithm
 an efficient way to calculate the greatest common divisor of two numbers.
 Defined notation ak and bk, k is the steps the Euclidean algorithm will take
 For one step, b1=0, two steps, b2>=1
 For more steps,
 ak=bk+1, ak-1=bk
 bk-1=ak mod bk => ak=q*bk+bk-1 => bk+1=q*bk+bk-1
 Since q>=1, bk+1>=bk+bk-1
 Let Fib(n) stands for nth Fibonacci number.
 Fib(n) = Fib (n-1) + Fib (n-2)




> 2 Fib (n-2)
> 2*(2* Fib (n-4))
> 2*(2*(2* Fib (n-6)))
In general, Fib(n)>2k Fib(n-2k), Let n-2k=1
Fib (n) > 2(n-1)/2 Fib(1) = 2(n-1)/2
Fib (n+1) = a+b, a+b > 2(n+1-1)/2 and n < 2log(a+b)
O(log(a + b))
Input: a, b not both zero
Euclidean(a, b)
if b=0
return a
endif
Euclidean(b, a%b)
endEuclidean
 Modular exponentiation
 a type of exponentiation performed
over a modulus.
 compute md mod n.
 Input
 integer d is expressed as a binary
number dkdk-1…d0.
 Using dynamic programming, it will
look up the previous result form the
table.
 Time complexity will be O(2*k). k is
the length of binary number d.
Key length
Number of attempts
(Primality test)
Time cost (sec)
Average Time cost
(sec)
200
37
0.007381
0.00019
1000
52
0.088834
0.00171
2000
276
1.170117
0.00423
3000
742
7.202896
0.00970
4000
2399
46.41253
0.01924
5000
870
34.46468
0.03961
6000
1333
82.85450
0.06152
 [1] Diffie, W., and Hellman, M. “New directions in cryptography”, IEEE Trans. Inform. Theory IT-22, pp. 644-654, 1976
 [2] G.N. Shinde, and H.S. Fadewar, “Faster RSA Algorithm for Decryption Using Chinese Remainder Theorem”, ICCES, vol.5, no.4,
pp.255-26, 2008
 [3] H. W. Lenstra, Jr., “Miller’s primality test”, Inform. Process. Lett. 8:2, pp. 86-88, 1979.
 [4] L. Zhong, “Modular exponentiation algorithm analysis for energy consumption and performance,” tech. rep., Citeseer,2000.
 [5] Nentawe Y. Goshwe, “Data Encryption and Decryption Using RSA Algorithm in a Network Environment”, International Journal of
Computer Science and Network Security, Vol.13 No.7, pp. 9-13, 2013
 [6] R.L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”,
Communications of the ACM, Volume21 Issue 2, pp. 120-126, 1978.
 [7] Rene Schoof, “Four primality testing algorithms”, Algorithmic Number Theory, Volume 44, 2008.