格的初探

HNP问题

格的初探

安全客

[RSA3]P4

矩阵markdown

发现一个格密码Blog

还有一个格密码

第一次接触格，解RSA

\(a = r^{-1}*m \pmod{p}\)

\(\Rightarrow a*r = m + k*p\) \[ \left[ \begin{matrix} r & k \end{matrix} \right] \left[ \begin{matrix} 1 & a \\ 0 & p \end{matrix} \right] = \left[ \begin{matrix} r & m \end{matrix} \right] \]

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


a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

# a*r = flag + k*p
M = matrix(ZZ,[[1,a],[0,p]])
r,m = M.LLL()[0]
print(r,m)
flag = long_to_bytes(abs(m))
print(flag) 

自己构造一个格

\(a = r^{-1}*m \pmod{p}\)

\(\Rightarrow a*r = m + k*p\) \(\Rightarrow r*a - k*p = m\) \[ \left[ \begin{matrix} r & k \end{matrix} \right] * \left[ \begin{matrix} a & 1 \\ -p & 0 \end{matrix} \right] = \left[ \begin{matrix} m & r \end{matrix} \right] \]

import libnum
a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

mat = [[a,1],[-p,0]]
M = Matrix(mat)
h = M.LLL()
print(h)
flag = libnum.n2s(int(h[0][0]))
print(flag)
# b'NSSCTF{e572546b-abb5-4358-8970-471abc12b7ef}'

开始格

复现博客无趣的浅

有这样的一些等式，然后A,B已知,k的bit位数要小于p的bit位数，等式数量足够的情况下，少6bit位数可以求解k

具体构造如下矩阵

其中K为ki同bit位数的数（bit_length(ki)=250 K=2^250)

Z为需要自己构造的数 \[ \begin {pmatrix} l_1 & \cdots & l_i & x &1 \end{pmatrix} \times M = \begin{pmatrix} k_1 & \cdots & k_i & Z*x&K \end{pmatrix} \] 要尽可能的满足Z*x的bit位数与K一致

MTCTF2022 strange_rsa3

from Crypto.Util.number import *
from secret import flag3
 
 
qBits = 2048
pBits = 512
num = 2
q = getPrime(qBits)
p = [getPrime(pBits) for _ in range(num)]
r = [getRandomRange(1, 2**(pBits * 2))]
 
a = getRandomRange(1, 2**pBits)
b = getRandomRange(1, 2**pBits)
gift = (p[0] * a - p[1]) * inverse(b, p[0] * p[1]**2) % (p[0] * p[1]**2)
r.append(a * r[0] % p[1]**2)
 
n = [p[i] * q + r[i] for i in range(num)]
e = 0x10001
c = pow(bytes_to_long(flag3), e, q)
 
output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')
 

n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999

题目：

Alt text

先求p0，p1

Alt text

# 上面的公式是连分数 跟代码没关系
# 因为我的连分数没有解出来p0，p1
mat = [[2^1024,n[1]],[0,-n[0]]]      # p0*n[1] - p1*n[0] = p0*r1 - p1*r0 
mat = Matrix(ZZ,mat)
L = mat.LLL()[0]
p0,p1 = mat.solve_left(L)            # p = L*mat**(-1) 这样也可以，一样的
print(p0,p1)

求a，b

浅 ：然后就是通过gift的那个式子构造格子求解出a,b。先变化一下成文章开头的那种形式

Alt text

浅 ：a,b未知，然后a,b的bit位数远小于mod=p0 * p1^2.构造格子

\[ \\M = \begin{pmatrix} mod & & \\ A & 1 & \\ B & & K \end{pmatrix} \] \[ \\ A=p0*gift^{-1}\\ B=p1*gift^{-1}\\ mod=p0*p1^2 \\ K=2^{512} \\ \]

\[ \\ A*a - B = b \pmod{mod} \] \[ \begin{pmatrix} k & a & -1 \end{pmatrix}\times M = \begin{pmatrix}k*p+A*a-B & a & -K\end{pmatrix}=\begin{pmatrix}b & a & -K \end{pmatrix} \]

M = [[mod,0,0],[A,1,0],[B,0,2^512]]
M = Matrix(M)
h = M.LLL()
b = abs(hhh[0][0])
a = abs(hhh[0][1])
# a 11022212982424652632647405376934304592755205611710996956605750639057526541029596360155260174701488414125581957719469209021506720182948113423105539872264354 
# b 9864245136392130046455737513510508070496025625897918994462477425135301427183420481191209852444833597428299605829396903107753368813219485870517193682708546

\(a*r_0 = r_1 \pmod{p_1^2}\)

\(\Rightarrow a*r_0*p_0 = r_1*p_0 \pmod{p_0*p_1^2}\)

\(p_1*n_0 = p_0*p_1*q + r_0*p_1\)

\(p_0*n_1 = p_0*p_1*q + r_1*p_0\)

\(\Rightarrow p_0*n_1 - p_1*n_0 = r_1 * p_0 -r_0*p_1\)

\(\Rightarrow p_0*n_1 - p_1*n_0 = r_0*(a*p_0 - p_1)\pmod{p_0*p_1^2}\)

\(\Rightarrow r_0 = (p_0*n_1 - p_1*n_0)*(gift*b)^{-1}\pmod{p_0*p_1^2}\)

完整代码

环境：SageMath 9.3 Notebook

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


n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999
e = 0x10001
mat = [[2^1024,n[1]],[0,-n[0]]]      # p0*n[1] - p1*n[0]
mat = Matrix(ZZ,mat)
L = mat.LLL()[0]                     # p0*n[1] - p1*n[0] == L[1]
p0,p1 = mat.solve_left(L)            # p = L*mat**(-1) 这样也可以，一样的
print(p0,p1)

print('--------------分割-------------')
p = L*mat**(-1)
print(p)
print('---------------验证完毕-----------')
print(p0*n[1] - p1*n[0] == L[1])      # true

p0,p1 = abs(p0),abs(p1)
# print(p0,p1)
mod = Integer(p0 * (p1^2))            # 转换成sage的Integer型   <class 'sage.rings.integer.Integer'>
# print(type(mod),type(gift))         # 或者ZZ  也可以
A = p0 * inverse(gift,mod) % mod
B = p1*inverse(gift,mod) % mod
# a*A - B = b % mod
M = [[mod,0,0],[A,1,0],[B,0,2^512]]
M = Matrix(M)
hhh = M.LLL()
print(hhh[0])
#print(hhh[1])
#print(hhh[2])

b = abs(hhh[0][0])
a = abs(hhh[0][1])
# print(a,b)
# p0*n[1] - p1*n[0] = r0*(a*p0-p1)%(p0*p1^2)
r0 = (p0*n[1]-p1*n[0])*inverse(gift*b,mod)%mod
p = (n[0] - r0)//p0
phi = ZZ(p-1)
d = inverse(e,phi)
m = pow(c,d,p)
flag = long_to_bytes(ZZ(m))
print(flag)