Project1

标题: RSA加密OAEP方案 [打印本页]
作者: guoxiaomi    时间: 2018-4-19 16:56
标题: RSA加密OAEP方案
本帖最后由 guoxiaomi 于 2018-4-27 23:56 编辑

RSA加密算法是一种非对称的加密手段，由于只是用来加密对称加密的秘钥（对于AES加密来说，128位的密钥足以保证安全），只会在传输密钥的时候执行一次，实际的运算量也不是很大，而且 ruby 自带 Bignum，写起来也方便些

1楼是数学原理，实用的生成秘钥对、加密方案在3、4楼，在RM中使用的话，需要用dll弄一个计算sha-1的函数（见5楼）。
2楼是C#的代码
6楼是针对 256-bit RSA密钥的攻击，仅仅花了5分钟，说明取更大的密钥的必要性

如此就可以用完成大概安全的公钥加密传输了。

下面是正文：

首先，从网上抄了3个函数，用来求模反和幂模
RUBY 代码复制
  1. def egcd(a, b)
  2.     if a == 0
  3.         [b, 0, 1]
  4.     else
  5.         g, y, x = egcd(b % a, a)
  6.         [g, x - (b / a) * y, y]
  7.     end
  8. end
  9.  
  10. def modinv(a, m)
  11.     g, x, y = egcd(a, m)
  12.     if g == 1
  13.         x % m
  14.     else
  15.         raise
  16.     end
  17. end
  18.  
  19. def modpow(a, b, n)
  20.     rec = 1
  21.     while (b != 0)
  22.         if b & 1 != 0
  23.             rec = (rec * a) % n
  24.         end
  25.         a = (a * a) % n
  26.         b = b >> 1
  27.     end
  28.     rec % n
  29. end

然后登陆 www.wolframalpha.com，用类似 prime closest to 2^256 * 1.23456789 的指令得到几个很大的质数，比如下面的几个例子
RUBY 代码复制
  1. # p = 340282366920938463463374607431768211507 # 128-bit
  2. # q = 442367076997220017613959734844163358521 # 128-bit
  3. # p = 114321529704002274578921084903793614162317645586699719492822694265655811637217 # 256-bit
  4. # q = 170095105326940384212383024501862619327831639589164392574626096589661701930901 # 256-bit
  5. p = 39391335229695556645551048713636649037690892144144766626387899639258047233085306918331113608222769414886203283497951067975814999508178451226732581907071099 # 512-bit
  6. q = 8091612085720357837842476099645383223098769278647227328308631524827867677878737958899289093390100825439815397081936915739099782156677184746940143587294947 # 512-bit
  7.  
  8. n = p * q
  9. e = 65537
  10.  
  11. str = '1234567890abcdef'
  12. m = str.unpack('C*').inject(0){|s, i| (s << 8) + i}
  13. p m
  14. p c = modpow(m, e, n) # public key: e, n
  15.  
  16. d = modinv(e, (p-1) * (q-1)) # private key: d, n
  17. p m2 = modpow(c, d, n), m == m2


提醒一下，m是明文，c是密文，用m生成c只需要知道 e = 65537 和 n = p * q
解密的话需要知道 (p-1)*(q-1) 和 n，也就是 p 和 q，而用 n 求 p、q 几乎是不可能的
正常的加密要求 m < n，这里 n ~ 1024 bit 是足够长的
上面的内容显示结果：
  1. 65392825175610104412735852254614283622
  2. 55038560310780067437062090146057515347452012654059325469405078165508476134024808261020076587516103483241454346122071285542898770131400418286780269941688027757584931240339204470841864636279890281715398177884324364339943921202813369696583386135438024241244203849337673874382470838957284345740774426383985682694
  3. 65392825175610104412735852254614283622
  4. true
复制代码
作者: 不死鸟之翼    时间: 2018-4-22 21:25
本帖最后由 不死鸟之翼 于 2018-4-22 21:35 编辑

冒个泡 顺便C#大法好 啥都有）

