RSA加密OAEP方案

guoxiaomi

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

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

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

下面是正文：

首先，从网上抄了3个函数，用来求模反和幂模
[pre lang="ruby"]def egcd(a, b)
    if a == 0
        [b, 0, 1]
    else
        g, y, x = egcd(b % a, a)
        [g, x - (b / a) * y, y]
    end
end

def modinv(a, m)
    g, x, y = egcd(a, m)
    if g == 1
        x % m
    else
        raise
    end
end

def modpow(a, b, n)
    rec = 1
    while (b != 0)
        if b & 1 != 0
            rec = (rec * a) % n
        end
        a = (a * a) % n
        b = b >> 1
    end
    rec % n
end[/pre]
然后登陆 www.wolframalpha.com，用类似 prime closest to 2^256 * 1.23456789 的指令得到几个很大的质数，比如下面的几个例子
[pre lang="ruby"]# p = 340282366920938463463374607431768211507 # 128-bit
# q = 442367076997220017613959734844163358521 # 128-bit
# p = 114321529704002274578921084903793614162317645586699719492822694265655811637217 # 256-bit
# q = 170095105326940384212383024501862619327831639589164392574626096589661701930901 # 256-bit
p = 39391335229695556645551048713636649037690892144144766626387899639258047233085306918331113608222769414886203283497951067975814999508178451226732581907071099 # 512-bit
q = 8091612085720357837842476099645383223098769278647227328308631524827867677878737958899289093390100825439815397081936915739099782156677184746940143587294947 # 512-bit

n = p * q
e = 65537

str = '1234567890abcdef'
m = str.unpack('C*').inject(0){|s, i| (s << 8) + i}
p m
p c = modpow(m, e, n) # public key: e, n

d = modinv(e, (p-1) * (q-1)) # private key: d, n
p m2 = modpow(c, d, n), m == m2[/pre]

提醒一下，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

复制代码

不死鸟之翼

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

[pre lang="CSHARP"]namespace RSATest
{
    class Program
    {
        static RSAParameters GenKeyPair()
        {
            var RSA = new RSACryptoServiceProvider();
            return RSA.ExportParameters(true);
        }

        static byte[] Encrypt(byte[] m, byte[] n, byte[] e)
        {
            var RSA = new RSACryptoServiceProvider();
            var param = new RSAParameters()
            {
                Modulus = n,
                Exponent = e
            };
            RSA.ImportParameters(param);
            return RSA.Encrypt(m, false);
        }

        static byte[] Decrypt(byte[] c, RSAParameters param)
        {
            var RSA = new RSACryptoServiceProvider();
            RSA.ImportParameters(param);
            return RSA.Decrypt(c, false);
        }

        static void Main(string[] args)
        {
            var param = GenKeyPair();
            var s = "1234567890abcdef";
            var m = Encoding.UTF8.GetBytes(s);
            var c = Encrypt(m, param.Modulus, param.Exponent);
            var m2 = Decrypt(c, param);
            var s2 = Encoding.UTF8.GetString(m2);
            Console.WriteLine(s);
        }
    }
}
[/pre]

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


另外没C#的话还可以用Windows Powershell 反正都是.net）雾
[pre lang="Powershell"]$rsa=New-Object -TypeName "System.Security.Cryptography.RSACryptoServiceProvider"
$arr=[System.Text.Encoding]::UTF8.GetBytes("1234567890abcdef")
echo $rsa.Encrypt($arr,$false)[/pre]

guoxiaomi

利用 ssh-keygen 生成 rsa 的密钥：

1. ssh-keygen -t rsa -f ./test -C 'test'

复制代码

用下面的脚本读取公钥（test.pub）中的e和n，在rpg maker中的不需要 require 'base64' ：
[pre lang="ruby"]require 'base64'

s = File.open('test.pub', 'r') do |f|
    Base64.decode64 f.read.split(/\s+/)[1]
end

i = 0
vars = []
while i < s.length do
    length = s[i...i+4].unpack('H*')[0].to_i(16)
    i += 4
    vars.push s[i...i+length]
    i += length
end
p vars[0], i == s.length
p e = vars[1].unpack('H*')[0].to_i(16)
p n = vars[2].unpack('H*')[0].to_i(16)[/pre]
如此就可以得到 e 和 n
解析私钥（test）用：

1. openssl rsa -in test -text

复制代码

反正保存私钥的服务端肯定有办法去做解密的~

guoxiaomi

[pre lang="ruby"]# ---------------------------------------------------------
# RSA
# ---------------------------------------------------------
# For OAEP:
# https://www.emc.com/collateral/w ... phy-standard-wp.pdf
# ---------------------------------------------------------

require 'base64'
require 'digest/sha1'

