EasyRSA

题目

#encoding:utf-8
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2

class RSAEncryptor:
    def __init__(self):
        self.g = self.a = self.b = 0
        self.e = 65537
        self.factorGen()
        self.product()

    def factorGen(self):
        while True:
            self.g = getPrime(500)
            while not gmpy2.is_prime(2*self.g*self.a+1):
                self.a = random.randint(2**523, 2**524)
            while not gmpy2.is_prime(2*self.g*self.b+1):
                self.b = random.randint(2**523, 2**524)
            self.h = 2*self.g*self.a*self.b+self.a+self.b
            if gmpy2.is_prime(self.h):
                self.N = 2*self.h*self.g+1
                print(len(bin(self.N)))
                return

    def encrypt(self, msg):
        return gmpy2.powmod(msg, self.e, self.N)


    def product(self):
        with open('/flag', 'rb') as f:
            self.flag = f.read()
        self.enc = self.encrypt(self.flag)
        self.show()
        print(f'enc={self.enc}')

    def show(self):
        print(f"N={self.N}")
        print(f"e={self.e}")
        print(f"g={self.g}")


RSAEncryptor()

题解

common prime RSA

已知g，跑脚本，发现出不来，可能是n太大了

g<a+b l论文题

WriteUps of MRCTF2021(Crypto) - Hao Jiang (d33b4t0.com)

D=iroot(right-left,2)[0]

D=left+k*D+i

爆破k,i

from Crypto.Util.number import *
from gmpy2 import iroot
n=49772654129918657265017224959299193495254216585967338739168650086191861452300412241047407950798411859067491869373788703824137456447978969803056902795716761959456067322414974169421894154465055989257454095985468450965871903811764399815267585258819854363996386931089197996828905892681960861726159749735774108745226042906570756722357743172225643921367590629441403631522125208757797647194016249362483845335014324978898865368651612654770948881872945053238350136592858869040599417498072502578977509399218927696625823452901084714222938417072759781842694565170281682723041605537728448510423962109995153717150631738378455222143
e=65537
g=2609290269584876920945282873479122171178002733919064880382724262163153884664689961266033962348331708825468959551801467334031011446564187579427413906013
enc=8746228432198832861930372453161088485197230618631505905414017869471355572344313577427383903965789443478715003718363394360186991846873876398410009152511266623674374274283784883312995156935241021352151414458858673836877962149382867511081524115963592083483210153140792701514143301995333969969720387297837376730082792179388710037042252702035179813508558042408844638147209995246943768994171598974221817596785121808048589249601097296707973010675362719565455350535238171942291239855095128733387738770119373232485878725070488565456741677674517927469025903637807463975221698069881171348847239113426711052607025112106263748508


beta = 2*g
s = (n-1)//beta
u = s//beta
v = s% beta