CSHARP 代码复制
  1. namespace RSATest
  2. {
  3.     class Program
  4.     {
  5.         static RSAParameters GenKeyPair()
  6.         {
  7.             var RSA = new RSACryptoServiceProvider();
  8.             return RSA.ExportParameters(true);
  9.         }
  10.  
  11.         static byte[] Encrypt(byte[] m, byte[] n, byte[] e)
  12.         {
  13.             var RSA = new RSACryptoServiceProvider();
  14.             var param = new RSAParameters()
  15.             {
  16.                 Modulus = n,
  17.                 Exponent = e
  18.             };
  19.             RSA.ImportParameters(param);
  20.             return RSA.Encrypt(m, false);
  21.         }
  22.  
  23.         static byte[] Decrypt(byte[] c, RSAParameters param)
  24.         {
  25.             var RSA = new RSACryptoServiceProvider();
  26.             RSA.ImportParameters(param);
  27.             return RSA.Decrypt(c, false);
  28.         }
  29.  
  30.         static void Main(string[] args)
  31.         {
  32.             var param = GenKeyPair();
  33.             var s = "1234567890abcdef";
  34.             var m = Encoding.UTF8.GetBytes(s);
  35.             var c = Encrypt(m, param.Modulus, param.Exponent);
  36.             var m2 = Decrypt(c, param);
  37.             var s2 = Encoding.UTF8.GetString(m2);
  38.             Console.WriteLine(s);
  39.         }
  40.     }
  41. }


一楼所述的textbook RSA（没有填充）用来展示数学原理没问题，但实际使用会有安全性问题，业界实践都是有padding的 比如OAEP（最优非对称加密填充）
所以用C#你会发现每次加密的结果都不一样）


另外没C#的话还可以用Windows Powershell 反正都是.net）雾
POWERSHELL 代码复制
  1. $rsa=New-Object -TypeName "System.Security.Cryptography.RSACryptoServiceProvider"
    

  2. $arr=[System.Text.Encoding]::UTF8.GetBytes("1234567890abcdef")
    

  3. echo $rsa.Encrypt($arr,$false)
作者: guoxiaomi    时间: 2018-4-23 11:39
利用 ssh-keygen 生成 rsa 的密钥：
  1. ssh-keygen -t rsa -f ./test -C 'test'
复制代码

用下面的脚本读取公钥（test.pub）中的e和n，在rpg maker中的不需要 require 'base64' ：
RUBY 代码复制
  1. require 'base64'
  2.  
  3. s = File.open('test.pub', 'r') do |f|
  4.     Base64.decode64 f.read.split(/\s+/)[1]
  5. end
  6.  
  7. i = 0
  8. vars = []
  9. while i < s.length do
  10.     length = s[i...i+4].unpack('H*')[0].to_i(16)
  11.     i += 4
  12.     vars.push s[i...i+length]
  13.     i += length
  14. end
  15. p vars[0], i == s.length
  16. p e = vars[1].unpack('H*')[0].to_i(16)
  17. p n = vars[2].unpack('H*')[0].to_i(16)

如此就可以得到 e 和 n
解析私钥（test）用：
  1. openssl rsa -in test -text
复制代码

反正保存私钥的服务端肯定有办法去做解密的~
作者: guoxiaomi    时间: 2018-4-27 11:43
本帖最后由 guoxiaomi 于 2018-4-27 11:45 编辑