module RSA
  def int2str(i)
    hex = i.to_s(16)
    hex = '0' + hex if hex.size % 2 == 1
    [hex].pack('H*')
  end

  def str2int(s)
    s.unpack('H*')[0].to_i(16)
  end

  def load_pub(fn)
    s = File.open(fn, 'r') do |f|
      Base64.decode64 f.read.split(/\s+/)[1]
    end

    i = 0
    vars = []
    while i < s.length do
      length = str2int(s[i...i+4])
      i += 4
      vars.push s[i...i+length]
      i += length
    end

    if i == s.size
      e, n = str2int(vars[1]), str2int(vars[2])
      return [e, n]
    else
      return false
    end
  end

  def egcd(a, b)
    if a == 0
        [b, 0, 1]
    else
        g, y, x = egcd(b % a, a)
        [g, x - (b / a) * y, y]
    end
  end

  def modinv(a, m)
      g, x, y = egcd(a, m)
      if g == 1
          x % m
      else
          raise
      end
  end

  def modpow(a, b, n)
      rec = 1
      while (b != 0)
          if b & 1 != 0
              rec = (rec * a) % n
          end
          a = (a * a) % n
          b = b >> 1
      end
      rec % n
  end

  def i2osp(i, len)
    a = []
    len.times do
      a.push(i & 255)
      i = i >> 8
    end
    a.reverse.pack('C*')
  end

  alias os2ip str2int

  def xor(s1, s2)
    raise if s1.size != s2.size
    int2str(str2int(s1) ^ str2int(s2))
  end

  def sha1(s)
    Digest::SHA1.digest(s)
  end

  def mgf1(s, l)
    t = ''
    for i in 0..(l / 20) # 20 is sha1 output length
      t << sha1(s + i2osp(i, 4))
    end
    t[0...l]
  end

  alias encrypt_public modpow
end

include RSA

# try to encrypt a 128-bit aes key:
aes_key = 'Say:hello,world!'
# ---------------------------------------------------------
# 0. load public key
# ---------------------------------------------------------
e, n = load_pub('test.pub')

# ---------------------------------------------------------
# 1. length checking
# ---------------------------------------------------------
L = ''
DB = ''
k = int2str(n).size
lHash = sha1(L)
hLen = lHash.size
M = aes_key
mLen = M.size
if hLen > 2 << 61 - 1 # check for sha-1
  raise 'label too long'
elsif mLen + 2 * hLen + 2 > k
  raise 'message too long'
end

# ---------------------------------------------------------
# 2. EME-OAEP encoding
# ---------------------------------------------------------
PS = "\x00" * (k - 2 * hLen - mLen - 2)
DB << (lHash + PS + "\x01" + M)
seed = Array.new(hLen).collect{|e| rand(256)}.pack('C*')
maskedDB = xor(DB, mgf1(seed, k - hLen - 1))
maskedseed = xor(seed, mgf1(maskedDB, hLen))

EM = "\x00" + maskedseed + maskedDB
print Base64.encode64(EM)

# ---------------------------------------------------------
# 3. RSA encryption
# ---------------------------------------------------------
m = os2ip(EM)
c = encrypt_public(m, e, n)
C = i2osp(c, k)
print Base64.encode64(C)
[/pre]
PHP的测试代码，把ruby代码的输出 Base64.encode64(C) 复制到 $data里，直接在服务端把私钥写出来了：
[pre lang="php"]<?php
    $key = "-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAw2pCSxFVb2g1JwKjXK7CT7cVuSqo5emnWKyhjeqQjSvDUS3x
