RSA¶

RSA是1977年由罗纳德·李维斯特（Ron Rivest）, 阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的. 当时他们三人都在麻省理工学院工作. RSA就是他们三人姓氏开头字母拼在一起组成的

加密流程¶

选择一对不相等且足够大的质数p，q
计算p、q的乘积，记为n

计算n的欧拉函数

选择一个与互素的数e

，，一般常见的e为65537

计算e关于的逆元d

将（e，n）作为公钥公开，用于加密；将（d，n）作为私钥保存，用于解密
具体加密过程

具体解密过程

分解n¶

e = 65537
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708

分解n

http://www.factordb.com/

yafu

from Crypto.Util.number import *
from gmpy2 import *

p = 275127860351348928173285174381581152299

q = 319576316814478949870590164193048041239

e = 65537
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708

n = p*q
phi = (p - 1) * (q - 1)
d = invert(e, phi)
m = pow(c, d, n)


print(long_to_bytes(m))
# bytes_to_long()
# LitCTF{factordb!!!}

共模攻击¶

from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)

n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409

c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638

其中

通过扩展欧几里得算法我们可以知道，一定存在一组数，使得

from Crypto.Util.number import *
from gmpy2 import *


n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409

c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638

_, s1, s2 = gcdext(e1, e2)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(long_to_bytes(m))

# NSSCTF{same_module_attack!}

格¶

前置知识¶

向量和向量空间¶

以二维向量空间举例，我们可以任意取一个点A，连接原点O和A点，这就构成成了一个向量。我们也可以用A点的坐标来表示这个向量,就像这样v=(x,y)

向量满足加减、数乘和点积运算，下面举例说明（加粗表示向量）

v=(a , b)，w=(c , d)

v + w = （a + c，b + d）（减法同理）

c * w = （c * a， c * b ）（数乘）

v * w = a * c + b * d （点积）

多维是同理的

然后向量还分行向量和列向量，可以简单理解为行向量就是在纸上横着写的向量（确信），列向量就是在纸上竖着写的向量（确信）

向量大小和基¶

用来表示向量的长度，其大小是(高中应该就有这个知识点的)

这里还有一些关于线性独立的知识点，比如向量空间里有一组向量

满足方程

当全为零时等式才成立，那么这k个向量就是线性无关的，反之线性相关

而向量空间的基底会要求是一组线性无关的向量，当我们有了这一组向量基，我们就可以用这个基底来表示这个向量空间中的任意向量

拿二维空间举例

就是一组线性无关的基底，这两个向量就可以表示整个二维平面

其实了解一下矩阵会更有帮助，但是我就不介绍了（有试着想写一下，但是发现讲不清楚，还是留给大家的线代老师吧）

线代课程（放一个宋浩老师线代课的链接吧）

格定义¶

推荐文章

格攻击之小未知数方程求解入门——原理与例子 | Tover's Blog

这里先放一个课本上的定义

可能看起来比较难懂，但是我们还是从上面那个二维平面出发，我们已经知道了我们可以用一组基底来表示整个二维平面（基底不唯一），我们是通过把这两个向量乘以不同的系数后相加得到的，那么想象一下，我们如果令系数只为整数会怎么样呢？

这个时候，我们通过这个基底，就只能得到空间里的一些点，那么这个就是一个整数格

，其中a、b取任意实数

靠a、b取整数，则可以得到格

把矩阵当作B，向量设为x，就可以写成

我们把基底写成一个矩阵，那么就可以得到上面定义里的写法，同时这个矩阵的行列式的值，叫做这个基本域的容积

同时如果我们扩展到n维向量空间，就是定义里的表示

格常见问题¶

通过上面我们简单了解了一下格是什么，长什么样，那么就要考虑能拿它干什么

这就得提一下格上的两个常见问题，一个是最短向量问题（SVP），另一个是最近向量问题（CVP）

SVP是指我们要在格L上找到一个最短的非零向量，使得最小

LLL格基规约¶

这里的运用就是根据关系找到一个基底的矩阵，矩阵中所有数是已知的，然后我们要求解的向量（要求解的未知数构成的向量）是一些数作用在这个矩阵后得到，这个向量就在格上，然后我们期望这个向量是最短向量，以此来求解未知数，下面放一个代码

# sage
from gmpy2 import *
from Crypto.Util.number import *
#from tqdm import *

a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587
b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609


mat = [[b,0],[a,1]]
M = Matrix(ZZ,mat)
qq,pp= M.LLL()[0]   # 最短向量

print(pp)
print(qq)

