奇安信攻防社区-格基规约在ctf中的简单应用

格基规约在ctf中的简单应用

2020年7月22日，美国国家标准局NIST公布了其举办的后量子密码标准竞赛的第三轮入选算法，在7个正式入选第三轮的算法中，有5个都属于格密码的范畴，而与此同时，在我国密码学会举办的后量子密码算法竞赛中，格密码也在其中占据了相当大的比例。本篇主要介绍格的基本概念，以及在ctf解题中常使用的LLL算法的应用条件和情况。

题目分析
====

2023华中赛区的一道Crypto题目

```python
from Crypto.Util.number import *
from Crypto.Cipher import AES
#from Crypto.Util.Padding import pad
import os
import random

flag = b'xxx'
key = os.urandom(8)

def confusion1(key,p):
    M = bin(bytes_to_long(key))[2:].zfill(8 * len(key))
    print(M)
    pubkey = [random.randint(2,p - 2) for i in range(len(M))]
    enc = 0
    for k,m in zip(pubkey,M):
        enc += k * int(m)
        enc %= p
    return pubkey,enc

def confusion2():
    p = getPrime(256)
    q = getPrime(256)
    n = p * q
    s = (pow(p, q, n) + pow(q, p, n)) % n
    return p, n, s

p, n, s = confusion2()
pub, enc = confusion1(key,p)

aes = AES.new(key=key * 2, IV=key[::-1]*2, mode=AES.MODE_CBC)
ct = aes.encrypt(pad(flag,16)).hex()
'''
print(n)
print(s)
print(pub)
print(enc)
print(ct)'''

'''
5807248177480126027119403055965286287144859449082262491643270033152984965460949168152029397814146027079699650957723265118570233589832570125646440805767223
152889326545785477096356902655732958412112919155808830200062689462882806426296
[19912814047884167648188242021802816689791656841095865020941140470659137200211, 5992774932199884385046532822430145041648225402862550041474845305702215865423, 116118526117572795521843166228490592016716635740466397353517444779253746008, 79611661328528799001891234939688186624633423816562600074033534646831551193642, 11201330056762546845368465915094258836393137611453170251695463876206948831654, 51814574836040371941096091641028682662886855616420840669109269026998859276607, 3647508277290095392118459729275509003227458636100150139184274479343829875367, 50008752268318584970474038376501777497018441360261934423774201782593105290844, 48652613457958350684880413212045509213650244145951503657303825349252777664707, 33679262276087576015102551944765928897760825230519751684397851007290306600385, 23948887565333344203989720984394123398524799088794723003448891253226435336898, 40200506134453897345380856209260657457859475081597918499318205980568067373458, 30589117927199947589193370883702601883604573342293536728089110411645091119951, 36961995904674807436552010244729050273938037863053903502110853162535455167488, 3933887154458986348533752525296529281275718262725847523094541917838082900548, 27275001811044089036813021125172735315813557850948572962055731673594546337977, 38990163905164799567121739674309878741495421715559087343681401527526750929391, 1497875043388493258245188040363275261199397082188701752393416883999929882408, 16805681792092976452604332638161529673451582498214182968459336267342136632172, 71674995266289068464649355441667567062740811686486048798305754537313134645969, 78915321210892303619306333088806762686175406224770282910074688257279175727146, 14154216005774824451127847685001091956873818169826639386146070549314912985434, 13869149407315116505124752630934618263788943719378156422222781741489960228518, 33022215501062121409710115401323007232697331242586685838474400476003811083905, 16295235433324594352148008873433587653040729537454982872255450701340767226098, 60478278667497366388948470379715858839620002274031078263798201883205893927198, 8823537922007329024278189757021311788012998108630093165430357665650942121358, 80306111444635621297715902687042838702472599956558134114062653403282228975070, 7563081001868435320286665852562041705982198457812801738228791159965149117022, 35786995332347282894063922907051180796262991110683768651921643566118493546801, 73869202022492415528733299521497930278614562496203614079741799714603264426617, 33394891478254501693649623928482210422461506721232710317979640663055224789096, 38899811041840297809977940830514835624868898077474307845864955074756219530350, 77030890585631225254713296818339544623231074366456442666895453737146541395573, 29355679224007748015132627979355376091759614251694113834654209626215816057816, 22333858741037149466953066296599617201803447088553905832644042459531682565436, 78978475643427553084766292152304931423030177848775605977434140156777802402955, 75924948076371846290967418374982594981053654607052025147196130662104147138623, 66617944908718798797835315300799681296382171232551202195227916587455945227658, 27280242198438797357248519182278586452353580897404583053780671607628567488785, 72366647275255146252476898397703781162817501020911030055986807469146441012211, 15693429824758577366090016253792024092118275998092271177740034382412934803761, 56876663056993943876573704560647660087756982498944618966351257861221533367945, 48850079825622141021623614347565040109014976045762021870196624634451645554325, 42935297677116598316922765239813369521103057703954888706060755437115203233825, 77676386141547827014222497453595139957288509399645134869173748515667162998868, 61692832566501415332602333064232720972841339038244230280775474725879067285342, 59935962915366705982417370015604163429623908211082078495545637225528882736151, 11169553746786570871826982502702306494122460399861473654590538509392678300829, 44977001882740172705747119252771484856754339378589430920436273404386756225160, 71322663318516410980295382780477116311548054659578019786245193556035790121374, 8679556081692766155713204363401339665554421957323214459774754684683898806431, 29148415342443285977921465793624876962360841618349722402533566785018046049424, 26865644187161015078019476789739496218677145936761329639161153671860915940618, 45087329624883102443141827440852362559512927376507034810399591235843124929968, 12960756134356540794580312293747037913909184765689308061091941063316718649360, 10489893987104833112024498494893757180965062620376522955416987720076763706072, 40989478373472156601839418863649825038329570556224239508593833995793883981434, 49702357292313541349527436910420037304364893415809268611405218313484615792675, 3393670940661161544587399243585206161967150988175766327035012996523332148891, 20478795575363230834220392160597964331545387928843850020354958899032305614266, 61642538818552605317484742325284153917596069814066012075251869233756881167880, 20935987281450018714604078956520889079208295992084806694975532945355183541588, 44670148732893145232572180224389070863612044327488381970087423692600064137323]
943526211458148402090198515882180426826215253055908690994965287737003397153
3c38fab9ec1b9993ed3ab457aac0c5a1af6fd945b305b9a971dc62eca39deb52062a0405ad1f0c20ac7d33e4a2836cbb
'''
```

