Crypto

格密码

from Crypto.Util.number import *
from gmpy2 import invert
from flag import flag
flag = flag.encode("utf-8")
m = bytes_to_long(flag)


def strongGenerate():
    P = getStrongPrime(4096)
    while True:
        a = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = invert(a, P) * g % P
        return P, h, a


def strongEncrypt(p, h, a):
    random_int = getRandomNBitInteger(1000)
    cipher = (h * random_int + m * a) % p
    return cipher


p, h, a = strongGenerate()
c = strongEncrypt(p, h, a)
print("h=", h)
print("p=", p)
print("c=", c)
"""
h= 311970364425799366998489758816351964614898164597015962390522858760089331210269507769408330245745888541705059882396722340774681935443615888403494901415226651295201132556613291289590900246992553502513664561058230713840616052310750850144077552701142563872837663789636304968423919464707545482008647087312063949024744195318160335652074407874634742273493108112212110123691909346846612115479023950119286716243604630664235633831784083300431161225131883065150778501178458601885263943907964612851841356128492283759401129349655263360496418606534637831065564054627124545266130146585012568948018083420026867791483624987951876329968315410612748989452628410331813540143425873481351220499681815979569479285905651270208308396719282247586008816711527598915797885618862654168623002012746684102245733757428828517277952675441290263051618987121956646671901357370585784409633697165339182406341764320293630983680416055584947772382282259966044517683538433409836256995980804901093405108581243143413703339657071622279140236369465154220363993923085583049720512383384577159975134910449465903227555419552492606439149153015674603047695345700309870206034743317361786333732070962362572427411597266252707397451423195512449103367120235737550650354427690243524900449675
p= 958396606448120961344481821891302529131234571519205540072533929007120447482644938027839069855225984909598017115601687321093037138370623689366302399472755221666720998204960391688686871213784218139146955110040572010513513710257471193690475085340782434134757767894370195789546551282060123540167285748706110004061656181247087025993389812671658906912145384679566372037915179523706023309666826191629634851598509448675340758156737530185937223948687001934035933966720541257653562031308634592003639145311246147664928094381997264652669457904886666262851691565920076364034433600062253014377522558972668765617631467665085324790312091927917199333642804731490452686230714946707520153374983386856748968281865500447110447064499127304576389450231449458997253721401398074788997192735673939296531420329207264490272774186484762804708405995307032141715953080254098506768585899454119852852002578252291310329200959476618660765556861112558404254680356703540148703891793429589128285327230398620737214653509556883409293525132433655639546382948760666188308135216174434756100646981938900940757869329579150360836505992616459066632938605335205569767007863591747811468281490752448411521431430302168214014717351186242150709061058943921599462022604009950194741903607
c= 767158168672362136291238223905378538545444315829681403660668665037917788547250510431680762324989504337886911129872811283399423182492713085621340850466620775416712732614020830060267436728824312319343522189998875569791210615658554329492772575522352284894778864900683043087475949382767603528807809596004213194946687583749277851731545121301799909443549367647188538291294493900118514585149301404415365107375148502163345229200555520367376148986792681776613941685900525114359918025093194374564154918465789098039688273260831196880453048787881692220588699313824407443049610470566611891830120455606865304514498141918370250200060333776115471607369861567714061571248634366226901360555240991881037749649258353302128601187117945261098036478588953880956746052307508140721683848770369771427200654010686745459084737649483182116223928908511586372587312845173805333061611628627699056444060210866689908925857413693914088384801590539118419817748706914585535977225375257595014121709225398146804929559026288825337416874187757876993164395155899845807880799091660701491902131855351054079661782867046531376623992742661604584530403794933640735943298254524984623808363772872836875750554022138997087590785362832339405833456398277842368920260448389099114876068641
"""

