开发者社区> 5na6pyt44b2ti> 正文

iOS逆向 06:RSA加密(上)

简介: iOS逆向 06:RSA加密(上)
+关注继续查看

本文主要介绍RSA的数学原理、以及RSA的代码演示


引子


密码学


是指研究信息加密、破解密码的技术科学。最早可以追溯到追溯到2000年前。而当今的密码学是以数学为基础的。


密码学发展史


  • 在1976年以前,所有的加密方法都是同一种模式:加密、解密使用同一种算法。在交互数据的时候,彼此通信的双方就必须将规则告诉对方,否则没法解密。那么加密和解密的规则(简称密钥),它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法(symmetric encryption algorithm)
  • 1976年,两位美国计算机学家 迪菲(W.Diffie)、赫尔曼( M.Hellman ) 提出了一种崭新构思,可以在不直接传递密钥的情况下,完成密钥交换。这被称为“迪菲赫尔曼密钥交换”算法。开创了密码学研究的新方向


RSA数学原理


上世纪70年代产生的一种加密算法。其加密方式比较特殊,需要两个密钥:公开密钥简称公钥(publickey)和私有密钥简称私钥(privatekey)。公钥加密,私钥解密;私钥加密,公钥解密。这个加密算法被称为的RSA


离散对数问题


现在想实现这一种 加密容易,但是破解很难的加密算法,利用数学运算,如mod取模,有如下方案:


  • 质数做模数,例如17
  • 找一个比17小的数作为n次方的基数,例如3
  • 找出基数的n次方 mod 质数 = 固定的数,求n


3^? mod 17 = 12,此时的`?`是多少呢?(mod -> 求余数,在西方被称为时钟算数)

从下方的规律中可以看出,3的1次方~16次方 mod 17 得到的结果都是不同的,且结果分布在 [1,17)上。此时将 3 称为 17 的原根

image.png

所以根据图中所示,? 可能是13,可能是29等。即从这里可以看出:通过 12 去反推3的?次方是很难的。如果质数加大,反推的难度也会加大。


质数:公约数只有1和自己,其中2是一个特殊质数


欧拉函数φ(读 fai)


定义


任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?计算这个值的方式就叫做欧拉函数,使用Φ(n)表示


互质关系


如果两个正数,除了1以外,没有其他公因数,就称这两个数是互质关系(comprime)


欧拉函数特点


  • 1、当n是质数时,Φ(n) = n - 1
  • 2、如果n可以分解成两个互质的整数之积,例如 n = A * B,则Φ(A * B) = Φ(A) * Φ(B)


所以,根据欧拉函数的以上两个特点,可以得到如下结论:

  • 如果N是两个互质数P1和P2乘积,则Φ(N) = Φ(P1 * P2) = Φ(P1) * Φ(P2) = (P1-1) * (P2-1)


练习


  • 计算8的欧拉函数:和8互质的有4个,即Φ(8) = 4( 1,2,3,4,5,6,7,8 - 1-8中有4个数和8互质)
  • 计算7的欧拉函数:和7互质的有6个,即Φ(7) = 6(12345,6,7 - 1-7中有6个数和7互质)
  • 计算56的欧拉函数:Φ(56) = Φ(7 * 8) = Φ(7) * Φ(8) = 6 * 4 = 24


欧拉定理


欧拉定理


如果两个正整数 m 和 n 互质,那么 m 的Φ(n)次方减去1,可以被n整除。即 (m^Φ(n) - 1) / n ≡ 0 ==> m^Φ(n) mod n ≡ 1


费马小定理(欧拉定理的特殊情况)


如果两个正整数 m 和 n 互质,而且 n 为质数,那么 Φ(n) 结果就是 n-1,即 m^(n-1) mod n = 1

  • 例如 m=6,n=5,那么 6^(5-1) mod 5 = 1


公式转换


