IOS 逆向开发(一)密码学 RSA
密码学是指研究信息加密,破解密码的技术科学。密码学的起源可追溯到2000年前。而当今的密码学是以数学为基础的。
发展历史
publickey
)和私有密钥简称私钥(privatekey
)。公钥加密,私钥解密;私钥加密,公钥解密。这个加密算法就是伟大的RSA先从一个问题开始:三的多少次方模 17 等于 12?
显然 , 对于离散对数问题 , 其正向计算得到右边 12 很简单. 但是反向运算时 , 就无从下手. 只能穷举 .
而且当模数使用质数 17 时 , 结果固定在 1 ~ 17 之间. 而当 17 这个模数足够大时 , 就算知道采用的是这个算法 , 也知道 17 这个质数和答案 , 想要再计算出来上图中这个问号值 , 可以想象到其难度和计算量有多大 .
如下图:
从上图我们可以看出,3的N次方取模17的结果是范围:从1到16的任意一个数字。这样3称为17的原根。
这样我们得出一个规律用来加密,3 的 N次方,也就是上面图的
的问号,我们可以用作N(公式中的?号)作为明文,得到密文 12 。这样即使黑客得到我们在网络中传输的密文12 ,就是他知道这个公式,他也很难反算出我们的明文 N。特别是我们把被模数17改的更大一些,如改为几百位的数字,那么黑客基本上是不可能通过这个公式反算出我们的明文的。他只能通过不断试错的暴力破解方式。通过上面这个公式反算,计算出明文N的问题叫做离散对数问题
先了解一些概念
如果一个数N是质数,那么小于N的数都会与N 这个数字互为质数。如N=5,那么1,2,3,4都与5构成互质关系,那么 Φ(5) = 4,表示有4个数与5构成互质关系。
通过上面的一些推理,我们不难发现欧拉函数的特点:
例如 15 = 3 * 5 ,Φ(5*3)=Φ(5)Φ(3) , 而 Φ(5) = 4,Φ(3) = 2, 则Φ(53)=Φ(5)*Φ(3) = 4 * 2 = 8, 也就是15有8个数与它构成互质关系。
模反元素:如果两个正整数e和x互质,那么一定可以找到整数d,使得 ed-1 被x整除。那么d就是e对于x的“模反元素”
如上图所示,转换过程5步即可:d 是 e 相对于 φ(n) 的模反元素 注意 : 公式推导第一步时 我们欧拉定理的前提是 m 和 n 互质 , 但是由于模反元素的关系 , 其实只要满足 m < n 上述结果依然成立.
如果上面的这个公式可以拆分为两次,就可以用来加密。
从终端打印结构可以看出:n = 15 只要 m < n 也就是 m <= 14 无论是否是质数,公式:都成立。M = 4, N = 15, φ(n) = 8, e = 3, d ? 3d -1 = 8 d = (8k+1)/3 -> ( 3, 11) 这里我们可以取d = 11
上面验证知道,m,n不一定要,只需要m < n即可。
- 第一次是服务器端做的运算:3^15mod 17 = 6
- 第二次是客户端自己拿到服务器端的6继续做的一次运算:6^13 mod17 = 10
- 第二次运算的6 用第一次的3^15替换就实际上得到:3^15^13 mod17 = 10
- 第一次是在客户端做的运算:3^13mod17 = 12
- 第二次是拿到客户端的12继续做一次运算:12^15mod17 = 10
- 第二次运算的12实际上是用3^13代替:3^13^15 mod 17 = 10
上面的计算套用公式: 如上面服务器端的计算: m=3, e=13, n=17, C=12 (运算公式:3^13mod17 = 12) 实际上就是:m^e mod n = C 然后由于d = 15, (运算公式:12^15 mod 17 = 10) 实际上就是: C^d mod n = m ,由于 C = m ^ e mod n,可以得到 m ^ e ^ d mod n = m, 也就是:m ^ (ed) mod n = m 实际上就是对ed 进行了拆分,拆分成了两次运算。
其中 d 是 e 相对于 φ(n) 的模反元素 , 因为 x = Φ(n) , 那么同样 , e 和 φ(n) 是互质关系
- 加密: m ^ e mod n = c, (c 加密的结果,m是明文, e和n就是公钥,d和n就是私钥)
- 解密:c ^ d mod n = m
- n 会非常大,长度一般为 1024 个二进制位。(目前人类已经分解的最大整数,232 个十进制位,768 个二进制位)
- 由于需要求出 φ(n),所以根据欧函数特点,最简单的方式 n 由两个质数相乘得到: 质数:p1、p2 . 那么 Φ(n) = (p1 -1) * (p2 - 1)
- 最终由 φ(n) 得到 e 和 d 。 总共生成 6 个数字:p1、p2、n、φ(n)、e、d 其中 n 和 e 组成公钥 . n 和 d 组成私钥 . m 为明文 . c为密文 .
- 除了公钥用到了 n 和 e 其余的 4 个数字是不公开的。
m ^ e mod n = c 加密 c ^ d mod n = m 解密 我们假设 n = 15 则 φ(n) = φ(15) = 8, 假设 e = 3 假设 d= 19 假设明文 m = 7 先来计算出加密:c = 7 ^ 3 mod 15 = 13 然后解密:13 ^ 19 mod 15 = 7
- 总共生成 6 个数字:p1、p2、n、φ(n)、e、d 其中 n 和 e 组成公钥 . n 和 d 组成私钥 . m 为明文 . c为密文 .
- 除了公钥用到了 n 和 e 其余的 4 个数字是不公开的。
- 黑客要破解实际上就是根据n, 去求φ(n), 而当n比较大时,是很难算出φ(n),φ(n)只能通过试错的方式去暴力破解(用因式分解方式)。
- 要求出φ(n) 目前最大只能计算到232个十进制位,只是运算时间的问题,如果量子计算机真的出来了,因为量子计算理论上运算量是无穷大的,所以可以破解这个φ(n),由于银行等很多大公司都是用的RSA加密方式,所以量子计算的问世,将会对密码学产生很大的影响。
- 生成RSA私钥,秘钥长度为1024bit 终端输入命令:
openssl genrsa -out private.pem 1024
- 从私钥中提取公钥 终端输入命令:
openssl rsa -in private.pem -pubout -out public.pem
- 通过上面两步分别已经生成了公钥,私钥文件
- 我们查看一下生成的公钥,私钥是什么东东
- 查看一下公钥内容:
- 实际上公钥,私钥都是经过base64加密的,我们接下来将私钥转换成明文查看: 终端输入命令:
openssl rsa -in private.pem -text -out private.txt
- 我们查看一下私钥的明文: 终端输入:cat private.txt
vi message.txt
openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt 复制代码加密后的内容hello变成了乱码了。
penssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt 复制代码解密后在dec.txt输出了原来的明文hello
penssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin 复制代码
openssl rsautl -verify -in enc.bin -inkey public.pem -pubin -out dec.txt 复制代码
解密到dec.txt ,我们可以看到解密后的明文也还原了hello
openssl req -new -key private.pem -out rsacert.csr 复制代码
会生成一个.csr文件 其中按提示输入一些信息,如邮箱,密码等
openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt 复制代码
openssl x509 -outform der -in rsacert.crt -out rsacert.der 复制代码
openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt 复制代码
这个时候会提示我们输入密码,如下图:
输入密码后(需要确认两次密码)
这样我们就提前到了p12文件
实际上我们就可以用p.p12 和 rsacert.der进行加密和解密
base64 kyl.jpg -o pic.txt 复制代码
base64 pic.txt -o 123.png -D 复制代码解码后我们得到123.png图片
KRSACryptor.h文件如下:
// // KRSACryptor.h // 001-KylAppEncrypt // // Created by 孔雨露 on 2019/12/14. // Copyright © 2019 Apple. All rights reserved. // #import <Foundation/Foundation.h> NS_ASSUME_NONNULL_BEGIN @interface KRSACryptor : NSObject + (instancetype)shared; /** * 生成密钥对 * * @param keySize 密钥尺寸,可选数值(512/1024/2048) */ - (void)generateKeyPair:(NSUInteger)keySize; /** * 加载公钥 * * @param publicKeyPath 公钥路径 * @code # 生成证书 $ openssl genrsa -out ca.key 1024 # 创建证书请求 $ openssl req -new -key ca.key -out rsacert.csr # 生成证书并签名 $ openssl x509 -req -days 3650 -in rsacert.csr -signkey ca.key -out rsacert.crt # 转换格式 $ openssl x509 -outform der -in rsacert.crt -out rsacert.der @endcode */ - (void)loadPublicKey:(NSString *)publicKeyPath; /** * 加载私钥 * * @param privateKeyPath p12文件路径 * @param password p12文件密码 * @code openssl pkcs12 -export -out p.p12 -inkey ca.key -in rsacert.crt @endcode */ - (void)loadPrivateKey:(NSString *)privateKeyPath password:(NSString *)password; /** * 加密数据 * * @param plainData 明文数据 * * @return 密文数据 */ - (NSData *)encryptData:(NSData *)plainData; /** * 解密数据 * * @param cipherData 密文数据 * * @return 明文数据 */ - (NSData *)decryptData:(NSData *)cipherData; @end NS_ASSUME_NONNULL_END 复制代码
KRSACryptor.m文件如下:
// // KRSACryptor.m // 001-KylAppEncrypt // // Created by 孔雨露 on 2019/12/14. // Copyright © 2019 Apple. All rights reserved. // #import "KRSACryptor.h" // 填充模式 #define kTypeOfWrapPadding kSecPaddingPKCS1 // 公钥/私钥标签 #define kPublicKeyTag "com.logic.EncryptDemo.publickey" #define kPrivateKeyTag "com.logic.EncryptDemo.privatekey" static const uint8_t publicKeyIdentifier[] = kPublicKeyTag; static const uint8_t privateKeyIdentifier[] = kPrivateKeyTag; @interface KRSACryptor() { SecKeyRef publicKeyRef; // 公钥引用 SecKeyRef privateKeyRef; // 私钥引用 } @property (nonatomic, retain) NSData *publicTag; // 公钥标签 @property (nonatomic, retain) NSData *privateTag; // 私钥标签 @end @implementation KRSACryptor + (instancetype)shared { static id instance; static dispatch_once_t onceToken; dispatch_once(&onceToken, ^{ instance = [[self alloc] init]; }); return instance; } - (instancetype)init { self = [super init]; if (self) { // 查询密钥的标签 _privateTag = [[NSData alloc] initWithBytes:privateKeyIdentifier length:sizeof(privateKeyIdentifier)]; _publicTag = [[NSData alloc] initWithBytes:publicKeyIdentifier length:sizeof(publicKeyIdentifier)]; } return self; } #pragma mark - 加密 & 解密数据 - (NSData *)encryptData:(NSData *)plainData { OSStatus sanityCheck = noErr; size_t cipherBufferSize = 0; size_t keyBufferSize = 0; NSAssert(plainData != nil, @"明文数据为空"); NSAssert(publicKeyRef != nil, @"公钥为空"); NSData *cipher = nil; uint8_t *cipherBuffer = NULL; // 计算缓冲区大小 cipherBufferSize = SecKeyGetBlockSize(publicKeyRef); keyBufferSize = [plainData length]; if (kTypeOfWrapPadding == kSecPaddingNone) { NSAssert(keyBufferSize <= cipherBufferSize, @"加密内容太大"); } else { NSAssert(keyBufferSize <= (cipherBufferSize - 11), @"加密内容太大"); } // 分配缓冲区 cipherBuffer = malloc(cipherBufferSize * sizeof(uint8_t)); memset((void *)cipherBuffer, 0x0, cipherBufferSize); // 使用公钥加密 sanityCheck = SecKeyEncrypt(publicKeyRef, kTypeOfWrapPadding, (const uint8_t *)[plainData bytes], keyBufferSize, cipherBuffer, &cipherBufferSize ); NSAssert(sanityCheck == noErr, @"加密错误,OSStatus == %d", sanityCheck); // 生成密文数据 cipher = [NSData dataWithBytes:(const void *)cipherBuffer length:(NSUInteger)cipherBufferSize]; if (cipherBuffer) free(cipherBuffer); return cipher; } - (NSData *)decryptData:(NSData *)cipherData { OSStatus sanityCheck = noErr; size_t cipherBufferSize = 0; size_t keyBufferSize = 0; NSData *key = nil; uint8_t *keyBuffer = NULL; SecKeyRef privateKey = NULL; privateKey = [self getPrivateKeyRef]; NSAssert(privateKey != NULL, @"私钥不存在"); // 计算缓冲区大小 cipherBufferSize = SecKeyGetBlockSize(privateKey); keyBufferSize = [cipherData length]; NSAssert(keyBufferSize <= cipherBufferSize, @"解密内容太大"); // 分配缓冲区 keyBuffer = malloc(keyBufferSize * sizeof(uint8_t)); memset((void *)keyBuffer, 0x0, keyBufferSize); // 使用私钥解密 sanityCheck = SecKeyDecrypt(privateKey, kTypeOfWrapPadding, (const uint8_t *)[cipherData bytes], cipherBufferSize, keyBuffer, &keyBufferSize ); NSAssert1(sanityCheck == noErr, @"解密错误,OSStatus == %d", sanityCheck); // 生成明文数据 key = [NSData dataWithBytes:(const void *)keyBuffer length:(NSUInteger)keyBufferSize]; if (keyBuffer) free(keyBuffer); return key; } #pragma mark - 密钥处理 /** * 生成密钥对 */ - (void)generateKeyPair:(NSUInteger)keySize { OSStatus sanityCheck = noErr; publicKeyRef = NULL; privateKeyRef = NULL; NSAssert1((keySize == 512 || keySize == 1024 || keySize == 2048), @"密钥尺寸无效 %tu", keySize); // 删除当前密钥对 [self deleteAsymmetricKeys]; // 容器字典 NSMutableDictionary *privateKeyAttr = [[NSMutableDictionary alloc] init]; NSMutableDictionary *publicKeyAttr = [[NSMutableDictionary alloc] init]; NSMutableDictionary *keyPairAttr = [[NSMutableDictionary alloc] init]; // 设置密钥对的顶级字典 [keyPairAttr setObject:(__bridge id)kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType]; [keyPairAttr setObject:[NSNumber numberWithUnsignedInteger:keySize] forKey:(__bridge id)kSecAttrKeySizeInBits]; // 设置私钥字典 [privateKeyAttr setObject:[NSNumber numberWithBool:YES] forKey:(__bridge id)kSecAttrIsPermanent]; [privateKeyAttr setObject:_privateTag forKey:(__bridge id)kSecAttrApplicationTag]; // 设置公钥字典 [publicKeyAttr setObject:[NSNumber numberWithBool:YES] forKey:(__bridge id)kSecAttrIsPermanent]; [publicKeyAttr setObject:_publicTag forKey:(__bridge id)kSecAttrApplicationTag]; // 设置顶级字典属性 [keyPairAttr setObject:privateKeyAttr forKey:(__bridge id)kSecPrivateKeyAttrs]; [keyPairAttr setObject:publicKeyAttr forKey:(__bridge id)kSecPublicKeyAttrs]; // SecKeyGeneratePair 返回密钥对引用 sanityCheck = SecKeyGeneratePair((__bridge CFDictionaryRef)keyPairAttr, &publicKeyRef, &privateKeyRef); NSAssert((sanityCheck == noErr && publicKeyRef != NULL && privateKeyRef != NULL), @"生成密钥对失败"); } /** * 加载公钥 */ - (void)loadPublicKey:(NSString *)publicKeyPath { NSAssert(publicKeyPath.length != 0, @"公钥路径为空"); // 删除当前公钥 if (publicKeyRef) CFRelease(publicKeyRef); // 从一个 DER 表示的证书创建一个证书对象 NSData *certificateData = [NSData dataWithContentsOfFile:publicKeyPath]; SecCertificateRef certificateRef = SecCertificateCreateWithData(kCFAllocatorDefault, (__bridge CFDataRef)certificateData); NSAssert(certificateRef != NULL, @"公钥文件错误"); // 返回一个默认 X509 策略的公钥对象,使用之后需要调用 CFRelease 释放 SecPolicyRef policyRef = SecPolicyCreateBasicX509(); // 包含信任管理信息的结构体 SecTrustRef trustRef; // 基于证书和策略创建一个信任管理对象 OSStatus status = SecTrustCreateWithCertificates(certificateRef, policyRef, &trustRef); NSAssert(status == errSecSuccess, @"创建信任管理对象失败"); // 信任结果 SecTrustResultType trustResult; // 评估指定证书和策略的信任管理是否有效 status = SecTrustEvaluate(trustRef, &trustResult); NSAssert(status == errSecSuccess, @"信任评估失败"); // 评估之后返回公钥子证书 publicKeyRef = SecTrustCopyPublicKey(trustRef); NSAssert(publicKeyRef != NULL, @"公钥创建失败"); if (certificateRef) CFRelease(certificateRef); if (policyRef) CFRelease(policyRef); if (trustRef) CFRelease(trustRef); } /** * 加载私钥 */ - (void)loadPrivateKey:(NSString *)privateKeyPath password:(NSString *)password { NSAssert(privateKeyPath.length != 0, @"私钥路径为空"); // 删除当前私钥 if (privateKeyRef) CFRelease(privateKeyRef); NSData *PKCS12Data = [NSData dataWithContentsOfFile:privateKeyPath]; CFDataRef inPKCS12Data = (__bridge CFDataRef)PKCS12Data; CFStringRef passwordRef = (__bridge CFStringRef)password; // 从 PKCS #12 证书中提取标示和证书 SecIdentityRef myIdentity; SecTrustRef myTrust; const void *keys[] = {kSecImportExportPassphrase}; const void *values[] = {passwordRef}; CFDictionaryRef optionsDictionary = CFDictionaryCreate(NULL, keys, values, 1, NULL, NULL); CFArrayRef items = CFArrayCreate(NULL, 0, 0, NULL); // 返回 PKCS #12 格式数据中的标示和证书 OSStatus status = SecPKCS12Import(inPKCS12Data, optionsDictionary, &items); if (status == noErr) { CFDictionaryRef myIdentityAndTrust = CFArrayGetValueAtIndex(items, 0); myIdentity = (SecIdentityRef)CFDictionaryGetValue(myIdentityAndTrust, kSecImportItemIdentity); myTrust = (SecTrustRef)CFDictionaryGetValue(myIdentityAndTrust, kSecImportItemTrust); } if (optionsDictionary) CFRelease(optionsDictionary); NSAssert(status == noErr, @"提取身份和信任失败"); SecTrustResultType trustResult; // 评估指定证书和策略的信任管理是否有效 status = SecTrustEvaluate(myTrust, &trustResult); NSAssert(status == errSecSuccess, @"信任评估失败"); // 提取私钥 status = SecIdentityCopyPrivateKey(myIdentity, &privateKeyRef); NSAssert(status == errSecSuccess, @"私钥创建失败"); } /** * 删除非对称密钥 */ - (void)deleteAsymmetricKeys { OSStatus sanityCheck = noErr; NSMutableDictionary *queryPublicKey = [[NSMutableDictionary alloc] init]; NSMutableDictionary *queryPrivateKey = [[NSMutableDictionary alloc] init]; // 设置公钥查询字典 [queryPublicKey setObject:(__bridge id)kSecClassKey forKey:(__bridge id)kSecClass]; [queryPublicKey setObject:_publicTag forKey:(__bridge id)kSecAttrApplicationTag]; [queryPublicKey setObject:(__bridge id)kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType]; // 设置私钥查询字典 [queryPrivateKey setObject:(__bridge id)kSecClassKey forKey:(__bridge id)kSecClass]; [queryPrivateKey setObject:_privateTag forKey:(__bridge id)kSecAttrApplicationTag]; [queryPrivateKey setObject:(__bridge id)kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType]; // 删除私钥 sanityCheck = SecItemDelete((__bridge CFDictionaryRef)queryPrivateKey); NSAssert1((sanityCheck == noErr || sanityCheck == errSecItemNotFound), @"删除私钥错误,OSStatus == %d", sanityCheck); // 删除公钥 sanityCheck = SecItemDelete((__bridge CFDictionaryRef)queryPublicKey); NSAssert1((sanityCheck == noErr || sanityCheck == errSecItemNotFound), @"删除公钥错误,OSStatus == %d", sanityCheck); if (publicKeyRef) CFRelease(publicKeyRef); if (privateKeyRef) CFRelease(privateKeyRef); } /** * 获得私钥引用 */ - (SecKeyRef)getPrivateKeyRef { OSStatus sanityCheck = noErr; SecKeyRef privateKeyReference = NULL; if (privateKeyRef == NULL) { NSMutableDictionary * queryPrivateKey = [[NSMutableDictionary alloc] init]; // 设置私钥查询字典 [queryPrivateKey setObject:(__bridge id)kSecClassKey forKey:(__bridge id)kSecClass]; [queryPrivateKey setObject:_privateTag forKey:(__bridge id)kSecAttrApplicationTag]; [queryPrivateKey setObject:(__bridge id)kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType]; [queryPrivateKey setObject:[NSNumber numberWithBool:YES] forKey:(__bridge id)kSecReturnRef]; // 获得密钥 sanityCheck = SecItemCopyMatching((__bridge CFDictionaryRef)queryPrivateKey, (CFTypeRef *)&privateKeyReference); if (sanityCheck != noErr) { privateKeyReference = NULL; } } else { privateKeyReference = privateKeyRef; } return privateKeyReference; } @end 复制代码
- (void) testRSAEncrpt { //1.加载公钥 [[KRSACryptor shared] loadPublicKey:[[NSBundle mainBundle] pathForResource:@"rsacert.der" ofType:nil]]; //2.加载私钥 [[KRSACryptor shared] loadPrivateKey: [[NSBundle mainBundle] pathForResource:@"p.p12" ofType:nil] password:@"123456"]; } static void my_encrypt(){ NSData * result = [[KRSACryptor shared] encryptData:[@"hello" dataUsingEncoding:NSUTF8StringEncoding]]; //base64编码 NSString * base64 = [result base64EncodedStringWithOptions:0]; NSLog(@"加密之后:%@\n",base64); //解密 NSData * dcStr = [[KRSACryptor shared] decryptData:result]; NSLog(@"%@",[[NSString alloc] initWithData:dcStr encoding:NSUTF8StringEncoding]); } 复制代码