iOS-逆向07-密码学 iOS-逆向07-密码学

《iOS底层原理文章汇总》

1.RSA加密 I.密码学发展
A.离散对数问题

文章图片
image 3为质数17的原根，若质数17很大，则想要破解会很难，只有不断的试错
B.欧拉函数

文章图片
图片.png 关于互质关系
如果两个正整数，除了1以外，没有其他公因数，
我们就称这两个数是互质关系（coprime）。注意:两个相等的数之间不构成互质关系
欧拉函数特点
一、当n是质数的时候，φ(n)=n-1。
二、如果n可以分解成两个互质的整数之积，如n=AB则：
φ(AB)=φ(A)* φ(B)
根据以上两点得到：
如果N是两个质数P1 和 P2的乘积则
φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示
如:
计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8
φ(8) = 4
计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7
φ(7) = 6
计算56的欧拉函数
φ(56) = φ(8) * φ(7) = 4 * 6 = 24
C.欧拉定理

如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。

D.费马小定理

欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。

文章图片
image E.公式转换

文章图片
图片.png 第一步到第二步存在一个定理
m**φ(n)% n = 1 ==> x = 1
==> x ** k = 1 ** k
存在一个定理:x ** k = m ** (φ(n)k)%n
即m ** (φ(n)k)%n = 1
试算
M = 4
n = 15
φ(n) = 24 = 8
E = 3 和φ(n)互质
D: 3d - 1 = φ(n) * k = 8k == > 3*d = 8k + 1
D:11,19