阅读 487

iOS逆向 RSA理论

欢迎阅读iOS逆向系列(按序阅读食用效果更加)

写在前面

这篇文章将从RSA理论RSA终端操作RSA代码操作三个方面去了解和使用RSA加密。一到四节是理论部分,觉得看的无趣的小伙伴们可以直接跳到第五节

数学小课堂

  1. 质数:又叫素数,在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数,如2,3,5,7
  2. 因数:又叫约数,整数a除以整数b(b≠0) 的商正好是整数,则b是a的因数,如2是4的约数
  3. 互质:如果两个正整数,没有除1以外的公因数,则称它们为互质关系,如7和9互质
  4. 取模运算:又叫时钟运算,与我们平时所说的取余运算略有不同(两者区别可自行百度,在RSA运算中两者的运算结果是一致的),取模符号为 mod,取余符号为 %
  5. 同余定理: 幂运算性质:如果a≡b mod m,那么a^{n}≡b^{n}modm

一、密码学发展历史

  1. 早期:使用密码本(罗马字母与数字对应的一张表)
  2. 1976年以前:对称加密算法,加密解密使用同一种规则(密钥),这种规则的保护就显得极为重要,一旦泄露或po解,所有的信息都能被解密出来
  3. 1976年:“迪费赫尔曼密钥交换”算法是由美国两个计算机学家迪费(W.Diffie)、赫尔曼(M.Hellman)共同提出的构思,可以在不直接传递密钥的情况下进行密钥交换
  4. 1977年:RSA加密问世。RSA是由美国麻省理工学院的数学家罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出并用他们的名字命名的

二、RSA中的数学原理

  1. 原根:g^{i} mod p ≠ g^{j} mod p (p为质数),其中i≠j且i, j介于1至(p-1)之间,则g为p的原根 如:因为3^1 mod 17 = 3,3^2 mod 17 = 9...3^16 mod 17 = 1,3的1~16次方mod17的值都不相同,所以3为17的原根

  2. 欧拉函数:在小于正整数n的数中,与n互质的数的个数

特点:

  • 如果n = A * B,且A、B互质,则Φ(n) = Φ(A) * Φ(B)
  • n为质数时,Φ(n) = n - 1,如Φ(17) = 16
  1. 欧拉定理:如果两个正整数m和n互质,那么m的Φ(n)次方减1可以被n整除

条件: m与n互质

公式: m^{Φ(n)} mod n ≡ 1

  1. 费马小定理:是欧拉定理的一种特殊情况,n自身为质数时,Φ(n) = n - 1

条件: m与n互质,且n为质数

公式: m^{n-1}mod n ≡ 1

  1. 模反元素:如果两个正整数e和x互质,那么一定可以找到整数d,使得ed-1被x整除,而d被称作e对于x的模反元素

条件: e与x互质

公式: e * d mod x ≡ 1

  1. 欧拉函数和模反元素的公式推演

接下来我们利用已知的数学公式来推演公式:

① 在欧拉定理公式中,m^{Φ(n)} mod n ≡ 1等式两边同k次方,根据同余定理的幂运算性质就可以得到m^{k*Φ(n)} mod n ≡ 1

② 然后在等式两边同乘m,即可得出m^{k*Φ(n)+1} mod n ≡ m

③ 在模反元素公式中,e * d mod x ≡ 1去掉mod运算符。既然ed-1可以被x整除,那么ed必然是x的k倍数+1

④ 在x=φ(n)的情况下,m^{ed} mod n ≡ n

总结: 欧拉函数和模反元素可以推出RSA加密的前身,而且根据多次计算,发现所满足的必要条件与欧拉函数并不一致

条件:

  1. m < n;
  2. d是e对于φ(n)的模反元素;

公式:m^{ed} mod n ≡ n

数学家们花了许多时间和精力都没有想到继续拆分这个公式的方法,知道迪费、赫尔曼两个大佬的出现才解决了这个难题,同时迪费赫尔曼密钥交换也开创了密码学的新方向

三、迪费赫尔曼密钥交换

