signin
之前的hnp问题文章里写了，这里就不多提了。
bad_prime
from Crypto.Util.number import *
from secret import flag
M = 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6
def getMyprime(BIT):
while True:
p = int(pow(65537, getRandomRange(M>>1, M), M)) + getRandomInteger(BIT-int(M).bit_length()) * M
if isPrime(p):
return p
p = getMyprime(1024)
q = getPrime(1024)
n = p * q
m = bytes_to_long(flag)
print("Try to crack the bad RSA")
print("Public key:", n)
print("The flag(encrypted):", pow(m, 65537, n))
print("Well well, I will give you the hint if you please me ^_^")
leak = int(input("Gift window:"))
if M % leak == 0:
print("This is the gift for you: ", p % leak)
else:
print("I don't like this gift!")
getMyprime函数里的生成过程与roca问题类似，误导了我。
- $M = k1\cdot leak$
- $res = p + k2\cdot leak$
输入合适的leak，再根据位数关系，可以知道k2的大小范围，不超过2^55，可以构造copper直接解出k2来，p能直接求：
P.<k> = PolynomialRing(Zmod(n))
f = res + k*leak
f = f.monic()
root = f.small_roots(X=2^55,beta=0.4)
print(root)
#[10172920676999212]
p有了就是基础RSA了。
welcomesigner2
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
import random
flag = b"***********************************"
def pad(message):
return message + b"\x00"*((16-len(message)%16)%16)
def myfastexp(m,d,N,j,N_):
A = 1
B = m
d = bin(d)[2:][::-1]
n = len(d)
N = N
for i in range(n):
if d[i] == '1':
A = A * B % N
# a fault occurs j steps before the end of the exponentiation
if i >= n-1-j:
N = N_
B = B**2 % N
return A
def encrypt(message,key):
key = bytes.fromhex(md5(str(key).encode()).hexdigest())
enc = AES.new(key,mode=AES.MODE_ECB)
c = enc.encrypt(pad(message))
return c
border = "|"
print(border*75)
print(border, "Hi all, I have another algorithm that can quickly calculate powers. ", border)
print(border, "But still there's something wrong with it. Your task is to get ", border)
print(border, "its private key,and decrypt the cipher to cat the flag ^-^ ", border)
print(border*75)
while True:
# generate
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 17
if GCD(e,(p-1)*(q-1)) == 1:
d = inverse(e,(p-1)*(q-1))
n_ = n
break
n_ = n
msg = bytes_to_long(b"Welcome_come_to_WMCTF")
sig = pow(msg,d,n)
assert sig == myfastexp(msg,d,n,0,n_)
CHANGE = True
while True:
try:
ans = input("| Options: \n|\t[G]et data \n|\t[S]ignatrue \n|\t[F]ault injection \n|\t[Q]uit\n").lower().strip()
if ans == 'f':
if CHANGE:
print(border,"You have one chance to change one byte of N. ")
temp,index = input("bytes, and index:").strip().split(",")
assert 0<= int(temp) <=255
assert 0<= int(index) <= 1023
n_ = n ^ (int(temp)<<int(index))
print(border,f"[+] update: n_ -> \"{n_}\"")
CHANGE = False
else:
print(border,"Greedy...")
elif ans == 'g':
print(border,f"n = {n}")
print(border,f"flag_ciphertext = {encrypt(flag,d).hex()}")
elif ans == 's':
index = input("Where your want to interfere:").strip()
sig_ = myfastexp(msg,d,n,int(index),n_)
print(border,f"signature of \"Welcome_come_to_WMCTF\" is {sig_}")
elif ans == 'q':
quit()
except Exception as e:
print(border,"Err...")
quit()
关键在myfastexp函数，了解了下，是快速幂取模算法，目的就是快速求出$a^b \pmod n$
和welcomesigner1，caib不是很能理解，贴下佬们的wp
WMCTF2023 Crypto_无趣的浅的博客-CSDN博客
[WMCTF 2023] crypto_石氏是时试的博客-CSDN博客
2023 WMCTF SU Write-Up | TEAM-SU (su-team.cn)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com