密码学

密码学是指研究信息加密,破解密码的技术科学.密码学的起源可追溯到2000年前,如今的密码学是以数学为基础的.

发展历史

密码学的历史大致可以追溯到两千年前,相传古罗马将凯撒大帝为了防止敌方截获情报,用密码传送情报.凯撒的做法很简单,就是对二十个罗马字母建立一张对应报表.这样,如果不知道密码本,即使截获一段信息也看不懂.从凯撒大帝时代到上世纪70年代这段时间里,密码学发展的非常缓慢,因为设计者基本上靠经验.没有运用数学原理.
在1976年以前,所有的加密方法都是同一种模式:加密、解密使用同一种算法.在交互数据的时候,彼此通信的双方就必须将规则告诉对方,否则没法解密.那么加解密的规则(简称密钥),它保护就显得尤为重要.传递密钥就成为了最大的隐患.这种加密方式被称为对称加密算法.
1976年,两位美国计算机学家迪菲(W.Diffie)、赫尔曼(M.Hellman)提出了一种崭新构思,可以在不直接传递密钥的情况下,完成密钥交换.这被称为“迪菲赫尔曼密钥交换”算法.开创了密码学研究的新方向.
1977年三位麻省理工学院的数学家罗纳德·李威斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起设计了一种算法,可以实现非对称加码.这个算法用他们三个人的名字命名,叫做RSA算法.

RSA数学原理

质数:约数只有1和自己;

离散对数问题

例如 3^x % 17 = 12 ,3为17的原根, 才会有下图的规律;
3^17%17=3,318%17=9 ...

欧拉函数

概念补充 1、互质关系:如果两个正整数,除了1以外,没有其他公因数,我们就称这两个数是互质关系.
思考:任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?
计算这个值的方式叫做欧拉函数,使用𝞅(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
欧拉函数特点
1、当n是质数的时候,𝞅(n)=n-1.
2、如果n可以分解成两个互质的整数之积,如n=A*B,则:
𝞅(A * B) = 𝞅(A) * 𝞅(B)
根据N是两个互质P1和P2的乘积则:
𝞅(N) = 𝞅(P1) * 𝞅(P2) = (P1-1) * (P2-1)

欧拉定理

如果两个正整数m和n互质,那么m的𝞅(n)次方减1,可以被n整除.
m^𝞅(n) mod n = 1

费马小定理

欧拉定理的特殊情况: 如果两个正整数m和n互质,而且n为质数!那么𝞅(n)结果就是n-1.

公式转换

验证过程

m = 9
n = 35
𝞅(35) = 𝞅(5) * 𝞅(7) = 4 * 6 = 24
e = 5
e * d = k * x + 1
当 x = 𝞅(n)时
5 * d = 24 * k + 1
d = (24 * k + 1)/5
k = 6, d = 145/5 = 29
k = 11, d = 265/5 = 53
验证
m^ e*d%n = n