密码学-费马小定理在RSA中的应用1

• 费马小定理

• 二项式定理式

• 同余和同余的一些应用

• 同余在RSA中的应用

• 相关例题

• 费马小定理–1

• 费马小定理–2

费马小定理

若 为素数，，则 。

另一个形式：对于任意整数 ，有 。

二项式定理式

二项式定理阐明了一个展开式的系数：

展开得到

同余和同余的一些应用

两个整数a和b，a-b能被整数m整除，则a与b余m相等。即:。

推理得:

• 。

• c为余数

• c为余数

等价条件1:

可得

证明:

如果，则，即，即能被n整除，因此a与b模n同余。

等价条件2:

可得 或者

证明:

如果，且，则能被n整除，即，即，即。

如果，且，则能被n整除，即，即，即。

等价条件3:

可得

证明:

a与b模n同余，互换位置不影响。

同余在RSA中的应用

pow函数

在python中，一般使用pow函数。

a = pow(c, d, n)

即:

推理得:

• 此时k>0
• 此时k<0

相关例题

费马小定理–1

一、题目

from Crypto.Util.number import *
from secret import flag
flag = bytes_to_long(flag)

p = getPrime(1024)
q = p+1
assert flag**2 < p
a = pow(flag+p, q, p)

print('p=',p) 
print('a=',a)

'''
p= 132485702522161146757217734716447479208806639208543182360084149642567339473293168036770464973129405874692085101982109256055320486303869520189058357502693388509190430447787056423080714947904812339604787610679547711291646116182650401371922642011766279740399192613052280061981102203595808184804858315094410004923
q=132485702522161146757217734716447479208806639208543182360084149642567339473293168036770464973129405874692085101982109256055320486303869520189058357502693388509190430447787056423080714947904812339604787610679547711291646116182650401371922642011766279740399192613052280061981102203595808184804858315094410004924
a= 1718205151527213531940354061216609955728503626623437131525315244599535856595391286686273033612529023037466615611832668265075325829196053041494716601943531710744433426780718569225
'''

二、解析

三、思路

• 费马小定理

• 对第一个式子进行变形得:

• =>

• =>

• =>

  =>

• 根据二项式展开定理:

• 根据模运算法则:

• 根据 :

• 结合费马小定理:

四、解题

from Crypto.Util.number import long_to_bytes
from gmpy2 import gmpy2

a = 1718205151527213531940354061216609955728503626623437131525315244599535856595391286686273033612529023037466615611832668265075325829196053041494716601943531710744433426780718569225
print(long_to_bytes(gmpy2.iroot(a,2)[0]))

费马小定理–2

题目来源:风二西

1、题目

p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
hint = pow(2020 * p + 2021, q, n)
n=27020725261160598541077357737650775795182555998856810737571508044949928734067444441660366270392732456051807439301564552672200975582350577967001486740668193835704559129378410828266554536148151615878808327988333060924165410762016082268322936465413880236634083213834739549234631742766416876749808978934944262651307600621868854944164060642189749365967978497831698002669974744487926082412272998646851047638183126945784060957075393737537570645086672473571281053798891685646561828588448040073373363454584468753860529849749093081434144360661566815886630699933232263079413562069476421802192735693386029862725050469209845710383
c=10188807385387617708190575473905502994151677148079820873886980571555051900701810208218351138721306416600688313703084580808183634201231599134123549448962443376514560489130860694363901933597676373555599555647232128717993571185822894818704143675318690577221330618533739592165564396729937983659337232822442555504262694675199751730664450120569727835850996566436129543730932040989365233424791093843941154003052950306359994891955336607690065213304872738280674213630736611351982705373394299097653653497017756036211550125607093109216729483090391729134062236908282557149575812220142872855836932590459512028618076264332235518829
hint=15179972145975733285419381814235528011288991423484121653543845156913121513320504879647666067298415751234264897435338898933073713420024176276221164394369781676781604128149168834126855517212300158864797800121336042194751965268493010327202598446572764475343894613152062609436699715193914479572113800212525965140106015838636914979735618606768207651697548364440806425770871133439416876157686985836939255598747973339866125864303982956813846287509191028829738926404992619459242904729015823730553526572575372668559669124599614613391797015393641171177282129497503752370800088634017972208535899870704612274473042064675033593148

2、分析

3、思路

•  ①

• 由等价条件1可知道，①等价于  ②

• 由等价条件3可知道，②等价于

• 由①得，由等价条件2得

• ③ (k为负数，因为(>hint)

• ④ (k为正数，因为(>hint)

• 根据二项式展开定理，两边同时余p，此时③等价于

• 由等价条件1可知 (k的正负数与hint和大小有关) 此时通过求kp和n的最大公约数即可求出p，进而分解n。但是很遗憾q未知。

接下来使用费马小定理

• 由等价条件1和费马小定理可知: 此时，，可得，由等价条件2得，。 即 等价于 ，进而由于n=pq，得

最终得到

• 即:，此时，此时即可通过求最大公因数分解n。

4、解题

import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
from gmpy2 import gcd
n=27020725261160598541077357737650775795182555998856810737571508044949928734067444441660366270392732456051807439301564552672200975582350577967001486740668193835704559129378410828266554536148151615878808327988333060924165410762016082268322936465413880236634083213834739549234631742766416876749808978934944262651307600621868854944164060642189749365967978497831698002669974744487926082412272998646851047638183126945784060957075393737537570645086672473571281053798891685646561828588448040073373363454584468753860529849749093081434144360661566815886630699933232263079413562069476421802192735693386029862725050469209845710383
c=10188807385387617708190575473905502994151677148079820873886980571555051900701810208218351138721306416600688313703084580808183634201231599134123549448962443376514560489130860694363901933597676373555599555647232128717993571185822894818704143675318690577221330618533739592165564396729937983659337232822442555504262694675199751730664450120569727835850996566436129543730932040989365233424791093843941154003052950306359994891955336607690065213304872738280674213630736611351982705373394299097653653497017756036211550125607093109216729483090391729134062236908282557149575812220142872855836932590459512028618076264332235518829
hint=15179972145975733285419381814235528011288991423484121653543845156913121513320504879647666067298415751234264897435338898933073713420024176276221164394369781676781604128149168834126855517212300158864797800121336042194751965268493010327202598446572764475343894613152062609436699715193914479572113800212525965140106015838636914979735618606768207651697548364440806425770871133439416876157686985836939255598747973339866125864303982956813846287509191028829738926404992619459242904729015823730553526572575372668559669124599614613391797015393641171177282129497503752370800088634017972208535899870704612274473042064675033593148
e = 65537
# 公约数求P
p = gcd(pow(2021,n,n)-hint, n)
phi = (p-1)*(n//p -1)
d = gmpy2.invert(e,phi)
print(long_to_bytes((pow(c,d,n))))