博客> iOS逆向(1)-密码学(RSA)
iOS逆向(1)-密码学(RSA)
2019-07-17 07:37 评论:0 阅读:257 三吉i

原文地址请点击

各大厂面试题,iOS技术专栏

要讲逆向,那么肯定少不了密码学,因为所有的逆向(攻防)都是对已加密的数据进行解密。所以我们必须初步了解加密的方式有哪些,毕竟知己知彼,才能百战百胜。

接下来,我将从以下四方面来讲述密码学相关的内容: 1、什么是密码学 2、RSA数学原理 3、RSA终端命令 4、总结

1、什么是密码学

密码学的历史大致可以追溯到两千年前,相传古罗马名将凯撒大帝为了防止敌方截获情报,用密码传送情报。凯撒的做法很简单,就是对二十几个罗马字母建立一张对应表。这样,如果不知道密码本,即使截获一段信息也看不懂。

从凯撒大帝时代到上世纪70年代这段很长的时间里,密码学的发展非常的缓慢,因为设计者基本上靠经验。没有运用数学原理。

在1976年以前,所有的加密方法都是同一种模式:加密、解密使用同一种算法。在交互数据的时候,彼此通信的双方就必须将规则告诉对方,否则没法解密。那么加密和解密的规则(简称密钥),它保护就显得尤其重 要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法(symmetric encryption algorithm)。

1976年,两位美国计算机学家 迪菲(W.Diffie)、赫尔曼( M.Hellman ) 提出了一种崭新构思,可以在不直接传递密钥的情况下,完成密钥交换。这被称为“迪菲赫尔曼密钥交换”算法。开创了密码学研究的新方向。

1977年三位麻省理工学院的数学家 罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起设计了一种算法,可以实现非对称加密。这个算法用他们三个人的名字命名,叫做RSA算法。

也就是说「迪菲赫尔曼密钥交换」在密码学历史的车轮中成为了一个转折点。

2、RSA数学原理

咱们这里先把所有需要用到的公式定理列出来: 1、取模运算 2、欧拉函数φ 3、欧拉定理,费马小定理 4、模反元素 5、迪菲赫尔曼密钥交换

1、取模运算

