程序员

RSA的数学基础

2019-12-10  本文已影响0人  Wayne维基

概要

RSA是一种非对称加密算法,非常普遍,主要涉及的数学知识

互质

概念:两个正整数,除了1以外没有其他公因子(公约数)。
(补充:公因子同时能被两个数整数的整数,是这两个数的公因子,求最大公约数可以用辗转相除法
)

注意区分质数(素数prime)概念:质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

举例: 7和20,20是不是质数,但是和7是互质数。

互质相关结论:

欧拉函数

假设需要求解下面问题:
给定正整数n,小于等于n的所有正整数中,求解有多少个与n互质?
欧拉函数就能解这个问题。
(欧拉函数用希腊字母 \phi表示,棒棒糖造型的那个符号,但是这里打不出来,后续用O代替。)

结合前面互质所得到的相关结论。

【证明方式todo:剩余定理和拉格朗日定理】
理解这个公式的要领,这其实是一个概率公式,比如,x = 12,p1 = 2,p2 = 3,n = 2,第一个质因素p1 = 2,小于等于12的数字中,有多少和12有公约数p1呢,答案是有12 / p1 = 6个 。意思是,小于等于12的数字中,有 1/p1概率的数字和12不互质,那么有x*(1-1/p1)个数字与x互质。

欧拉定理

【定理】如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立(同余性质):


image

费马小定理

【定理】
a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p)

模反元素

【定义】如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1,b就叫做a的"模反元素"。

举例:
3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...},即如果b是a的模反元素,则 b+kn 都是a的模反元素

a的 φ(n)-1 次方,就是a的模反元素

扩展欧几里得算法

todo

RSA 生成公私钥过程

RSA 不可破解原因

1 已经知道了 n和e,可以破解d么?
ed = 1 ( mod O(n))
那么 ed = k* O(n) + 1。
d = ( k*O(n) + 1 )/ e

2 上面式子需要求O(n),可解就能破解d
O(n) = (p-1)(q-1), n = p*q
所以只要知道了p和q,就能知道O(n)

3 但是:大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。所以认为n足够大,当前的计算机算力,n = p*q分解不出来。
因此目前被破解的最长RSA密钥就是768位。

RSA加密解密有效性证明

注意:
1 m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。
2 公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种"对称性加密算法"(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

1 假设 m 和 n 互质,欧拉定理
m ^ O(n) = 1 (mod n)
所以
m^(kO(n)+1)%n = (m^(kO(n)) * m) % n(取模的乘法结合律)
=( ([mO(n)%n*....*mO(n)%n] %n%n...%n ) * (m %n ) ) %n
= (m % n ) %n
= m % n
= m
解密完成
2 假设m与n不互质
n = p * q,那么 m = h * p 或者 h * q
假设m = h * p,且 m和 q 一定 互质
所以:
m ^ (O(q)) = 1 (mod n)
m ^ (q-1) = 1 (mod n)
所以:
m ^ (q-1) = k * n + 1

前面得到了式子:
c ^ d % n = m^(k*O(n)+1)%n
= { m * [m ^ ((p-1)(q-1))] ^ k }%n (带入:m ^ (q-1) = k * n + 1)
= m * [kn + 1]^(k(q-1)) %n
= m%n (m小于n)
= n

上一篇 下一篇

猜你喜欢

热点阅读