格的学习过程

ctf中的格密码

NRTU格密码

[深育杯 2021]

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

def encrypt(plaintext):
    p = getStrongPrime(3072) 
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        c = (r * h + m * f) % p
        return (h, p, c)

h, p, c = encrypt(flag)
with open("cipher.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")
h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672

首先看关系式子

\[h\equiv(f^{-1}*g) modp\\\\\] \[c\equiv(r*h+m*f)modp\\\\\] \[c\equiv(r*f^{-1}*g+m*f)modp\\\\\] \[c*f\equiv(r*g+m*f^2)modp\\\\\] 先可以得到这些式子

然后我们再看这几个数的bit位，p为3072位，r，f为1024位,m为明文的话一般不会特别大，所以可以得到s

\[c*f=r*g+m*f^2\\\\\] \[设c*f=t\\\\\] \[t=r*g+m*f^2\\\\\] \[模去 g\\\] \[t\equiv m*f^2modg\\\\\] \[m\equiv t*f^{-1}*f^{-1}modg\\\\\] \[然后再看\\\\\] \[h\equiv(f^{-1}*g) modp\\\\\] \[h*f\equiv gmodp\\\\\] \[f*h=g+k*p\\\\\] \[f*h+(-k)*p=g\\\\\] \[满足这个形式 a*v+a_1*v_1=g\\\\\] \[\begin{align} \begin{bmatrix} f&-k \end{bmatrix}*\begin{bmatrix} 1 & h \\\\ 0 & p \end{bmatrix}=\begin{bmatrix} f&f*h-k*p \end{bmatrix}=[f&g]\end{align} \] \[这边很明显是求解svp问题最短向量\\\\\] \[那么如何在lattice里求最短向量呢？\\\\\]

\[在2维里，早在200年前，高斯（Gauss）就发现了一个能稳定求解的算法（Gauss Lattice Reduction）\\\\。\]

\[令L是由两个基向量v1, v2所张成的2维lattice，假定|v1| < |v2|，我们现在通过减去v1的某个倍数来使得v2变短\\\\\] \[v_2^{*}=v_2-\frac{v_1*v_2}{||v_1^{2}||}*v1\\\\\] \[然后可以借助sagemath求解最短向量\]$$

from Crypto.Util.number import long_to_bytes

h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672

L = matrix(ZZ, [[1, h],[0, p]])
v = L.LLL()[0]
f, g = map(abs, v)

a = f * c % p % g
m = a * inverse_mod(f*f, g) % g
print(long_to_bytes(m))

GGH加密

GGH的加密过程如下

\[c=m*B+e\\\] \[m:由明文组成的1*n的向量\\\] \[B:由公钥组成的n*n的矩阵\\\] \[e:一个1*n的向量\\\] \[c:加密后的明文\\\]

\[cvp:给定一个不在格L中的向量的向量W∈R^m,找到最接近w在格上的向量v∈L，\\\\\] \[其实就是找到一个最短的欧几里得范数||w-v||最小化的向量v∈L.\\\\\] \[Hermite定理:每个维数为n的格L都包含一个非零向量v∈L，满足:\\\\\] \[||v||^2\le \sqrt[]{n}det(L)^{\frac{1}{n}}\\\\\] \[1.使得维数n的每个格L都包含一个非零向量v∈L使得下列式子成立\\\\\] \[||v||^2\le \gamma _ndet(L)^{\frac{2}{n}}\\\\\] \[2.使得等式1成立的\gamma _n^{'}的最小值范围（n很大的情况）满足:\\\\\] \[\frac{n}{2\pi e}\le \gamma _n \le \frac{n}{\pi e}\\\\\] \[也可以拓展到多个向量。\\\\\] \[||v_1||||v_2||||v_3||......||v_n|| \le n^{\frac{n}{2}}(det(L))\\\\\] \[通过阿达马不等式:||v_1||||v_2||||v_3||......||v_n|| \ge det(L)\\\\\] \[我们可以在格基为A=v_1,....mv_n的格L定义一个标量:\\\\\] \[0< H(A)=(\frac{detL}{||v_1||||v_2||||v_3||......||v_n||})^{\frac{1}{n}} \le1\] \[值越接近1，基向量越接近正交\]

\[ GGH其实就是一个cvp问题，常见的sage脚本如下 \]

def CVP(lattice, target):
    print("executing Gram_Schmidt")
    gram = lattice.gram_schmidt()[0]
    print("Finish")
    t = target
    for i in reversed(range(lattice.nrows())):
        c = ((t * gram[i]) / (gram[i] * gram[i])).round()
        t -= lattice[i] * c
    return target - t

\[ GGH需要考虑的是如何将原始的CVP问题简化为另一个CVP问题\\ \]