首页 / 算法 / #Python&密码学中的简单算法
#Python&密码学中的简单算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了#Python&密码学中的简单算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9196字，纯文字阅读大概需要14分钟。
内容图文
目录
密码学编程应用
\quad 本篇主要记录使用Python实现的几个密码学学习中用到的简单的算法，随着学习过程将不断更新和补充。代码和文章中的问题欢迎批评指正。
欧几里得算法
- 即辗转相除，用于求最大公因子。递归和迭代都很简单,直接上代码:
递归版本
def gcd(a,b):
if a<b:
a,b = b,a
if a%b==0:
return b
return (b,a%b)
迭代版本
def gcd(a, b):
while a != 0:
a, b = b % a, a
return b
\quad 注意 : :\quad :在这个迭代版本中b是被除数,a是除数,且无需满足a<b,(如果a>b,则第一步会将两者交换)
扩展欧几里得算法
-
扩展欧几里得算法可以求出两数最大公因子的线性表示.常用于求模逆.(模逆: a ? a ? 1 ≡ 1 ( m o d p ) \quad a\cdot a^{-1}\equiv1(mod p)\quad a?a?1≡1(modp)称 a ? 1 a^{-1} a?1为a的逆元)
-
原理如下:
( a , p ) = 1 (a,p)=1 (a,p)=1,即a,p互素,则1可以写成 x ? a + y ? p = 1 x\cdot a+y\cdot p=1 x?a+y?p=1根据扩展欧几里得算法可以求出x,y;显然,x即为a的逆元.根据上述思想,我们只需要求x,即写函数求a,p线性表示1的系数.
-
代码实现:
迭代版本
def findModInverse(a, m): #扩展欧几里得求逆元
if(gcd(a,m)!=1):
return None
u1,u2,u3=1,0,a
v1,v2,v3=0,1,m
while v3!=1:#每次相减都把数值大的赋给u3,因此一定是v3先为1
q = u3//v3
u1,u2,u3,v1,v2,v3 = v1,v2,v3,(u1-q*v1),(u2-q*v2),(u3-q*v3)
return v1%m
递归版本
def exgcd(a,b):#仅适用于a,b互素的情况
if a%b ==1:
return 1,-(a//b)
x,y = exgcd(b,a%b)
return y,x-(a//b)*y
对于两数不互素的情况，求两数线性表示最大公因子的系数：
def Exgcd(a, b):
if (b == 0):
return 1, 0, a
x, y, gcd = Exgcd(b, a % b)
return y, x-a//b*y, gcd
穷举素性检测&埃拉托色尼筛
- 这个是真没什么好说的,穷举 [ 2 , ? n ? ] [2,\lfloor \sqrt n\rfloor] [2,?n ??]即可,直接上代码:
def isPrime(num):
if num < 2:
return False
for i in range(2, int(math.sqrt(num)) +1):
if num % i == 0:
return False
return True
-
埃拉托色尼筛法:
一个数如果不能被小于等于他开根后的所有数整除，则是素数
def is_prime_Eratsn(num):
lis=list(range(3,num+2,2))
res = []
while True:
res.append(lis[0])
lis = list(filter(lambda x: x%lis[0]!=0,lis))#删素数的倍数
if(len(lis)==0):
break
if num in lis:
return False
else:
return True
Miller_Rabin素性检测
-
主要用到费马小定理和二次探测定理.下图为两个定理的简单证明.
图片引自他人博客,链接附上: \quad 图片来源
- 费马定理只是n是素数的必要条件。即费马定理不成立，n一定是合数；费马定理成立，n可能是素数。
def Miller_Rabin(n):
if (n == 2):
return True
if (n < 2 or n & 1 == 0):
return False
m = n - 1
k = 0
while (m & 1 == 0): #n-1=(2^k)*m
k += 1
m >>= 1
for i in range(0, 10): #测试10次
a = random.randint(1,n-1) #随机取a
x = pow(a, m, n) #求a^m(modn)
for j in range(0, k):
if x==1 or x == n-1:#考察a^m(modn)…… a^{2^{k-1}*m} (modn)
#若同余1 or 同余 n-1，通过本轮测试
break
x = x*x%n
else:
return False
return True
P o l l a r d ′ s Pollard's Pollard′s ρ \rho ρ 分解大数
-
分解大数是密码学中的困难问题，RSA的安全性就依赖于分解大数的困难性。 P o l l a r d ′ s Pollard's Pollard′s ρ \rho ρ是运用概率的思想分解
较小的大数 -
该方法的基本思想如下:
\quad 假设 N N N是某个需要分解的数, p p p是其质因子,并且假设 p p p相对于 N N N是一个较小的数。
\quad x 0 x_0 x0?是 Z / n Z Z/nZ Z/nZ上的一个随机整数。例如 x 0 = 2 x_0 = 2 x0?=2。
f ( x ) ∈ Z ? x ? f(x)\in Z\lfloor x\rfloor f(x)∈Z?x?是多项式。一般是使用 f ( x ) = x 2 + 1 f(x)=x^2+1 f(x)=x2+1或 f ( x ) = x 2 ? 1 f(x)=x^{2}-1 f(x)=x2?1。
根据多项式构造伪拟随机序列 { x 0 , x 1 , x 2 , ? x i } \{x_0,x_1,x_2,\cdots x_i\} {x0?,x1?,x2?,?xi?}，
\quad 其中 x i + 1 = f ( x i ) ( m o d N ) x_{i+1}=f(x_i)\pmod{N} xi+1?=f(xi?)(modN)。如果 x i ≡ x j ( m o d P ) x_i\equiv x_j\pmod{P} xi?≡xj?(modP),
而根据序列的定义,这两个数模 N N N不相等，即 x i ≠ x j ( m o d N ) x_i \neq x_j\pmod{N} xi??=xj?(modN),这样 g = gcd ? ( a b s ( x i ? x j ) , N ) g=\gcd(abs(x_i - x_j),N) g=gcd(abs(xi??xj?),N)就是N的非平凡因子。\quad 因此，该算法的实质就是要找到拟随机序列中两个模 p p p同余的数。
\quad 虽然事先并不知道 p p p，因此无法直接判断 x i ≡ x j ( m o d N ) x_i\equiv x_j\pmod{N} xi?≡xj?(modN)是否成立,但是可以通过计算 g = gcd ? ( a b s ( x i ? x j ) , N ) g=\gcd(abs(x_i - x_j),N) g=gcd(abs(xi??xj?),N)，并判断 1 < g < N 1<g<N 1<g<N是否成立来间接知道这一点。 -
将p按照算术定理形式分解( p = q 1 e 1 ? q 2 e 2 ? q 3 e 3 ? ? q i e i p = q_1^{e_1}\cdot q_2^{e_2}\cdot q_3^{e_3}\cdots \cdots q_{i}^{e_{i}} p=q1e1???q2e2???q3e3????qiei??)用到前置算法 M i l l e r _ R a b i n Miller\_Rabin Miller_Rabin素性检测和 g c d gcd gcd等,代码如下:
import random
def p_rho(n):
x = random.randint(1,n-1)
y = x
temp = 2
i = 0
c = 1
while(True):
i+=1
x = (x*x+c)%n
d = gcd(abs(x-y),n)
if n>d>1:
return d
if x == y:
c+=1
if i == temp:
y = x
temp <<= 1
#print('i,temp:',i,temp)
def fac(n):
if Miller_Rabin(n):
return "素数"
ans = {}#素分解字典
while(not Miller_Rabin(n)):
x = p_rho(n)
while not Miller_Rabin(x):#如果是合数，继续分解
x = p_rho(x)
ans[x] = 1 if (x not in ans) else ans[x]+1
n //= x
ans[n] = 1 if (n not in ans) else ans[n]+1
#print(ans)
res = []
for i in ans.items():
res.append(i[0]**i[1])
return res
B S G S BSGS BSGS求解离散对数
-
B a b y _ s t e p _ G i a n t _ s t e p a l g o r i t h m Baby\_step\_Giant\_step\quad algorithm Baby_step_Giant_stepalgorithm，简称BSGS，是在较小范围内求解离散对数问题的一种方法。什么是离散对数问题？… …
-
有限域上的离散对数问题简而言之就是
g x ≡ t ( m o d p ) g^x \equiv t \pmod{p} gx≡t(modp)
给定p, t, g,其中p为素数，g为模p的原根.求解x，x满足 g x ≡ t ( m o d p ) g^x \equiv t \pmod{p} gx≡t(modp) 。 -
因为g是原根，因此x的取值范围在 [ 1 , p ? 1 ] [1,p-1] [1,p?1]，暴力破解的话就是遍历这个范围，每次计算 g x i m o d ?? p g^{x_i}\mod{p} gxi?modp看看是否等于t即可。
-
BSGS的思想是空间换时间，具体流程如下：
- 设 x = k ? s ? r x = k\cdot s-r x=k?s?r 其中 r = ? p ? r=\lceil \sqrt p \rceil r=?p ??, r r r取值范围为 [ 0 , s ) [0,s) [0,s)，则有：
g x ≡ t ( m o d p ) ? g k ? s ? r ≡ t ( m o d p ) ? g k ? s ≡ g r ? t ( m o d p ) g^x \equiv t \pmod{p} \Longleftrightarrow g^{k\cdot s-r} \equiv t \pmod{p} \Longleftrightarrow g^{k\cdot s} \equiv g^{r}\cdot t \pmod{p} gx≡t(modp)?gk?s?r≡t(modp)?gk?s≡gr?t(modp)
-
首先令 r r r遍历 [ 0 , s ) [0,s) [0,s),并将对应结果,即 g r ? t ( m o d p ) g^{r}\cdot t \pmod{p} gr?t(modp)存到一张哈希表中(方便后续查找)
-
再令 k k k遍历 [ 1 , s ] [1,s] [1,s],并每次将结果,即 g k ? s ? r ≡ t ( m o d p ) g^{k\cdot s-r} \equiv t \pmod{p} gk?s?r≡t(modp) 在哈希表中查找,找到 k i k_{i} ki?, r i r_{i} ri? 使得 g k i ? s ≡ g r i ? t ( m o d p ) g^{k_{i}\cdot s} \equiv g^{r_{i}}\cdot t \pmod{p} gki??s≡gri??t(modp)
-
这样就得到了结果: \quad x = k ? s ? r x=k\cdot s-r x=k?s?r,
- 所谓 G i a n t _ s t e p Giant\_step Giant_step和 B a b y _ s t e p Baby\_step Baby_step分别指同余式左右两边的遍历过程,即左边每次乘 g g g,右边每次乘 g s g^{s} gs。由于查表的时间复杂度为 O ( 1 ) O(1) O(1),因此实际上该算法可以将时间复杂度降到 p \sqrt p p ?,代价是存储空间开销增加。显然，当p很大的时候，这种方法也无法求解。
import math as ma
def bsgs(a,b,range_,p):
s = ma.ceil(ma.sqrt(range_))
m = {}
g_step = pow(a,s,p)
#设x= ks - r
#遍历r,m中存储b*a^r，r取值范围为[1,range_]
tem = b
for r in range(s):
m[tem] = r
tem =tem * a % p
tem = 1
for k in range(1,s+1):
tem =tem * g_step % p#tem = a^{ks} (mod p)
if tem in m.keys():#若存在a^{ks}≡b*a^r (mod p)，则返回 ks-r
return (k*s - m[tem])
return False
P h o l i g _ H e l l m a n Pholig\_Hellman Pholig_Hellman 算法
-
该方法同样是解决离散对数问题的。上面提到BSGS在p很大的时候也是没法直接用的，不过可以结合这个 P h o l i g _ H e l l m a n Pholig\_Hellman Pholig_Hellman 算法使用。
-
该算法的基本思想如下：
对于 g x ≡ t ( m o d p ) g^x \equiv t \pmod{p} gx≡t(modp)， φ ( p ) \varphi (p) φ(p)（即p-1） 为模 p p p循环群的阶. x x x为
φ ( p ) \varphi (p) φ(p)的一个剩余系.直接求解 x x x 困难,那如果我们能先求出 x x x在模 φ ( p ) \varphi (p) φ(p)因子的群中的代表元,再用孙子定理合并成模 φ ( p ) \varphi (p) φ(p)意义下的x,我们就可以得到结果了。这就要求我们首先要分解 p ? 1 p-1 p?1,根据算数定理, p ? 1 p-1 p?1有唯一分解形式:
p ? 1 = q 1 e 1 ? q 2 e 2 ? q 3 e 3 ? ? q i e i p-1 = q_1^{e_1}\cdot q_2^{e_2}\cdot q_3^{e_3}\cdots \cdots q_{i}^{e_{i}} p?1=q1e1???q2e2???q3e3????qiei??
至于分解方式可以使用前面提到的 P o l l a r d ′ s Pollard's Pollard′s ρ \rho ρ a l g o r i t h m algorithm algorithm -
算法基本流程如下：
该方法的基本流程如下:
-
分解 φ ( p ) = q 1 e 1 ? q 2 e 2 ? q 3 e 3 ? ? q i e i \varphi (p) = q_1^{e_1}\cdot q_2^{e_2}\cdot q_3^{e_3}\cdots \cdots q_{i}^{e_{i}} φ(p)=q1e1???q2e2???q3e3????qiei??
-
利用每一项因子,即 q i e i q_{i}^{e_{i}} qiei??,求解 g φ ( p ) / q i e i g^{\varphi(p) / {q_i}^{e_i}} gφ(p)/qi?ei?和 t φ ( p ) / q i e i t^{\varphi(p) / {q_i}^{e_i}} tφ(p)/qi?ei?
-
求解 x i x_i xi?对于 x i x_i xi?有 ( g φ ( p ) / q i e i ) x i ≡ t φ ( p ) / q i e i ( m o d p ) (g^{\varphi(p) / {q_i}^{e_i}})^{x_{i}}\equiv t^{\varphi(p) / {q_i}^{e_i}} \pmod {p} (gφ(p)/qi?ei?)xi?≡tφ(p)/qi?ei?(modp)，这一步求解可以用BSGS
-
得到方程组
{ x ≡ x 1 ( m o d q 1 e 1 ) x ≡ x 2 ( m o d q 2 e 2 ) x ≡ x 2 ( m o d q 3 e 3 ) ? x ≡ x i ( m o d q i e i ) \left\{ \begin{array}{lr} x\equiv x_1 \pmod{{q_1}^{e_1}} & \\ x\equiv x_2 \pmod{{q_2}^{e_2}} & \\ x\equiv x_2 \pmod{{q_3}^{e_3}} & \\ \cdots &\\ x\equiv x_i \pmod{{q_i}^{e_i}} & \\ \end{array} \right. ????????????x≡x1?(modq1?e1?)x≡x2?(modq2?e2?)x≡x2?(modq3?e3?)?x≡xi?(modqi?ei?)??
使用孙子定理（CRT）求解即得结果
-
该算法的关键在于把 m o d φ ( p ) mod \varphi (p) modφ(p)的问题转化成了若干子问题求解，难度也随之降低.我们再来回顾这种分解是怎样做到的:
且看算法流程中第2步和第3步:
g x ≡ t ( m o d p ) g^x \equiv t \pmod{p} gx≡t(modp)被转化为子问题 ( g φ ( p ) / q i e i ) x i ≡ t φ ( p ) / q i e i ( m o d p ) (g^{\varphi(p) / {q_i}^{e_i}})^{x_{i}}\equiv t^{\varphi(p) / {q_i}^{e_i}} \pmod {p} (gφ(p)/qi?ei?)xi?≡tφ(p)/qi?ei?(modp)
可以看到求解 x i x_{i} xi?同样是求解对数问题,但是由于底数变为 g φ ( p ) / q i e i g^{\varphi(p) / {q_i}^{e_i}} gφ(p)/qi?ei?，因此这不再是一个在阶为 φ ( p ) \varphi (p) φ(p)的循环群上的求解问题，而是一个在阶为 q i e i {q_i}^{e_i} qi?ei?的循环群上的求解问题。而 q i e i {q_i}^{e_i} qi?ei?是 φ ( p ) \varphi (p) φ(p)的因子，显然求解更为容易。 -
代码如下：
def pholig_hellman(g,t,p):
lis = fac(p-1)
a = [pow(g,(p-1)//i,p) for i in lis]
b = [pow(t,(p-1)//i,p) for i in lis]
res = {}.fromkeys(lis,0)
cnt = 0
x = 0
for i in lis:
x = bsgs(a[cnt],b[cnt],i,p)
cnt+=1
res[i] = x
return CRT(res)
未完待续……
内容总结
以上是互联网集市为您收集整理的#Python&密码学中的简单算法全部内容，希望文章能够帮你解决#Python&密码学中的简单算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。