iOS安全之路--RSA

来源:http://www.chinese-glasses.com 作者:Web前端 人气:132 发布时间:2020-04-07
摘要:时间: 2019-10-16阅读: 98标签: 算法 一、RSA简介 在介绍RSA之前,先介绍下对称、非对称加密。 这篇文章我本来是想写了放到极客时间上我写的专栏里面的,但是专栏的内容是需要仔细斟酌

时间: 2019-10-16阅读: 98标签: 算法

一、RSA简介

在介绍RSA之前,先介绍下对称、非对称加密。

这篇文章我本来是想写了放到极客时间上我写的专栏里面的,但是专栏的内容是需要仔细斟酌的。这篇文章我认为还是偏难,不适合整个专栏的内容和难度的定位,因此我把它稍微加工了一下,放到我这个博客上。

对称加密:

A选择某一种加密规则,对信息进行加密;
B使用同一种规则,对信息进行解密。
由于加密和解密使用同样规则(密钥),这被称为"对称加密算法"。

在专栏中的第 36 讲的选修课堂(该讲预计在 12 月初发布)中,我介绍了 Diffie–Hellman 密钥交换这一算法,它可以说是质数在加密技术中的一个应用,并且是通过其中的 “模幂运算” 来实现的。今天,我来介绍质数的另一个应用,RSA 背后的算法。我在互联网上搜索了一下,我发现基本没有能把它背后的实现原理用浅显的中文叙述讲清楚的,但我还是想试一试,看看能不能尽可能避开那些难懂的术语,用尽量形象和易于理解的方式,把 RSA 背后的原理讲清楚。

非对称加密:

B生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
A获取B的公钥,然后用它对信息加密。
B得到加密后的信息,用私钥解密。
公钥加密的信息只有私钥解得开,加解密的密钥是不同的,这被称为"非对称加密算法"。

*以上的A一般指的是客户端、B一般是服务器端。

RSA就是非对称加密算法的一种。

在专栏的第 02 讲,我们讲了非对称性加密,比如通过公钥加密的数据,能且只能通过私钥来解密,可是这是怎样实现的呢?这就要讲 RSA 加密技术的原理了。现在,假定我们要通过 RSA 来进行安全的通信,于是你要使用我发布的公钥来对数据加密,加密以后发给我,我拿到加密数据以后使用对应的私钥解密,而攻击者截获了这个加密数据并尝试破解。

二、算法描述

RSA算法的数论基础:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。
在算法描述之前,需要补充一些数学知识。

模幂等式

素数(质数)

素数指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。

我们在介绍 Diffie–Hellman 密钥交换的时候讲到了这个模幂等式:

互质数

公因数只有1的两个数,叫做互质数。
判断方法主要有以下几种:
两个不同的质数一定是互质数。例如,2与7、13与19。
一个质数,另一个不为它的倍数,这两个数为互质数。例如,3与10、5与 26。
相邻的两个自然数是互质数。如 15与 16。
相邻的两个奇数是互质数。如 49与 51。
较大数是质数的两个数是互质数。如97与88。
小数是质数,大数不是小数的倍数的两个数是互质数。例如 7和 16。
2和任何奇数是互质数。例如2和87。
1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。
辗转相除法。

gᵃ mod p = A

指数运算(乘方计算)

指数运算计算结果称为幂。nm指将n自乘m次。把nm看作乘方的结果,叫做”n的m次幂”或”n的m次方”。其中,n称为“底数”,m称为“指数”。

从难度上看它具有如下三个特性:

模运算

模运算即求余运算。和模运算紧密相关的一个概念是“同余”。数学上,当两个整数除以同一个正整数,若得相同余数,则二整数同余。两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模m同余,记作: a ≡ b (mod m);读作:a同余于b模m,或者,a与b关于模m同余。例如:26 ≡ 14 (mod 12)。

