跳转至

一些知识的记录

来点欧拉函数的知识

欧拉函数的定义式为：

\[ \phi(n) = { a | 1 \leq a \leq n, \gcd(a,n) = 1 } \]

当n为质数时，\(phi(n) = n-1\)

当n为合数时，可以通过欧拉定理来计算，表达式为：

\[ \phi(n) = n \prod_{i=1}^{k}(1- \frac{1}{p_i}) \]

其中\(n = p_1^{a_1} * p_2^{a_2} *...*p_k^{a_k}\)

欧拉定理即 \(\phi(n) = n * (1- 1/p_1) * (1- 1/p_2) * ... * (1- 1/p_k)\)

欧拉函数是对称的，即 \(\phi(n) = \phi(n-1)\)

来看两个例子：

已知\(n=p*p*q\)，p和q是质数，写出phi(n)的表达式

由于\(n = p*p*q\)，所以phi(n)可以通过欧拉定理来计算：

\[ \phi(n) = n \prod_{i=1}^{3}(1- \frac{1}{p_i}) \]

因为p,q是质数，所以\(phi(p^2) = p^2 - p,phi(q) = q - 1\)

所以

\[ \phi(n) = n * (1- \frac{1}{p})^2 * (1- \frac{1}{q}) \]
\[ \phi(n) = (p*p*q) * (1- \frac{1}{p})^2 * (1- \frac{1}{q}) \]
\[ \phi(n) = (p*p*q) * (1- \frac{2}{p}+\frac{1}{p^2}) * (1- \frac{1}{q}) \]
\[ \phi(n) = (p*p*q) * (\frac{p^2-2p+1}{p^2}) * (\frac{q-1}{q}) \]
\[ \phi(n) = (p*p*q) * (\frac{p^2-p}{p^2}) * (\frac{q-1}{q}) \]
\[ \phi(n) = (p*p*q-p*p*q) * (\frac{p-1}{p}) * (\frac{q-1}{q}) \]
\[ \phi(n) = (p-1)*p*(q-1) \]

所以 \(\quad phi(n) = (p-1)*p*(q-1)\)

已知\(n=(p^3)*(q^4)\)，p和q是质数，写出phi(n)的表达式

由于\(n = (p^3)*(q^4)\)，所以\(phi(n)\)可以通过欧拉定理来计算：

\[ \phi(n) = n \prod_{i=1}^{2}(1- \frac{1}{p_i}) \]

因为p,q是质数，所以 \(phi(p^3) = p^3 - p^2,phi(q^4) = q^4 - q^3\)

所以

\[ \phi(n) = (p^3)*(q^4) * (1- \frac{1}{p})^3 * (1- \frac{1}{q})^4 \]
\[ \phi(n) = (p^3)*(q^4) * (1- \frac{3}{p}+\frac{3}{p^2}-\frac{1}{p^3}) * (1- \frac{4}{q}+\frac{6}{q^2}-\frac{4}{q^3}+\frac{1}{q^4}) \]
\[ \phi(n) = (p^3)*(q^4) * (\frac{p^3-3p^2+3p-1}{p^3}) * (\frac{q^4-4q^3+6q^2-4q+1}{q^4}) \]
\[ \phi(n) = (p^3)*(q^4) * (\frac{p^3-p^2}{p^3}) * (\frac{q^4-q^3}{q^4}) \]
\[ \phi(n) = (p^3)*(q^4) * (1-\frac{1}{p}) * (1-\frac{1}{q}) \]
\[ \phi(n) = (p^2)(q^3)(p-1)*(q-1) \]

所以 \(\quad phi(n) = (p^2)(q^3)(p-1)*(q-1)\)

例题

SICTF 2023

from flag import flag
import libnum
from Crypto.Util.number import getPrime
m=libnum.s2n(flag)
n=getPrime(16)
for i in range(233):
    n*=getPrime(16)