取模运算(“Modulo Operation”)和取余运算(“Complementation ”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。 在这列出各种负数情况的例子供大家理解: 7 mod 4 = 3(商 = 1 或 2,1<2 xss=removed xss=removed xss=removed mod(负,正)=正 mod(正,负)=负 xss=removed xss=removed link.juejin.im?target=https://zh.wikipedia.org/wiki/原根)?)。> 3^(13 15) mod 17 = 3^(13 15) mod 17 根据模幂运算 ((m^e mod n)^d) mod n = m^(e*d) mod n ==> (3^13 mod 17)^13 mod 17 = (3^15 mod 17)^15 mod 17 由于 3^13 mod 17 = 12
3^15 mod 17 = 6 ==> 6^13 mod 17 = 12^15 mod 17 = 10 复制代码

m=3 ,e=13 ,d=15 ,n=17 ,C=12 复制代码


那么:

m^e mod n = c c^d mod n = (m^e mod n)^d mod n = m^(e*d) mod n 复制代码


又由于上面模反元素 最后得出

m^(e*d) mod n = m 复制代码


所以得出最终结论:

m^e mod n = c c^d mod n = m 复制代码


这个公式也就是我们最后的RSA加密公式!!! 其中:

公钥: n和e 私钥: n和d 明文: m 密文: c d是e对于φ(n)的“模反元素”。 复制代码


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

关于RSA的安全:
除了公钥用到了n和e 其余的4个数字是不公开的。
目前破解RSA得到d的方式如下:
1、要想求出私钥 d 。由于e*d = φ(n)*k + 1。要知道e和φ(n)。
2、e是知道的,但是要得到 φ(n),必须知道p1 和 p2。
3、由于 n=p1*p2。只有将n因数分解才能算出。

## 3、RSA终端命令

由于Mac系统内置OpenSSL(开源加密库),所以我们可以直接在终端上使用命令来玩RSA. OpenSSL中RSA算法常用指令主要有三个:

| 命令 | 含义 |
| --- | --- |
| genrsa | 生成并且输出一串RSA私钥 |
| rsautl | 使用RSA密钥进行加密、解密、签名和验证等运算 |
| rsa | 处理RSA密钥的格式转换等问题 |

#### 1、生成RSA私钥,密钥长度为1024bit

// 生成RSA私钥,密钥长度为1024bit openssl genrsa -out private.pem 1024 复制代码


![image.png](https://upload-images.jianshu.io/upload_images/16555213-386a1aa5e8194b07.png?imageMogr2/auto-orient/strip|imageView2/2/w/1240)

#### 2、从私钥中提取公钥

// 从私钥中提取公钥 openssl rsa -in private.pem -pubout -out public.pem 复制代码


![image.png](https://upload-images.jianshu.io/upload_images/16555213-02a5e418e23171a2.png?imageMogr2/auto-orient/strip|imageView2/2/w/1240)

#### 3、将私钥转换成为明文

// 将私钥转换成为明文 openssl rsa -in private.pem -text -out private.txt cat private.txt 复制代码


![image.png](https://upload-images.jianshu.io/upload_images/16555213-486d64779f5a101e.png?imageMogr2/auto-orient/strip|imageView2/2/w/1240)

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

// 新建一个文件,在文件中随意输入内容,比如输入字符串”Hello“ vim 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 // 查看加密后的文件 cat enc.txt
// 查看解密后的文件 cat dec.txt
复制代码


![image.png](https://upload-images.jianshu.io/upload_images/16555213-8a1a58afcb5f7e7d.png?imageMogr2/auto-orient/strip|imageView2/2/w/1240)

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

// 私钥加密 openssl rsautl -sign -in message.txt -inkey private.pem -out enc_2.txt // 公钥加密 openssl rsautl -verify -in enc_2.txt -inkey public.pem -pubin -out dec_2.txt 复制代码

![image.png](https://upload-images.jianshu.io/upload_images/16555213-e0a50218f8609156.png?imageMogr2/auto-orient/strip|imageView2/2/w/1240)

## 4、总结:

1、由于RSA加密解密用的不是一套数据,所以其保证了安全性。
2、由于私钥过大,所以效率较低
3、如果有一天量子计算机被普及(计算速度极快),那么1024位已经不足以让RSA安全。
从凯撒大帝时代到上世纪70年代这段很长的时间里,密码学的发展非常的缓慢,因为设计者基本上靠经验。没有运用数学原理。

在1976年以前,所有的加密方法都是同一种模式:加密、解密使用同一种算法。在交互数据的时候,彼此通信的双方就必须将规则告诉对方,否则没法解密。那么加密和解密的规则(简称密钥),它保护就显得尤其重 要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法(symmetric encryption algorithm)。

1976年,两位美国计算机学家 迪菲(W.Diffie)、赫尔曼( M.Hellman ) 提出了一种崭新构思,可以在不直接传递密钥的情况下,完成密钥交换。这被称为“迪菲赫尔曼密钥交换”算法。开创了密码学研究的新方向。

1977年三位麻省理工学院的数学家 罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起设计了一种算法,可以实现非对称加密。这个算法用他们三个人的名字命名,叫做RSA算法。

也就是说「迪菲赫尔曼密钥交换」在密码学历史的车轮中成为了一个转折点。

## 2、RSA数学原理

咱们这里先把所有需要用到的公式定理列出来:
1、取模运算
2、欧拉函数φ
3、欧拉定理,费马小定理
4、模反元素
5、迪菲赫尔曼密钥交换

#### 1、取模运算

取模运算(“Modulo Operation”)和取余运算(“Complementation ”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。
在这列出各种负数情况的例子供大家理解:
7 mod 4 = 3(商 = 1 或 2,1<2 xss=removed xss=removed xss=removed mod(负,正)=正 mod(正,负)=负 xss=removed xss=removed link.juejin.im?target=https://zh.wikipedia.org/wiki/原根)?)。> 3^(13 * 15) mod 17 = 3^(13 * 15) mod 17 
根据模幂运算 ((m^e mod n)^d) mod n = m^(e*d) mod n
==>  (3^13 mod 17)^13 mod 17 = (3^15 mod 17)^15 mod 17
由于   3^13 mod 17 = 12      
          3^15 mod 17 = 6
==>  6^13 mod 17 =  12^15 mod 17 = 10
复制代码

 m=3  ,e=13  ,d=15  ,n=17  ,C=12
复制代码

那么:

 m^e mod n = c
 c^d mod n = (m^e mod n)^d mod n = m^(e*d) mod n
复制代码

又由于上面模反元素 最后得出

 m^(e*d) mod n = m
复制代码

所以得出最终结论:

m^e mod n = c
c^d  mod n = m
复制代码

这个公式也就是我们最后的RSA加密公式!!! 其中:

公钥: n和e 
私钥: n和d
明文:    m
密文:    c
d是e对于φ(n)的“模反元素”。
复制代码

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

关于RSA的安全: 除了公钥用到了n和e 其余的4个数字是不公开的。 目前破解RSA得到d的方式如下: 1、要想求出私钥 d 。由于ed = φ(n)k + 1。要知道e和φ(n)。 2、e是知道的,但是要得到 φ(n),必须知道p1 和 p2。 3、由于 n=p1*p2。只有将n因数分解才能算出。

3、RSA终端命令

由于Mac系统内置OpenSSL(开源加密库),所以我们可以直接在终端上使用命令来玩RSA. OpenSSL中RSA算法常用指令主要有三个:

命令 含义
genrsa 生成并且输出一串RSA私钥
rsautl 使用RSA密钥进行加密、解密、签名和验证等运算
rsa 处理RSA密钥的格式转换等问题

1、生成RSA私钥,密钥长度为1024bit

// 生成RSA私钥,密钥长度为1024bit
openssl genrsa -out private.pem 1024
复制代码

image.png

2、从私钥中提取公钥

// 从私钥中提取公钥
openssl rsa -in private.pem -pubout -out public.pem
复制代码

image.png

3、将私钥转换成为明文

// 将私钥转换成为明文
openssl rsa -in private.pem -text -out private.txt
cat private.txt
复制代码

image.png

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

// 新建一个文件,在文件中随意输入内容,比如输入字符串”Hello“
vim 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
// 查看加密后的文件
cat enc.txt  
// 查看解密后的文件
cat dec.txt  
复制代码

image.png

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

// 私钥加密
openssl rsautl -sign -in message.txt -inkey private.pem -out enc_2.txt
// 公钥加密
openssl rsautl -verify -in enc_2.txt -inkey public.pem -pubin -out dec_2.txt
复制代码

image.png

4、总结:

1、由于RSA加密解密用的不是一套数据,所以其保证了安全性。 2、由于私钥过大,所以效率较低 3、如果有一天量子计算机被普及(计算速度极快),那么1024位已经不足以让RSA安全。

收藏
0
sina weixin mail 回到顶部