特性 ①:已知 g、a 和 p,求 A 容易;特性 ②:已知 g、p 和 A,求 a 困难;特性 ③:已知 a、p 和 A,求 g 也困难。

欧拉函数

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

图片 1

欧拉函数

有了这些数学知识,下面开始描述RSA算法,场景为A要与B进行加密通信。描述出处

再看看上面我们介绍的模幂公式关于离散对数求解的三种难易程度不同的情况吧,我们在 Diffie–Hellman 密钥交换中应用了特性 ① 和特性 ②,而在 RSA 中,我们还要应用特性 ① 和特性 ③。

1.随机选择两个不相等的质数p和q。

A选择了61和53。(实际应用中,这两个质数越大,就越难破解)

观察特性 ①,我们可以利用它来设计 RSA 加密,即让 g 代表需要被加密的实际值,而 a、p 可以公开。于是你就求出它的 a 次幂,并取 p 模,得到了 “密文” A,把它发给我。这个过程中,如果 A 被截获,那么根据特性 ③,已知 A、p 和 a,攻击者是很难求解出 g 来的。我们已经说过了,这符合 “正向计算简单,逆向求解困难” 这一特性,这一点很适合用来加密。

2.计算p和q的乘积n。

A把61和53相乘。

n = 61×53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。(实际应用中,RSA密钥一般是1024位,重要场合则为2048位)

但是和前面的 Diffie–Hellman 密钥交换不同的是,我们并不是要让所有人都求解这个 g 困难,因为密文是发给我的,我得很容易求解这个 g 才行啊,要不然就像是用一把没人拥有钥匙的锁来加密,这把锁就失去意义了。

3.计算n的欧拉函数φ(n)。

根据公式:

  φ(n) = (p-1)(q-1)

A算出φ(3233)等于60×52,即3120。

我们再来观察一下这个模幂等式:

4.随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。

A在1到3120之间,随机选择了17。(实际应用中,常常选择65537)

gᵃ mod p = A

5.计算e对于φ(n)的模反元素d。

所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。

 ed ≡ 1 (mod φ(n))

这个式子等价于

  ed - 1 = kφ(n)

于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。

  ex + φ(n)y = 1

已知 e=17, φ(n)=3120,

  17x + 3120y = 1

这个方程可以用"扩展欧几里得算法"求解,此处省略具体过程。A算出一组整数解为 (x,y)=(2753,-15),即 d=2753。
至此所有计算完成。

藉由 Diffie–Hellman 密钥交换带来的灵感,如果我们构造这样一个和上式形式一致,但变量具有一定对称性的等式:

6.将n和e封装成公钥,n和d封装成私钥。

在例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。
实际应用中,公钥和私钥的数据都采用ASN.1格式表达。

Aᵈ mod p = g

三、算法实现

@implementation CATSecurity

#pragma mark -- RSA
#pragma mark -- public methods

+ (NSString *)rsaEncryptString:(NSString *)str publicKey:(NSString *)pubKey{
    NSData *data = [self rsaEncryptData:[str dataUsingEncoding:NSUTF8StringEncoding] publicKey:pubKey];
    NSString *ret = base64_encode_data(data);
    return ret;
}

+ (NSData *)rsaEncryptData:(NSData *)data publicKey:(NSString *)pubKey{
    if(!data || !pubKey){
        return nil;
    }
    SecKeyRef keyRef = [self _addPublicKey:pubKey];
    if(!keyRef){
        return nil;
    }
    return [self _encryptData:data withKeyRef:keyRef];
}

+ (NSString *)rsaDecryptString:(NSString *)str publicKey:(NSString *)pubKey{
    NSData *data = [[NSData alloc] initWithBase64EncodedString:str options:NSDataBase64DecodingIgnoreUnknownCharacters];
    data = [self rsaDecryptData:data publicKey:pubKey];
    NSString *ret = [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding];
    return ret;
}

