SHARE
TWEET

welcome to rsa.rb

a guest Apr 19th, 2017 129 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*")
RAW Paste Data
Top