left = (2*int(sqrt(n))//beta-2-v)//beta
right = (3*int(sqrt(2)*sqrt(n))//(2*beta) - 2 - v )//beta
print(left)
print(right)
print(right-left)
print(iroot(right-left,2))

D = iroot(right - left , 2)[0] + 1
b = pow(2 , beta, n)
dic = {}
base = int(pow(b , left , n))
diff = int(pow(b , D , n))
for i in range(D+1):
    temp = base & 0xfffffffffff
    if temp in dic:
        print(i)
    dic[temp] = i
    base *= diff
    base %= n
print('baby step done')
base = pow(b , u , n)
diff = inverse(b , n)

for i in range(D + 1):
    temp = int(base) & 0xfffffffffff
    if temp in dic:
        print(i , dic[temp])
        c = left + dic[temp]*D + i
        xy = u - c
        x_y = v + c * beta
        temp = iroot(x_y ** 2 - 4 * xy, 2)[0]
        x = (x_y + temp) // 2
        y = (x_y - temp) // 2
        p = x * beta + 1
        q = y * beta + 1
        d = inverse(e, (p-1)*(q-1))
        print(long_to_bytes(int(pow(enc, d, n))))
    base *= diff
    base %= n

apbq

题目

I obtained several sets of ap + bq through channel measurement. Can you solve it?

from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys

class RSA():
    def __init__(self, privatekey, publickey):
        self.p, self.q, self.d = privatekey
        self.n, self.e = publickey

    def encrypt(self, plaintext):
        if isinstance(plaintext, bytes):
            plaintext = bytes_to_long(plaintext)
        ciphertext = pow(plaintext, self.e, self.n)
        return ciphertext

    def decrypt(self, ciphertext):
        if isinstance(ciphertext, bytes):
            ciphertext = bytes_to_long(ciphertext)
        plaintext = pow(ciphertext, self.d, self.n)
        return plaintext

def get_keypair(nbits, e = 65537):
    p = getPrime(nbits//2)
    q = getPrime(nbits//2)
    n = p * q
    d = inverse(e, n - p - q + 1)
    return (p, q, d), (n, e)

if __name__ == '__main__':
    pt = './output.txt'
    fout = open(pt, 'w')
    sys.stdout = fout

    block_size = ceil(len(flag)/3)
    flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
    e = 65537

    print(f'[+] Welcome to my apbq game')
    # stage 1
    print(f'┃ stage 1: p + q')
    prikey1, pubkey1 = get_keypair(1024)
    RSA1 = RSA(prikey1, pubkey1)
    enc1 = RSA1.encrypt(flag[0])
    print(f'┃ hints = {prikey1[0] + prikey1[1]}')
    print(f'┃ public key = {pubkey1}')
    print(f'┃ enc1 = {enc1}')
    print(f'----------------------')

    # stage 2
    print(f'┃ stage 2: ai*p + bi*q')
    prikey2, pubkey2 = get_keypair(1024)
    RSA2 = RSA(prikey2, pubkey2)
    enc2 = RSA2.encrypt(flag[1])
    kbits = 180
    a = [getRandomNBitInteger(kbits) for i in range(100)]
    b = [getRandomNBitInteger(kbits) for i in range(100)]
    c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
    print(f'┃ hints = {c}')
    print(f'┃ public key = {pubkey2}')
    print(f'┃ enc2 = {enc2}')
    print(f'----------------------')

    # stage 3
    print(f'┃ stage 3: a*p + q, p + bq')
    prikey3, pubkey3 = get_keypair(1024)
    RSA3 = RSA(prikey3, pubkey3)
    enc3 = RSA2.encrypt(flag[2])
    kbits = 512
    a = getRandomNBitInteger(kbits)
    b = getRandomNBitInteger(kbits)
    c1 = a*prikey3[0] + prikey3[1]
    c2 = prikey3[0] + b*prikey3[1]
    print(f'┃ hints = {c1, c2}')
    print(f'┃ public key = {pubkey3}')
    print(f'┃ enc3 = {enc3}')

题解

stage1:p+q

hints = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
public_key = (89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589, 65537)
enc1 = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247
n, e = public_key
# p*(hints-p) = n
from gmpy2 import iroot
from Crypto.Util.number import *

de = hints**2 - 4*n
p = (hints + iroot(de, 2)[0]) // 2
q = n // p
print(long_to_bytes(pow(enc1, inverse(e, (p-1)*(q-1)), n)))
# b'flag{yOu_can_'

stage2: aip + biq

c = [a[i]*prikey2[0] + b[i]*prikey2[1]

hints = 
n,e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
enc2 = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244

import itertools
from Crypto.Util.number import long_to_bytes

V = hints
k = 2^800
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]

for s, t in itertools.product(range(4), repeat=2):
    T = s*B[0] + t*B[1]
    a1, a2, a3 = T[:3]
    kq = gcd(a1 * hints[1] - a2 * hints[0], n)
    if 1 < kq < n:
        print('find!', kq, s, t)
        break

p = 9067773077510925207378520309595658022345214442920360440202890774224295250116442048990578009377300541280465330975931465993745130297479191298485033569345231
q = n // p
print(long_to_bytes(pow(enc2, inverse(e, (p-1)*(q-1)),n)))
b's0lve_the_@pb'

stage3

第三部分他是用的第二部分的rsa进行加密的

enc3 = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
print(long_to_bytes(pow(enc3, inverse(e, (p-1)*(q-1)),n)))
b'q_prob1em!!}'

21 step

题目

import re
import random
from secrets import flag
print(f'Can you weight a 128 bits number in 21 steps')
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'

command = input().strip()
assert command[-1] == ';'
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])

step = 21
for i in command[:-1].split(';'):
    t = i.translate(str.maketrans('', '', '=AB0123456789'))
    if t in ['>>', '<<', '+', '-', '&', '^']:
        step -= 1
    elif t in ['*', '/', '%']:
        step -= 3
if step < 0:exit()

success = 0
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
for _ in range(100):
    A = random.randrange(0, 2**128)
    wa = w(A)
    B = 0
    try : exec("global A; global B;" + command)
    except : exit()
    if A == wa:
        success += 1

if success == 100:
    print(flag)

题解

题目要求我们用21步求出128比特随机数的汉明重量。

找到variable-precision SWAR算法，让AI写一个128比特的实现代码。

def variable_precision_swar(A):
    # Step 1: Initialize the counter
    B = 0

    # Step 2: Parallel calculation of 4-bit Hamming weights
    A = (A & 0x55555555555555555555555555555555) + ((A >> 1) & 0x55555555555555555555555555555555)
    A = (A & 0x33333333333333333333333333333333) + ((A >> 2) & 0x33333333333333333333333333333333)

    # Step 3: Combine intermediate results
    A = (A + (A >> 4)) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F
    A = (A + (A >> 8)) & 0x00FF00FF00FF00FF00FF00FF00FF00FF
    A = (A + (A >> 16)) & 0x0000FFFF0000FFFF0000FFFF0000FFFF
    A = (A + (A >> 32)) & 0x00000000FFFFFFFF00000000FFFFFFFF
    A = (A + (A >> 64)) & 0x0000000000000000FFFFFFFFFFFFFFFF

    # Step 4: Extract the final result
    B = A & 0x7F  # The result is in the lower 7 bits

    return B

# Test the function
import random

def test_variable_precision_swar():
    for _ in range(100):
        A = random.randrange(0, 2**128)
        expected = bin(A).count('1')
        result = variable_precision_swar(A)
        if result != expected:
            print(f"Failed for {A}: expected {expected}, got {result}")
            return False
    print("All tests passed!")
    return True

test_variable_precision_swar()

按上面代码改写成符合要求的表示是，每一行需要4步，一共七步，完全不够用。

经过尝试以后发现，以下这几步中，最后&0x??????????????????????，这一操作可以忽略，并不影响结果，只需要最后&0x7f即可。这样以下运算只需要10+1步。

# Step 3: Combine intermediate results
A = (A + (A >> 4)) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F
A = (A + (A >> 8)) & 0x00FF00FF00FF00FF00FF00FF00FF00FF
A = (A + (A >> 16)) & 0x0000FFFF0000FFFF0000FFFF0000FFFF
A = (A + (A >> 32)) & 0x00000000FFFFFFFF00000000FFFFFFFF
A = (A + (A >> 64)) & 0x0000000000000000FFFFFFFFFFFFFFFF

转换一下

B=A>>1;B=B&113427455640312821154458202477256070485;A=A&113427455640312821154458202477256070485;A=A+B;B=A>>2;B=B&68056473384187692692674921486353642291;A=A&68056473384187692692674921486353642291;A=A+B;B=A>>4;A=A+B;A=A&20016609818878733144904388672456953615;B=A>>8;A=A+B;B=A>>16;A=A+B;B=A>>32;A=A+B;B=A>>64;A=A+B;A=A&127;