baby crypto
凯撒签到
whuo{squi4h_s1fx3h_v0h_co_i4b4T}
grey{caes4r_c1ph3r_f0r_my_s4l4D}
The Vault
这里只有一个check_keys函数，加密这块破不了，只要过了check_keys就行。
from hashlib import sha256
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from math import log10
FLAG = "grey{fake_flag}"
n = pow(10, 128)
def check_keys(a, b):
if a % 10 == 0:
return False
# Check if pow(a, b) > n
if b * log10(a) > 128:
return True
return False
def encryption(key, plaintext):
iv = "Greyhats".encode()
cipher = AES.new(key, AES.MODE_CTR, nonce = iv)
return cipher.encrypt(plaintext)
print("Welcome back, NUS Dean. Please type in the authentication codes to open the vault! \n")
a = int(input("Enter the first code: "))
b = int(input("Enter the second code: "))
if not check_keys(a, b):
print("Nice try thief! The security are on the way.")
exit(0)
print("Performing thief checks...\n")
thief_check = get_random_bytes(16)
# Highly secure double encryption checking system. The thieves stand no chance!
x = pow(a, b, n)
first_key = sha256(long_to_bytes(x)).digest()
second_key = sha256(long_to_bytes(pow(x, 10, n))).digest()
if thief_check == encryption(first_key, encryption(second_key, thief_check)):
print("Vault is opened.")
print(FLAG)
else:
print("Stealing attempts detected! Initializing lockdown")
只要a=1,b随意，但是要求a不能为1，不过可以是n+1
a = n+1
b = 2#grey{th3_4n5w3R_T0_Th3_3x4M_4nD_3v3ry7H1N6_1s_42}
GreyCat Trial
两次素数测试
from random import randint
FLAG = "grey{fake_flag}"
print("Lo and behold! The GreyCat Wizard, residing within the Green Tower of PrimeLand, is a wizard of unparalleled prowess")
print("The GreyCat wizard hath forged an oracle of equal potency")
print("The oracle hath the power to bestow upon thee any knowledge that exists in the world")
print("Gather the requisite elements to triumph over the three trials, noble wizard.")
print()
a = int(input("The first element: "))
b = int(input("The second element: "))
print()
all_seeing_number = 23456789
# FIRST TRIAL
if b <= 0:
print("Verily, those who would cheat possess not the might of true wizards.")
exit(0)
if pow(all_seeing_number, a - 1, a) != 1:
print("Alas, thy weakness hath led to defeat in the very first trial.")
exit(0)
# SECOND TRIAL
trial_numbers = [randint(0, 26) for i in range(26)]
for number in trial_numbers:
c = a + b * number
if pow(all_seeing_number, c - 1, c) != 1:
print("Thou art not yet strong enough, and thus hast been vanquished in the second trial")
exit(0)
# THIRD TRIAL
d = a + b * max(trial_numbers)
if (d.bit_length() < 55):
print("Truly, thou art the paramount wizard. As a reward, we present thee with this boon:")
print(FLAG)
else:
print("Thou art nigh, but thy power falters still.")
这个看似简单题，一直没找着方法，然后看了WP两个着
在 Primes in Arithmetic Progression Records
有一堆别人作好的素数，选一个适合大小的即可。
'''
According to this page tracking records for primes in arithmetic progression, the smallest known end for an AP-26 is:3486107472997423 + 1666981·23#·n (12783396861134173)
We technically need an AP-27, but will have to work with this because the best known AP-27 is too big. We note that the success rate is approximately
, and can just keep retrying until it works.
'''
a = 3486107472997423
b = 371891575525470
另一个方法是一个爆破，在很小范围内看成功的概率，由于这26个数是随机取的，有时候会有些并不出现，所以并不需要通过所有测试，多试几回也能成功。
from random import randint
def get_probability(a, b):
all_seeing_number = 23456789
trial_numbers = [i for i in range(26)]
successes = 0
for number in trial_numbers:
c = a + b * number
if pow(all_seeing_number, c - 1, c) == 1:
successes += 1
return successes / len(trial_numbers)
for i in range(1,50):
p = get_probability(i, 2)
print(i, p)
#a=3,b=2时成功率84% 多次运行即可成功EncryptService
AES_CTR模式是把counter加密后与明文异或，显然如果ctr相同再异或一次就回来了，不过这个key是256之了，一个个试
import os
from Crypto.Cipher import AES
from hashlib import sha256
FLAG = "grey{fake_flag_please_change_this}"
assert(len(FLAG) == 40)
secret_key = os.urandom(16)
def encrypt(plaintext, iv):
hsh = sha256(iv).digest()[:8]
cipher = AES.new(secret_key, AES.MODE_CTR, nonce=hsh)
ciphertext = cipher.encrypt(plaintext)
return ciphertext.hex()
print("AES is super safe. You have no way to guess my key anyways!!")
print("My encryption service is very generous. Indeed, so generous that we will encrypt any plaintext you desire many times")
try:
plaintext = bytes.fromhex(input("Enter some plaintext (in hex format): "))
except ValueError:
print("We are incredibly generous, yet you display such selfishness by failing to provide a proper hex string")
exit(0)
for i in range(256):
ciphertext = encrypt(plaintext, i.to_bytes(1, 'big'))
print(f"Ciphertext {i}: {ciphertext}")
print()
print("We will reward a lot of money for the person that can decipher this encrypted message :)")
print("It's impossible to decipher anyways, but here you go: ")
print("Flag: ", encrypt(FLAG.encode("ascii"), os.urandom(1)))
from pwn import xor
enc = bytes.fromhex('90a9cb7f769ae85e8619188c3c1a2faa7817cd26472df0058358d7724cad5fe03b50bbe781061962')
for v in c:
t = bytes.fromhex(v)
print(xor(t,enc))
#grey{0h_m4n_57r34m_c1ph3r_n07_50_53cur3}OT
这题需要找到两个数n,n+1的分解，看WP，还是两个着，
import secrets
import hashlib
from Crypto.Util.number import isPrime, long_to_bytes
FLAG = b'grey{fake_flag}'
e = 0x10001
def checkN(N):
if (N < 0):
return "what?"
if (N.bit_length() != 4096):
return "N should be 4096 bits"
if (isPrime(N) or isPrime(N + 23)):
return "Hey no cheating"
return None
def xor(a, b):
return bytes([i ^ j for i,j in zip(a,b)])
def encrypt(key, msg):
key = hashlib.shake_256(long_to_bytes(key)).digest(len(msg))
return xor(key, msg)
print("This is my new Oblivious transfer protocol built on top of the crypto primitive (factorisation is hard)\n")
print("You should first generate a number h which you know the factorisation,\n")
print("If you wish to know the first part of the key, send me h")
print(f"If you wish to know the second part of the key, send me h - {23}\n")
N = int(input(("Now what's your number: ")))
check = checkN(N)
if check != None:
print(check)
exit(0)
k1, k2 = secrets.randbelow(N), secrets.randbelow(N)
k = k1 ^ k2
print("Now I send you these 2 numbers\n")
print(f"pow(k1, e, N) = {pow(k1, e, N)}")
print(f"pow(k2, e, N+23) = {pow(k2, e, N + 23)}\n")
print("Since you only know how to factorise one of them, you can only get one part of the data :D\n")
print("This protocol is secure so sending this should not have any problem")
print(f"flag = {encrypt(k, FLAG).hex()}")
print("Bye bye!")
第一还是那个网站
n1_fact = [7, 462770317, 5694507743]
n2_fact = [2, 2, 2, 3, 41, 857, 1559, 339023, 2343209079636457154747528091249224327826476095035652043863204963528742512659334966004677662229161019950483083366584485458548138280449093341862002378977954167933497368219007597603755403106504457342524731378152141064507021879321139562219662472972474776122252631953409761238215160613209971558173741803026979254214210727528142216553898876030291198626181784265607599995908726045509487718799462181771728090038238068962056777644992988892938124008992438950549472345044426855638833877506876728312782161167647747290824784748696754246159892136814441488314325403562730367144917966990736400033017352989925334985594945295887660260144968909191465152707699303607693854298865103549470740231242767344488974983844208891266194478474170742048476973621036892530585345861314676222967700381339468070033580937158526944117868721156005290278361321242499022780770109629887890569960968326394919597157591985091545402257594210821663401565236232981650710950040799762586385335353099840799701838611631226315955970308578031727803805560549254048967932250161687173341134600016684183728290540325814498855833184665851382340485507560611728519283837988674497703692142667372814441920058176679479875671554322375842868866916030160361839169885024648792639108310409]
n1 = mult(n1_fact)**64
n2 = mult(n2_fact)
print(n1.bit_length())
assert n1 + 23 == n2
import itertools
import gmpy2
phi1 = itertools.product([(v-1)*v**63 for v in n1_fact])
phi2 = itertools.product([v-1 for v in n2_fact])
d1 = invert(e,phi1)
d2 = invert(e,phi2)第二这有才有意义 生成一个23*k*2^m 的数，使其+1是素数，两个分解就都有了
for i in range(1, 1<<24, 2):
order = 4096-(23).bit_length()-i.bit_length()
p = i*2**order + 1
if is_prime(p):
print(i)
break
#2013PLCG
这个看了半天WP，也没看明白
结3，80和两个随机数，然后一堆运算后%256得到一个数支加密
import secrets
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
FLAG = b'grey{fake_flag}'
while True:
sample = [3, 80] + [secrets.randbelow(256) for _ in range(2)]
if len(sample) == len(set(sample)) and 0 not in sample:
break
def getBiasRandomByte():
return secrets.choice(sample)
def getRandomByte():
n = 0; g = 0
for _ in range(20):
n += getBiasRandomByte() * getBiasRandomByte()
for _ in range(20):
g = (g + getBiasRandomByte()) % 256
for _ in range(n):
g = (getBiasRandomByte() * g + getBiasRandomByte()) % 256
return g
def encrypt(msg):
key = bytes([getRandomByte() for _ in range(6)])
cipher = AES.new(pad(key, 16), AES.MODE_CTR, nonce=b'\xc1\xc7\xcc\xd1D\xfbI\x10')
return cipher.encrypt(msg)
print("Hello there, this is our lucky numbers")
print(" ".join(map(str,sample)))
s = int(input("Send us your lucky number! "))
if not (0 <= s <= 10):
print("I dont like your number :(")
exit(0)
for i in range(s):
print("Here's your lucky flag:", encrypt(FLAG).hex())第一种方法是爆破后两个随机数，当其都是16的倍数时，那个人得到16和64，这些运算很大概率会出现0，128，208，然后就可以用这6个数去爆破结果（它不是均匀的256个数）
#We find that the byte ends up being one of [3, 80, 16, 64] about 61% of the time, and one of [0, 128, 208] another 12% of the time. So to make this simple we hope that our key only contains bytes from these 7 possible values.
cts = '''
247692734a39dbf895bc7ce9a38871551c18d744810b1920e6170fa92ccc4b3e2fe6a95ae72292110b78c5065bec72440b317a5ddb296126
c1a183e98205ddefa55a35925570493198928a1bfccdae69846dd12dec76b05316796efa9c76096c5774ce32766c2421a7c4fe7aa73f191f
d287ef4d396311abe5403b887c6c5bc85f081cf132c84bf0fe5ae536d815db70c8b233f313a4398606b1b8f6e9e6888fee43d12f405c60d3
9e708b90c66feeae44ee33cec21f0eb6e18d32bd39d0923fbbd72dc19b890f87582b70467c1b27ec88811db24f6029d93650078b67a9b050
66abaaef5630322ceaf9d64b1ec98843695446f9767e0bd632e661a7b2e9d1dbd0f303913695392084207d35032585ad3f3f59d1b505450a
9d6e07c4054e6244654cdb7d0a4b0d0f862d4501e93a2d2e63afe277438bab86a4865399be3be282463d03b344aadaab115706b164b166da
12af626ab1d20e221cb4950e5e76d994ec6f4e0645a7ccd414e70ea4740bdf0998d0783e5bc085acba776d7596442509077c971247c16100
cbef3197bd8b5fca426b6d3f5ad4d95a475d399a802eed6c270bba652df091d0b450ca8bf8ff1c13b3e5cbd85d6fd3ed2353b33eddf4cfa1
5b2111328b099a7b9857b886348a8c59b7a1a6004e6837e312507b0b338be1fb077cd7041284d3c817dd2961db5bf21e5a6605c92cd52067
ae20d773cf0fe43be929f52a359cf9e7afe11648f58230cf53fd691051188b66097c5eaba03e24b234b31eeffdf3e5144d1b18a6386b2b77
'''
dic = {x[:5]:x[5:] for x in map(bytes.fromhex, cts.split())}
candidate_bytes = [3, 80, 16, 64, 0, 128, 208]
for key in cartesian_product([candidate_bytes] * 6):
cipher = AES.new(pad(bytes(key), 16), AES.MODE_CTR, nonce=b'\xc1\xc7\xcc\xd1D\xfbI\x10')
if tail := dic.get(cipher.encrypt(b'grey{')):
print(b'grey{' + cipher.encrypt(tail))
break另外一种方法，和有复杂，不过存个板子不错。实在是不大懂，虽然也有爆破的行为但感觉成功率会比较高。而且矩阵运算并不费时。
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all import *
from pwn import *
def decrypt(msg, key):
cipher = AES.new(pad(key, 16), AES.MODE_CTR, nonce=b'\xc1\xc7\xcc\xd1D\xfbI\x10')
return cipher.decrypt(msg)
while True:
r = remote("localhost", 9999)
r.recvuntil("our lucky numbers\n")
sample = list(map(int, r.recvline().decode().strip().split()))
trans = [[0 for _ in range(2**8)] for _ in range(2**8)]
for i in sample:
for j in sample:
for k in range(2**8):
trans[k][(j * k + i) % 256] += (1)/(len(sample)^2)
for i in range(2**8):
trans[i][i] -= 1
trans[i].append(1)
T = Matrix(QQ, trans)
T = T.transpose()
v = list(T.solve_right(vector([0 for _ in range(256)] + [1])))
for i in range(len(v)):
v[i] = (v[i], i)
v.sort(key=lambda x : x[0])
# for i in range(len(v)):
# print(v[i][0].n(50), v[i][1])
k = sum(map(lambda x : x[0], v[-12:])).n(50)
print(sample)
print(k)
if (k < 0.4):
r.close()
continue
arr = list(map(lambda x : x[1], v[-12:]))
print(arr)
r.sendline("10")
for _ in range(10):
r.recvuntil("lucky flag: ")
c = bytes.fromhex(r.recvline().decode())
for i in range(12**6):
key = []
for _ in range(6):
key.append(int(arr[i % 12]))
i = i // 12
key = bytes(key)
if b'grey{' in decrypt(c, key):
print(decrypt(c, key))
exit(0)
r.close()
Encrypt
程序很短，问题是两个方程3个未知数。不过sage很善长这个。只是我不会而已。
from Crypto.Util.number import bytes_to_long
from secrets import randbits
FLAG = b'fake_flag'
p = randbits(1024)
q = randbits(1024)
def encrypt(msg, key):
m = bytes_to_long(msg)
return p * m + q * m**2 + (m + p + q) * key
n = len(FLAG)
s = randbits(1024)
print(f'n = {n}')
print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {encrypt(FLAG[:n//2], s)}')
print(f'c2 = {encrypt(FLAG[n//2:], s)}')第一种是直接构造矩阵然后规约（保存）
n = 60
p = 154086578594169457435595675666643895734811841080572558765373507236578028216591747533849923751469191596377661004029046877904042460778919103625210259448925051403568654035172094553059686620938995150323671690612067502149750334217640430881837803398594614204799922967620005040202036583050736150941842152536365544084
q = 125017463628708786112045898783989519686518641018787292892390877841668306746146702301981172263729102252453507006240973911324033106244068376643435622158128309826549542204034257871545558185841458407254799884829820319949756220781717646450760642511971882897039183232753628829418868493229485015468373205449789812260
c1 = 31118850289098152832161049930974564440792673516199584784484864528279481500612948601526706062621276262711210497739562987491633664814289725255046485262798604510626941827187912034287402128550018798165331343869198539137692903451118993538977788768945912026980846832254010558073806464461172522295653614635829516912620303901074895536704497550933805653512993413784431814034970399353908315083734783641688845887335175756415452320057666293794222522192970247045775053062573130002154959221285571979645935259561842756575513382500001710093979669436220490166791279222321068474420336287079321260681992725702004322840264333436628467610
c2 = 31118850289098152832161049930974564440792673516199584784484864528279481500612948601526706062621276262711210497739562987491633664814289725255046485262798604510626941817672660832127847041917018566902241465270388458210289299587958256824375312920716794521835108724034002277333245660951027397544591256117371462945925063227877052543505162260331377627961855698406102909764518955398788366432268123471930922870790059289526241832032413046933338032005163677585629816264668273416126506175004091486421225900247767247311587061422436593600806854703842740334379936590431991884721985057366825456467986462930236986239275935656810387114
from Crypto.Util.number import long_to_bytes
var('a b k')
f = p * a + q * a**2 + (a + p + q) * k - c1
g = p * b + q * b**2 + (b + p + q) * k - c2
h = f.resultant(g, k).expand()
print(h)
arr = [
abs(h.coefficient(a, 2).coefficient(b, 1)),
abs(h.coefficient(a, 2).coefficient(b, 0)),
abs(h.coefficient(a, 1).coefficient(b, 0)),
abs(h.coefficient(a, 0).coefficient(b, 1)),
]
constT = h.coefficient(a, 0).coefficient(b, 0)
X = 2^200
M = [
[1, 0, 0, 0, arr[0], 1, 0, 0, 0, 0],
[0, 1, 0, 0, arr[1], 0, 2^(n//2 * 8), 0, 0, 0],
[0, 0, 1, 0, arr[2], 0, 0, 2^(n//2 * 8 * 2), 0, 0],
[0, 0, 0, 1, arr[3], 0, 0, 0, 2^(n//2 * 8 * 2), 0],
[0, 0, 0, 0, constT, 0, 0, 0, 0, 2^(n//2 * 8 * 3)],
]
M = Matrix(ZZ, M)
for i in M:
print(i)
print()
L = M.LLL()[0]
a = abs(L[2])
b = abs(L[3])
print(long_to_bytes(a) + long_to_bytes(b))
第二种解法，这人可能是个数学家。
先想办法弄出一个模来把key模掉，然后直接copperSmith求解
#c = p*m + q*m**2 + (m+p+q)key
#m+p+q 除 c+(p+q)(p-p*q-q**2) 以 c+(p+q)(p-p*q-q**2)为模,用CopperSmith求解
def solve(c):
x = Zmod(c+(p+q)*(p-p*q-q**2))['x'].gen()
m = (x+p+q).small_roots(X=2**240, beta=1/3)[0]
return long_to_bytes(int(m))
print(solve(c1) + solve(c2))Fancy
一个多项式的加密
from Crypto.Util.number import getPrime
from secrets import randbits
from hashlib import shake_256
FLAG = b'???'
p = 2^29 - 33
F.<x,y> = GF(p)[]
G.<x,y> = F.quotient(F.ideal([x^3 - y^2 + 1, y^7 - 11]))
def xor(a, b):
return bytes([i ^^ j for i, j in zip(a,b)])
def encrypt_flag(s):
secret = b",".join(map(lambda x : str(x).encode(), s.lift().coefficients()))
key = shake_256(secret).digest(len(FLAG))
return xor(key, FLAG)
g = 1 + x + y
a = randbits(1024); A = g^a
b = randbits(1024); B = g^b
S = A^b
f = open("output.txt", 'w')
f.write(f"c = {encrypt_flag(S).hex()}\n")
f.write(f"A = {A}\n")
f.write(f"B = {B}\n")
'''
c = cd519d06bf85ecafdb84111ab63d509e49ffb8cfc78fee4f4cbc3c007a96d2060613f5c0a208325569bf3476d4ea839c10d4667d3dfb5d0d650d79153b
A = -210623603*x^2*y^6 + 223917991*x^2*y^5 - 234939507*x*y^6 - 103510738*x^2*y^4 - 255193765*x*y^5 + 245323126*y^6 - 41129482*x^2*y^3 + 3293396*x*y^4 + 265040169*y^5 - 175348566*x^2*y^2 - 8922481*x*y^3 - 76227659*y^4 - 127516194*x^2*y - 97886874*x*y^2 - 207888821*y^3 - 123290485*x^2 + 93703664*x*y - 146824287*y^2 - 229640558*x - 5428142*y - 185137098
B = 155912203*x^2*y^6 - 50064221*x^2*y^5 + 107681922*x*y^6 - 249464027*x^2*y^4 - 13560651*x*y^5 - 178499062*y^6 + 75225430*x^2*y^3 + 241399622*x*y^4 + 8431316*y^5 - 15433512*x^2*y^2 - 80127041*x*y^3 - 199374666*y^4 + 203619258*x^2*y + 20681482*x*y^2 - 92775952*y^3 - 46663623*x^2 + 171776018*x*y - 164809964*y^2 - 186955302*x + 235677332*y - 173567532
'''这个题先存存吧，也看不懂也不一定用得上，这在github上有，不过看起来太费劲，时通时不通。
from hashlib import shake_256
def xor(a, b):
return bytes([i ^^ j for i, j in zip(a,b)])
def decrypt(s, c):
secret = b",".join(map(lambda x : str(x).encode(), s.coefficients()))
key = shake_256(secret).digest(len(c))
return xor(key, c)
p = 2^29 - 33
d1 = 3
d2 = 7
pari.allocatemem(42949672960)
F = PolynomialRing(GF(p), 'a', d1 * d2 + 2)
variables = F.gens()
x = variables[0]
y = variables[1]
G = F.quotient(F.ideal([x^d1 - y^2 + 1, y^d2 - 11]))
variables = G.gens()
x = variables[0]
y = variables[1]
g = 1 + x + y
c = bytes.fromhex("cd519d06bf85ecafdb84111ab63d509e49ffb8cfc78fee4f4cbc3c007a96d2060613f5c0a208325569bf3476d4ea839c10d4667d3dfb5d0d650d79153b")
A = -210623603*x^2*y^6 + 223917991*x^2*y^5 - 234939507*x*y^6 - 103510738*x^2*y^4 - 255193765*x*y^5 + 245323126*y^6 - 41129482*x^2*y^3 + 3293396*x*y^4 + 265040169*y^5 - 175348566*x^2*y^2 - 8922481*x*y^3 - 76227659*y^4 - 127516194*x^2*y - 97886874*x*y^2 - 207888821*y^3 - 123290485*x^2 + 93703664*x*y - 146824287*y^2 - 229640558*x - 5428142*y - 185137098
B = 155912203*x^2*y^6 - 50064221*x^2*y^5 + 107681922*x*y^6 - 249464027*x^2*y^4 - 13560651*x*y^5 - 178499062*y^6 + 75225430*x^2*y^3 + 241399622*x*y^4 + 8431316*y^5 - 15433512*x^2*y^2 - 80127041*x*y^3 - 199374666*y^4 + 203619258*x^2*y + 20681482*x*y^2 - 92775952*y^3 - 46663623*x^2 + 171776018*x*y - 164809964*y^2 - 186955302*x + 235677332*y - 173567532
f = 0
for i in range(d1):
for j in range(d2):
f += variables[2 + d2 * i + j] * x^i * y^j
def hom(k):
M = [[0 for _ in range(d1 * d2)] for _ in range(d1 * d2)]
t = (f * k).lift()
for i in range(d1):
for j in range(d2):
for k in range(d1 * d2):
M[k][d2 * i + j] = t.coefficient({x:i, y: j, variables[2 + k]: 1})
return Matrix(GF(p), M)
G = hom(g)
AA = hom(A)
print(p)
print(G)
gg = G.charpoly()
n = len(G.rows())
factors = factor(gg)
val = []
mods = []
order = 1
for f in factors:
print(f)
FF = GF(p ^ f[0].degree())
root = f[0].change_ring(FF).roots()[0][0]
v = (G.change_ring(FF) - root * 1).right_kernel_matrix().rows()[0]
P = [v] + [[1 if i == j else 0 for j in range(n)] for i in range(n - 1)]
P = Matrix(FF, P).transpose()
T1 = P^-1 * G.change_ring(FF) * P
T2 = P^-1 * AA.change_ring(FF) * P
o = T1[0][0].multiplicative_order()
if (lcm(order, o) == order):
continue
order = lcm(order, o)
val.append(T2[0][0].log(T1[0][0]))
mods.append(T1[0][0].multiplicative_order())
a = crt(val, mods)
print(order)
s = (B^a).lift()
print(s)
print(decrypt(s, c))QRSA
一个自定义的运算
from Crypto.Util.number import bytes_to_long
from secret import qa, qb, pa, pb
FLAG = b'fake_flag'
class Q:
d = 41
def __init__(self, a, b):
self.a = a
self.b = b
def __add__(self, other):
return Q(self.a + other.a, self.b + other.b)
def __sub__(self, other):
return Q(self.a - other.a, self.b - other.b)
def __mul__(self, other):
a = self.a * other.a + Q.d * self.b * other.b
b = self.b * other.a + self.a * other.b
return Q(a, b)
def __mod__(self, other):
# Implementation Hidden
# ...
return self
def __str__(self) -> str:
return f'({self.a}, {self.b})'
def power(a, b, m):
res = Q(1, 0)
while (b > 0):
if (b & 1): res = (res * a) % m
a = (a * a) % m
b //= 2
return res
p, q = Q(pa, pb), Q(qa, qb)
N = p * q
m = Q(bytes_to_long(FLAG[:len(FLAG)//2]), bytes_to_long(FLAG[len(FLAG)//2:]))
e = 0x10001
c = power(m, e, N)
print(f"N_a = {N.a}")
print(f"N_b = {N.b}")
print(f"C_a = {c.a}")
print(f"C_b = {c.b}")
print(f"e = {e}")
print(f"D = {Q.d}")跟着一篇论文的官WP
from decimal import Decimal, getcontext
getcontext().prec = int(10000)
class Q:
d = 41
def __init__(self, a, b):
self.a = a
self.b = b
def __add__(self, other):
return Q(self.a + other.a, self.b + other.b)
def __sub__(self, other):
return Q(self.a - other.a, self.b - other.b)
def __mul__(self, other):
a = self.a * other.a + Q.d * self.b * other.b
b = self.b * other.a + self.a * other.b
return Q(a, b)
def __mod__(self, other):
r = Decimal(int(other.a * other.a - Q.d * other.b * other.b))
q = self * Q(other.a, -other.b)
qa = int((Decimal(int(q.a))/r).to_integral_exact())
qb = int((Decimal(int(q.b))/r).to_integral_exact())
res = self - Q(qa, qb) * other
return res
def __str__(self) -> str:
return f'({self.a}, {self.b})'
def power(a, b, m):
res = Q(1, 0)
while (b > 0):
if (b & 1): res = (res * a) % m
a = (a * a) % m
b //= 2
return res
N_a = 2613240571441392195964088630982261349682821645613497396226742971850092862049682714123355029612448609254303796690909646594946069650719320421550307082460305103785198772732273571020529003974320397237096691522804712706512030715753640155668659684093067319185265153545236392472134496428382266600090383797614653942221936332929175557303391656241351117808833959918253404012245633586322491783496235954011173498460231177697737092488315432823871012224368640000000
N_b = 406631291381063062708368640624433195177629887128324992156536215422427085251271158548246052765619573442134462500652616281986273622217404519958464200902599497611719198311591180368508835389781999428982410097278062504076636059232055783729252448502542597951710294264137195997893054083787667027206495381119048279226753306334118272352371363733528942151156768581101905518532465160584386180402709606771189313858666352673319676040954150310530906188677120000000
C_a = 2548711194583905242838482900078294859199882484375229964715550469790767416706725411953362845724983002558821710679258499982960453598798074631796750663774845415692650589352513765870894878170769435087683220330986573614974529690187792931316475879984809267941606365493481277785184076320720487644565808909403821593150101568803446075808715002632463329841749179295823686361086890490703942659897558782785569910876849941888829825694107185482012864247559426111336
C_b = 400941158148299866665115436146084555297152646914223433988293961893848206718639579342053294961462797881591789534709492717097892667288044693824228320005182068933966525404665323301134912609777110824069569544060608441451336249895977866445507357131208911196230972379132737483251711155975474018188763433151191428844929401881703566513896999328525340678378000286116960582957867857836600614501387296599091266404311307529322130111164410987643652390537358307965
e = 65537
N = Q(N_a, N_b)
c = Q(C_a, C_b)
f = factor(N.a * N.a - Q.d * N.b * N.b)
print(f)
ord1 = 1
ord2 = 1
for i in f:
ord1 *= (i[0] - 1)**2 * (i[0]**2 - 1) * i[0]**i[1]
ord2 *= (i[0] - 1) * i[0]**(i[1] - 1)
d1 = int(inverse(e, ord1))
d2 = int(inverse(e, ord2))
m1 = power(c, d1, N)
m2 = power(c, d2, N)
print(N)
print(c)
print(long_to_bytes(m1.a) + long_to_bytes(m1.b))
print(long_to_bytes(m2.a) + long_to_bytes(m2.b))这种跟论文的，在比赛时间内看不懂论文也就作不出来了，再说还不知道是哪篇论文
还是那个大牛的另一种解法，更牛，其实就一句F.quo(F.gen()**2-D)((C_a,C_b))
e = 65537
D = 41
N = N_a**2 - D*N_b**2
F = Zmod(N)['x']
C = F.quo(F.gen()**2-D)((C_a,C_b))
phi = euler_phi(N)
g = gcd(list(C**phi-1)+[N_a,N_b])
d = int(pow(e,-1,phi))
print(b''.join(long_to_bytes(int(x%g)) for x in C**d))
