前言本文的RSA例子代码更新在我的github上。 RSA算法是最重要算法之一,它是计算机通信安全的基石,保证了加密数据不会被破解。本文主要参考了参考资料中的文章,介绍一下RSA算法的内容,自己写一遍,算是学习了。 历史1.对称加密算法在1976年以前,所有的加密方法都是同一种模式'对称加密算法'(Symmetric-key algorithm):
这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方,否则无法解密。 2.非对称加密算法1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为'Diffie-Hellman密钥交换算法'。
如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。 3.RSA算法的出现1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。 数论知识1.质数一个大于1的自然数,除了1和它本身外,不能被其他自然数整除(除0以外)的数称之为质数(素数);否则称为合数。 2.互质数互质,又称互素。若N个整数的最大公因子是1,则称这N个整数互质。 3.指数运算
4.模运算
例如,10 mod 3 = 1 、26 mod 6 = 2 、28 mod 2 = 0 5.同余
6.欧拉函数
例如,在1到8之中,与8形成互质关系的是1、3、5、7,所以φ(n)=4
由上易得,若我们知道一个数n可以分解为两个质数p和q的乘积,则有 7.欧拉定理
比如,3和7互质,而7的欧拉函数φ(7)等于6,所以3的6次方(729)减去1,可以被7整除(728/7=104)。 8.模反元素意即,如果两个正整数a和n互质,那么一定可以找到整数b 比如,3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...},即如果b是a的模反元素,则 b+kn 都是a的模反元素。 算法基础1.实例先通过一个实例来理解RSA算法的过程: 甲要发给乙一个加密内容:m=65 加密出c 甲将使用公钥加密的密文c=2790发送给乙 解密出m 从始至终,用来解密的私钥(n,d)=(3233,2753)一直都在乙处,从未泄露。乙给甲的仅仅是用来加密的公钥(3233,17),这个公钥并不能用来解密,即使被他人截获,也没有任何泄密的风险。 2.计算公私钥
至此,整个rsa公私钥的算法就清楚了 3.推导整个过程中,让人困扰的可能是 式子1 与 式子2 事实上式子2就是从式子1推导出来,具体过程可以参考RSA算法原理(二),这边也做一个简单描述: 4.安全性在上面给出的例子中,一共出现了6个数字:
其中公钥用到了(n,e),剩下4个不知。关键私钥(n,d),关键值是d,不能泄露d。 那么,有无可能在已知n和e的情况下,推导出d?
结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。 算法实现iOS中的实现与使用iOS的 //加密方法OSStatus SecKeyEncrypt( SecKeyRef key, SecPadding padding, const uint8_t *plainText, size_t plainTextLen, uint8_t *cipherText, size_t *cipherTextLen) __OSX_AVAILABLE_STARTING(__MAC_10_7, __IPHONE_2_0);//解密方法OSStatus SecKeyDecrypt( SecKeyRef key, /* Private key */ SecPadding padding, /* kSecPaddingNone, kSecPaddingPKCS1, kSecPaddingOAEP */ const uint8_t *cipherText, size_t cipherTextLen, /* length of cipherText */ uint8_t *plainText, size_t *plainTextLen) /* IN/OUT */ __OSX_AVAILABLE_STARTING(__MAC_10_7, __IPHONE_2_0); 但这个framework的api只支持从标准证书文件(cer,crt)中读取公私钥。 所以先要使用openssl生成公钥证书public_key.der和私钥证书private_key.p12。然后读取公私钥,再用framework进行加密。 RSAEncryptor* rsaEncryptor = [[RSAEncryptor alloc] init]; NSString* publicKeyPath = [[NSBundle mainBundle] pathForResource:@'public_key' ofType:@'der']; NSString* privateKeyPath = [[NSBundle mainBundle] pathForResource:@'private_key' ofType:@'p12']; [rsaEncryptor loadPublicKeyFromFile: publicKeyPath]; [rsaEncryptor loadPrivateKeyFromFile: privateKeyPath password:@'']; // 这里,请换成你生成p12时的密码 NSString* restrinBASE64STRING = [rsaEncryptor rsaEncryptString:@'I.O.S']; NSLog(@'Encrypted: %@', restrinBASE64STRING); // 请把这段字符串Copy到JAVA这边main()里做测试 NSString* decryptString = [rsaEncryptor rsaDecryptString: restrinBASE64STRING]; NSLog(@'Decrypted: %@', decryptString); 具体的RSAEncryptor代码,这里就不贴了,可以从我的github上找相应的iOS加解密的代码。上面还有一个c++的RSA算法的例子,可以看一下。 总结本文主要还是整理了网上各个文章,其中数学原理解释的最清楚的应该是阮一峰的RSA算法原理(一)与RSA算法原理(二)。数学原理上有不懂的可以再看一下这两篇文章。最后总结一下RSA算法加密方式。
参考资料本文CSDN地址 |
|