根据加密代码，有如下关系式$$ \left\{ \begin{align} h & \equiv a^{-1} \cdot g \mod P \\ c & \equiv (r \cdot h + m \cdot a) \mod P \end{align} \right.$$ $$ \begin{bmatrix} k & a \end{bmatrix} \begin{bmatrix}p & 0 \\ h & 1\end{bmatrix} = \begin{bmatrix} g & a \end{bmatrix}$$

可化为$ g = a \cdot h + k \cdot P$，根据此式构建格。但需要确定k还是a作为第二个参数。转化一下求密文c的公式。

$$c \cdot a \equiv (r \cdot g + m \cdot a^2)\ mod \ P \\m \cdot a^2 \equiv ((c \cdot a) \ mod P \ )\ mod\ g \\m \equiv ((c \cdot a) \ mod P \ ) \cdot a^{-2} mod\ g$$

我们选定a。构建格$$ \begin{bmatrix} k & a \end{bmatrix} \begin{bmatrix}p & 0 \\ h & 1\end{bmatrix} = \begin{bmatrix} g & a \end{bmatrix}$$

m = Matrix([[p, 0], [h, 1]])  
g, a = m.LLL()[0]  
f = (a * c % p) * inverse_mod(a^2, g) % g  
  
print(bytes.fromhex(hex(f)[2:]))

DSA签名

from multiprocessing import Process  
import os  
import random  
import socket  
from ecdsa import ecdsa as ec   
from datetime import datetime  
RNG = random.Random()  
import hashlib  
  
g = ec.generator_192  
N = g.order()  
secret = RNG.randrange(1, N)  
PUBKEY = ec.Public_key(g, g * secret)  
PRIVKEY = ec.Private_key(PUBKEY, secret)  
  
BANNER = """  
Welcome to Hust Signer. What do you want to do?  
1) Make signature  
2) Get the flag >"""  
  
def read_line(s):  
    body = b""  
    while True:  
        ch = s.recv(1)  
        if ch == b"\n":  
            break  
        body = body + ch  
    return body  
  
  
  
def go(s):  
    try:  
        s.send(BANNER.encode())  
        line = read_line(s)  
        if line == b"1":  
            now = datetime.now()  
            time = now.strftime("%H:%M:%S")  
            random_data = f"{RNG.getrandbits(512):x}"  
            hash = int(hashlib.md5(f"{time}:{random_data}".encode()).hexdigest(), 16)  
            nonce = RNG.randrange(1, N)  
            signature = PRIVKEY.sign(hash, nonce)  
            s.send(f"{signature.r}, {signature.s}, {hash}\n".encode())  
        elif line == b"2":  
            now = datetime.now()  
            time = now.strftime("%H:%M:%S")  
            to_check = int(hashlib.md5(f"{time}:get_flag".encode()).hexdigest(), 16)  
            s.send(f"Get signature for md5(\"{time}:get_flag\")\n".encode())  
            try:   
                sig_line = read_line(s).decode().split(",")  
            except ValueError:  
                s.send("Error!".encode())  
            sig = ec.Signature(int(sig_line[0]), int(sig_line[1]))  
            if PUBKEY.verifies( to_check, sig ):  
                s.send(b"Congratulation! Here is your flag:")  
                f = open("/flag", "r")  
                flag = f.read()  
                f.close()  
                s.send(flag.encode())  
            else:  
                s.send(b"Failed!\n")  
        else:  
            s.send(b"What?")  
    except socket.timeout:  
        print("Exit via timeout!")  
    finally:  
        s.close()  
      
if __name__ == '__main__':  
    s = socket.socket()  
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)  
    s.bind(("0.0.0.0", 8000))  
    s.listen(10)  
    while True:  
        client, addr = s.accept()  
        print(f"Got connect from {addr}")  
        p = Process(target=go, args=(client,))  
        p.daemon = True  
        p.start()  
        client.close()

ECDSA中r由随机数k以及生成元G生成。
注意到每次生辰signature所给的r相同。这说明随机值k相同。

即r相同
我们获取两次signature，来破解k与d
再申请下一次签名所用的时间，生成签名

import hashlib

from Crypto.Util.number import inverse