RUBY 代码复制
  1. # ---------------------------------------------------------
  2. # RSA
  3. # ---------------------------------------------------------
  4. # For OAEP:
  5. # [url]https://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2-rsa-cryptography-standard-wp.pdf[/url]
  6. # ---------------------------------------------------------
  7.  
  8. require 'base64'
  9. require 'digest/sha1'
  10.  
  11. module RSA
  12.   def int2str(i)
  13.     hex = i.to_s(16)
  14.     hex = '0' + hex if hex.size % 2 == 1
  15.     [hex].pack('H*')
  16.   end
  17.  
  18.   def str2int(s)
  19.     s.unpack('H*')[0].to_i(16)
  20.   end
  21.  
  22.   def load_pub(fn)
  23.     s = File.open(fn, 'r') do |f|
  24.       Base64.decode64 f.read.split(/\s+/)[1]
  25.     end
  26.  
  27.     i = 0
  28.     vars = []
  29.     while i < s.length do
  30.       length = str2int(s[i...i+4])
  31.       i += 4
  32.       vars.push s[i...i+length]
  33.       i += length
  34.     end
  35.  
  36.     if i == s.size
  37.       e, n = str2int(vars[1]), str2int(vars[2])
  38.       return [e, n]
  39.     else
  40.       return false
  41.     end
  42.   end
  43.  
  44.   def egcd(a, b)
  45.     if a == 0
  46.         [b, 0, 1]
  47.     else
  48.         g, y, x = egcd(b % a, a)
  49.         [g, x - (b / a) * y, y]
  50.     end
  51.   end
  52.  
  53.   def modinv(a, m)
  54.       g, x, y = egcd(a, m)
  55.       if g == 1
  56.           x % m
  57.       else
  58.           raise
  59.       end
  60.   end
  61.  
  62.   def modpow(a, b, n)
  63.       rec = 1
  64.       while (b != 0)
  65.           if b & 1 != 0
  66.               rec = (rec * a) % n
  67.           end
  68.           a = (a * a) % n
  69.           b = b >> 1
  70.       end
  71.       rec % n
  72.   end
  73.  
  74.   def i2osp(i, len)
  75.     a = []
  76.     len.times do
  77.       a.push(i & 255)
  78.       i = i >> 8
  79.     end
  80.     a.reverse.pack('C*')
  81.   end
  82.  
  83.   alias os2ip str2int
  84.  
  85.   def xor(s1, s2)
  86.     raise if s1.size != s2.size
  87.     int2str(str2int(s1) ^ str2int(s2))
  88.   end
  89.  
  90.   def sha1(s)
  91.     Digest::SHA1.digest(s)
  92.   end
  93.  
  94.   def mgf1(s, l)
  95.     t = ''
  96.     for i in 0..(l / 20) # 20 is sha1 output length
  97.       t << sha1(s + i2osp(i, 4))
  98.     end
  99.     t[0...l]
  100.   end
  101.  
  102.   alias encrypt_public modpow
  103. end
  104.  
  105. include RSA
  106.  
  107. # try to encrypt a 128-bit aes key:
  108. aes_key = 'Say:hello,world!'
  109. # ---------------------------------------------------------
  110. # 0. load public key
  111. # ---------------------------------------------------------
  112. e, n = load_pub('test.pub')
  113.  
  114. # ---------------------------------------------------------
  115. # 1. length checking
  116. # ---------------------------------------------------------
  117. L = ''
  118. DB = ''
  119. k = int2str(n).size
  120. lHash = sha1(L)
  121. hLen = lHash.size
  122. M = aes_key
  123. mLen = M.size
  124. if hLen > 2 << 61 - 1 # check for sha-1
  125.   raise 'label too long'
  126. elsif mLen + 2 * hLen + 2 > k
  127.   raise 'message too long'
  128. end
  129.  
  130. # ---------------------------------------------------------
  131. # 2. EME-OAEP encoding
  132. # ---------------------------------------------------------
  133. PS = "\x00" * (k - 2 * hLen - mLen - 2)
  134. DB << (lHash + PS + "\x01" + M)
  135. seed = Array.new(hLen).collect{|e| rand(256)}.pack('C*')
  136. maskedDB = xor(DB, mgf1(seed, k - hLen - 1))
  137. maskedseed = xor(seed, mgf1(maskedDB, hLen))
  138.  
  139. EM = "\x00" + maskedseed + maskedDB
  140. print Base64.encode64(EM)
  141.  
  142. # ---------------------------------------------------------
  143. # 3. RSA encryption
  144. # ---------------------------------------------------------
  145. m = os2ip(EM)
  146. c = encrypt_public(m, e, n)
  147. C = i2osp(c, k)
  148. print Base64.encode64(C)