+ (NSData *)rsaDecryptData:(NSData *)data publicKey:(NSString *)pubKey{
    if(!data || !pubKey){
        return nil;
    }
    SecKeyRef keyRef = [self _addPublicKey:pubKey];
    if(!keyRef){
        return nil;
    }
    return [self _decryptData:data withKeyRef:keyRef];
}

+ (NSString *)rsaDecryptString:(NSString *)str privateKey:(NSString *)privKey{
    NSData *data = [[NSData alloc] initWithBase64EncodedString:str options:NSDataBase64DecodingIgnoreUnknownCharacters];
    data = [self rsaDecryptData:data privateKey:privKey];
    NSString *ret = [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding];
    return ret;
}

+ (NSData *)rsaDecryptData:(NSData *)data privateKey:(NSString *)privKey{
    if(!data || !privKey){
        return nil;
    }
    SecKeyRef keyRef = [self _addPrivateKey:privKey];
    if(!keyRef){
        return nil;
    }
    return [self _decryptData:data withKeyRef:keyRef];
}

#pragma mark -- RSA
#pragma mark -- private methods

static NSString *base64_encode_data(NSData *data){
    data = [data base64EncodedDataWithOptions:0];
    NSString *ret = [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding];
    return ret;
}

static NSData *base64_decode(NSString *str){
    NSData *data = [[NSData alloc] initWithBase64EncodedString:str options:NSDataBase64DecodingIgnoreUnknownCharacters];
    return data;
}

+ (NSData *)_stripPublicKeyHeader:(NSData *)d_key{
    // Skip ASN.1 public key header
    if (d_key == nil) return(nil);

    unsigned long len = [d_key length];
    if (!len) return(nil);

    unsigned char *c_key = (unsigned char *)[d_key bytes];
    unsigned int  idx    = 0;

    if (c_key[idx++] != 0x30) return(nil);

    if (c_key[idx] > 0x80) idx += c_key[idx] - 0x80 + 1;
    else idx++;

    // PKCS #1 rsaEncryption szOID_RSA_RSA
    static unsigned char seqiod[] =
    { 0x30,   0x0d, 0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01,
        0x01, 0x05, 0x00 };
    if (memcmp(&c_key[idx], seqiod, 15)) return(nil);

    idx += 15;

    if (c_key[idx++] != 0x03) return(nil);

    if (c_key[idx] > 0x80) idx += c_key[idx] - 0x80 + 1;
    else idx++;

    if (c_key[idx++] != '') return(nil);

    // Now make a new NSData from this buffer
    return([NSData dataWithBytes:&c_key[idx] length:len - idx]);
}

//credit: http://hg.mozilla.org/services/fx-home/file/tip/Sources/NetworkAndStorage/CryptoUtils.m#l1036
+ (NSData *)_stripPrivateKeyHeader:(NSData *)d_key{
    // Skip ASN.1 private key header
    if (d_key == nil) return(nil);

    unsigned long len = [d_key length];
    if (!len) return(nil);

    unsigned char *c_key = (unsigned char *)[d_key bytes];
    unsigned int  idx    = 22; //magic byte at offset 22

    if (0x04 != c_key[idx++]) return nil;

    //calculate length of the key
    unsigned int c_len = c_key[idx++];
    int det = c_len & 0x80;
    if (!det) {
        c_len = c_len & 0x7f;
    } else {
        int byteCount = c_len & 0x7f;
        if (byteCount + idx > len) {
            //rsa length field longer than buffer
            return nil;
        }
        unsigned int accum = 0;
        unsigned char *ptr = &c_key[idx];
        idx += byteCount;
        while (byteCount) {
            accum = (accum << 8) + *ptr;
            ptr++;
            byteCount--;
        }
        c_len = accum;
    }

    // Now make a new NSData from this buffer
    return [d_key subdataWithRange:NSMakeRange(idx, c_len)];
}