这里拿了一张Hank老师的思维导图来进行说明:

  1. 服务器生成一个随机数15,然后根据固定的算法3^{15}mod17得到加密后的信息6发送给客户端
  2. 客户端同时生成一个随机数13,根据同样的算法3^{13}mod17得到信息12发给服务器
  3. 服务器和客户端根据得到的信息照着原来的算法再次运算,就能得到对方发的真实信息,信息交换中也不会涉及到密钥的交换

注意:

  1. 信息在传输过程中,第三方只能截取到信息6信息12,并不能截取到真实信息
  2. 算法规律是彼此都知道的,就算算法泄露出去了,根据离散对数中的原根概念,已知3^n mod 17=12,想求出n也绝非易事

其实迪费赫尔曼当时的目的只是为了在密钥交换的时候更加安全,而之后RSA三兄弟站了出来

四、RSA的诞生

迪费赫尔曼已经成功将m^{ed} mod n ≡ n拆分成m^{e} mod n= cc^{d} mod n = n,只是没有提出这一理念

  1. RSA算法 加密算法:m^{e} mod n= c 解密算法:c^{d} mod n = n 其中m是明文,c是密文,n和e是公钥,n和d是私钥 **条件:**① m < n;② d是e对于φ(n)的模反元素
  2. RSA说明
    1. n会非常大,长度一般为1024位
    2. 由于需要求出φ(n),所以根据欧函数特点,最简单的方式n由两个质数相乘得到: 质数p1、p2
    3. 最终由φ(n)得到e 和 d,总共生成6个数字:p1、p2、n、φ(n)、e、d
    4. 除了公钥用到的n和e,其余4个数字是不公开的
  3. RSA的安全性
    1. 想要po解RSA得到d,由于e * d = φ(n) * k + 1,就要先知道e和φ(n)
    2. 要得到φ(n)必须知道质数p1、p2
    3. 由于n = p1 * p2,只有将n因数分解才能算出
  4. RSA的特点
    1. 相对安全
    2. 加密效率低
    3. 加密数据小(一般用来加密Hash值做对称加密)

五、RSA终端使用

  1. 生成私钥 openssl genrsa -out private.pem 1024
  2. 私钥中提取公钥 openssl rsa -in private.pem -pubout -out public.pem
  3. 查看公钥 cat public.pem
  4. 将私钥转成文本文件 openssl rsa -in private.pem -text -out private.txt
  5. 用公钥加密 openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
  6. 用私钥解密 openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
  7. 用私钥签名 openssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin
  8. 用公钥验证 openssl rsautl -verify -in enc.bin -inkey public.pem -pubin -out dec.txt
  9. 查看二进制文件 xxd enc.bin

六、证书生成

  1. 生成请求证书文件,需要填写国家、省市、组织名 钥匙串也可以从证书颁发机构请求证书 openssl req -new -key private.pem -out rsacert.csr
  2. 证书签名 openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt
  3. 生成公钥 openssl x509 -outform der -in rsacert.crt -out rsacert.der
  4. 生成私钥 openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt

七、Base64编码

base64可以将任意的二进制数据进行编码,编码成为由65个字符组成的文本文件,是二进制数据的一种表现 base64编码是由(A-Z,a-z,0-9,+ / =)组成的,最少为24个字符位,从左至右6个为一组,不足6个则补零,用等号来填补最后的空白 如A的二进制是01000001,补到24位是010000 010000 000000 000000,转换成base64码就是QQ==

  1. 终端编码 base64 xxx.jpeg -o xxx.text
  2. 终端解码 base64 xxx.text -o xxx.jpeg -D
  3. 代码编码
// 对一个字符编码
- (NSString *)base64Endcode:(NSString *)str {
	NSData *data = [str dataUsingEncoding:NSUTF8StringEncoding];
	return [data base64EncodedStringWithOptions:0];
}
复制代码
  1. 代码解码
// 对一个编码解密
- (NSString *)base64Decode:(NSString *)str {
	NSData *data = [[NSData alloc] initWithBase64EncodedString:str options:0];
	return [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding];
}
复制代码

写在后面

掌握RSA和相关编码知识有助于逆向的学习,很多地方都会用到这块知识