对称与非对称RSA加密

加密方法根据是否使用同一把密钥,分为对称与非对称加密。使用同一把钥匙进行加密及解密,称为对称加密。使用一对钥匙,其中一把钥匙加密的内容,必须用与之配对的钥匙解密,称为非对称加密。对称加密是可逆的,非对称加密是不可逆的。

对称加密及密钥交换

异或运算就是一种对称加密。比如使用二进制密钥1111对二进制数字1010进行异或运算:加密过程1010xor1111=0101,解密过程0101xor1111=1010。第一次异或运算是加密,第二次异或运算是解密。数学过程就是AxorBxorB=A。异或是可逆运算,而取模是不可逆运算。比如5%3=2, 但是X%3=2求X,这X就有很多解,3*n+2,运算不可逆。

要使用对称加密通讯内容,就需要双方通过安全方式交换密钥。使用取模运算结合指数运算,就可以通过“迪菲-赫尔曼-墨克密钥交换方案(Diffie–Hellman–Merkle key exchange)”安全交换密钥。过程如下:

  1. 双方约定一个运算法则g^X%p。比如g=3, p=5;
  2. Alice选一个私密的数X=a,执行g^a%p运算得到A。比如a=2,A=3^2%5=4;
  3. Bob选一个私密的数X=b,执行g^b%p运算得到B。比如b=3,B=3^3%5=2;
  4. 通讯告知各自运算得到的结果,A=4,B=2;
  5. Alice通过自己私密的a=2和Bob告知的B=2,算出密钥K=B^a%p=2^2%5=4;
  6. Bob通过自己私密的b=2和Alice告知的A=4,算出密钥K=A^b%p=4^3%5=4;
  7. 之后采用对称密钥K加密内容进行通讯。

如下图所示,红色为私密内容,其它都可公开:

由于第三方不知道Alice和Bob内心想的那个数是什么,即便窃听了全部通讯过程,也无法算出密钥。

非对称RSA加密

若是使用非对称加密,就无需考虑密钥交换的事。将公钥PublicKey公开,隐藏与之对应的私钥PrivateKey。公钥加密的内容只能用与之对应的私钥解密,反之亦然。公钥加密的内容,只有拥有私钥的接收方才能解密,确保信息不泄露。私钥加密的内容,任何人都可以拿公钥尝试解密,验证发信人都身份,可当作电子签名使用。其中一种公开公钥的算法就是RSA加密算法。RSA是三个发明人首字母的缩写,Ron Rivest、Adi Shamir、Leonard Adleman。他们在文章《A Method for Obtaining Digital Signatures and Public-Key Cryptosystems》中描述了该方法。

简单说,随机挑选两个隐密的大质数p, q, 计算n=p*q,r=(p-1)*(q-1)。对信息M加密得到密文C=E(M)=M^e%n;对密文C解密得到原文M=D(C)=C^d%n。私钥是(d, n),公钥是(e, n)。私钥d满足gcd(d,r) = 1,gcd指greatest common divisor,最大公约数,即d是与r互质的整数;公钥e满足e*d%r=1,e和d相乘对r取模,余数是1。使用公钥加密过程为Encryption E,使用私钥解密过程为Decryption D,密文称为Ciphertext C。E, D满足:D(E(M))=M,E(D(M))=M,即用其中一把钥匙加密对内容,要用与之配对的钥匙解密。

整个过程:

  1. 随机私密大质数p, q, 计算n=p*q, r=(p-1)*(q-1);
  2. 挑选私钥d,满足gcd(d,r)=1;计算公钥e,满足e*d%r=1;
  3. 销毁p, q, r;公开公钥(e, n),保密私钥(d, n);
  4. Bob发信息M给Alice,就用Alice的公钥(e, n)加密:C=M^e%n;
  5. Alice收到密文C,用自己的私钥(d, n)解密:M=C^d%n。

举个简单例子:

  1. 挑选p=2, q=5,计算出n=10, r=4;
  2. 挑选私钥d=3,计算出公钥e=7;(可在WolframAlpha 输入gcd(x,4)=1挑一个3,输入x*3%4=1挑一个7);
  3. Alice全网公开公钥(7, 10), 保密私钥(3, 10);
  4. Bob发信息2给Alice,使用Alice的公钥(7, 10)加密:2^7%10=8 (在WolframAlpha 输入2^7 mod 10得到8);信息2使用Alice的公钥加密后的密文是8。
  5. Alice收到密文8,使用私钥(3, 10)解密:8^3%10=2。2这就是Bob发给Alice的信息。

示意图如下:

每个字母通过ASCII表都对应着一个数字编码,通过将数字进行RSA加密,就可以保证通讯过程即便被监听,通讯内容也不会被第三方知道。上面的n=p*q=10,换算成二进制就是1010,4-bit加密。HTTPS通讯协议,zerossl默认证书是RSA-4096bit加密。ProtonMail默认是RSA-2048bit加密。

要破解RSA,方法是因数分解n,取得p和q。目前就是拼计算机的速度,遍历法求解。比如上文的n=10,一猜就是p=2, q=5。目前有记录的,被破解的最长RSA密钥是768位,2009年被破解。

2019/12/29, Sat

Leave a Reply

Your email address will not be published. Required fields are marked *