r = 4672667200964722149623422575414394567666891392104258711792  
s1 = 1380082547722347378199432499915005653260602000840320490370  
h1 = 265628125087488969453564701837010287748  
  
  
s2 = 6206469118472605849488707538555465546857317706194151509947  
h2 = 284612552192339916331883431288259294492  
n = 0xffffffffffffffffffffffff99def836146bc9b1b4d22831  # ECDSA 使用的 n 值  
# 根据公式计算私钥 dnumerator = (h1 - h2) % n  
denominator = (s1 - s2) % n  
k = (numerator * inverse(denominator, n)) % n  
print(f"[+] Recovered k: {k}")  
  
# 利用 k 计算私钥 dd = ((s1 * k - h1) * inverse(r, n)) % n  
print(f"[+] Recovered private key d: {d}")

time = "20:36:14"  
to_check = int(hashlib.md5(f"{time}:get_flag".encode()).hexdigest(), 16)  
  
s_new = (inverse(k, n) * (to_check + d * r)) % n  
print(f"[+] New signature: r = {r}, s = {s_new}")

简单RSA

from Crypto.Util.number import getPrime,bytes_to_long
with open("flag.txt","rb") as f:
    flag = f.read().strip()
m = bytes_to_long(flag)
e = 65537


for x in range(10):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    c = pow(m, e, n)

    print("n =", n)
    print("c =", c)

多组n，c且使用相同e进行加密。提取不同n的公因子。

import sys
from functools import reduce

import gmpy2
import libnum
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
from gmpy2 import *

n = [n0, n1, n2, n3, n4, n5, n6, n7, n8, n9]
c = [c0, c1, c2, c3, c4, c5, c6, c7, c8, c9]

for i in range(len(n)):
    for j in range(len(n)):
        if(i!=j):
            if(gmpy2.gcd(n[i],n[j])!=1):   #求出最大公约数(p)
                print(i,j)                 
                p = gmpy2.gcd(n[i],n[j])
                print("p = ",p)
                q = n[i] // p
                print("q = ",q)
                d = gmpy2.invert(e , (p-1)*(q-1))
                print("d = ",d)
                m = pow(c[i],d,n[i])
                print("m = ",m)
                print(libnum.n2s(int(m)))

分组密码工作模式

import os
import socket
from multiprocessing import Process
from Crypto.Cipher import AES
auth_key = os.urandom(16)


def getFlag():
    try:
        with open("/flag","r") as f:
            flag = f.read()
        f.close
    except Exception:
        return "error"
    return flag


MENU = """
Enter your choice:
1) Create HUSTCTFer Account
2) Create Admin Account
3) Login
4) Exit
"""

def read_line(s):
    body = b""
    while True:
        ch = s.recv(1)
        if ch == b"\n":
            break
        body = body + ch
    return body

def go(s):
    try:
        s.send("Only admin can get the flag ! \n".encode())
        while True:
            s.send(MENU.encode())
            line = read_line(s)
            if line == b"1":
                token = b'HUSTCTFer!______'
                user_key = os.urandom(16)
                cipher = AES.new(auth_key, AES.MODE_CBC, user_key)
                code = cipher.encrypt(token)
                s.send(f'here is your token: {user_key.hex() + code.hex()} \n'.encode())
            elif line == b"2":
                s.send('Not Admin !!!!!!'.encode())
            elif line == b"3":
                s.send("Enter your token > \n".encode())
                try:
                    authcode = read_line(s).decode()
                    user_key = bytes.fromhex(authcode)[:16]
                    code = bytes.fromhex(authcode)[16:]
                    cipher = AES.new(auth_key, AES.MODE_CBC, user_key)
                    token = cipher.decrypt(code)
                except Exception as e:
                    s.send("Decrypt error\n".encode())
                    break
                if token == b'AdminAdmin!_____':
                    s.send("Hello Admin! Here is your FLAG: ".encode())
                    flag = getFlag()
                    s.send(flag.encode())
                    break
                elif token == b'HUSTCTFer!______':
                    s.send('Have fun!!\n'.encode())
                    break
                else:
                    s.send('Who are you?\n'.encode())
                    break
            elif line == b"4":
                s.send('ByeBye\n'.encode())
                break
            else:
                s.send('WTF\n'.encode())
        s.close()
    except socket.timeout:
        print("Exit for timeout!")
    finally:
        s.close()


