2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name RSA Group Name RSA Code Elliptic Curve Cryptograrhy Group /Project No. 13-B /Project Leader 1009087 Takahiro Okubo /Group Leader 1009064 Takumi Ito /Group Member 1009064 Takumi Ito 1009067 Hanako Hakodate 1009076 Yoshitaka Nagai 1009145 Manami Oikawa Masaaki Shirase Advisor Osamu Konishi 2012 1 18 Date of Submission January 18, 2012
RSA 4 RSA RSA RSA RSA RSA RSA - i -
Abstract This project implements a device for person who are not interested in cryptography to enjoy by visualization of break. Then, we divide into four groups, Birthday paradox, RSA cryptography, Elliptic Curve Cryptography, Implementation and learn it about a code the first term. The RSA cryptograph group and the Elliptic Curve Cryptography were united and learned the second term. RSA cryptography is generally used widely because safety is secured by the hardness prime factoring of big numerical. Elliptic Curve Cryptography is a relatively new cryptography. Elliptic Curve Cryptography can handle the processing that is equal to RSA cryptography in short time. Attacker of Symmetric key cryptography which many persons images needs thought such as the Frequency analysis. On the other hand, public key cryptosystems such as RSA and elliptic curve cryptographies can decipher by using a way of thinking of Birthday paradox. Therefore the birthday paradox is very important in the fild of the cryptography. We want to implement plain visualization of the decryption by this project. Keyword Public key cryptosystem, Birthday Paradox, RSA cryptography, Elliptic Curve Cryptography - ii -
1 1 1.1................................. 1 1.2...................................... 1 2 2 2.1............................ 2 2.2............................... 2 3 4 3.1.......................................... 4 3.2.......................................... 4 4 5 4.1.......................................... 5 4.2........................................ 5 4.3.......................................... 5 4.4..................................... 5 4.5........................................... 5 4.6........................................ 5 4.7........................................ 6 4.8...................................... 6 4.9...................................... 7 4.10 DES....................................... 7 4.11..................................... 7 4.12...................................... 8 4.13...................................... 9 4.14..................................... 10 5 RSA 11 5.1.......................................... 11 5.2.................................... 11 5.3..................................... 11 5.4........................................ 12 5.5.......................................... 12 5.6 RSA.................................... 13 6 4 15 6.1........................................ 15 6.2........................................ 15 - iii -
6.3.......................................... 15 6.4....................................... 15 7 16 7.1 RSA.................................. 16 7.2................................ 16 7.3........................... 17 7.4........................................ 17 7.5.......................................... 18 7.6.................................... 19 8 21 8.1..................................... 21 8.2................................. 21 8.3.......................................... 21 8.4........................................ 22 8.5..................................... 22 8.6.............................. 23 8.7.................................. 23 8.8.......................................... 23 8.9................................. 24 8.10.......................................... 26 9 28 9.1.................................... 28 9.2............... 28 9.3........................... 35 9.3.1.................................... 35 9.3.2.................................... 35 9.3.3.................................... 35 9.3.4................................... 35 10 36 10.1....................................... 36 10.1.1............................... 36 10.1.2............................... 36 10.1.3............................. 37 10.2....................................... 38 10.2.1............................... 38 10.2.2............................... 39 10.2.3............................. 40 11 42 11.1.......................................... 42 - iv -
11.2.......................................... 42 12 44 13 45 A 50 B 51 52 - v -
1 1.1 1.2 Group Report of 2011 SISP - 1 - Group Number 13-B
2 2.1 RSA 2.2 RSA 3 4 RSA RSA 3 RSA RSA RSA RSA RSA RSA Group Report of 2011 SISP - 2 - Group Number 13-B
ipad Group Report of 2011 SISP - 3 - Group Number 13-B
3 ipad RSA PARI/GP 2 2 3.1 RSA RSA PARI/GP RSA 3.2 PARI/GP Group Report of 2011 SISP - 4 - Group Number 13-B
4 4.1 4.2 4.3 ( ) 4.4 4.5 4.6 Group Report of 2011 SISP - 5 - Group Number 13-B
4.7 4.8 2 2 1 2 3 RSA 1 1 2 ElGamal 2 1 3 DES 64bit 64bit 64bit 1024bit ElGamal 1024bit 2024bit 1024bit RSA RSA RSA ElGamal, Group Report of 2011 SISP - 6 - Group Number 13-B
4.9 DES 4.10 DES DES 64 56 DES DES 3 DES UNIX DES UNIX DES /etc/passwd UNIX 8 DES 56 DES 16 24 4.11 Group Report of 2011 SISP - 7 - Group Number 13-B
4.12 IC Group Report of 2011 SISP - 8 - Group Number 13-B
4.13 2 1 1 Group Report of 2011 SISP - 9 - Group Number 13-B
4.14 3 DES Group Report of 2011 SISP - 10 - Group Number 13-B
5 RSA Ronald Rivest Adi Shamir Leonard Adleman 3 1978 RSA 5.1 RSA RSA RSA 5.2 RSA 1 p q 2 n = p q (n) (p 1)(q 1) n 3.gcd, ( ) 1 e( ) gcd e n e,n 4 de mod (n) d d n d,n 5 e,n p,q,d 5.3 ( ) Group Report of 2011 SISP - 11 - Group Number 13-B
(1. C = M e mod n (2. M = C d mod n RSA 1 5.4 RSA RSA RSA, RSA 5.5 1975 n d n f(x) ( ) X 2 + 1 X0 Xi = f(xi 1) mod n X0 = 2, f(x) = X 2 + 1, n=1133 X0 = 2, X1 = 5, X2 = 26, X3 = 677... Y i = Xi mod d d=11 Yi Y 0 = 2, Y 1 = 5, Y 2 = 4, Y 3 = 6... Xi = f(xi 1) mod n Yi d f(y i 1) d ( d ) i j Y i = Y j t Y i + t = Y j + t Yi Yj Xi = Xj(mod d) d Xi Xj Xi Xj gcd(n, Xi Xj) n c c j-i i j Group Report of 2011 SISP - 12 - Group Number 13-B
5.1 5.6 RSA RSA p q p = 7, q = 13 n = p q = 72 e = 5 (n) = (p 1) (q 1) = 220 e 1 ed 1(mod ( )) n d d = 29 e n (e, n) = (5, 72) n x e (mod n) x = 33 e (mod n) = 335(mod 72) = 6 6 d 6 d (mod n) = 33 d (n) = 72 (n) n Group Report of 2011 SISP - 13 - Group Number 13-B
n p q (n) Group Report of 2011 SISP - 14 - Group Number 13-B
6 4 6.1 6.2 6.3 ( ) 6.4 Group Report of 2011 SISP - 15 - Group Number 13-B
7 7.1 RSA RSA RSA C ASCII RSA p,q N e d e (p 1) (q 1) d (p 1) (q 1) e d RSA N 7.2 a, b (a b) a b r a b b r b r r 0 a b 1071 1029 1071 1029 42 1029 42 21 42 21 21 1. m, n (m n) 2. n = 0 m 3. m n n n m 2. Group Report of 2011 SISP - 16 - Group Number 13-B
7.3 m, n gcd(m,n) am + bn = gcd(m, n) a, b 1071 1029 1071 = 1 1029 + 42 1029 = 24 42 + 21 42 = 2 21 21 = 1029 24 42 = 1029 24 (1071 1 1029) = 24 1071 + 25 1029 m, n 1 am + bn = c c (a, b) e d 7.4 p=7 q=13 e=5 April P r e s s 80 114 101 115 115 ASCII 33 e mod N) 47 81 68 82 82 73 9 87 10 10 33 Group Report of 2011 SISP - 17 - Group Number 13-B
j * x + + 7.5 (p 1)*(q 1) e d (p 1) (q 1) = 6 12 = 72 e = 5 72 = 5 14 + 2 5 = 2 2 + 1 1 = 5 2 2 = 5 (72 5 14) 2 = 5 29 72 2 d = 29 33 j * x + + 73 9 87 10 10 d 47 81 68 82 82 33 80 114 101 115 115 P r e s s Group Report of 2011 SISP - 18 - Group Number 13-B
7.6 p q N e p q d N N=91 e=7 Me[6vC N f(x) = x2 + 1 mod N x = 2 y = 2 d = 1 x = f(x) = 5 y = f(f(y)) = f(5) = 26 d = gcd( x y, N) = gcd(21, 91) = 7 p = 7 q f(x) = x2 + 10 mod N x = f(x) = 14 y = f(f(y)) = f(14) = 24 d = gcd( x y, N) = gcd(10, 91) = 1 d 1 x = f(x) = 24 Group Report of 2011 SISP - 19 - Group Number 13-B
y = f(f(y)) = f(40) = 63 d = gcd( x y, N) = gcd(39, 91) = 13 q = 13 p q e d (p 1) (q 1) = 6 12 = 72 e = 7 72 = 7 10 + 2 7 = 2 3 + 1 1 = 7 2 3 = 7 (72 7 10) 3 = 7 31 72 3 d = 31 33 M e [ 6 v C 44 68 58 21 85 34 d 33 119 101 105 103 104 116 w e i g h t Group Report of 2011 SISP - 20 - Group Number 13-B
8 8.1 y 2 = x 3 + ax + b 4a 3 + 27b 2 0 8.2 8.3 x y E : y 2 = x 3 + ax + b P Q R = P + Q 1. P Q L 2. E L R 3.R x R R R R = R R P + Q E : y 2 = x 3 + ax + b P(x1,y1) Q(x2,y2) R(x3,y3) Group Report of 2011 SISP - 21 - Group Number 13-B
P Q x3 = 2 x1 x2 y3 = (x1 x3) y1 = (y2 y1)/(x2 x1) P Q x3 = 2 2x1 y3 = (x1 x3) y1 = (3x1 2 + a)/2y1 8.4 x y E : y 2 = x 3 + ax + b P S = 2P 1. P 2. E S 3.S x S S P 2P 8.5 P d P d d * P = P + + P d * P d? 1 8 * P = P + P + P + P + P + P + P + P Group Report of 2011 SISP - 22 - Group Number 13-B
8 * P = 2 * (2 * (2 * P)) 8.6 Z p Z mod p m ( p - 1)2 m ( p + 1)2 P Q ip = Q i 8.7 y 2 = x 3 + ax + b P s s Q Q = sp Q P s P Q s s P Q s 8.8 RSA Group Report of 2011 SISP - 23 - Group Number 13-B
RSA RSA RSA RSA 8.1 8.9 k P, Q = kp, y 2 = x 3 + ax + b ( ) Group Report of 2011 SISP - 24 - Group Number 13-B
( ) X r A = rp B = X + rq A B (A,B) ( ) k B ka B ka = (X + rq) k(rp ) = X + rkp krp = X P, Q = kp, y 2 = x 3 + x + b k = 13 P = (1, 1) P = (1, 1), 2P = (2, 16), 3P = (13, 9), 4P = (16, 8), 5P = (11, 7) 6P = (18, 4), 7P = (7, 8), 8P = (15, 8), 9P = (8, 5), 10P = (8, 14) 11P = (15, 11), 12P = (7, 11), 13P = (18, 15), 14P = (11, 12), 15P = (16, 11) 16P = (13, 10), 17P = (2, 3), 18P = (1, 18), 19P = (0, 0) 19 Q = kp = 13P = 13(1, 1) = (18, 15) X = (15, 11) r = 3 A = rp = 3(1, 1) = (13, 9) B = X + 3 Q = (15, 11) + 3(18, 15) = (15, 11) + 3 13P = (15, 11) + (13, 10) = (9, 2) = ((13, 9), (9, 2)) k = 13 (9, 2) 13(13, 9) = (9, 2) (13, 10) = ( 4, 8) = (19 4, 19 8) = (15, 11) Group Report of 2011 SISP - 25 - Group Number 13-B
= X 8.10 PARI/GP s p q q = sp p q s p q p 100 p = 1000000000; p = nextprime(p); q = p + 1 ellap(e, p); P (x, y) x = Mod(1, p); y = Mod(2, p); s s = 1 + random(q 1); m p m m = random(p); m m C1 r = 1 + random(q 1); C1 = ellpow(e, P, r); Group Report of 2011 SISP - 26 - Group Number 13-B
a b a1 b1 A1 q A1 = f(a1, b1, R1); a = A[1]b=A[2]a1 = A1[1]b1=A1[2] a b a1 b1 s s1 if(gcd(b b1, l) == 1, s1 = Mod((a1 a)/(b b1), l); s1 = lift(s1); s1 s s1 s s m Group Report of 2011 SISP - 27 - Group Number 13-B
9 9.1 4 5 PARI/GP 6 RSA 7 RSA 8 9 10 RSA RSA 11 12 1 9.2 Group Report of 2011 SISP - 28 - Group Number 13-B
4 PARI/GP PARI/GP PARI/GP 5 RSA RSA Mod PARI/GP PARI/GP 6 RSA PARI/GP RSA Mod 7 8 9 RSA 10 11 12 Group Report of 2011 SISP - 29 - Group Number 13-B
1 4 PARI/GP PARI/GP PARI/GP 5 RSA RSA Mod PARI/GP PARI/GP 6 RSA PARI/GP Mod 7 8 9 RSA Group Report of 2011 SISP - 30 - Group Number 13-B
10 11 RSA 12 1 4 PARI/GP PARI/GP PARI/GP 5 RSA RSA Mod Group Report of 2011 SISP - 31 - Group Number 13-B
PARI/GP PARI/GP 6 7 8 C 9 RSA RSA RSA 10 RSA Java Java C RSA 11 Group Report of 2011 SISP - 32 - Group Number 13-B
RSA 12 RSA RSA 1 4 PARI/GP PARI/GP PARI/GP 5 RSA RSA Mod PARI/GP PARI/GP 6 7 Group Report of 2011 SISP - 33 - Group Number 13-B
8 9 10 SAR SAR 11 SAR 12 Group Report of 2011 SISP - 34 - Group Number 13-B
1 9.3 9.3.1 RSA RSA 9.3.2 RSA RSA 9.3.3 9.3.4 Group Report of 2011 SISP - 35 - Group Number 13-B
10 10.1 10.1.1 10.1.2 Group Report of 2011 SISP - 36 - Group Number 13-B
RSA 10.1.3 10 6.54 10 6.5 Group Report of 2011 SISP - 37 - Group Number 13-B
10.2 10.1 10.2.1 i Pad Group Report of 2011 SISP - 38 - Group Number 13-B
10.2.2 Group Report of 2011 SISP - 39 - Group Number 13-B
RSA 10.2.3 10 6.46 10 6.53 i Pad Group Report of 2011 SISP - 40 - Group Number 13-B
RSA Group Report of 2011 SISP - 41 - Group Number 13-B
11 11.1 RSA PARI/GP RSA od RSA PARI/GP PARI/GP RSA RSA PARI/GP RSA RSA 1975 RSA RSA RSA 11.2 6.54 6.5 6.46 6.53 RSA RARI/GP RSA Group Report of 2011 SISP - 42 - Group Number 13-B
RSA PARI/GP RSA RSA RSA Group Report of 2011 SISP - 43 - Group Number 13-B
12 RSA RARI/GP RSA Group Report of 2011 SISP - 44 - Group Number 13-B
13 RSA RSA RSA RSA RSA RSA RSA SA Group Report of 2011 SISP - 45 - Group Number 13-B
RSA RSA RSA RSA RSA PARI/GP RSA Group Report of 2011 SISP - 46 - Group Number 13-B
RSA RSA RSA RSA RSA Group Report of 2011 SISP - 47 - Group Number 13-B
RSA RSA RSA RSA RSA RSA Group Report of 2011 SISP - 48 - Group Number 13-B
Group Report of 2011 SISP - 49 - Group Number 13-B
A PARI/GP PARI/GP PARI/GP PARI/GP RSA TeX TeX TeX Adobe Illustrator CS4 Adobe Illustrator CS4 Group Report of 2011 SISP - 50 - Group Number 13-B
B Tex Group Report of 2011 SISP - 51 - Group Number 13-B
[1],,, Java,, 2008. [2],,, 2008. [3] J.H., J.,, 1995. [4],,,, 2001. [5],,, 1999. [6] PARI/GP, http://pari.math.u-bordeaux.fr/ [7], http://dev.sbins.co.jp/cryptography/crypto graphy01.html Group Report of 2011 SISP - 52 - Group Number 13-B