要运用LLL算法是有条件的，就是我们要通过这个算法来求最短向量，那么我们要求的向量起码得是最短向量，这就得看一下上面的最短向量存在定理，我们要求解的向量长度满足条件后才是最短向量，才可以用LLL算法，然后格的维数也不能太高，不然准确度不高，耗时也会长。

题目(NTRU)¶

from secret import flag
from Crypto.Util.number import *

q = getPrime(2048)

f = getPrime(1024)
g = getPrime(768)

h = (inverse(f, q) * g) % q

m = bytes_to_long(flag)

e = (getPrime(32) * h + m) % q

print((h, q))
print(e)

# (8916452722821418463248726825721257021744194286874706915832444631771596616116491775091473142798867278598586482678387668986764461265131119164500473719939894343163496325556340181429675937641495981353857724627081847304246987074303722642172988864138967404024201246050387152854001746763104417773214408906879366958729744259612777257542351501592019483745621824894790096639205771421560295175633152877667720038396154571697861326821483170835238092879747297506606983322890706220824261581533324824858599082611886026668788577757970984892292609271082176311433507931993672945925883985629311514143607457603297458439759594085898425992, 31985842636498685945330905726539498901443694955736332073639744466389039373143618920511122288844282849407290205804991634167816417468703459229138891348115191921395278336695684210437130681337971686008048054340499654721317721241239990701099685207253476642931586563363638141636011941268962999641130263828151538489139254625099330199557503153680089387538863574480134898211311252227463870838947777479309928195791241005127445821671684607237706849308372923372795573732000365072815112119533702614620325238183899266147682193892866330678076925199674554569018103164228278742151778832319406135513140669049734660019551179692615505961)
# 20041713613876382007969284056698149007154248857420752520496829246324512197188211029665990713599667984019715503486507126224558092176392282486689347953069815123212779090783909545244160318938357529307482025697769394114967028564546355310883670462197528011181768588878447856875173263800885048676190978206851268887445527785387532167370943745180538168965461612097037041570912365648125449804109299630958840398397721916860876687808474004391843869813396858468730877627733234832744328768443830669469345926766882446378765847334421595034470639171397587395341977453536859946410431252287203312913117023084978959318406160721042580688

求解思路，所以要求f和g

from random import randint
from gmpy2 import *
from Crypto.Util.number import *
import math

h,q = (8916452722821418463248726825721257021744194286874706915832444631771596616116491775091473142798867278598586482678387668986764461265131119164500473719939894343163496325556340181429675937641495981353857724627081847304246987074303722642172988864138967404024201246050387152854001746763104417773214408906879366958729744259612777257542351501592019483745621824894790096639205771421560295175633152877667720038396154571697861326821483170835238092879747297506606983322890706220824261581533324824858599082611886026668788577757970984892292609271082176311433507931993672945925883985629311514143607457603297458439759594085898425992, 31985842636498685945330905726539498901443694955736332073639744466389039373143618920511122288844282849407290205804991634167816417468703459229138891348115191921395278336695684210437130681337971686008048054340499654721317721241239990701099685207253476642931586563363638141636011941268962999641130263828151538489139254625099330199557503153680089387538863574480134898211311252227463870838947777479309928195791241005127445821671684607237706849308372923372795573732000365072815112119533702614620325238183899266147682193892866330678076925199674554569018103164228278742151778832319406135513140669049734660019551179692615505961)
f = getPrime(1024)
g = getPrime(768)

K=2**0

e=math.e
pi=math.pi


n = 2
det = q

# 行列式的值(赫米特)
temp1=gmpy2.iroot(n,2)[0] * gmpy2.iroot(det,n)[0]
print(temp1.bit_length())

# 高斯
# temp = (n/(2*math.e*math.pi))**(0.5)
# a= gmpy2.iroot(det,n)[0]
# temp1=int(temp*a)
# print(temp1.bit_length())


# 向量大小
temp2 = gmpy2.iroot(f**2+g**2,2)[0]
temp2=int(temp2)
print(temp2.bit_length())
if temp1.bit_length() >= temp2.bit_length():
 print("true")
else:
 print("false")

可以得到解题代码为

from sage.all import *
from Crypto.Util.number import *
from gmpy2 import *