e=65537
c=pow(m,e,n)
print(c)
print(n)
'''
44457399775772165283580795763046604956432217865936749114390645714446263790235445725770165521476841968764175721036280702731933849090719866149354613431301887740671003826556620460836983488011711209908075106260857650574672356032244606425941095128801765463716482316101398637519304864271794460829068714740938719022156283319142938782439784724450045931039355442034325311037568791297455084676548879770834712506552233840348850684727096270392080049993135041218143811167688449496243036317450681348089315258831745988434134987055263393540923865029931594717328162951158311497514418799360413513590684301435386737514918075848373373755748782672860711406169316940293554209702288482064854840802876490202123903888235028119047988176327629542924415737212649237787748145773301112682790682933658516724691338727523894513267588035437093188599375494920656327919129240066252636130803666175859640361767805549884909317548802917210333235914904622641997249853362378711924024129399688535136879208010081166848163897114124726692078532337827810846421365846926064892472698603597461932481745017020417072013702099809833423003201003030492
157077292656328898849823499976497003976795705913326943955927601882559735301000546878663484930436631929909115065166613744548816622146802007640124796249330573411377703969505934904150600987843325674764620305047603408490558134670867673308099650843329640744997672015466571290660161290811275435569339606335117906571999000341133024698424364682800683662193063661214736762852739324479859236963365531207752799197178993887860855078852702337761399225640575281412171035871278933493943575572155382899938265639764715616686123949482372238288859715465115400317136714757882965887595246507450491169518000205087415380208167764110920711042584766805992237919576823121108078407699912757901788925718859790257450499775129521327827653298451904392241906547672843110356658889638496906522290674659574024024440113632175010053065452660076447040937842478007881589334096496073556056726805396937630799201696246079227214272205462258357482722478243481697053301054600954126539848778226175296162997813416634702496577009409960503948474494741296663849482119365434792563324547643352816519125305335959420429699475765642610737903235960423173
'''

n中有许多重复小质数

用sagemath的euler_phi函数分解即可

n = 157077292656328898849823499976497003976795705913326943955927601882559735301000546878663484930436631929909115065166613744548816622146802007640124796249330573411377703969505934904150600987843325674764620305047603408490558134670867673308099650843329640744997672015466571290660161290811275435569339606335117906571999000341133024698424364682800683662193063661214736762852739324479859236963365531207752799197178993887860855078852702337761399225640575281412171035871278933493943575572155382899938265639764715616686123949482372238288859715465115400317136714757882965887595246507450491169518000205087415380208167764110920711042584766805992237919576823121108078407699912757901788925718859790257450499775129521327827653298451904392241906547672843110356658889638496906522290674659574024024440113632175010053065452660076447040937842478007881589334096496073556056726805396937630799201696246079227214272205462258357482722478243481697053301054600954126539848778226175296162997813416634702496577009409960503948474494741296663849482119365434792563324547643352816519125305335959420429699475765642610737903235960423173
c = 44457399775772165283580795763046604956432217865936749114390645714446263790235445725770165521476841968764175721036280702731933849090719866149354613431301887740671003826556620460836983488011711209908075106260857650574672356032244606425941095128801765463716482316101398637519304864271794460829068714740938719022156283319142938782439784724450045931039355442034325311037568791297455084676548879770834712506552233840348850684727096270392080049993135041218143811167688449496243036317450681348089315258831745988434134987055263393540923865029931594717328162951158311497514418799360413513590684301435386737514918075848373373755748782672860711406169316940293554209702288482064854840802876490202123903888235028119047988176327629542924415737212649237787748145773301112682790682933658516724691338727523894513267588035437093188599375494920656327919129240066252636130803666175859640361767805549884909317548802917210333235914904622641997249853362378711924024129399688535136879208010081166848163897114124726692078532337827810846421365846926064892472698603597461932481745017020417072013702099809833423003201003030492
e = 65537
phi = euler_phi(n)
d = gmpy2.invert(e, phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

# SICTF{13578a78-1bd1-483e-8c01-4d501c8b52bb}