+ (SecKeyRef)_addPublicKey:(NSString *)key{
    NSRange spos = [key rangeOfString:@"-----BEGIN PUBLIC KEY-----"];
    NSRange epos = [key rangeOfString:@"-----END PUBLIC KEY-----"];
    if(spos.location != NSNotFound && epos.location != NSNotFound){
        NSUInteger s = spos.location + spos.length;
        NSUInteger e = epos.location;
        NSRange range = NSMakeRange(s, e-s);
        key = [key substringWithRange:range];
    }
    key = [key stringByReplacingOccurrencesOfString:@"r" withString:@""];
    key = [key stringByReplacingOccurrencesOfString:@"n" withString:@""];
    key = [key stringByReplacingOccurrencesOfString:@"t" withString:@""];
    key = [key stringByReplacingOccurrencesOfString:@" "  withString:@""];

    // This will be base64 encoded, decode it.
    NSData *data = base64_decode(key);
    data = [self _stripPublicKeyHeader:data];
    if(!data){
        return nil;
    }

    //a tag to read/write keychain storage
    NSString *tag = @"RSAUtil_PubKey";
    NSData *d_tag = [NSData dataWithBytes:[tag UTF8String] length:[tag length]];

    // Delete any old lingering key with the same tag
    NSMutableDictionary *publicKey = [[NSMutableDictionary alloc] init];
    [publicKey setObject:(__bridge id) kSecClassKey forKey:(__bridge id)kSecClass];
    [publicKey setObject:(__bridge id) kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType];
    [publicKey setObject:d_tag forKey:(__bridge id)kSecAttrApplicationTag];
    SecItemDelete((__bridge CFDictionaryRef)publicKey);

    // Add persistent version of the key to system keychain
    [publicKey setObject:data forKey:(__bridge id)kSecValueData];
    [publicKey setObject:(__bridge id) kSecAttrKeyClassPublic forKey:(__bridge id)
     kSecAttrKeyClass];
    [publicKey setObject:[NSNumber numberWithBool:YES] forKey:(__bridge id)
     kSecReturnPersistentRef];

    CFTypeRef persistKey = nil;
    OSStatus status = SecItemAdd((__bridge CFDictionaryRef)publicKey, &persistKey);
    if (persistKey != nil){
        CFRelease(persistKey);
    }
    if ((status != noErr) && (status != errSecDuplicateItem)) {
        return nil;
    }

    [publicKey removeObjectForKey:(__bridge id)kSecValueData];
    [publicKey removeObjectForKey:(__bridge id)kSecReturnPersistentRef];
    [publicKey setObject:[NSNumber numberWithBool:YES] forKey:(__bridge id)kSecReturnRef];
    [publicKey setObject:(__bridge id) kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType];

    // Now fetch the SecKeyRef version of the key
    SecKeyRef keyRef = nil;
    status = SecItemCopyMatching((__bridge CFDictionaryRef)publicKey, (CFTypeRef *)&keyRef);
    if(status != noErr){
        return nil;
    }
    return keyRef;
}