dn1k4uTq24c701kpHkdXYl2WCJlDAJrIYD1KH6dzFAEOXNWKlKWIkcF7YkvnhZnn
eHJw5ZhYuTM7cligkMeFW8UWb8tI/SsBmCQZrA/spJ03JmqJtoIY9PQXO+XAGqCy
ZLxnHz40bvRMncgjPm4XENojrVtzh9LdRei8N3RkZw4gEcVaPpPgJze2ObSKdZ4+
CUtuFOSdap7K7o2N2d8S/Y7Jd+hH84FnSMpKlwsrr5unWeSFE67iNJV/KDH7V7Su
5J1GB9WgOBkxOm86+EXhrQfeuBI0Jqh/HQPKlwIDAQABAoIBAHkQqcWMFZwRuWxT
rBXNh0CPsvumvEDEQxMi0Gv1uFxdkoIGrqO0B/6xx/b9j0je4iSKGk8sn7jwCpyj
SCSnk/aMbTUlelp1SYfSDgwPDHvXfrY8pTTv4ZW8jqseXGP5GHDZy3sRXVchYDTI
ohI5u1Xn/7n0VKiONIdHjmKjnolSNj8DRGYJ/nL9u4QenX0tGN43/lqP7UhO/O7D
OdU9ysLn7glad6EARmMbG8hxIavdLvJ6F5HS9tpVT+9jTgi9t4mqdP6YTeh10fWa
KQ7HFCOb9Wmu84YRNgb1+9w+ARGoe6r+aO1HTtE2DtoycExWOL0Ic2zhtKpKdv7N
8eZc7iECgYEA5Kuou03+IKlwDizgWAvsCifSWxRFcUAoCvR/xnDF80wqSxVWtJTF
KaPHqU6uNTlFHvda+KRy0N6g8bc0+nrF8ZaOzMMM7tZTtY29mp5dZawD7zODTEGa
XXzDbLyA8+rW3XZpuHlXJH6rovFyXvcZK+w5ekmeJI0NMwxTlvkUUK8CgYEA2sUf
6wZ2A/+FMjaqNWM5Nii/vth9F3VIQgpNC45batRyr2xSJBrug6Jd9R/N5qizWJR8
7/KYHwalqbqufj74PwodGRCR8QWoIK6msOEnIPNzhr+iFvFesjMvfF2MmPYzBT40
U+aJjqYS39rQRJuKlg6GcVEYiGu3J0Dc0LVqDpkCgYABGkLKBGpBRg/gQZ8jTYtp
0R9WiRZ8oU6QHvWuw0RxE+DwU74DSORaewuvaU21u/z1VUP/Buv2zdwAzl1XB9iE
fbFak2YwkJ/+tBxB7pmMr/Ok556uc3KHGN7oW1BT3MIEd1mzJgKhjmrNclSW2KIq
cA0m5cv5aSSzJlAQ3kqWyQKBgQCOL96931Ym5RVJ/JOF3Xaax8NQI96xt21+Vrma
kCzEc04SzAFbLBHnhkkw/znQ98aRBPlq7q6GQ8i6VvYAYabxOf6NguKH11hd3YXD
oqLO3MwyQSz1Ym1cvr3XQ+oUpLemabaS7VxsVW4hBlOks79QJiKlVcLvL6s7nQGn
uLE0yQKBgQDAtCjdKbGGo8OFg2FKFD5vGXSXMscchi0ImyN4gAxRK3rlx5fyoo+X
WUFSHdC3vO9TM00S07eXIuaOaHWjQUOzoTXKmQk4bvf5nZy6u+NvuPwGmwXXCCD2
Z+tK5j2eJ6DkOCwms9IA5kISZkxcFQASlywTihpkmXW9V9mXB0vk5g==
-----END RSA PRIVATE KEY-----
";
    $data = "gEg4eOsosLi3LxguBSsyz7GVM/TBZo8XZYH97YYdNes9oL/1RYbbYp7jnfVt
IWQpaeXFl/PBg+d1vy2R0C1YSuvqKJ/h5a6SddgNCF0sY40T3Pwg1n6bHcjp
AXy+lrduQqnAUivppJF0UTY6Bv6DvdzQ5odd5On1tcZPzX/oGTAEYMiCZRWm
OCqDPa7CqO2ohDaY0v+Ke8pxZh/my/VeyxVjprvkV3CWm4fE0DTwAnvSJtSJ
6zJV0iEMsigfdSk9CnWPkCkeaHHCbj9mQ25u+bjtoFAw+FpQAzB9CF6YQHI/
hCe4BPr8odOxdZtyKhgtdyENOmdPRWewtIhPc7PtJw==";
    echo $data;
    $data = base64_decode($data);
    openssl_private_decrypt($data, $decrypted, $key, OPENSSL_NO_PADDING);
    echo "<br>NOPADDING!<br>";
    echo base64_encode($decrypted);
    echo "<br>";
    openssl_private_decrypt($data, $decrypted2, $key, OPENSSL_PKCS1_OAEP_PADDING);
    echo "<br>OAEP!<br>";
    echo $decrypted2."<br>";
    echo base64_encode($decrypted2);
?>
[/pre]
公钥：
[pre lang="txt"]ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDDakJLEVVvaDUnAqNcrsJPtxW5Kqjl6adYrKGN6pCNK8NRLfF2fWTi5OrbhzvTWSkeR1diXZYImUMAmshgPUofp3MUAQ5c1YqUpYiRwXtiS+eFmed4cnDlmFi5MztyWKCQx4VbxRZvy0j9KwGYJBmsD+yknTcmaom2ghj09Bc75cAaoLJkvGcfPjRu9EydyCM+bhcQ2iOtW3OH0t1F6Lw3dGRnDiARxVo+k+AnN7Y5tIp1nj4JS24U5J1qnsrujY3Z3xL9jsl36EfzgWdIykqXCyuvm6dZ5IUTruI0lX8oMftXtK7knUYH1aA4GTE6bzr4ReGtB964EjQmqH8dA8qX test
[/pre]

guoxiaomi

（强行互动）用于计算sha-1的dll在我写的SAE服务器里就弄好了：hash.dll，输入一个字符串返回40位的hex码，所以用的时候要转换一下~
[pre lang="ruby"]SHA1 = Win32API.new('hash.dll', 'sha1_v', ['p', 'p', 'i'], 'v')
def sha1(s)
  buffer = "\0" * 40
  SHA1.call(buffer, string, string.size)
  [buffer].pack('H*')
end
[/pre]

qweytr_1

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质数相乘只用五分钟）