LittleRSA与格密码
Shinichicun
编辑于 2022年10月01日 14:43

简述：

    本文主要是讲一道"RSA+LLL&#​34;的题以及格密码的简单知识

一、题目

题目来源：DASCTF X CBCTF 2022九月挑战赛

代码块
Python
自动换行
复制代码
from Crypto.Util.number import *
import sympy
import random
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
phi = (p-1)*(q-1)
e = 65537
n = p * q
c = pow(m, e, n)

s = getPrime(300)
N = getPrime(2048)
g = p * inverse(s,N)**2 % (N**2)
print(N)
print(g)
print(n)
print(c)

'''
19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
'''
复制成功

二、格密码

(一)格的定义

    给定n维空间中一组线性无关向量，其整系数组合构成的集合称为格。如下图所示：

    此处的 b_1%2C...%2Cb_n(b_1%2C...%2Cb_n%E2%88%88R%5Em) 定义为格基。同一个格可以由多组不同的格基生成。因为格是否满秩对它的性质研究影响不大，所以通常研究满秩的格。此处如果m=n，则称该“格”满秩。因为格是否满秩对它的性质研究影响不大，所以通常研究满秩的格。

    e.g  格基和可以产生二维空间的所有整数格。如下图：

    

(二)、格上的最短向量问题

    格上的最短向量问题是指求格中一个最短的非零向量的问题，定义如下：

(三)、LLL算法

    在1982年，A.K.Lenstra 、H.W.Lenstra 和 L.lovasz

提出一种解决SVP问题的算法，通常称之为LLL算法。

    关于该算法的应用，可以参考这篇文章：https://blog.csdn.net/forest_LL/article/details/123733641

三、解题过程

    当时做这道题的时候，我只是看出这是个RSA加密，而且题目脚本里有一行与p有关：

 g = p * inverse(s,N)**2 % (N**2) 

    所以我当时知到得从这里入手。但当时我无从下手(果然我还是很菜。。。)

    后来看了题解才知道这就是在造一个格子：

gs%5E2%3Dp%2BkN%5CRightarrow%20%20(s%5E2%2C-k)%5Cbegin%7Bpmatrix%7D1%26g%5C%5C0%26N%5C%5C%20%5Cend%7Bpmatrix%7D%3D(s%5E2%2Cp)

    因此这里用一下LLL算法,就可以求出p了:

代码块
Python
自动换行
复制代码
# sage
from Crypto.Util.number import *
import gmpy2

N = 19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
g = 101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
n = 90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
c = 51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
e = 0x10001

g = g % N
M = Matrix(2, 2, [1, g, 0, N])
res = M.LLL()[0]
p = abs(res[1]) # 对结果取绝对值一劳永逸
assert n % p == 0
q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))
复制成功

四、参考文章

1，DASCTF X CBCTF 2022九月挑战赛wp  

2，脚本来源：http://t.csdn.cn/hv8wj

3，《公钥密码学的数学基础》

CTF CRYPTO
cv18876923