if __name__ == '__main__':
    s = socket.socket()
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    s.bind(("0.0.0.0", 7000))
    s.listen(10)
    while True:
        client, addr = s.accept()
        print(f"Got connect from {addr}")
        p = Process(target=go, args=(client,))
        p.daemon = True
        p.start()
        client.close()

CBC模式前一个密文分组与之后的明文异或后在加密成密文。本质上将“HUSTCTFer!______”形成的密文机密后以“AdminAdmin!_____”为明文（都是16字节，恰好一个组）。利用字节反转攻击，我们可以将user_key（初始向量，可看作前一组密文）与这两个明文异或，重新生成token。这样解密时code相当于与自身以及“AdminAdmin!_____”异或，得到AdminAdmin!_____。

token = "230b1db61e3a087d391317067431636216ecb4e238d34c110b08c7137808aa4a"
iv = bytes.fromhex(token[:32])

t1 = b'HUSTCTFer!______'
t2 = b'AdminAdmin!_____'

iv2 = b''

for i in range(16):
    k = t1[i]^t2[i]^iv[i]
    iv2 += k.to_bytes(1, "big")
iv = iv2
token = iv.hex() + token[32:]
print(token)、

古典密码破译

已知一个密码体制是$Z^{127}$​上的三阶Hill密码，明密文空间均为ASCII码为0-126的字符，短块处理方式为：如果明文是3的整数倍，则补充3个空格’\x20’;如果明文不是3的整数倍，那么就补充1到2个空格直到明文总长度为3的倍数。现在已知一密文为
>u\x10l9\npI,0\x04^J\x00ib\x03\x0c\x158d\x1f\x08Ixk\nF\x19fz\x14PT\x04\x03>R~

它是对’vmc{}’型flag加密的结果，那么flag= ？

我们只考虑明文的其中3行，即第一行（全已知），第二行（2个未知），最后一行（0~2个已知）。

以最后一行125 32 32 为例（暴力枚举两个元素，如x 125 32需暴力3个），枚举后首先检查是否可逆，可逆通过解线性方程求出密钥矩阵k，再对密文解密查看是否符合明文标准（全字符字母）。剩余可自行修改数据尝试。

  
from Crypto.Util.number import *  
  
r = b'>u\x10l9\npI,0\x04^J\x00ib\x03\x0c\x158d\x1f\x08Ixk\nF\x19fz\x14PT\x04\x03>R~'  
a = [int(x) for x in r]  
  
print(a)  
elements = [118, 109, 99, 123, 0, 0, 125, 32, 32]  
p = matrix(Zmod(127), 3, 3, elements)  
  
elements = [62, 117, 16, 108, 57, 10, 62, 82, 126]  
  
c = matrix(Zmod(127), 3, 3, elements)  
  
for i in range(0, 127):  
    for j in range(127):  
        p[1, 1] = j  
        p[1, 2] = i  
        f = True  
        if p.is_invertible() is True:  
            k = p.solve_right(c)  # pk = c
            d = ''  
            for kk in range(13):  
                tmp = matrix(Zmod(127), 1, 3, a[kk * 3 : (kk + 1) * 3])  
                A = k.solve_left(tmp)  
                for l in range(3):  
                    char = chr(A[0, l])  
                    if not char ==' ' and not char.isprintable():  
                        f = False  
                        break                    d += char  
                if f is False:  
                    break  
            if f is True:  
                print(f'123 {i} {j} | {d}')

RSA加密算法

from Crypto.Util.number import *
from sympy import nextprime

flag = 'vmc{****************}'

part1 = flag[:19]
part2 = flag[19:]
assert (len(flag) == 37)

