zzZxby's blog

NTRU

发表于
本文字数： 578 阅读时长 ≈ 2 分钟
简单记录一维NTRU加解密流程

NTRU学习

加解密流程

NTRU属于n维上的加解密算法，目前遇到的NTRU问题都是一维问题，可以化简的比较简单一些

  • 参数

    模：

    私钥：

    公钥：

    临时密钥r

  • 加密：

  • 解密： 再乘上即可得到

  • 参数大小：

    显然当时才能正确解密

  • 考虑格 同时我们有

    因为 则如果我们能够找到则可以得到

  • 更多条件 此时发现向量的长度为

[NSSRound#11 Basic]NTR

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import gmpy2
from flag import flag
from Crypto.Util.number import *

def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)

def encrypt(cipher, p, z):
    message = bytes_to_long(cipher)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    return c

p, x, y, z = init()
c = encrypt(flag, p, z)
with open("cipher.txt", "w") as f:
    f.write("binz = " + str(bin(z)) + "\\n")
    f.write("binp = " + str(bin(p)) + "\\n")
    f.write("binc = " + str(bin(c)) + "\\n")
    
binz = 0b1111100101011101011001011000000011001000111011100000100101111010101111100000110010011110110011110010001000100110110001101011111100111100101100100011100011100010101110101101000001110110000010100101100110111111100111101011001010101001100110110010110011001110100100001100100000101100010001100100101011111111010001011110100110000001100001001011001011111000000110100010111111110011000010100110010111111111100001101010001011000100111100100001010001001011001000011110001101000110001010010010100101011110011011111010011000000010110111000100011101010110001000011011011011110101010001010101010010110110100000100101010100111011000110001110110100101101011110010100001100011010100011010000011101110001111101110110001010111010010011000110001011101001001001101101001011010001011110001110000011001100111110110001111000000001010111100000111101000100000100010000110011011100100001001101100111010110101111010111000011101101110100110001000111110100011110111010010001011011101011001001000010011111010001011110101111000001000001011101110000110111011010001101100001100101011101110110010000000011010101010111010110111111010101011001010011010001101110001000011001100000001101111100011111110001010110101011100100111100110000101010110111010111011110000100110001011001101001010101101100000010010010111101110010100111100111001000011001110101101111010110011101000011000011111001000110000110011001000011111100011010010011111011110110000110111001101111011110001001101111101001000110110000101001101111000101110000111111000111110111110110010010011000110101000001010011100011110000110100101000111001010111010111000101101011111111000101000010111111111101110111001100010111111001111110010101110100010001001101110001000011010101011010111100101101101011101011100101010100100000001000100110101110010010101110000111001000100100101101011110100110010010110010011110101111010100010000100011110111110110001110001001001001100110010001011110101101100011011110000100001101001011001011101011110000001010010100110110000100101100101011100100101010010001000111010100000111000011101000011110101110010

binp = 0b10111100110000001011101110111001111010110101010010111101100111000000010100101110000001001100100111101100010111011000010001100111011100010010010010111111111001111000110010110000001011101000011110101111111100010101011010000110111110010000010001010010110001010010111111011011101111001100110101101101001010000001001100000100100111000001111111100100110101110111001011100011010101010000101101001111101111111010011010101010001000011110011000011001001011101011011010101110100010101011010011011010101000001000011011111100000110111010100100101100000110000111010010000111010000101100101100110010111011111100101111011111001000111110010101111000000011100110011100000010100011100110011000011111001001110000000001001011011011101111000111100101000011101111111110101001100010110001110001011010110011111011011110001110110110011100000110011000100000111001000111101000011110000011100101010111010001100101110101101100101111100100011111011101011010101110011001100000100010000000101101101111001110010011000000001100000100101001010011000101101100110100110010011010111110000111000011010011101110110100110010001001000101011101100110001011111000101000111011001110101100111110110010100000011001011101111001101000111111011101110000000000011000010101101011100011110101100001001011000110100100010110011011100101111110111010011010110111011011100010010100101111110111010111010101000010001000001001101111110110000010000100100101100000111101111000110110011010001000111001101000110101111101101100110001000100100010001100010100100101011100100010100110001011011101101100101010101001101101101001000001111011111111100010010110100000110111001110000011010110000011100010110101111000101001000001001101000101111011111000110011001011001101000010011110101001100101111000110011011001111010100001001000111111000010011001000000111110011111111101100100100010000011110111010110101000111111010111011110110010100001010011001101111111010001000100001110011101011011000110101001111100100000100010011010010000111000100110101000100011010100010011110110100100110100001000011100000111011000011010001000111001