PHP的测试代码，把ruby代码的输出 Base64.encode64(C) 复制到 $data里，直接在服务端把私钥写出来了：
PHP 代码复制
  1. <?php
  2.     $key = "-----BEGIN RSA PRIVATE KEY-----
  3. MIIEpAIBAAKCAQEAw2pCSxFVb2g1JwKjXK7CT7cVuSqo5emnWKyhjeqQjSvDUS3x
  4. dn1k4uTq24c701kpHkdXYl2WCJlDAJrIYD1KH6dzFAEOXNWKlKWIkcF7YkvnhZnn
  5. eHJw5ZhYuTM7cligkMeFW8UWb8tI/SsBmCQZrA/spJ03JmqJtoIY9PQXO+XAGqCy
  6. ZLxnHz40bvRMncgjPm4XENojrVtzh9LdRei8N3RkZw4gEcVaPpPgJze2ObSKdZ4+
  7. CUtuFOSdap7K7o2N2d8S/Y7Jd+hH84FnSMpKlwsrr5unWeSFE67iNJV/KDH7V7Su
  8. 5J1GB9WgOBkxOm86+EXhrQfeuBI0Jqh/HQPKlwIDAQABAoIBAHkQqcWMFZwRuWxT
  9. rBXNh0CPsvumvEDEQxMi0Gv1uFxdkoIGrqO0B/6xx/b9j0je4iSKGk8sn7jwCpyj
  10. SCSnk/aMbTUlelp1SYfSDgwPDHvXfrY8pTTv4ZW8jqseXGP5GHDZy3sRXVchYDTI
  11. ohI5u1Xn/7n0VKiONIdHjmKjnolSNj8DRGYJ/nL9u4QenX0tGN43/lqP7UhO/O7D
  12. OdU9ysLn7glad6EARmMbG8hxIavdLvJ6F5HS9tpVT+9jTgi9t4mqdP6YTeh10fWa
  13. KQ7HFCOb9Wmu84YRNgb1+9w+ARGoe6r+aO1HTtE2DtoycExWOL0Ic2zhtKpKdv7N
  14. 8eZc7iECgYEA5Kuou03+IKlwDizgWAvsCifSWxRFcUAoCvR/xnDF80wqSxVWtJTF
  15. KaPHqU6uNTlFHvda+KRy0N6g8bc0+nrF8ZaOzMMM7tZTtY29mp5dZawD7zODTEGa
  16. XXzDbLyA8+rW3XZpuHlXJH6rovFyXvcZK+w5ekmeJI0NMwxTlvkUUK8CgYEA2sUf
  17. 6wZ2A/+FMjaqNWM5Nii/vth9F3VIQgpNC45batRyr2xSJBrug6Jd9R/N5qizWJR8
  18. 7/KYHwalqbqufj74PwodGRCR8QWoIK6msOEnIPNzhr+iFvFesjMvfF2MmPYzBT40
  19. U+aJjqYS39rQRJuKlg6GcVEYiGu3J0Dc0LVqDpkCgYABGkLKBGpBRg/gQZ8jTYtp
  20. 0R9WiRZ8oU6QHvWuw0RxE+DwU74DSORaewuvaU21u/z1VUP/Buv2zdwAzl1XB9iE
  21. fbFak2YwkJ/+tBxB7pmMr/Ok556uc3KHGN7oW1BT3MIEd1mzJgKhjmrNclSW2KIq
  22. cA0m5cv5aSSzJlAQ3kqWyQKBgQCOL96931Ym5RVJ/JOF3Xaax8NQI96xt21+Vrma
  23. kCzEc04SzAFbLBHnhkkw/znQ98aRBPlq7q6GQ8i6VvYAYabxOf6NguKH11hd3YXD
  24. oqLO3MwyQSz1Ym1cvr3XQ+oUpLemabaS7VxsVW4hBlOks79QJiKlVcLvL6s7nQGn
  25. uLE0yQKBgQDAtCjdKbGGo8OFg2FKFD5vGXSXMscchi0ImyN4gAxRK3rlx5fyoo+X
  26. WUFSHdC3vO9TM00S07eXIuaOaHWjQUOzoTXKmQk4bvf5nZy6u+NvuPwGmwXXCCD2
  27. Z+tK5j2eJ6DkOCwms9IA5kISZkxcFQASlywTihpkmXW9V9mXB0vk5g==
  28. -----END RSA PRIVATE KEY-----
  29. ";
  30.     $data = "gEg4eOsosLi3LxguBSsyz7GVM/TBZo8XZYH97YYdNes9oL/1RYbbYp7jnfVt
  31. IWQpaeXFl/PBg+d1vy2R0C1YSuvqKJ/h5a6SddgNCF0sY40T3Pwg1n6bHcjp
  32. AXy+lrduQqnAUivppJF0UTY6Bv6DvdzQ5odd5On1tcZPzX/oGTAEYMiCZRWm
  33. OCqDPa7CqO2ohDaY0v+Ke8pxZh/my/VeyxVjprvkV3CWm4fE0DTwAnvSJtSJ
  34. 6zJV0iEMsigfdSk9CnWPkCkeaHHCbj9mQ25u+bjtoFAw+FpQAzB9CF6YQHI/
  35. hCe4BPr8odOxdZtyKhgtdyENOmdPRWewtIhPc7PtJw==";
  36.     echo $data;
  37.     $data = base64_decode($data);
  38.     openssl_private_decrypt($data, $decrypted, $key, OPENSSL_NO_PADDING);
  39.     echo "<br>NOPADDING!<br>";
  40.     echo base64_encode($decrypted);
  41.     echo "<br>";
  42.     openssl_private_decrypt($data, $decrypted2, $key, OPENSSL_PKCS1_OAEP_PADDING);
  43.     echo "<br>OAEP!<br>";
  44.     echo $decrypted2."<br>";
  45.     echo base64_encode($decrypted2);
  46. ?>