h,p=(8916452722821418463248726825721257021744194286874706915832444631771596616116491775091473142798867278598586482678387668986764461265131119164500473719939894343163496325556340181429675937641495981353857724627081847304246987074303722642172988864138967404024201246050387152854001746763104417773214408906879366958729744259612777257542351501592019483745621824894790096639205771421560295175633152877667720038396154571697861326821483170835238092879747297506606983322890706220824261581533324824858599082611886026668788577757970984892292609271082176311433507931993672945925883985629311514143607457603297458439759594085898425992, 31985842636498685945330905726539498901443694955736332073639744466389039373143618920511122288844282849407290205804991634167816417468703459229138891348115191921395278336695684210437130681337971686008048054340499654721317721241239990701099685207253476642931586563363638141636011941268962999641130263828151538489139254625099330199557503153680089387538863574480134898211311252227463870838947777479309928195791241005127445821671684607237706849308372923372795573732000365072815112119533702614620325238183899266147682193892866330678076925199674554569018103164228278742151778832319406135513140669049734660019551179692615505961)
c =20041713613876382007969284056698149007154248857420752520496829246324512197188211029665990713599667984019715503486507126224558092176392282486689347953069815123212779090783909545244160318938357529307482025697769394114967028564546355310883670462197528011181768588878447856875173263800885048676190978206851268887445527785387532167370943745180538168965461612097037041570912365648125449804109299630958840398397721916860876687808474004391843869813396858468730877627733234832744328768443830669469345926766882446378765847334421595034470639171397587395341977453536859946410431252287203312913117023084978959318406160721042580688

def decrypt(f, g, c):
    a = c * f % p
    return a * pow(f, -1, g) % g

M = matrix([[1, h], [0, p]])
L = M.LLL()
shortest_vector = L[0]
if shortest_vector < 0:
    shortest_vector = -shortest_vector
f, g = shortest_vector
m = decrypt(f, g, c)
print(m)
print(long_to_bytes(int(m)))


# 240545625414656445795697416299836828697587638044418742943136404284040669983557024929358783705357829768985339005
# flag{Lattice_reduction_magic_on_NTRU#82b08b2d}

coppersmith¶

定理¶

设N是一个大整数，是 N 的一个因子，设是一个d阶(次数为d)的多项式，令，其中，那么对于给定的，有

在模N意义下，可以快速求出满足的全体正整数解（就是求出X以内的根）
给定，可以快速求出模p意义下较小的根（就是求模因子意义下的根，可以解决低位丢失类题目）

原理¶

有了这个定理，相信大家一定好奇为什么，为什么可以这么做，但是这个原理挺复杂的，下面会简单讲一下我的理解，不一定对，建议直接看截图

就是把一个多项式看成一个多维向量，再构造成一个格，之后再运用LLL格基规约找到一个范数最小的向量，然后根据一个引理，就可以找到这个多项式的一个根。

small_roots¶

知道这么一个定理后我们期望在代码层面实现它，这就要用到Sagemath里的small_roots这个函数，下面会具体介绍这个函数，首先放一个具体实现

R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
P = p + x
low_p = P.monic().small_roots(X = 2**340, beta = 0.4)
print(low_p)

PolynomialRing ：构造多项式环

Zmod(n) ：模运算

implementation='NTL' ：执行 NTL

small_roots( X=？ , beta=？ , epsilon=？)：计算多项式的小整数根，返回结果是一个列表

X：根的绝对上界，比如说下面那道题目，上界就是2**340

beta：coopersmith里的一个参数，给定，以快速求出模某个p意义下较小的根，其中，是n的因数，一般取0.4

epsilon：也是coppersmith里的一个参数，程序默认好像是，平时不太会用到这个参数，需要时加在beta后面就行

monic()：用于将多项式的首项系数归一化为1。它接受一个多项式作为参数，然后返回一个新的多项式，其中首项系数已经被归一化为1。这个过程可以简化多项式的表达式，使其更易于计算和分析。

这样简单的使用方法就了解了，可以看看下面的题目，自己运用一下

题目¶

m低位丢失¶

n=13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211
e=3

m=random.getrandbits(512)

c=pow(m,e,n)=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517

((m>>72)<<72)=2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

long_to_bytes(m).encode('hex')=

表示29，右移3位得到，再左移三位得到，表示24，缺少了101

from gmpy2 import *
from Crypto.Util.number import *

n=13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211
e=3

c=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517


m1 = 2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
f = (m1+x)^3-c

m_low = f.monic().small_roots(X = 2**72, beta = 0.5,epsilon=0.02)[0]

print(m_low)
print(long_to_bytes(int(m1+int(m_low))))

p低位丢失¶

n=12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219

e=65537

m=random.getrandbits(512)

c=pow(m,e,n)=627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778

((p>>128)<<128)=97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672

from gmpy2 import *
from Crypto.Util.number import *

n=12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219

e=65537


c=627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778

p1=97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672

R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
f = p1+x

p_d = f.monic().small_roots(X = 2**128, beta = 0.5,epsilon=0.02)[0]
print(p1+p_d)
p = int(p1+p_d)
q = n//p

phi_n = (p - 1) * (q - 1)
d = inverse(e, phi_n)
m = pow(c, d, n)


print(long_to_bytes(int(m)))