+ (SecKeyRef)_addPrivateKey:(NSString *)key{
    NSRange spos;
    NSRange epos;
    spos = [key rangeOfString:@"-----BEGIN RSA PRIVATE KEY-----"];
    if(spos.length > 0){
        epos = [key rangeOfString:@"-----END RSA PRIVATE KEY-----"];
    }else{
        spos = [key rangeOfString:@"-----BEGIN PRIVATE KEY-----"];
        epos = [key rangeOfString:@"-----END PRIVATE KEY-----"];
    }
    if(spos.location != NSNotFound && epos.location != NSNotFound){
        NSUInteger s = spos.location + spos.length;
        NSUInteger e = epos.location;
        NSRange range = NSMakeRange(s, e-s);
        key = [key substringWithRange:range];
    }
    key = [key stringByReplacingOccurrencesOfString:@"r" withString:@""];
    key = [key stringByReplacingOccurrencesOfString:@"n" withString:@""];
    key = [key stringByReplacingOccurrencesOfString:@"t" withString:@""];
    key = [key stringByReplacingOccurrencesOfString:@" "  withString:@""];

    // This will be base64 encoded, decode it.
    NSData *data = base64_decode(key);
    data = [self _stripPrivateKeyHeader:data];
    if(!data){
        return nil;
    }

    //a tag to read/write keychain storage
    NSString *tag = @"RSAUtil_PrivKey";
    NSData *d_tag = [NSData dataWithBytes:[tag UTF8String] length:[tag length]];

    // Delete any old lingering key with the same tag
    NSMutableDictionary *privateKey = [[NSMutableDictionary alloc] init];
    [privateKey setObject:(__bridge id) kSecClassKey forKey:(__bridge id)kSecClass];
    [privateKey setObject:(__bridge id) kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType];
    [privateKey setObject:d_tag forKey:(__bridge id)kSecAttrApplicationTag];
    SecItemDelete((__bridge CFDictionaryRef)privateKey);

    // Add persistent version of the key to system keychain
    [privateKey setObject:data forKey:(__bridge id)kSecValueData];
    [privateKey setObject:(__bridge id) kSecAttrKeyClassPrivate forKey:(__bridge id)
     kSecAttrKeyClass];
    [privateKey setObject:[NSNumber numberWithBool:YES] forKey:(__bridge id)
     kSecReturnPersistentRef];

    CFTypeRef persistKey = nil;
    OSStatus status = SecItemAdd((__bridge CFDictionaryRef)privateKey, &persistKey);
    if (persistKey != nil){
        CFRelease(persistKey);
    }
    if ((status != noErr) && (status != errSecDuplicateItem)) {
        return nil;
    }

    [privateKey removeObjectForKey:(__bridge id)kSecValueData];
    [privateKey removeObjectForKey:(__bridge id)kSecReturnPersistentRef];
    [privateKey setObject:[NSNumber numberWithBool:YES] forKey:(__bridge id)kSecReturnRef];
    [privateKey setObject:(__bridge id) kSecAttrKeyTypeRSA forKey:(__bridge id)kSecAttrKeyType];

    // Now fetch the SecKeyRef version of the key
    SecKeyRef keyRef = nil;
    status = SecItemCopyMatching((__bridge CFDictionaryRef)privateKey, (CFTypeRef *)&keyRef);
    if(status != noErr){
        return nil;
    }
    return keyRef;
}

+ (NSData *)_encryptData:(NSData *)data withKeyRef:(SecKeyRef) keyRef{
    const uint8_t *srcbuf = (const uint8_t *)[data bytes];
    size_t srclen = (size_t)data.length;

    size_t block_size = SecKeyGetBlockSize(keyRef) * sizeof(uint8_t);
    void *outbuf = malloc(block_size);
    size_t src_block_size = block_size - 11;

    NSMutableData *ret = [[NSMutableData alloc] init];
    for(int idx=0; idx<srclen; idx+=src_block_size){
        //NSLog(@"%d/%d block_size: %d", idx, (int)srclen, (int)block_size);
        size_t data_len = srclen - idx;
        if(data_len > src_block_size){
            data_len = src_block_size;
        }

        size_t outlen = block_size;
        OSStatus status = noErr;
        status = SecKeyEncrypt(keyRef,
                               kSecPaddingPKCS1,
                               srcbuf + idx,
                               data_len,
                               outbuf,
                               &outlen
                               );
        if (status != 0) {
            NSLog(@"SecKeyEncrypt fail. Error Code: %d", status);
            ret = nil;
            break;
        }else{
            [ret appendBytes:outbuf length:outlen];
        }
    }

    free(outbuf);
    CFRelease(keyRef);
    return ret;
}