公钥：
TXT 代码复制
  1. ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDDakJLEVVvaDUnAqNcrsJPtxW5Kqjl6adYrKGN6pCNK8NRLfF2fWTi5OrbhzvTWSkeR1diXZYImUMAmshgPUofp3MUAQ5c1YqUpYiRwXtiS+eFmed4cnDlmFi5MztyWKCQx4VbxRZvy0j9KwGYJBmsD+yknTcmaom2ghj09Bc75cAaoLJkvGcfPjRu9EydyCM+bhcQ2iOtW3OH0t1F6Lw3dGRnDiARxVo+k+AnN7Y5tIp1nj4JS24U5J1qnsrujY3Z3xL9jsl36EfzgWdIykqXCyuvm6dZ5IUTruI0lX8oMftXtK7knUYH1aA4GTE6bzr4ReGtB964EjQmqH8dA8qX test
作者: guoxiaomi    时间: 2018-4-27 12:02
（强行互动）用于计算sha-1的dll在我写的SAE服务器里就弄好了：hash.dll，输入一个字符串返回40位的hex码，所以用的时候要转换一下~
RUBY 代码复制
  1. SHA1 = Win32API.new('hash.dll', 'sha1_v', ['p', 'p', 'i'], 'v')
  2. def sha1(s)
  3.   buffer = "\0" * 40
  4.   SHA1.call(buffer, string, string.size)
  5.   [buffer].pack('H*')
  6. end

作者: qweytr_1    时间: 2018-4-27 22:38
guoxiaomi 发表于 2018-4-27 12:02
（强行互动）用于计算sha-1的dll在我写的SAE服务器里就弄好了：hash.dll，输入一个字符串返回40位的hex码， ...