赛题主要分为俩部分confusion1和confusion2

最后加密的使用的是一个AES加密，所以要得到flag就是要求解出key

先看confusion2函数，因为p参与了confusion1的运算，需要先把p算出来

已知的条件是n和s，从confusion2可以得到以下俩个等式

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-c05dd7056651c295dac1d4e45ffbc933405aef0a.png)

对于第二个式子，一般就要降幂，通过小费马定理  
![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-b7559eb07e5b855de1e6c45531f9b59101ca3a3e.png)  
将式子改造如下

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-1a468dbb4a8d8bbbba7644db454bb2fa1636ca76.png)

因为p和q是互质的，所以得到p+q = s

之后列二元一次方程进行求解，利用公式直接求解

```python
a = 1
b = -s 
c = n
import math
print((-b+gmpy2.iroot((b**2-4*a*c),2)[0])//(2))
#p=82489360571007005103156287602218122116425054717674044023016114841888353407607
```

得到p之后再看confusion1  
将key转成二进程，之后乘上pub数组对应的位置的数，进行累加，最后对p取模  
因为有一边都是0和1,这个问题可以转成从一个数组中挑选若干数进行相加求和，最后对p取模，现在给你这个数组和结果，要你求解挑选了哪些数。  
虽然整个数组只有64个，但要暴力也是不可能的，并且加上取模操作，时间消耗根本不可能  
当时对这个问题的概念也不清楚，只能在线搜索是否存在相关解法，感谢队友yyds。  
这里其实就是一个背包加密问题

背包加密问题
======

详细的我就不介绍了，这里就简单概括下

背包问题可以用如下式子表示

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-beecb8342f383563f7e1abcf6e4ce54e36a20854.png)

这里的x取值为0和1,表示的就是要明文的01表示，为了便于解密，a\_i使用了超递增序列（每个元素都比前面元素之和要大）

```python
{1，2，5，9，20}
```

这样解密就很方便了，从后往前推，如果W大于a\_i，那么x\_i= 1,反之x\_i=0。  
这里就存在一个特性，对于一个超递增序列，是很容易根据W,a求出明文，但对于一个无序序列，就非常困难，Merkle-Hellman公钥加密就利用这个特性，使用模数和逆元，加密时使用的是无序序列，解密时是超递增序列

无序序列和超递增序列的元素关系如下

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-c08ac760ad401883caaca21369b0aac4a0d854d6.png)

w就是私钥，b序列是无序序列和p一起作为公钥，解密时，将b序列乘上w^(-1)，转化为超递增序列

但该方法也存在问题，破译的基本思想是我们不一定要找出正确的乘数 w（即陷门信息），只需找出任意模数 `m′` 和乘数 `w′`，只要使用 `w′` 去乘公开的背包向量 B 时，能够产生超递增的背包向量即可。