+ (NSString *)_encryptString:(NSString *)str privateKey:(NSString *)privKey{
    NSData *data = [self encryptData:[str dataUsingEncoding:NSUTF8StringEncoding] privateKey:privKey];
    NSString *ret = base64_encode_data(data);
    return ret;
}

+ (NSData *)encryptData:(NSData *)data privateKey:(NSString *)privKey{
    if(!data || !privKey){
        return nil;
    }
    SecKeyRef keyRef = [self _addPrivateKey:privKey];
    if(!keyRef){
        return nil;
    }
    return [self _encryptData:data withKeyRef:keyRef];
}

+ (NSData *)_decryptData:(NSData *)data withKeyRef:(SecKeyRef) keyRef{
    const uint8_t *srcbuf = (const uint8_t *)[data bytes];
    size_t srclen = (size_t)data.length;

    size_t block_size = SecKeyGetBlockSize(keyRef) * sizeof(uint8_t);
    UInt8 *outbuf = malloc(block_size);
    size_t src_block_size = block_size;

    NSMutableData *ret = [[NSMutableData alloc] init];
    for(int idx=0; idx<srclen; idx+=src_block_size){
        //NSLog(@"%d/%d block_size: %d", idx, (int)srclen, (int)block_size);
        size_t data_len = srclen - idx;
        if(data_len > src_block_size){
            data_len = src_block_size;
        }

        size_t outlen = block_size;
        OSStatus status = noErr;
        status = SecKeyDecrypt(keyRef,
                               kSecPaddingNone,
                               srcbuf + idx,
                               data_len,
                               outbuf,
                               &outlen
                               );
        if (status != 0) {
            NSLog(@"SecKeyEncrypt fail. Error Code: %d", status);
            ret = nil;
            break;
        }else{
            //the actual decrypted data is in the middle, locate it!
            int idxFirstZero = -1;
            int idxNextZero = (int)outlen;
            for ( int i = 0; i < outlen; i++ ) {
                if ( outbuf[i] == 0 ) {
                    if ( idxFirstZero < 0 ) {
                        idxFirstZero = i;
                    } else {
                        idxNextZero = i;
                        break;
                    }
                }
            }

            [ret appendBytes:&outbuf[idxFirstZero+1] length:idxNextZero-idxFirstZero-1];
        }
    }

    free(outbuf);
    CFRelease(keyRef);
    return ret;
}
@end

最后附上工程地址

这其实是什么?这不就是将加密的数据 A,经过模幂运算以后,得到了原始的未加密数据 g 了吗?也就是说,既然 a 是公钥,那么这里的 d 就是所谓的 “私钥” 啊。

好,我们把后面这个公式的 A 通过前面那个公式来带入,得到:(gᵃ mod p)ᵈ mod p = g,根据我们前面介绍模幂运算时提到的联等公式,它就可以化简为:

gᵃᵈ mod p = g

因此这个式子,就表示出了公钥、私钥,以及被加密数之间的关系。

接下去,我们来思考怎样生成这个私钥 d。

欧拉函数

为了继续进行后面的分析,我们需要一点知识储备,首先是欧拉函数。欧拉函数 φ(x) 表示,有多少不大于 x 的正整数中,与 x 互质的数目(即公因数只有 1)。

举例来说,要计算 φ(4),你看不大于 4 的正整数包括 1、2、3、4,其中:

1 和 4 互质;2 不和 4 互质,因为它们有公因数 2;3 和 4 互质;4 不和 4 互质,因为它们有公因数 4。

所以 φ(4) = 2。

欧拉函数 φ(x) 一般很难计算,但是如果 x 是质数,情况就不同了,因为质数和任何比它小的正整数互质,比如 φ(5) = 4,这四个数分别是 1、2、3、4,因此,在 x 是质数的情况下:

φ(x) = x – 1

本文由10bet发布于Web前端,转载请注明出处:iOS安全之路--RSA

关键词:

频道精选

最火资讯