binc = 0b10010000101011001111100100111010110111010101110110010011001001001010011011001100000001010110000011000110001101000101100000110110101011101101000011100100000100000011101001101000111101010010010011100001100011111101100001110011111101101100100101010000101110101111110001001101101000000100110011001000011101000001011101101001010010010010101010001101111011101100011011001110101111100111101111100010111111100100010001001111110110001101100111000111101110111101001110100010101001010110001010111101000100101011111001010010110011101101100000111010010000111000100001001011101001101011111101100000011100101111001011010110101010011011110110110010000011100110001100010101010101100000001100111111001011011101101010001001001000001101001001101011111010000000110111110010101100101100111101110001110111001000000000010110110110000000110001100010001011110011101111011011000111010011101000001101100011110110110011101011001100011001011000110011111011100111101000001100011100011001000110010101101000001101110010000011111001101011011101101010000011010010111110111111111100101101101111101001101110100111010001000010101110111011000000100110001000110010000110101011100011110110011011010011101000001101110001111010000110001100001010010111101000101001100010010010001010100110011111101010101100110100111100011011010011011101011001101111010111000100011100111101011001010110111111000101011110001010100100000000001110110110100001011110000000010000010101011010010100011101111001111101110001001011110100001110010100111011010110001100100100011010100110001011100111010110100111101101111101011011011001101101010100101001011011101010011100011001111111010100001010101001101000111101100110000110101100000111110001010100000101111011000101011011101111100100100111111111000110110001100011110111010001011011001011011101001100111111110110000101011110101101000110101000111001101001010001001110010010000011110011111111101001001010101010000110000101101000100100011111101110011001011001001101010011101111100101101101111100011001101011101100001001110101100001001100011000110011001010111100000101110100

题解

观察加密流程，z属于公钥，p是模数，c是密文，加密流程就是NTRU的一维问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *

p = int("0b10111100110000001011101110111001111010110101010010111101100111000000010100101110000001001100100111101100010111011000010001100111011100010010010010111111111001111000110010110000001011101000011110101111111100010101011010000110111110010000010001010010110001010010111111011011101111001100110101101101001010000001001100000100100111000001111111100100110101110111001011100011010101010000101101001111101111111010011010101010001000011110011000011001001011101011011010101110100010101011010011011010101000001000011011111100000110111010100100101100000110000111010010000111010000101100101100110010111011111100101111011111001000111110010101111000000011100110011100000010100011100110011000011111001001110000000001001011011011101111000111100101000011101111111110101001100010110001110001011010110011111011011110001110110110011100000110011000100000111001000111101000011110000011100101010111010001100101110101101100101111100100011111011101011010101110011001100000100010000000101101101111001110010011000000001100000100101001010011000101101100110100110010011010111110000111000011010011101110110100110010001001000101011101100110001011111000101000111011001110101100111110110010100000011001011101111001101000111111011101110000000000011000010101101011100011110101100001001011000110100100010110011011100101111110111010011010110111011011100010010100101111110111010111010101000010001000001001101111110110000010000100100101100000111101111000110110011010001000111001101000110101111101101100110001000100100010001100010100100101011100100010100110001011011101101100101010101001101101101001000001111011111111100010010110100000110111001110000011010110000011100010110101111000101001000001001101000101111011111000110011001011001101000010011110101001100101111000110011011001111010100001001000111111000010011001000000111110011111111101100100100010000011110111010110101000111111010111011110110010100001010011001101111111010001000100001110011101011011000110101001111100100000100010011010010000111000100110101000100011010100010011110110100100110100001000011100000111011000011010001000111001",2)
h = int("0b1111100101011101011001011000000011001000111011100000100101111010101111100000110010011110110011110010001000100110110001101011111100111100101100100011100011100010101110101101000001110110000010100101100110111111100111101011001010101001100110110010110011001110100100001100100000101100010001100100101011111111010001011110100110000001100001001011001011111000000110100010111111110011000010100110010111111111100001101010001011000100111100100001010001001011001000011110001101000110001010010010100101011110011011111010011000000010110111000100011101010110001000011011011011110101010001010101010010110110100000100101010100111011000110001110110100101101011110010100001100011010100011010000011101110001111101110110001010111010010011000110001011101001001001101101001011010001011110001110000011001100111110110001111000000001010111100000111101000100000100010000110011011100100001001101100111010110101111010111000011101101110100110001000111110100011110111010010001011011101011001001000010011111010001011110101111000001000001011101110000110111011010001101100001100101011101110110010000000011010101010111010110111111010101011001010011010001101110001000011001100000001101111100011111110001010110101011100100111100110000101010110111010111011110000100110001011001101001010101101100000010010010111101110010100111100111001000011001110101101111010110011101000011000011111001000110000110011001000011111100011010010011111011110110000110111001101111011110001001101111101001000110110000101001101111000101110000111111000111110111110110010010011000110101000001010011100011110000110100101000111001010111010111000101101011111111000101000010111111111101110111001100010111111001111110010101110100010001001101110001000011010101011010111100101101101011101011100101010100100000001000100110101110010010101110000111001000100100101101011110100110010010110010011110101111010100010000100011110111110110001110001001001001100110010001011110101101100011011110000100001101001011001011101011110000001010010100110110000100101100101011100100101010010001000111010100000111000011101000011110101110010",2)
c = int("0b10010000101011001111100100111010110111010101110110010011001001001010011011001100000001010110000011000110001101000101100000110110101011101101000011100100000100000011101001101000111101010010010011100001100011111101100001110011111101101100100101010000101110101111110001001101101000000100110011001000011101000001011101101001010010010010101010001101111011101100011011001110101111100111101111100010111111100100010001001111110110001101100111000111101110111101001110100010101001010110001010111101000100101011111001010010110011101101100000111010010000111000100001001011101001101011111101100000011100101111001011010110101010011011110110110010000011100110001100010101010101100000001100111111001011011101101010001001001000001101001001101011111010000000110111110010101100101100111101110001110111001000000000010110110110000000110001100010001011110011101111011011000111010011101000001101100011110110110011101011001100011001011000110011111011100111101000001100011100011001000110010101101000001101110010000011111001101011011101101010000011010010111110111111111100101101101111101001101110100111010001000010101110111011000000100110001000110010000110101011100011110110011011010011101000001101110001111010000110001100001010010111101000101001100010010010001010100110011111101010101100110100111100011011010011011101011001101111010111000100011100111101011001010110111111000101011110001010100100000000001110110110100001011110000000010000010101011010010100011101111001111101110001001011110100001110010100111011010110001100100100011010100110001011100111010110100111101101111101011011011001101101010100101001011011101010011100011001111111010100001010101001101000111101100110000110101100000111110001010100000101111011000101011011101111100100100111111111000110110001100011110111010001011011001011011101001100111111110110000101011110101101000110101000111001101001010001001110010010000011110011111111101001001010101010000110000101101000100100011111101110011001011001001101010011101111100101101101111100011001101011101100001001110101100001001100011000110011001010111100000101110100",2)

L = Matrix(ZZ, [[1, h],
                [0, p]])

f, g = L.LLL()[0]

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

print(long_to_bytes(m))

[深育杯 2021]GeGe

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

题解

大致加解密流程还是NTRU，但是这里对于明文的加密，多乘了一个f

但是构造格求解私钥的过程一致，求出f后就可以求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)
print(f)
print(g)

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