知道这道题是可以这么解，但怎么找到这个模式和乘数呢，使用`LLL（Lenstra-Lenstra-Lovász）格基约化`算法求解，代码如下：

```python
c = #无序序列
p = #模数，这里的模数不是转换无序序列的模数，
#   而是题目对W进行取模，我们必须遍历所有的可能的结果:enc +i*p
for i in range(30):
    enc = 943526211458148402090198515882180426826215253055908690994965287737003397153+i*p
    nbit = 64

A = Matrix(ZZ,nbit+1,nbit+1)
    for i in range(64):
        A[i,i] = 1
    for i in range(64):
        A[i,nbit] = c[i]
    A[nbit,nbit] = -1*enc
    res = A.LLL()
    for i in range(65):
        M = res.row(i).list()
        flag = True
        for m in M:
            if m!=0 and m!=1:
                flag = False
                break
        if flag:
            print(i,M)
            M = ''.join(str(j) for j in M)
            M = M[:-1]
            print(M)
#1111111010100000011001101101110111110101001100101010010100101000
```

这个就是key了，带入最后的AES解密就OK了。为什么可以使用LLL算法，什么情况下可以使用LLL算法，接下来就分析这个问题。

LLL（Lenstra-Lenstra-Lovász）格基约化算法
=================================

在了解LLL算法之前，首先必须了解格的定义

**格** ：给定一组线性无关的基向量 v\_1,v\_2,v\_3,…,v\_n ,

```php
    那么这些基向量的所有整系数线性组合a_1v_1+a_2v_2+…+a_nv_n,a_i∈Z所形成的集合，就叫作这组基向量所张成的格。
```

在格密码中存在着几个困难问题，这里常见的有俩个：

**最短向量问题（The Shortest Vector Problem, SVP）**  
在 lattice 中找到一个最短非零向量。亦即，找到一个非零向量v使得|v| 最小。

**最近向量问题（The Closest Vector Problem, CVP）**  
给定一个不在L中的向量v(非整数) ，找到向量u，最小化 |v - u|.

LLL 算法可以看作是二维格上高斯约化算法在更高维数格上的扩展。LLL算法及其变种算法是目前已知在较低维度的lattice中求解。在最短向量问题中，解出来的解可能不止一个比如在二维中就有四个（0，1），（0，-1），（1，0），（-1，0）。当我们可以将问题转换为求解格上的最短向量问题是，就可以尝试使用LLL算法，背包问题虽然看起来是一个CVP问题，但在一些条件的约束可以将其转换成SVP问题，从而使用LLL算法进行求解。

还是回到最开始的那个题目中要求解的部分：

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-14731a0945b3e716215b1277ca8bcbbb8ce458a0.png)

现在已经知道pub和enc

先将这俩个转换成一个格上的(n+1)\*(n+1)的矩阵，如下：

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-d16ec11aee85219880edc8b3817c24d67bf117f9.png)

以行向量作为基向量可以写成，这些行向量都是线性无关的，可以形成一个格

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-3daf5314b5d5204c24711d4c464e93c71de6dac1.png)  
因为key是位于这个格上的，存在如下关系:

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-48660637385da6d5bd3e2d4c5a9b1dff4136cc2b.png)

因为x的取值不是0,就是1，所以|t| &lt; sqrt(n) ，而这个对于由n+1个基向量，每个向量都包含n+1个整数组成的线性组合来说都是非常稀有的，可以认为这个就是该格的最短向量，甚至可以认为这是唯一的。这样就把问题转变成一个SVP问题，就可以使用LLL算法就行求解。  
‍

NTRU
====

NTRU是一个带有专利保护的开源公开密钥加密系统，使用基于格的加密算法来加密数据。它包括两部分算法：NTRUEncrypt用来加密，NTRUSign用来进行数字签名。与其他流行的公钥加密系统不同，它可以防止被Shor算法破解，并显著提升了性能。

这里介绍的是NTRU的一个比较低端的版本。  
首先先选定一个公共参数q，该数会作为之后的加解密中的模数  
选择俩个比较小的整数f,g ，它们的关系要满足如下:

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-5b43db21ecc2a9b5fa2f2e2ec1367e5f57351576.png)  
这种关系主要从位数上进行比较，之后进行公钥的计算

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-ef7cdbab68d28132c156f608cd9f209d0f4e4e8d.png)  
加密：m为明文，r是一个随机数

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-506f2886c4cbf45109f56d36987160c769d90758.png)  
解密：

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-5ed3475837f8e755e99890d52b6247d0797a984a.png)  
这里的f的逆元是在模g之中，计算出的b就是m  
证明：

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-0493c5a99c2557ba49e072b368a77b6c62d56a92.png)  
此时a就是小于q的，不存在取模的情况，就是真实值。