前提:m和n互为质数,且n为质数,有公式m^Φ(n) mod n ≡ 1


  • 由于1^k ≡ 1 ==> m^k*Φ(n) mod n ≡ 1
    • 推导:将x = m^Φ(n) mod n 看作一个整体 ==> x^k = m^(Φ(n)*k) mod n(是一个定理) 成立
    • 例如:m=6,n=7,则6^(7-1) mod 7 = 1 ==> 6^(6*2) mod 7 = 1
  • 由于1*m ≡ m ==> m^(k*Φ(n)+1) mod n ≡ m(成立条件:m 要比 n小
    • 例如:m=6,n=7,则6^(6*3+1) mod 7 = m


模反元素


如果两个正整数 e 和 x 互质,那么一定就可以找到整数d,使得 ed - 1 被x整除(即 (ed - 1)/x = 1),那么 d 就是 e 对于 x模反元素


  • e * d mod x = 1
    • 理解: e * d - 1 = x * k ==> e * d ≡ k*x + 1
  • e * d ≡ k*x + 1 ===> m^(e*d) mod n = m(条件:d 是相对于 Φ(n) 的模反元素)
    • kx + 1 = kΦ(n)+1 ==> m^(e*d) mod n = m
    • 例如:


- m :4
- n :15
- Φ(n):8
- e:(和Φ(n)互质)3
- d:3d-1=8k ==> d=(8k+1)/3 ==> d=11 19
- 4**(3*11)%5 = 4
- 4**(3*19)%5 = 4


迪菲赫尔曼密钥交换


如下图所示,是一个典型的迪菲赫尔曼密钥交换过程


image.png

  • 1、服务端先取一个随机数15,通过 3^15 mod 17 = 6,将6传给客户端(第三方可以窃取这个6)
  • 2、客户端通用的取一个随机数13,通过3^13 mod 17 = 12,将12传给服务器(第三方同样可以窃取这个12)
  • 3、客户端拿到服务器传过来的6,通过6^13 mod 17 = 10,得到10
  • 4、服务端拿到客户端传过来的12,通过12^15 mod 17 = 10,得到10
  • 所以综上所述,服务端和客户端想交换的数字是 10


以下是迪菲赫尔曼密钥交换的原理,最终经过两次计算,客户端和服务端都会得到一个相同的数字,用于数据的传输

image.png

  • 客户端:3 ^ 15 mod 17 = 6 + 6^13 mod 17 = 10 ==> 3 ^ (15 * 13) mod 17 = 10
  • 服务端:3 ^ 13 mod 17 = 12 + 12^15 mod 17 = 10 ==> 3 ^ (13 * 15) mod 17 = 10


RSA的诞生


由上面的迪菲赫尔曼密钥交换原理可知,由以下三个公式


- 1、m^e mod n = C
- 2、C^d mod n = m^(e*d) mod n
- 3、m^(e*d) mod n = m

其中c^d mod n = m ,主要是源于 c^d mod n = m^(e*d)mod n = m ,且d 是 e 相对于 φ(n)的模反元素。需要注意的是:m 和 n 既为互质,也为原根,即m 是n的原根


RSA算法


所以最终RSA算法的加解密公式为:


  • 加密:m^e mod n = c
  • 解密:c^d mod n = m
  • 公钥:n和e
  • 私钥:n和d
  • 明文:m
  • 密文:c


其中涉及的公钥、私钥、密文、明文有如下说明


  • 1、n会非常大,长度一般为1024个二进制位(目前人类已经分解的最大整数,232个十进制位,768个二进制位)
  • 2、由于需要求出φ(n),所以根据欧拉函数特点,最简单的求解φ(n)方式:n由两个质数相乘得到 质数:p1、p2
    • Φ(n) = (p1 -1) * (p2 - 1)
  • 3、最终由 Φ(n) 得到 e 和 d
  • 所以综上所述,总共生成6个数字:p1、p2、n、Φ(n)、e、d


算法演示

m:取值 3 或 12
n:3*5(两个质数相乘)

- φ(n) = (3-1)*(5-1)= 8
- e:3(e和Φ(n)互质)
- d:3d-1=8k ==> d = 11 / 19(由公式 e * d mod x = 1 求解)
- 加密:`m^e mod n = c` ==> 3^3 mod 8 = 3
- 解密:`c^d mod n = m` ==> 3^11 mod 8 = 3

关于RSA的安全说明


除了公钥用到了ne,其余的4个数字是不公开的,目前破解RSA得到d的方式如下:


  • 1、要想求出私钥 d,由于 e*d = φ(n)*k + 1。要知道eφ(n)
  • 2、e是知道的,但是要得到 φ(n),必须知道p1 和 p2
  • 3、由于 n=p1*p2。只有将n因数分解才能算出。


RSA算法说明


  • RSA效率不高,因为是数学运算,且m不能大于n,大数据不适合用RSA加密,一般用对称加密(用key)
    • 交换key时,用RSA加密
    • 大数据传递,其中大数据用key(即对称算法)加密


RSA终端命令


由于Mac系统内置OpenSSL(开源加密库),所以在mac的终端可以直接使用OpenSSl玩RSA,OpenSSL中RSA算法常用命令有3个


image.png

终端演示


  • 1、生成RSA私钥,密钥成都为1024bit
    • 命令:openssl genrsa -out private.pem 1024
      image.png

查看 cat private.pem文件,其中是base64编码

image.png

2、从私钥中提取公钥(即 n和e)

  • 命令:openssl rsa -in private.pem -pubout -out public.pem

    image.png

查看公钥:cat public.pem

image.png

3、生成的文件如下

image.png

4、将私钥转换为明文


  • 命令:openssl rsa -in private.pem -text -out private.txt
    image.png

5、通过公钥加密数据,私钥解密数据

image.png

  • 生成明文文件: vi message.txt
  • 查看文件内容:cat message.txt
  • 通过公钥进行加密:openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
  • 通过私钥进行解密:openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
    生成的文件如下所示


image.png


  • 6、通过私钥加密数据,公钥解密数据


    • 通过私钥进行加密(签名): openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt
    • 通过公钥进行解密(验证):openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt


总结


  • 对称加密(传统加密算法):公钥、私钥采用同一个key
  • RSA非对称加密(现代加密算法):加解密原理来源迪菲赫尔曼密钥交换
    • 欧拉函数:如果N是两个互质数P1和P2乘积,则Φ(N) = Φ(P1 * P2) = Φ(P1) * Φ(P2) = (P1-1) * (P2-1)
    • 欧拉定理:如果两个正整数 m 和 n 互质,那么 m 的Φ(n)次方减去1,可以被n整除。即 (m^Φ(n) - 1) / n ≡ 0 ==> m^Φ(n) mod n ≡ 1
    • 费马小定理:如果两个正整数 m 和 n 互质,而且 n 为质数,那么 Φ(n) 结果就是 n-1,即 m^(n-1) mod n = 1
    • 迪菲赫尔曼密钥交换原理
      • m^e mod n = C
      • C^d mod n = m^(e*d) mod n
      • m^(e*d) mod n = m
  • RSA算法
    • RSA原理:拆解两个(大)质数的乘积很难,所以RSA相对安全
    • 加密:M ^ e % N = C
    • 解密:C ^ d % N = M
    • 密文(加密后的):C
    • 明文(解密后的):M
    • 公钥:N 和 E
    • 私钥:N 和 D
    • RSA成立条件(总共有6个数字):


      • N 是由两个很大的质数(P1、P2)相乘得到!为了方便求出φ(N)(其中φ(n) = (p1-1)*(p2-1)
      • DE (一般是65537,0x10001(从终端演示中得出)) 相对于φ(N)模反元素


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19735 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
29045 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22511 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
16384 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20665 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14895 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23575 0
166
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载