密码学-费马小定理在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))))


原文始发于微信公众号(不懂安全的果冻):密码学-费马小定理在RSA中的应用1

版权声明:admin 发表于 2022年11月9日 下午1:35。
转载请注明:密码学-费马小定理在RSA中的应用1 | CTF导航

相关文章

暂无评论

暂无评论...