欧拉函数（Euler's totient function），即 ，表示的是小于等于 和 互质的数的个数。比如说 。当 n 是质数的时候，显然有 。

• 如果有 ，那么 。

  特别地，当 是奇数时 。

• 若 ，其中 是质数，那么 。

RSA原理

1. 随机选择两个不同大质数 和 ，计算
2. 根据欧拉函数，求得
3. 选择一个小于 的整数 ，使 和 互质。并求得 关于 的模反元素，命名为 ，有
4. 将 和 的记录销毁

即是根据欧拉函数来求的。

欧拉函数的性质--strange RSA1

一、题目

from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import *
from secret import flag
m = bytes_to_long(flag)
p = getPrime(128)
q = getPrime(128)
n = p * q
e = 65537
c = pow(m,e,n)
print(n,c)
e = 65537
n = 62193160459999883112594854240161159254035770172137079047232757011759606702281
c = 17331436837911040930486942133359735652484926528331507431552667656734821231501

二、解析

• 题目给定e、n、c，按照正常思路求解明文即可。

• 在分解n的时候得到"多个"p、q

三、思路

• 分解n。

• 根据欧拉函数求解:

• 根据欧拉函数的性质:

五、解题

分解n

求密文

import gmpy2
from Crypto.Util.number import long_to_bytes
e= 0x10001
n = 564070152909085514893862673848191100242629745476416876533996976389897932324860687952230733393080567203972999049426141761
c = 269509453821913281608300827585653465889617103481995203776655691658799441157871331220899710463748827149644657719450056013
q = 709662686105519282917793669093
p = 1058314117179226194777612760717
phi=(p**2-p)*(q**2-q)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))

欧拉函数的性质--unsafe_prime2

一、题目

from Crypto.Util.number import *
from flag import flag
import libnum
p=getPrime(1024)
n=p**3
e=65537
c=pow(libnum.s2n(flag),e,n)
print(n)
print(c)
#1781066779141074297846071955037887396311182371062305797790413639302252321886055189043670187843106208315282055227397316083218930657040969292641990094428330517286511511741846106485971830443788363541411679523274683568732340113625424593194464460018629545968907529693143364870519531630721083893407011154181539445417439610805148961135948617691115328261432541033785402520757881586489819563221498111411690769065511011083021336493731421274742041131952523427183184133413677315203810963447656037908287875212013900845740870561508870574734100843624059414134156975073835607712519402938132401964708681236647568922173471703538744207491065165405594141287750705055447493380970194312139898574699147098202027540057477562090764694370368571887563631557761911842054442637038169316686266784299889397326811768646649462480349219937292894824766045607723468654723947999531346474969019631500665628522355198334827965770037487344994396753505248472283247731
#1402371150275079475353867962992356093684205278224746766691813462864343871795075217989508355749642716635931824907174189358797217546624305634264458802157933311315419673854405865092102322247505412453586251582022669511221048298234732642016439123525455296325766292112758881774720932499142635136210314142144509741404827421282969081272484330382868174392651681290127032351489627054643864671335712011990584326951285867375878235135547391155357814807654366986019707719726796289990920154227959213228064918435259919697047405788311280560319520593639968900649500117511665741073545430999580686455996145426173603547052710181735901020361145546892741579951501409108067297139928103329203429485237575169217432586580425019729120741661192297552519858305628835738911159460615968385837687234565509200392302553443089729906970894661310333276852803980265040679214814192141779678148895736682538612828771031493541256243879854624644771924477873876038496224

二、解析

• 题目给出n、c、e，其中n=p**3

三、思路

• 分解n，可以直接开三次方，也可以进行因数分解。

• 根据欧拉函数

• 根据欧拉函数性质

四、解题

求p

from gmpy2 import gmpy2
n = 1781066779141074297846071955037887396311182371062305797790413639302252321886055189043670187843106208315282055227397316083218930657040969292641990094428330517286511511741846106485971830443788363541411679523274683568732340113625424593194464460018629545968907529693143364870519531630721083893407011154181539445417439610805148961135948617691115328261432541033785402520757881586489819563221498111411690769065511011083021336493731421274742041131952523427183184133413677315203810963447656037908287875212013900845740870561508870574734100843624059414134156975073835607712519402938132401964708681236647568922173471703538744207491065165405594141287750705055447493380970194312139898574699147098202027540057477562090764694370368571887563631557761911842054442637038169316686266784299889397326811768646649462480349219937292894824766045607723468654723947999531346474969019631500665628522355198334827965770037487344994396753505248472283247731
print(gmpy2.iroot(n,3)[0])

