# welcome to rsa.rb

a guest
Apr 19th, 2017
396
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. require 'prime'
2.
3. # calc (x,y) s.t. ax + by = gcd(a,b)
4. def extgcd(a,b)
5.   g = a
6.   x = 1
7.   y = 0
8.   if b != 0
9.     o = extgcd(b, a%b)
10.     x = o[:y]
11.     y = o[:x]
12.     g = o[:g]
13.     y -= (a / b) * x;
14.   end
15.   return {g:g, x:x, y:y}
16. end
17.
18. # calc a^b mod m
19. def modpow(a,b,m)
20.   r = 1
21.   while b>0
22.     r = r*a%m if (b&1)==1
23.     a = a*a%m
24.     b >>= 1
25.   end
26.   return r
27. end
28.
29. # calc a^-1 mod m
30. def modinv(a,m)
31.   ret = extgcd(a,m)[:x]
32.   return ret<0 ? ret+m : ret
33. end
34.
35. # check it is prime
36. # from : https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95#.E3.82.B3.E3.83.BC.E3.83.89.E4.BE.8B
37. def prime?(n)
38.   return true if n == 2
39.   return false if n == 1 || n & 1 == 0
40.   d = n-1
41.   d >>= 1 while d & 1 == 0
42.   20.times do
43.     a = rand(n-2) + 1
44.     t = d
45.     y = modpow(a,t,n)
46.     while t != n-1 && y != 1 && y != n-1
47.       y = (y * y) % n
48.       t <<= 1
49.     end
50.     return false if y != n-1 && t & 1 == 0
51.   end
52.   return true
53. end
54.
55. # random prime
56. def randprime(min, max)
57.   while true
58.     ret = rand(max-min) + min
59.     if prime?(ret)
60.       return ret
61.     end
62.   end
63. end
64.
65. # euler's phi function
66. def phi(pp,qq)
67.   if pp == qq
68.     return pp * (pp-1)
69.   else
70.     return (pp-1) * (qq-1)
71.   end
72. end
73.
74. # here is flag!
75. mes0 = "***CENSORED***"
76. mes0 = mes0.unpack("H*")[0].to_i(16)
77. # private key
78. p0 = 0x141e3aa4f32f59c29ccc6f80946b50e51
79. q0 = -1 # CENSORED
80. # public key
81. n0 = 0x24eb33d74405613381a6583310af3a8bde7cb9bb2b2bf56cb4dd979de737d6e83
82. e0 = 65537
83. # encrypt
84. cip0 = modpow(mes0, e0, n0)
85. # cip0 = 0x7a799e0b6f6e009851c74ea3a97ec79a449a92d4954004f77fc4165b43b9bfa5
86. puts cip0.to_s(16)
87. # decrypt test
88. puts [modpow(cip0, modinv(e0,phi(p0,q0)), n0).to_s(16)].pack("H*")