p1 = getStrongPrime(1152)
p2 = nextprime(p1)
try:
    if p2 - p1 > 1000:
        raise Exception("Error")
except:
    exit()

q1 = getStrongPrime(512)
q2 = nextprime(q1)

n1 = p1 * p1 * q1
e1 = getStrongPrime(1024)
msg1 = bytes_to_long(part1.encode())
c1 = pow(msg1, e1, n1)

n2 = p2 * p2 * q2
e2 = nextprime(e1)
msg2 = bytes_to_long(part2.encode())
c2 = pow(msg2, e2, n2)

output = open('secret.txt', 'w')
output.write('n1=' + str(n1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('e1=' + str(e1) + '\n')
output.write('n2=' + str(n2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('e2=' + str(e2) + '\n')
output.close()

将flag分成两部分进行加密。生成两个大素数（非常接近）p1, p2
生成两个较小素数（非常接近）q1,q2
$n_1 = p_1^2\cdot q_1$$n_2 = p_2^2 \cdot q_2$
之后用两个相近素数e加密。和普通wiener-attack不同的是，e和n没有近到相除约为1的地步，相差还是很大，即 解密指数d也许很大，解不出来。

e和n的关系不符合利用条件，但是$n_1$ 和 $n_2$的关系却符合。
$\frac{n_1}{n_2} = (\frac{p_1}{p_2})^2 \cdot \frac{q_1}{q_2}$

显然$\frac{n_1}{n_2} < \frac{q_1}{q_2}$
所以q1/q2在区间(N1/N2,1)之间。尝试对N1/N2进行连分数展开并求其各项渐进分数

import gmpy2
from Crypto.Util.number import *
import sympy
def continuedFra(x, y):
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    numerator = 0 # 分子
    denominator = 1 # 分母
    for x in cf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator

def getGradualFra(cf):
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(e, n):
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for q2,q1 in gf:
        if q1 == 0: continue
        if N2 % q2 == 0 and q2 != 1:# 此处也可写成 N1 % q1 == 0 and q1 != 1
            return q2


N1=27682578737141139764880192910976946263355689816882797515059917479242862799083599745594956880258244112867559722435850732812023189662581052511287867553308318268020022386306820424829898858029986193412922645944359409248568131057377380697236238480724883073062491532254626363468032145049953168789073328812076794158602028961853986034378144749656228541552641207393473830715156452473432130040360471566096165146087202836036783304640579183082301858529818598032339821237841219774124710789761912675044056265735587753304064079484844965820681168729776560497921764083742448045654891113500035063474318442078036531813957551086231747079155691690001433127187382636049871228279519466735719768798574776353687049667125384146566107739705553580693984918816215940308884007192621418304753551998125658993859095063641090798574130161651257890916914325076137436869018454577522833
c1=14360977893873474578201937159000122429359790977572665232657843468076201963407780015131857192621550737338805880514393357390576423731328871867241029260294051045710144482989801857054158816998897546124709802730198690244128545073634486145786763294634081834588146373913232490890078533918320777534358739106486350300547206365723045306767038214923412032633833255742963954701475401704385045019069883734625251436409851588044241336835452728962860280865504000103361559688861149086469939940113748174610019620309023214292662384279070127090992947332945432141695583191136521301940116585610033790348125114471980285332011918355578839128892075058698885319243593345096734776497817461251643381989958326810478500026684389358920342021836572511688796450072700142033952403561408907486022094802237175920044147084170050294965826258250618675638343726352907476393474128674488943
E1=138906518221471521524404330039616633297752765534176570868900039237133419857485415639423196636068397237296224442083213768630488100717977884415342104239280950424735129147986053115335928783190377695248250926374734988108972136349625965753649992146322810352768246041575396721661142246729747572832017510241749082431
N2=27682578737141139764880192910976946263355689816882797515059917479242862799083599745594956880258244112867559722435850732812023189662581052511287867553308576254232706953290519059976159239205559295965110148734449650209977235953163255494808056707188551192674128213090005439928085856216617642935948961573449294338310127166077195263402939848861686214485115686799032901147314759348481062418109120418661302585413868782602282463165171129063197961455779193665041902822948963032580054067050227612838335828201043413949164885293325493829570131849345344856137656453666135670724974184749115550720826497558763320127218251970576144750319782121194483563545371157323166968983176013145267856898865437101799958588342741257457472036311490402279982286349929050116350394664561659857216725849236910894778018502118673902399095646487808462155207034764432342699549109080808769
c2=11293777290569693972360166961981727494638218221438571150393361751316389824613571820229370915191500766619410597117671232443452691634734112652285521806824284959073558010661204730954928847260946403867297932862687770449632506087883187920107766050673462588812979708792790888354008526054467620780053118019643408427959406056087370960170992834047890080269663747877143270683069575318397144844481262382463469080755423097527007161449411933936669451476467352049264455203632729909164666006688294056405955940041007137719228484035343153943155100892867641033645111253109951972003798413524003505574000784399458705347262353155363413513341797868942085136977548116650815336000627353933708913237438841909324920070013498153627767891674969586034872104569344923832761239959420543717354211689339868787331074579605476477152218068810732089913023456240425720821047030224659918
E2=138906518221471521524404330039616633297752765534176570868900039237133419857485415639423196636068397237296224442083213768630488100717977884415342104239280950424735129147986053115335928783190377695248250926374734988108972136349625965753649992146322810352768246041575396721661142246729747572832017510241749082619
Q2=wienerAttack(N1,N2)
Q1 = sympy.prevprime(Q2)
P1 = gmpy2.iroot(N1 // Q1,2)[0]
P2 = sympy.nextprime(P1)
phi1 = P1 * (P1 - 1) * (Q1 - 1)
phi2 = P2 * (P2 - 1) * (Q2 - 1)
d1 = gmpy2.invert(E1,phi1)
d2 = gmpy2.invert(E2,phi2)
m1 = pow(c1,d1,N1)
m2 = pow(c2,d2,N2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

LFSR

from Crypto.Util.number import *  
from gmpy2 import *  
from SECRET import key  
import string  
import random  
  
FLAG = b"vmc{*****************************}"  
  
def get_random_flag(flag):  
    table = string.ascii_letters+string.digits  
    for _ in range(50-len(FLAG)):  
        flag += random.choice(table).encode()  
    return flag  
  
FLAG = get_random_flag(FLAG)  
print(len(FLAG))  # 50  
print(len(key))   # 5  
  
class LFSR:  
    def __init__(self):  
        self.msg = list(map(int,list(bin(bytes_to_long(FLAG))[2:].rjust(400,'0'))))  
        for _ in range(2024):  
            self.run()  
  
    def run(self):  
        bit = self.msg[0]  
        new = 0  
        for i in key:  
            new ^= self.msg[i]  
        self.msg = self.msg[1:] + [new]  
        return bit  
  
ILOVEHUST = LFSR()  
for _ in range(2024):  
    print(ILOVEHUST.run(), end='')  
  

加密首先将flag填充至50长度。将FLAG的二进制表示转换为一个长度为400的整数列表，其中每个整数要么是0要么是1，代表二进制位。

LFSR我们知道2*n长度的密文，则可以构建矩阵求解（因为矩阵在模二情况下不可逆，我们用求解线性方程的方式求解C）

#sage
binary_str = ""  
  
# Step 2: 构造 400x400 的 LFSR 解密矩阵 X，使用 GF(2) 模  
n = 400  
X = Matrix(GF(2), n, n, lambda i, j: int(binary_str[i + j]))  
  
  
S_401 = vector(GF(2), [int(binary_str[i]) for i in range(400, 800)])  
  
    # Step 4: 解线性方程组 X * result = S_401try:  
    result = X.solve_right(S_401)  
    print("解密后的向量:", result)  
except ValueError as e:  
    print("无法解方程组:", e)  
  
one_positions = [i for i in range(len(result)) if result[i] == 1]  
print("解密向量中 1 的位置:", one_positions)

逆向运行2024次，得到初始msg

class LFSR:  
    def __init__(self, key, output_sequence):  
        self.key = key  
        # 假设从输出序列反推得到的状态  
        # 为了简化，这里初始化一个与输出序列长度相同的状态列表（实际情况中要从输出序列推算）  
        self.msg = [int(bit) for bit in output_sequence]  # 初始化为输出序列  
        for _ in range(2024):  
            self.run()  
  
    def run(self):  
        # 获取当前 LFSR 状态  
        bit = self.msg[399]  
        new = 0  
        # 根据 key 索引计算反馈值  
  
        new ^= self.msg[14]  
        new ^= self.msg[105]  
        new ^= self.msg[202]  
        new ^= self.msg[351]  
        new ^= self.msg[391]  
        # 更新 LFSR 状态  
        self.msg = [new] + self.msg[:-1]  
        #print(new)  
  
  
  
# 初始化LFSR并进行回推  
lfsr = LFSR(key, output_sequence)  
print(lfsr.msg)

msg = []
  
  
binary_string = ''.join(map(str, msg))  # 先将二进制列表拼接成一个字符串  
  
# 将二进制字符串转为整数  
integer_value = int(binary_string, 2)  
print(integer_value)  
print(long_to_bytes(integer_value))

flag还原开头字母不是v，不影响，改成v后提交。

D-H密钥交换

def generate_key(p):  
    pri_key = getrandbits(1024)  
    pub_key = pow(7, pri_key, p)  
    return pri_key,pub_key  
  
def diffie_hellman(p, flag):  
    a,A = generate_key(p)  
    b,B = generate_key(p)  
  
    superkey = pow(B, a, p)  
    m = bytes_to_long(flag)  
    return (m * superkey) % p, A, B  
  
  
def go(input:Callable[[str],None], print:Callable[[str],None]):  
    p = int(input("P = "))  
    if isPrime(p) and p.bit_length() >= 1024:  
        c, a_pubKey, b_pubKey = diffie_hellman(p, getFlag())  
        print("Alice公钥: {}".format(a_pubKey))  
        print("Bob公钥: {}".format(b_pubKey))  
        print("密文: {}".format(c))  
    else:  
        print("非法 P")

p我们自选，可以构造平滑数来使离散对数问题易解。

注意生成的是1024位，不符合的重新生成。

from Crypto.Util import number  
import random  
  
def generate_smooth_prime(bits=1024):  
    # 预先选择一组较小的质数  
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]  
    p = 1  
  
    # 构造 p-1，使得它由多个小质数因数组成  
    while p.bit_length() < bits - 1:  
        prime = random.choice(small_primes)  
        p *= prime  
  
    # 调整 p 使其接近 1023 位  
    remaining_bits = bits - p.bit_length()  
    if remaining_bits > 0:  
        p *= random.getrandbits(remaining_bits) | 1  # 确保生成的数字为奇数  
    p += 1  # 令 p-1 满足条件  
  
    # 检查 p 是否为素数  
    if number.isPrime(p):  
        return p  
    else:  
        return generate_smooth_prime(bits)  
  
# 生成一个符合条件的 1024 位素数  
p = generate_smooth_prime(1024)  
print("生成的素数 p:", p)  
print("p 的位数:", p.bit_length())

暴力求解

from sympy import factorint, mod_inverse, discrete_log  
  
# 给定的 p, g, A
p = 
g = 7  
A =   
  
# 使用 SymPy 库进行离散对数计算  
try:  
    a = discrete_log(p, A, g)  
    print(f"求得 a = {a}")  
except ValueError as e:  
    print("无法快速求解离散对数:", e)

正常解flag

from Crypto.Util.number import inverse, long_to_bytes  
  
p = 
g =   
A = 
B =  
c = 
  
a = 
sk = pow(B, a, p)  
  
d = inverse(sk, p)  
m = (c * d) % p  
print(long_to_bytes(m))