求明文

import gmpy2
from Crypto.Util.number import long_to_bytes
e= 65537
n = 1781066779141074297846071955037887396311182371062305797790413639302252321886055189043670187843106208315282055227397316083218930657040969292641990094428330517286511511741846106485971830443788363541411679523274683568732340113625424593194464460018629545968907529693143364870519531630721083893407011154181539445417439610805148961135948617691115328261432541033785402520757881586489819563221498111411690769065511011083021336493731421274742041131952523427183184133413677315203810963447656037908287875212013900845740870561508870574734100843624059414134156975073835607712519402938132401964708681236647568922173471703538744207491065165405594141287750705055447493380970194312139898574699147098202027540057477562090764694370368571887563631557761911842054442637038169316686266784299889397326811768646649462480349219937292894824766045607723468654723947999531346474969019631500665628522355198334827965770037487344994396753505248472283247731
c = 1402371150275079475353867962992356093684205278224746766691813462864343871795075217989508355749642716635931824907174189358797217546624305634264458802157933311315419673854405865092102322247505412453586251582022669511221048298234732642016439123525455296325766292112758881774720932499142635136210314142144509741404827421282969081272484330382868174392651681290127032351489627054643864671335712011990584326951285867375878235135547391155357814807654366986019707719726796289990920154227959213228064918435259919697047405788311280560319520593639968900649500117511665741073545430999580686455996145426173603547052710181735901020361145546892741579951501409108067297139928103329203429485237575169217432586580425019729120741661192297552519858305628835738911159460615968385837687234565509200392302553443089729906970894661310333276852803980265040679214814192141779678148895736682538612828771031493541256243879854624644771924477873876038496224
p = 121216033233585299462279856144422199686140149244819402908675131452249143435823157035320400025743305736047792084067723177554239638229731651194515823556880874798950035236056266154727789682357822323822962110560589110432270068487448525123808163818606838762211746373156874518622834972063360072190758655502892772811
phi= (p**3-p**2)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))

欧拉函数的性质--Manyprime

一、题目

n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
c = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

二、解析

• 题目给出n、e、c，求解明文。

三、思路

• 分解n，发现分解出多个因数。

• 根据欧拉函数性质求解

四、解题

首先分解n

sage: ecm.factor(5806423918988431929295638568708977996508831527187617629322924822521525912798714215691620371904190364350417977398803895295936744855557
....: 922349009694020190556017816620445159992100326982759816313766511173186773687428676871801400487156271606417711180403725735754793308300929898007301
....: 055737005577171462518605888025093105347923107488985043949662638199599632735091197910375255044226066346401732775987748140995405555692571797159086
....: 429173553657914475087514018897240959649245131962813456654806880296399994726495491631475995401423675754138857296531665175957199918722230119698562
....: 59344396899748662101941230745601719730556631637)

求明文

import gmpy2
from Crypto.Util.number import long_to_bytes
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
c = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
factor = [9282105380008121879,
 9303850685953812323,
 9389357739583927789,
 10336650220878499841,
 10638241655447339831,
 11282698189561966721,
 11328768673634243077,
 11403460639036243901,
 11473665579512371723,
 11492065299277279799,
 11530534813954192171,
 11665347949879312361,
 12132158321859677597,
 12834461276877415051,
 12955403765595949597,
 12973972336777979701,
 13099895578757581201,
 13572286589428162097,
 14100640260554622013,
 14178869592193599187,
 14278240802299816541,
 14523070016044624039,
 14963354250199553339,
 15364597561881860737,
 15669758663523555763,
 15824122791679574573,
 15998365463074268941,
 16656402470578844539,
 16898740504023346457,
 17138336856793050757,
 17174065872156629921,
 17281246625998849649]
phi = 1
for i in factor:
   phi *=(i-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

欧拉函数的性质--Square Eyes

一、题目

N = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
c = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

二、解析

• 题目给定n、e、c，尝试分解n。

三、思路

• 分解n，p、q相等。

• 即:

四、解题

分解n

import gmpy2
from Crypto.Util.number import long_to_bytes
q=23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
p=23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
c = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
d = gmpy2.invert(e,(p**2-p))
m = pow(c,d,n)
print(long_to_bytes(m))