玩转RSA

通常说非对称加密，我们就能想到RSA，RSA的原理是什么呢，这就得从数据理论开始说起了

RSA数学理论：

欧拉定理：(a^φ(n))%n=1

即两个互素的数a和n，(a<n)存在：a的φ(n)次方与n的余数为1，其中φ(n)为小于n，并且与n互素的个数
如：
a为4，n为7，两个互为素数，φ(7)=6(因为7本身是素数，所以小于7并与其互素的数字有1，2，3，4，5，6), 4^6=4096=7585+1，即4^6%7=1
a为5，n为8，两个互为素数，φ(8)=4(小于8并与其互素的数字有1，3，5，7), 5^4=625=878+1，即5^5%8=1

简单推导如下：

如果一个正整数n，小于且与n互素的数的集合为{x1,x2,x3……xφ(n)}，用A0表示, a∈A0
设P0=x1x2x3……xφ(n)，则P0与n互素
设P1=((x1a)(x2a)(x3a)……(xφ(n)a))，设xia=yin+zi(zi∈A0)做替换,则P1=(y1n+z1)(y2n+z2)(y3n+z3)……(yφ(n)n+zφ(n))，其中z1,z2,z3……zφ(n)都不相等(因为xia=yin+zi,xja=yjn+zj => xia-xja=yin+z-yjn-zj=(yi-yj)n-(zi-zj) 假设zi-zj=0 => (xi-xj)a=(yi-yj)n，xi-xj小于n，a与n互素，产生矛盾)，则zi∈A0 P1=(xxxx)n+z1z2z3……zφ(n)
可得P1%n=P0%n，即((x1a)(x2a)(x3a)……(xφ(n)a))%n=x1x2x3……xφ(n)%n，简化为(a^φ(n)P0)%n=P0%n
因则P0与n互素，则(a^φ(n))%n=1,即为欧拉定理
如：
n为7时，A0={1，2，3，4，5，6}，取a为4，P0=123456，P1=(14)(24）(34)(44)(54)(64)=(70+4)(71+1)(71+5)(72+2)(72+6)(73+3)=xxx7+415263，即P1%7=P0%7
a为5，n为8，A0={1，3，5，7}，P0=1357, P1=(15)(35)(55)(57)=(80+5)(81+7)(83+1)(84+3)=xxx8+571*3，所以P1%8=P0%8

####RSA加密公式：b^(kφ(n)+1)%n=b
即，当一个正整数n为两个素数的乘积的时候，任何小于n的正整数b，都有b^(kφ(n)+1)%n=b公式成立
两个素数p、q，设n=pq，则与n不互素的数有p,2p……pq, q,2q……(p-1)q，总共有q+p-1个，其它都与n互素的，因此φ(n)=n-(q+p-1)=pq-q-p+1=(p-1)*(q-1)
如：
p=2,p=3 => n=6, φ(n)=2 => 2^(2+1)%6=8%6=2, 3^(2+1)%6=27%6=3, 4^(2+1)%6=64%6=4, 5^(2+1)%6=125%6=5
p=3,p=4 => n=12, φ(n)=6 => 5^(6+1)%12=78125%12=5, 5^(6+1)%12=78125%12=5, 11^(6+1)%12=19487171%12=11

######简单推导如下：
1、如果b与n互为素数，
则b^φ(n)%n=1 => b^(kφ(n))%n=1 => b^(kφ(n)+1)%n=b
2、如果b与n不互素，则b一定是p或者q的倍数，设b=mp,
则b与q互素 => b^φ(q)%q=1
因q为素数，所以φ(q)=q-1 => b^(q-1)=k1q+1 => b^(k(q-1)(p-1))=k2q+1 => b^(k(q-1)(p-1))b=k2qb+b => b^(kφ(n)+1)=k2mqp+b => b^(kφ(n)+1)=k2mn+b => b^(k*φ(n)+1)%n=b

####RSA加密解密元理：
依据 b^(kφ(n)+1)%n=b，如果能把b^(kφ(n)+1变成两个数的e和d的乘积，即kφ(n)+1=ed
则b^(ed)%n=b => ((b^e)^d)%n=b 可以分解成两步，c=(b^e)%n, (c^d)%n=b，这两步就分别为加密和解密
如果b为明文，那么c就是密文，(e,n)为公钥，(d,n)即为私钥
如：
n=15，φ(15)=8，
取k=4,则kφ(n)+1=33，可以取d=3,e=11, 那么对于明文为小于15的正数，

加密:  1^3%15=                       1%15 = 1 解密: 1^11%15=                       1%15= 1
加密:  2^3%15=                       8%15 = 8 解密: 8^11%15=              8589934592%15= 2
加密:  3^3%15=                      27%15 =12 解密:12^11%15=            743008370688%15= 3
加密:  4^3%15=                      64%15 = 4 解密: 4^11%15=                 4194304%15= 4
加密:  5^3%15=                     125%15 = 5 解密: 5^11%15=                48828125%15= 5
加密:  6^3%15=                     216%15 = 6 解密: 6^11%15=               362797056%15= 6
加密:  7^3%15=                     343%15 =13 解密:13^11%15=           1792160394037%15= 7
加密:  8^3%15=                     512%15 = 2 解密: 2^11%15=                    2048%15= 8
加密:  9^3%15=                     729%15 = 9 解密: 9^11%15=             31381059609%15= 9
加密: 10^3%15=                    1000%15 =10 解密:10^11%15=            100000000000%15=10
加密: 11^3%15=                    1331%15 =11 解密:11^11%15=            285311670611%15=11
加密: 12^3%15=                    1728%15 = 3 解密: 3^11%15=                  177147%15=12
加密: 13^3%15=                    2197%15 = 7 解密: 7^11%15=              1977326743%15=13
加密: 14^3%15=                    2744%15 =14 解密:14^11%15=           4049565169664%15=14

取k=13,则k*φ(n)+1=115，可以取d=7,e=15,

加密:  1^7%15=                       1%15 = 1 解密: 1^15%15=                       1%15= 1
加密:  2^7%15=                     128%15 = 8 解密: 8^15%15=          35184372088832%15= 2
加密:  3^7%15=                    2187%15 =12 解密:12^15%15=       15407021574586368%15= 3
加密:  4^7%15=                   16384%15 = 4 解密: 4^15%15=              1073741824%15= 4
加密:  5^7%15=                   78125%15 = 5 解密: 5^15%15=             30517578125%15= 5
加密:  6^7%15=                  279936%15 = 6 解密: 6^15%15=            470184984576%15= 6
加密:  7^7%15=                  823543%15 =13 解密:13^15%15=       51185893014090760%15=10
加密:  8^7%15=                 2097152%15 = 2 解密: 2^15%15=                   32768%15= 8
加密:  9^7%15=                 4782969%15 = 9 解密: 9^15%15=         205891132094649%15= 9
加密: 10^7%15=                10000000%15 =10 解密:10^15%15=        1000000000000000%15=10
加密: 11^7%15=                19487171%15 =11 解密:11^15%15=        4177248169415651%15=11
加密: 12^7%15=                35831808%15 = 3 解密: 3^15%15=                14348907%15=12
加密: 13^7%15=                62748517%15 = 7 解密: 7^15%15=           4747561509943%15=13
加密: 14^7%15=               105413504%15 =14 解密:14^15%15=      155568095557812224%15=14

可见，e和d也是多对的，还可以替换n,e,d的值用如下代码做验证(注意防止类型溢出)

long n = 15;
int e = 3;
int d = 11;

String pattern = "加密:%8s=\t%23s\t=%2s\t解密:%8s=\t%23s=%2s";
for (int i=1; i<n; i++) {
    long j = (long)Math.pow(i, e);
    long k = (long)Math.pow((j % n), d);
    System.out.println(String.format(pattern, i + "^" + e + "%" + n, j + "%" + n, j % n, (j % n) + "^" + d + "%" + n, k + "%" + n, k % n));
}

####求解二元二次方程ed=kφ(n)+1，其中φ(n)为已知，e,d,k都为正整数
此时如果固定d不变，
设e=x,k=-y，方程可以转换成dx+φy=1
由此可知我们取的d满足的条件为：d和φ要互素(如果d与φ不互素的话，如果它们有公约数θ，那么就有θ(ix+jy)=1，等式无法成立，因为i,j,x,y都为整数)
设d1=d%φ, m=(d-d1)/φ => d1=d-mφ
则(d-mφ+mφ)x+φy=1 => d1x+φ*(mx+y)=1 可以表示为 d1x1 + φ1y1=1
经过多次迭代之后dnxn+φnyn=1其中dn=0或者φn=1的时候，就有xn+φnyn=1
此时方程的根为：(xn, yn)为(1,0),(-φn+1,1)……(-mφn+1,m)……
再反向逆推出(x,y)来

用程序求dx+φy=1的代码如下①：

public static int[] getxy(int d, int φ) {
    if (d < φ) {
        int[] ret = getxy(φ, d);
        ret[0] = ret[1] + ret[0];
        ret[1] = ret[0] - ret[1];
        ret[0] = ret[0] - ret[1];
        return ret;
    }
    if (φ == 1) {
        return new int[] {0, 1};
    }
    int c = d / φ;
    int d1 = d % φ;
    if (d1 == 0) {
        throw new RuntimeException("nums not prime");
    }
    int[] ret = getxy(d1, φ);
    return new int[] {ret[0], ret[1] - c * ret[0]};
}

d=3,φ=8 => [3,-1] => x=3+8m,k=1+3m(m为整数) (k=-y), (e,k)可以为(11,4),(19,7),(27,10)……
d=5,φ=8 => [3,-1] => x=-3+8m,k=-2+5m(m为整数)
d=7,φ=8 => [3,-1] => x=-1+8m,y=-1+7m(m为整数),(e,k)可以为(15,13),(23,20),(31,27)……

加密(求指数并取模)简化

x1%n=y1,x2%n=y2,则可表示为：x1=k1n+y1,x2=k2n+y2 => x1x2=(k1k2n+y1k2+y2k1)n+y1y2 => (x1x2)%n=y1y2=((x1%n)(x2%n))%n
因此(a^m)%n=(((a^(m-1))%n)*(a%n)%n，因此求指数并取余可以用代码替代②

private static int getMode(int num, int exp, int module) {
    int calNum = 1;
    for (int i = 0; i < exp; i++) {
        calNum *= num;
        calNum = calNum % module;
    }
    return calNum;
}

long n = 15;
int e = 3;
int d = 11;

String pattern = "加密:%8s=\t%23s\t=%2s\t解密:%8s=\t%23s=%2s";
for (int i=1; i<n; i++) {
    int j = getMode(i, e, 15);
    int k = getMode(j, d, 15);
    System.out.println(String.format(pattern, i + "^" + e + "%" + n, j + "%" + n, j % n, (j % n) + "^" + d + "%" + n, k + "%" + n, k % n));
}

RSA使用

生成RSA公钥与私钥

根据上文的原理解析，可知生成RSA密钥文件，过程大致为
1、取两个大素数，p,q，令n=pq, 则φ(n)=(p-1)(q-1)
2、取一个与φ(n)互素的数d，一般都是用65537
3、根据函数②求出一对(e,k)来

######用openssl生成密钥对
1、利用openssl可以随机生成一个512位的(512指私钥的)私钥文件 private_key.pem
openssl genrsa -out private_key.pem 512
2、根据私钥生成一个公钥 public_key.pem
openssl rsa -in private_key.pem -pubout -out public_key.pem

查看

查看公钥
openssl rsa -pubin -in public_key.pem -text -noout

RSA Public-Key: (512 bit)
Modulus:
    00:ea:6b:cb:90:9f:1d:44:74:b6:c3:ff:fb:f5:bb:
    25:e9:ac:3c:ce:60:9c:98:3b:ed:1e:4e:1a:10:ee:
    e1:19:62:9d:16:26:69:df:85:a7:9a:a8:44:d2:80:
    61:d8:cf:98:db:81:a6:01:a2:41:29:1b:c5:7c:c9:
    39:b2:4a:0f:51
Exponent: 65537 (0x10001)

公钥格式

RSAPublicKey ::= SEQUENCE {
   modulus           INTEGER,  -- n
   publicExponent    INTEGER   -- e
}

查看私钥
openssl rsa -in private_key.pem -text -noout

RSA Private-Key: (512 bit, 2 primes)
modulus:
    00:ea:6b:cb:90:9f:1d:44:74:b6:c3:ff:fb:f5:bb:
    25:e9:ac:3c:ce:60:9c:98:3b:ed:1e:4e:1a:10:ee:
    e1:19:62:9d:16:26:69:df:85:a7:9a:a8:44:d2:80:
    61:d8:cf:98:db:81:a6:01:a2:41:29:1b:c5:7c:c9:
    39:b2:4a:0f:51
publicExponent: 65537 (0x10001)
privateExponent:
    00:c9:2c:6c:eb:d5:c0:d6:28:9b:58:24:ec:63:7b:
    92:13:b0:be:16:16:0f:0d:0e:10:75:bb:6c:df:2f:
    41:79:f7:e4:7e:37:df:64:b4:42:5d:cd:d6:e1:44:
    cb:c5:ae:d0:a5:87:ad:98:21:e2:8d:10:b9:a1:d2:
    70:9f:a0:04:01
prime1:
    00:f7:9d:dc:f8:67:c3:cd:37:d1:46:1a:d8:29:13:
    94:ea:24:b9:48:32:0b:71:4c:7b:c8:92:8b:af:54:
    48:8f:e1
prime2:
    00:f2:5b:90:49:df:bd:3b:93:30:0a:df:ea:12:65:
    9c:c0:cf:6a:52:6e:af:3e:20:de:43:0e:1b:a0:bb:
    f8:2d:71
exponent1:
    0f:ba:9c:65:bf:19:a5:f8:8c:b7:9a:4e:ee:d5:0a:
    99:90:f9:a0:07:65:c8:ad:a6:13:48:93:cc:f0:5a:
    a7:a1
exponent2:
    00:96:17:84:ad:6b:85:da:fe:55:93:76:86:94:ec:
    1e:fe:fd:b5:3f:e5:d2:5b:ac:a9:59:67:c4:4e:6f:
    fa:cb:d1
coefficient:
    39:42:b8:82:32:32:af:e1:b2:77:ad:d1:1b:f2:78:
    8e:e5:53:ac:e5:74:6e:2e:f0:a2:6e:81:88:39:67:
    85:7b

私钥格式

RSAPrivateKey ::= SEQUENCE {
 version Version,
 modulus INTEGER, -- n
 publicExponent INTEGER, -- e
 privateExponent INTEGER, -- d
 prime1 INTEGER, -- p
 prime2 INTEGER, -- q
 exponent1 INTEGER, -- d mod (p-1)
 exponent2 INTEGER, -- d mod (q-1)
 coefficient INTEGER -- (inverse of q) mod p 
}

可见私钥里面包含了所有的p、q、e、d、n等信息

验证

//转换成16进制的数字格式
> openssl rsa -in private_key.pem -text -noout|sed 's/://g'|tr 'a-z' 'A-Z'|awk '{if(match($0,/^[A-Z]+/)){print str;str=$0":"}else{str=str$1}}END{print str}'

RSA PRIVATE-KEY (512 BIT, 2 PRIMES):
MODULUS:00DF4D54818D8ACCD56E5F72985BBD69BB2F4957DE177FB221C6756B9F4CDD1EE1667330C466E3B3138DDEC9F7FF4A36EC2387C853B4EB0FAF5317CF924CEDACE3
PUBLICEXPONENT 65537 (0X10001):
PRIVATEEXPONENT:009DEFE2F252BB364F4AE68575CF8533D02A0CD4F2076AD101E48D4E567895F8ED1F066690B28D1A9422758B6840475EE9A512082E296CC429D90D9543A00391F1
PRIME1:00F8312B334BCC4B6FB5D45638D535A1640C4BC99D1C4289077556FBE7EA47669B
PRIME2:00E653B547E3924AF129D48CCCA88CC6CA2918D466D94809EF8783037419909359
EXPONENT1:511D68BC141AC9D0D1C17B088A0E4417F9B8CF44CCD6A6084CFE47C82D1676DF
EXPONENT2:00AF775FE8576750AE6EC69D4920B2B692B6425335D31BFD6DBC57C3DEC3C70F69

//验证p*q-n=0
> echo "ibase=16;obase=10;00F8312B334BCC4B6FB5D45638D535A1640C4BC99D1C4289077556FBE7EA47669B*00E653B547E3924AF129D48CCCA88CC6CA2918D466D94809EF8783037419909359-00DF4D54818D8ACCD56E5F72985BBD69BB2F4957DE177FB221C6756B9F4CDD1EE1667330C466E3B3138DDEC9F7FF4A36EC2387C853B4EB0FAF5317CF924CEDACE3"|bc
0

//验证(e*d)%((p-1)*(q-1))=1
> echo "ibase=16;obase=10;(10001*009DEFE2F252BB364F4AE68575CF8533D02A0CD4F2076AD101E48D4E567895F8ED1F066690B28D1A9422758B6840475EE9A512082E296CC429D90D9543A00391F1)%((00F8312B334BCC4B6FB5D45638D535A1640C4BC99D1C4289077556FBE7EA47669B-1)*(00E653B547E3924AF129D48CCCA88CC6CA2918D466D94809EF8783037419909359-1))"|bc
1

使用

加密一个字符串

echo “hello world”|openssl rsautl -encrypt -pubin -inkey public_key.pem |base64 -w 200
ETEiZkXmHhYLLp5M5H/SWwFliSwfdXStsNGT6Yx+UGPas+1s38e35zN8mb3Vqic07VOTvqxg2d+xONsCDLFNLmsRmok/sMb0hOYy97RCzPdsrHb0wfEEnze6yQVbp31qguI2KKTjb5+cwT3rOCMGzLlib5kr2OwsxNfIk0PyNms=

解密字符串

echo ‘O7W4OS1pEmkil5fNNok0qsXjiQLLuwGYUwbYTK8ax+AvvlNlHjUmXZFC/gOw8pJQTkvYR1ouXyNswgQf8OkScypDog38hoJFAcFNiWN4qZa+OImCjyLEuLCiRn5AJnHDnwugvP7dyqZjcbkFkcCelglx4IcJSdzRRfyTSfNUmYU=’|base64 -d|openssl rsautl -decrypt -inkey private_key.pem
hello world

加密解密成功了
看看RSA是不是很简单？