之后就对g取模，去掉rg，再乘上f在g上的逆元，就可以得到m。  
在NTRU中，公钥就是（q,h）,私钥就是(f,g)。  
那如何破解呢，思路和之前的背包密码一样，找到另外一组私钥可以满足式子再进行解密就行了。  
F，G满足以下条件

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-dc565578ed714b20536806d5b6b66961e04d95bc.png)  
改写之后的可以写成一个格的形式:  
![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-f40e15b887e8d4a38e444a686638bf7750c571c3.png)  
存在（F,R）满足以下式子：

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-9c4779f48bc83b5968ce84fd9d26a6b4d7e43300.png)  
通常，该问题能够转成在格上求解SVP问题，也就是（F，G）就是格上的最短向量。

为什么这里（F，G）是该格的最短向量，这里直接贴论文分析

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-176453cf5326be8c4c9536cbef64591a82835acd.png)  
![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-a321c84c8e63839427ae060466151756a6c16c88.png)

根据NTRU这种形式构造的格的最短向量的长度大概就是sqrt(q)，而(F,G)的长度为sqrt(q/2+q/2)，所以（F,G）有很大的概率就是该格上的最短向量，并且由于是二维的，可以很容易有LLL算法进行求解。

\[羊城杯 2022\]LRSA
----------------

```python
import gmpy2
from pwn import *
from hashlib import sha256
import string
from Crypto.Util.number import *
from random import *

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

m=bytes_to_long(flag)

def getPQ(p,q):
    P=getPrime(2048)
    Q=getPrime(2048)
    t=(p*P-58*P+q)%Q
    assert (isPrime(Q))
    return P,Q,t

B=getRandomNBitInteger(11)
p=getPrime(B)
q=getPrime(B)
n=p*q
e=65537
c=pow(m,e,n)
P,Q,t=getPQ(p,q)

print("B=",B)
print("P*P*Q=",P*P*Q)
print("P*Q*Q=",P*Q*Q)
print("t=",t)
print("c=",c)
```

通过因式分解，可以得到P和Q  
根据getPQ函数列出等式  
![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-2f80db68ea1d0ae2f9eebd0e3f78ca9ec020f9b6.png)  
其中t,P,Q已知，显然可以构造以下格

![图片.png](https://shs3.b.qianxin.com/attack_forum/2023/06/attach-b95ca97c741e206c4dc1980aa64fbeaa014ce691.png)  
也就是现在(p-58,t-q),题目给的B=1023，t=44，也就是（p-58,t-q）的长度在1023左右，而该格的最短向量的长度为sqrt(Q) = sqrt(2^2048^)= 2^1024^ ，很大概率就是最短向量，使用LLL求解。

```python
from Crypto.Util.number import *
B = 1023
PPQ = 17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
PQQ = 17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
t = 44
c = 4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
e = 65537

PQ = gcd(PPQ,PQQ)
P = PPQ//PQ
Q = PQQ//PQ

L = matrix(ZZ,[[1,P],[0,Q]])
v = L.LLL()[0]
p_58,t_q = map(abs,v)
p = p_58+58
q = t_q+t
print(p)
print(q)

n=p*q
phi= (p-1)*(q-1)
d =inverse_mod(e,phi)
m = Integer(pow(c,d,n))
print(long_to_bytes(m))
DASCTF{8f3djoj9wedj2_dkc903cwckckdk}
```

总结
==

背包算法的安全性起源于背包难题，它是一个NP完全问题，虽然后来发现该算法并不安全，但是由于它证明了如何将NP完全问题用于公开秘钥密码学 ，具有学习价值。LLL 算法可以看作是二维格上高斯约化算法在更高维数格上的扩展，无法解决高维上的SVP问题，可以很好解决类似NTRU的加密算法。

参考：  
<https://gal2xy.github.io/2022/04/19/%E6%A0%BC%E5%AF%86%E7%A0%81%E5%AD%A6%E4%B9%A0%EF%BC%88%E4%BA%8C%EF%BC%89/>  
<https://lazzzaro.github.io/2020/11/07/crypto-%E6%A0%BC%E5%AF%86%E7%A0%81/index.html>  
<https://www.ruanx.net/lattice-1/>  
‍

发表于 2023-07-17 09:00:01
阅读 ( 5082 )
分类：其他

格基规约在ctf中的简单应用

0 条评论