刚刚试了一下，指望128位质数的RSA还不如不加密……
建议至少按照标准用2048位的两个质数组合一个4096位的公钥
用的是例子里面的两个质数，然后把公钥送进msieve
In[1]:= p = 340282366920938463463374607431768211507
Out[1]= 340282366920938463463374607431768211507
In[2]:= q = 442367076997220017613959734844163358521
Out[2]= 442367076997220017613959734844163358521
In[3]:= p q
Out[3]= 150529716008511059192844022140063161898374205466644527991444838913354598701147
执行
msieve.exe -t 6 150529716008511059192844022140063161898374205466644527991444838913354598701147
得到msieve.log
  1. Fri Apr 27 22:32:24 2018  
  2. Fri Apr 27 22:32:24 2018  
  3. Fri Apr 27 22:32:24 2018  Msieve v. 1.46
  4. Fri Apr 27 22:32:24 2018  random seeds: 24c07960 fef15915
  5. Fri Apr 27 22:32:24 2018  factoring 150529716008511059192844022140063161898374205466644527991444838913354598701147 (78 digits)
  6. Fri Apr 27 22:32:24 2018  no P-1/P+1/ECM available, skipping
  7. Fri Apr 27 22:32:24 2018  commencing quadratic sieve (78-digit input)
  8. Fri Apr 27 22:32:24 2018  using multiplier of 3
  9. Fri Apr 27 22:32:24 2018  using 32kb Intel Core sieve core
  10. Fri Apr 27 22:32:24 2018  sieve interval: 12 blocks of size 32768
  11. Fri Apr 27 22:32:24 2018  processing polynomials in batches of 17
  12. Fri Apr 27 22:32:24 2018  using a sieve bound of 959759 (37824 primes)
  13. Fri Apr 27 22:32:24 2018  using large prime bound of 95975900 (26 bits)
  14. Fri Apr 27 22:32:24 2018  using trial factoring cutoff of 27 bits
  15. Fri Apr 27 22:32:24 2018  polynomial 'A' values have 10 factors
  16. Fri Apr 27 22:37:00 2018  37988 relations (19473 full + 18515 combined from 206527 partial), need 37920
  17. Fri Apr 27 22:37:00 2018  begin with 226000 relations
  18. Fri Apr 27 22:37:00 2018  reduce to 54259 relations in 2 passes
  19. Fri Apr 27 22:37:00 2018  attempting to read 54259 relations
  20. Fri Apr 27 22:37:00 2018  recovered 54259 relations
  21. Fri Apr 27 22:37:00 2018  recovered 44076 polynomials
  22. Fri Apr 27 22:37:00 2018  attempting to build 37988 cycles
  23. Fri Apr 27 22:37:00 2018  found 37988 cycles in 1 passes
  24. Fri Apr 27 22:37:00 2018  distribution of cycle lengths:
  25. Fri Apr 27 22:37:00 2018     length 1 : 19473
  26. Fri Apr 27 22:37:00 2018     length 2 : 18515
  27. Fri Apr 27 22:37:00 2018  largest cycle: 2 relations
  28. Fri Apr 27 22:37:01 2018  matrix is 37824 x 37988 (5.5 MB) with weight 1137187 (29.94/col)
  29. Fri Apr 27 22:37:01 2018  sparse part has weight 1137187 (29.94/col)
  30. Fri Apr 27 22:37:01 2018  filtering completed in 3 passes
  31. Fri Apr 27 22:37:01 2018  matrix is 27054 x 27118 (4.3 MB) with weight 900229 (33.20/col)
  32. Fri Apr 27 22:37:01 2018  sparse part has weight 900229 (33.20/col)
  33. Fri Apr 27 22:37:01 2018  saving the first 48 matrix rows for later
  34. Fri Apr 27 22:37:01 2018  matrix is 27006 x 27118 (2.8 MB) with weight 652841 (24.07/col)
  35. Fri Apr 27 22:37:01 2018  sparse part has weight 452517 (16.69/col)
  36. Fri Apr 27 22:37:01 2018  matrix includes 64 packed rows
  37. Fri Apr 27 22:37:01 2018  commencing Lanczos iteration
  38. Fri Apr 27 22:37:01 2018  memory use: 4.0 MB
  39. Fri Apr 27 22:37:08 2018  lanczos halted after 429 iterations (dim = 27006)
  40. Fri Apr 27 22:37:08 2018  recovered 18 nontrivial dependencies
  41. Fri Apr 27 22:37:08 2018  prp39 factor: 340282366920938463463374607431768211507
  42. Fri Apr 27 22:37:08 2018  prp39 factor: 442367076997220017613959734844163358521
  43. Fri Apr 27 22:37:08 2018  elapsed time 00:04:44
复制代码

可以看出，破解256bit公钥（2个128bit质数相乘只用五分钟）



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1