记录几道题
breakbox
题目：
#include <stdio.h>
#include <string.h>
#include <openssl/sha.h>
#define ROUND 16
// 0<sBox[i]<15
int sBox[16] ={
3, 10, 15, 12,
9, 2, 1, 7,
x, x, x, x,
x, x, x, x
};
void derive_round_key(unsigned int key, unsigned char *round_key, int length) {
unsigned int tmp = key;
int i;
for(i = 0; i < length / 16; i++)
{
memcpy(round_key + i * 16, &tmp, 4); tmp++;
memcpy(round_key + i * 16 + 4, &tmp, 4); tmp++;
memcpy(round_key + i * 16 + 8, &tmp, 4); tmp++;
memcpy(round_key + i * 16 + 12, &tmp, 4); tmp++;
}
}
void reverseBits(unsigned char* state) {
unsigned char temp[16];
int i,j;
for ( i = 0; i < 16; i++) {
unsigned char byte = 0;
for ( j = 0; j < 8; j++) {
byte |= ((state[i] >> j) & 1) << (7 - j);
}
temp[15 - i] = byte;
}
for ( i = 0; i < 16; i++) {
state[i] = temp[i];
}
}
void sBoxTransform(unsigned char* state) {
int i;
for ( i = 0; i < 16; i++) {
int lo = sBox[state[i] & 0xF];
int hi = sBox[state[i] >> 4];
state[i] = (hi << 4) | lo;
}
}
void leftShiftBytes(unsigned char* state) {
int i;
unsigned char temp[16];
for ( i = 0; i < 16; i += 4) {
temp[i + 0] = state[i + 2] >> 3 | (state[i + 1] << 5);
temp[i + 1] = state[i + 3] >> 3 | (state[i + 2] << 5);
temp[i + 2] = state[i + 0] >> 3 | (state[i + 3] << 5);
temp[i + 3] = state[i + 1] >> 3 | (state[i + 0] << 5);
}
for ( i = 0; i < 16; i++)
{
state[i] = temp[i];
}
}
void addRoundKey(unsigned char* state, unsigned char* roundKey, unsigned int round) {
int i,j;
for ( i = 0; i < 16; i++) {
for ( j = 0; j < 8; j++) {
state[i] ^= ((roundKey[i + round * 16] >> j) & 1) << j;
}
}
}
void encrypt(unsigned char* password, unsigned int key, unsigned char* ciphertext) {
unsigned char roundKeys[16 * ROUND] = {};
derive_round_key(key, roundKeys, 16 * ROUND);
unsigned char state[16];
memcpy(state, password, 16);
int round;
for ( round = 0; round < ROUND; round++)
{
reverseBits(state);
sBoxTransform(state);
leftShiftBytes(state);
addRoundKey(state, roundKeys, round);
}
memcpy(ciphertext, state, 16);
}
void main() {
unsigned char password[] = "";
unsigned int key = 0xFFFF00EE;
unsigned char ciphertext[16];
encrypt(password, key, ciphertext);
int i;
printf("Encrypted password:");
for (i = 0; i < 16; i++) {
printf("%02X", ciphertext[i]);
}
}
/* password_len = 16,and give you key,but we can not know sbox[:-8],please guess it! */
encry password:087BB2594D0BCE4CBE82620AB5BC7A96
input your password to get flag!
先把sbox已知的数逆出来得到，未知数就拿100来代替了
#逆向过程：
#s[0]=3 -> r[3] = 0
int rBox[16] = { 100, 6, 5, 0,
100, 100, 100, 7,
100, 4, 1,100 ,
3, 100, 100, 2 };
剩下几位靠爆破得到，我写的代码就是依托答辩，但是我觉得还挺好理解的
for (int i = 8; i < 16; i++)
{
rBox[0] = i;
for (int j = 8; j < 16; j++)
{
if (j == i) {
continue;
}
rBox[4] = j;
for (int k = 8; k < 16; k++) {
if (j == k || k == i) {
continue;
}
rBox[5] = k;
for (int i1 = 8; i1 < 16; i1++) {
if (k == i1 || i1 == j || i1 == i) {
continue;
}
rBox[6] = i1;
for (int j1 = 8; j1 < 16; j1++) {
if (i1 == j1 || j1 == i || j1 == j || j1 == k) {
continue;
}
rBox[8] = j1;
for (int k1 = 8; k1 < 16; k1++) {
if (j1 == k1 || k1 == i || k1 == j || k1 == i1 || k1 == k) {
continue;
}
rBox[11] = k1;
for (int i2 = 8; i2 < 16; i2++) {
if (k1 == i2 || i2 == i || i2 == j || i2 == k || i2 == i1 || i2 == j1) {
continue;
}
rBox[13] = i2;
for (int j2 = 8; j2 < 16; j2++) {
if (j2 == i2 || j2 == k || j2 == i || j2 == j || j2 == i1 || j2 == j1 || j2 == k1) {
continue;
}
rBox[14] = j2;
最后注意一下inv_leftShiftBytes就行了
exp：
#include <openssl/sha.h>
#include "stdlib.h"
#include <stdio.h>
#include <string.h>
#pragma warning(disable:4996)
#define ROUND 16
#pragma comment(lib,"libssl.lib")
#pragma comment(lib,"libcrypto.lib")
#include <stdbool.h>
#include <ctype.h>
void print(unsigned char* m) {
for (int i = 0; i < 16; i++) {
printf("%02X", m[i]);
}
printf("\n");
}
int is_all_visible(unsigned char* str) {
while (*str) { // 循环直到字符串的结尾（NULL字符）
if (!isprint((unsigned char)*str)) { // 如果字符不是可见的
return 0; // 返回假
}
str++; // 移动到下一个字符
}
return 1; // 所有字符都是可见的，返回真
}
// 判断字符串是否全部由可见字符组成
int visible_char_length(unsigned char* str) {
int count = 0;
while (*str) {
if (isprint((unsigned char)*str)) {
count++;
}
str++;
}
return count;
}
//S-Box 16x16
int rBox[16] = { 100, 6, 5, 0,
100, 100, 100, 7,
100, 4, 1,100 ,
3, 100, 100, 2 };
// 将十六进制字符串转换为 unsigned char 数组
void hex_to_bytes(const char* hex_str, unsigned char* bytes, size_t bytes_len) {
size_t hex_len = strlen(hex_str);
if (hex_len % 2 != 0 || hex_len / 2 > bytes_len) {
fprintf(stderr, "Invalid hex string length.n");
return;
}
for (size_t i = 0; i < hex_len / 2; i++) {
sscanf(hex_str + 2 * i, "%2hhx", &bytes[i]);
}
}
// 派生轮密钥
void derive_round_key(unsigned int key, unsigned char* round_key, int length) {
unsigned int tmp = key;
for (int i = 0; i < length / 16; i++)
{
memcpy(round_key + i * 16, &tmp, 4); tmp++;
memcpy(round_key + i * 16 + 4, &tmp, 4); tmp++;
memcpy(round_key + i * 16 + 8, &tmp, 4); tmp++;
memcpy(round_key + i * 16 + 12, &tmp, 4); tmp++;
}
}
// 比特逆序
void reverseBits(unsigned char* state) {
unsigned char temp[16];
for (int i = 0; i < 16; i++) {
unsigned char byte = 0;
for (int j = 0; j < 8; j++) {
byte |= ((state[i] >> j) & 1) << (7 - j);
}
temp[15 - i] = byte;
}
for (int i = 0; i < 16; i++) {
state[i] = temp[i];
}
}
/*void sBoxTransform(unsigned char* state) {
for (int i = 0; i < 16; i++) {
int lo = sBox[state[i] & 0xF];
int hi = sBox[state[i] >> 4];
state[i] = (hi << 4) | lo;
}
}*/
void inv_sBoxTransform(unsigned char* state) {
//for (int i = 0; i < 16; i++) {
// printf("%d ", rBox[i]);
// }
// printf("\n");
for (int i = 0; i < 16; i++) {
int lo = rBox[state[i] & 0xF];
int hi = rBox[state[i] >> 4];
state[i] = (hi << 4) | lo;
}
}
/*void leftShiftBytes(unsigned char* state) {
unsigned char temp[16];
for (int i = 0; i < 16; i += 4) {
temp[i + 0] = state[i + 2] >> 3 | (state[i + 1] << 5);
temp[i + 1] = state[i + 3] >> 3 | (state[i + 2] << 5);
temp[i + 2] = state[i + 0] >> 3 | (state[i + 3] << 5);
temp[i + 3] = state[i + 1] >> 3 | (state[i + 0] << 5);
}
for (int i = 0; i < 16; i++)
{
state[i] = temp[i];
}
}*/
void inv_leftShiftBytes(unsigned char* state) {
unsigned char temp[16];
for (int i = 0; i < 16; i += 4) {
// temp[i + 0] = state[i + 2] >> 3 | (state[i + 1] << 5);
//temp[i + 1] = state[i + 3] >> 3 | (state[i + 2] << 5);
//temp[i + 2] = state[i + 0] >> 3 | (state[i + 3] << 5);
//temp[i + 3] = state[i + 1] >> 3 | (state[i + 0] << 5);
temp[i + 0] = state[i + 2] << 3 | (state[i + 3] >> 5);
temp[i + 1] = state[i + 3] << 3 | (state[i + 0] >> 5);
temp[i + 2] = state[i + 0] << 3 | (state[i + 1] >> 5);
temp[i + 3] = state[i + 1] << 3 | (state[i + 2] >> 5);
}
for (int i = 0; i < 16; i++)
{
state[i] = temp[i];
}
}
// 轮密钥加
void addRoundKey(unsigned char* state, unsigned char* roundKey, unsigned int round) {
for (int i = 0; i < 16; i++) {
for (int j = 0; j < 8; j++) {
state[i] ^= ((roundKey[i + round * 16] >> j) & 1) << j;
}
}
}
// 加密函数
/*void encrypt(unsigned char* password, unsigned int key, unsigned char* ciphertext) {
unsigned char roundKeys[16 * ROUND] = {}; //
// 生成轮密钥
derive_round_key(key, roundKeys, 16 * ROUND);
// 初始状态为16字节的口令
unsigned char state[16]; // 初始状态为16字节的密码
memcpy(state, password, 16); // 初始状态为密码的初始值
// 迭代加密过程
for (int round = 0; round < ROUND; round++)
{
reverseBits(state);
sBoxTransform(state);
leftShiftBytes(state);
addRoundKey(state, roundKeys, round);
}
memcpy(ciphertext, state, 16);
}*/
void decrypt(unsigned char* ciphertext, unsigned int key, unsigned char* plaintext) {
unsigned char roundKeys[16 * ROUND] = {}; //
for (int i = 8; i < 16; i++)
{
rBox[0] = i;
for (int j = 8; j < 16; j++)
{
if (j == i) {
continue;
}
rBox[4] = j;
for (int k = 8; k < 16; k++) {
if (j == k || k == i) {
continue;
}
rBox[5] = k;
for (int i1 = 8; i1 < 16; i1++) {
if (k == i1 || i1 == j || i1 == i) {
continue;
}
rBox[6] = i1;
for (int j1 = 8; j1 < 16; j1++) {
if (i1 == j1 || j1 == i || j1 == j || j1 == k) {
continue;
}
rBox[8] = j1;
for (int k1 = 8; k1 < 16; k1++) {
if (j1 == k1 || k1 == i || k1 == j || k1 == i1 || k1 == k) {
continue;
}
rBox[11] = k1;
for (int i2 = 8; i2 < 16; i2++) {
if (k1 == i2 || i2 == i || i2 == j || i2 == k || i2 == i1 || i2 == j1) {
continue;
}
rBox[13] = i2;
for (int j2 = 8; j2 < 16; j2++) {
if (j2 == i2 || j2 == k || j2 == i || j2 == j || j2 == i1 || j2 == j1 || j2 == k1) {
continue;
}
rBox[14] = j2;
// 生成轮密钥
derive_round_key(key, roundKeys, 16 * ROUND);
// 初始状态为16字节的口令
unsigned char state[16]; // 初始状态为16字节的密码
memcpy(state, ciphertext, 16); // 初始状态为密码的初始值
// 迭代加密过程
for (int round = ROUND - 1; round >= 0; round--)
{
addRoundKey(state, roundKeys, round);
inv_leftShiftBytes(state);
inv_sBoxTransform(state);
reverseBits(state);
}
memcpy(plaintext, state, 16);
if (plaintext[0] > 31 && plaintext[0] < 127 && plaintext[1] > 31 && plaintext[1] < 127 && plaintext[2] > 31 && plaintext[2] < 127 && plaintext[3] > 31 && plaintext[3] < 127 && plaintext[4] > 31 && plaintext[4] < 127 && plaintext[5] > 31 && plaintext[5] < 127 && plaintext[6] > 31 && plaintext[6] < 127) {
printf("%s", plaintext);
printf("\n");
}
}
}
}
}
}
}
}
}
}
bool isPrintable(unsigned char* data, int length) {
for (int i = 0; i < length; i++) {
if (data[i] < 32 || data[i] > 126) {
return false;
}
}
return true;
}
int main() {
unsigned char ciphertext[16]; // 16字节的状态
long long int cnt111 = 0;
unsigned char plaintext[16]; // 16字节的状态
const char hex_ct[] = "087BB2594D0BCE4CBE82620AB5BC7A96";
unsigned int k = 0xFFFF00EE;
hex_to_bytes(hex_ct, ciphertext, 16);
long long cnt = 0;
decrypt(ciphertext, k, plaintext);
return 0;
}
ancat
猫脸变换，记录一下脚本
exp：
import matplotlib.pyplot as plt
import cv2
import numpy as np
from PIL import Image
def de_arnold(img,shuffle_time,a,b):
r, c, d = img.shape
dp = np.zeros(img.shape, np.uint8)
for s in range(shuffle_time):
for i in range(r):
for j in range(c):
x = ((a * b + 1) * i - b * j) % r
y = (-a * i + j) % c
dp[x, y, :] = img[i, j, :]
img = np.copy(dp)
cv2.imwrite(f"flag.png",img)
img_en = cv2.imread('en_flag.png')
de_arnold(img_en, 3,6, 9)
EandR
题目：
import random
from Crypto.Util.number import *
from password import password
password1 = bytes_to_long(password[0:10])
password2 = bytes_to_long(password[10:15])
password3 = bytes_to_long(password[15:])
q1 = getPrime(80)
a,b,c = [random.randrange(1,q1-1) for _ in "_yi_gei_woli_giaogiao"][:3]
def add(P,Q):
if P[0] != Q[0] and P[1] != Q[1]:
t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q1)) %q1
else:
t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q1))%q1
x3 = b*inverse(c,q1)*t*t - P[0] - Q[0]
y3 = t*(P[0] - x3) - P[1]
return (x3%q1, y3%q1)
def mul(t, A, B=0):
if not t: return B
return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)
G = (543964449142803087188784, 288605946000947449279542)
Ps = []
ms = [random.randrange(1,q1-1) for _ in "giaoli_wo_ki_gay_giao"[:4]] + [password1]
for m in ms:
P = mul(m,G)
Ps.append(P)
print(f'Ps = {Ps}')
#Ps = [(260275824641779979588305, 726300335217221063663551), (263184922060743661751480, 611614193933496916037740), (582822220331206509336492, 481246655450613023120881), (372364178450359878096924, 693486907224438901452705), (227415654827717701646056, 348607835248429842358207)]
def get_good_prime(bit_length):
while True:
a = random.getrandbits(bit_length//2)
b = random.getrandbits(bit_length//2)
if b % 3 == 0:
continue
p = a ** 2 + 3 * b ** 2
if p.bit_length() == bit_length and p % 3 == 1 and isPrime(p):
return p
def addtion(P, Q, mod):
m, n = P
p, q = Q
if p is None:
return P
if m is None:
return Q
if n is None and q is None:
x = m * p % mod
y = (m + p) % mod
return (x, y)
if n is None and q is not None:
m, n, p, q = p, q, m, n
if q is None:
if (n + p) % mod != 0:
x = (m * p + 2) * inverse(n + p, mod) % mod
y = (m + n * p) * inverse(n + p, mod) % mod
return (x, y)
elif (m - n ** 2) % mod != 0:
x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
return (x, None)
else:
return (None, None)
else:
if (m + p + n * q) % mod != 0:
x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
return (x, y)
elif (n * p + m * q + 2) % mod != 0:
x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
return (x, None)
else:
return (None, None)
def good_power(P, a, mod):
res = (None, None)
t = P
while a > 0:
if a & 1:
res = addtion(res, t, mod)
t = addtion(t, t, mod)
a >>= 1
return res
p = get_good_prime(512)
q = get_good_prime(512)
n = p * q
phi =(p**2 + p + 1) * (q **2 + q + 1)
d = getPrime(250)
e = inverse(d, phi)
m = (password2,password3)
c = good_power(m, e, n)
print(f"c = {c}")
print(f"n = {n}")
print(f"e = {e}")
#c = (85422492752594163973525590153185181637578599526748527548916818661479717263661942043798519054634085790883203742143922909753155434484575316617409323425452920098106836753343255561397020191055166143284978002585043504528894342913998542611098251874319443218091798571063752406953498370967948413185742430124774364502, 76360473484928457783902531276059575220337561977824728338226901050505962483334908329971039234703811585714576796248193194224345311394246955572476959264834718452867915059519112273971322043676881006521735191342236986562040370170197311513561834788296920114495955011761008433746711656717672295490499621868087698727)
#n = 132719529494169666440015361510648436961564899266678472070578908438683877891624167098238871100680873610907493030493888543311583489467977492321159269370993104122316666862684984291699054526052448281045072084505401048771540969410719257800557252293084614152823911423359393963461618267528202871491263273689330662483
#e = 11129124355754297663162018546827275323752484161275828202691755264373860584802812666274619573801591775394317054892274391559877638968525372552912822620960106630890646377568381371715175233391190130896052686700941699773696737503798559366444705210907918989156659958714227911553806284829827584317491856812837076773878027948902531976851782851828778907966453369256525240545004196650478844079204128934633946462554325449608508882698599949761290061856624339283077816678434588316049724978427174141375678236660470842166757271021085154473717712706728832602385344078603418705101145889874790221291898011811923959932221790456898299847
先看第一部分：
是一个ECC，我们可以通过题目中的
t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q1))%q1
t是曲线的斜率，就是原式求导后的结果，得到原式是
我们知道6组数据求四个未知量，那么我们可以使用groebner来求解其中的未知数
为了方便运算我们可以把原式看成
from Crypto.Util.number import *
G = (543964449142803087188784, 288605946000947449279542)
Ps = [(260275824641779979588305, 726300335217221063663551), (263184922060743661751480, 611614193933496916037740), (582822220331206509336492, 481246655450613023120881), (372364178450359878096924, 693486907224438901452705), (227415654827717701646056, 348607835248429842358207)]
R.<a,b,c>=ZZ[]
F = [a * G[0] ^ 3 + b * G[0] + c - G[1] ^ 2]
for _ in range(5):
f = a * Ps[_][0] ^ 3 + b * Ps[_][0] + c -Ps[_][1] ^ 2
F.append(f)
L = Ideal(F).groebner_basis()
print(L)
#[a + 226820338772807027243218, b + 773167489336543856487958, c + 758871032836012559341025, 813190268037982043592049]
#求解出a，b，c，q
得到完整的曲线后，进行映射成椭圆曲线其中
映射完之后，进行 discrete_log(Q, P, operation='+') 求解k即可
exp：
from Crypto.Util.number import *
G = (543964449142803087188784, 288605946000947449279542)
Ps = [(260275824641779979588305, 726300335217221063663551), (263184922060743661751480, 611614193933496916037740), (582822220331206509336492, 481246655450613023120881), (372364178450359878096924, 693486907224438901452705), (227415654827717701646056, 348607835248429842358207)]
print(long_to_bytes(G[0]))
#s0_3@5y_c0
R.<a,b,c>=ZZ[]
F = [a * G[0] ^ 3 + b * G[0] + c - G[1] ^ 2]
for _ in range(5):
f = a * Ps[_][0] ^ 3 + b * Ps[_][0] + c -Ps[_][1] ^ 2
F.append(f)
L = Ideal(F).groebner_basis()
print(L)
G = (543964449142803087188784, 288605946000947449279542)
q=813190268037982043592049
a = -226820338772807027243218 % q
b = -773167489336543856487958 % q
c = -758871032836012559341025 % q
P.<k> = PolynomialRing(GF(q))
f = k^3 - a
k = f.roots()
print(k)
k = 232592821046908396945406
gx = G[0] * k % q
gy = G[1]
tx = Ps[-1][0] * k % q
ty = Ps[-1][1]
A = b * inverse_mod(k,q)
B = c
E=EllipticCurve(Zmod(q),[A,B])
G=E(gx,gy)
print(G.order())
T=E(tx,ty)
dlp = discrete_log(T,G,operation='+')
print(long_to_bytes(dlp))
#ylcTf_e_or'
第二部分参考 ：糖醋小鸡块的博客
化为
令x=k，y=p+q
在进行二元copper求解x，y
exp：
from Crypto.Util.number import *
from gmpy2 import *
import itertools
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
n = 132719529494169666440015361510648436961564899266678472070578908438683877891624167098238871100680873610907493030493888543311583489467977492321159269370993104122316666862684984291699054526052448281045072084505401048771540969410719257800557252293084614152823911423359393963461618267528202871491263273689330662483
e = 11129124355754297663162018546827275323752484161275828202691755264373860584802812666274619573801591775394317054892274391559877638968525372552912822620960106630890646377568381371715175233391190130896052686700941699773696737503798559366444705210907918989156659958714227911553806284829827584317491856812837076773878027948902531976851782851828778907966453369256525240545004196650478844079204128934633946462554325449608508882698599949761290061856624339283077816678434588316049724978427174141375678236660470842166757271021085154473717712706728832602385344078603418705101145889874790221291898011811923959932221790456898299847
PR.<x,y>= PolynomialRing(Zmod(e))
f = 1 + x * (n ^ 2 - n + 1 + (n + 1) * y + y ^ 2)
res = small_roots(f, (2 ^ 256, 2 ^ 512), m=2, d=3)
pplusq = int(res[0][1])
pminusq = iroot(pplusq ^ 2 - 4 * n, 2)[0]
p = (pplusq + pminusq) // 2
q = n // p
print(p)
print(q)
#p =11535800156719048931347276045879377428643243582810776040089157673637898260385736466169737110946935313493516144396403906845807153884435472856105926366322231
#q = 11505012889536485414879400690227492114674311121404688222379266667261973620824161923078590149522686297199691051054957568059021196948596303095778287403345093
from Crypto.Util.number import *
from gmpy2 import *
import itertools
def addtion(P, Q, mod):
m, n = P
p, q = Q
if p is None:
return P
if m is None:
return Q
if n is None and q is None:
x = m * p % mod
y = (m + p) % mod
return (x, y)
if n is None and q is not None:
m, n, p, q = p, q, m, n
if q is None:
if (n + p) % mod != 0:
x = (m * p + 2) * inverse(n + p, mod) % mod
y = (m + n * p) * inverse(n + p, mod) % mod
return (x, y)
elif (m - n ** 2) % mod != 0:
x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
return (x, None)
else:
return (None, None)
else:
if (m + p + n * q) % mod != 0:
x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
return (x, y)
elif (n * p + m * q + 2) % mod != 0:
x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
return (x, None)
else:
return (None, None)
def good_power(P, a, mod):
res = (None, None)
t = P
while a > 0:
if a & 1:
res = addtion(res, t, mod)
t = addtion(t, t, mod)
a >>= 1
return res
c = (85422492752594163973525590153185181637578599526748527548916818661479717263661942043798519054634085790883203742143922909753155434484575316617409323425452920098106836753343255561397020191055166143284978002585043504528894342913998542611098251874319443218091798571063752406953498370967948413185742430124774364502, 76360473484928457783902531276059575220337561977824728338226901050505962483334908329971039234703811585714576796248193194224345311394246955572476959264834718452867915059519112273971322043676881006521735191342236986562040370170197311513561834788296920114495955011761008433746711656717672295490499621868087698727)
p =11535800156719048931347276045879377428643243582810776040089157673637898260385736466169737110946935313493516144396403906845807153884435472856105926366322231
q = 11505012889536485414879400690227492114674311121404688222379266667261973620824161923078590149522686297199691051054957568059021196948596303095778287403345093
e = 11129124355754297663162018546827275323752484161275828202691755264373860584802812666274619573801591775394317054892274391559877638968525372552912822620960106630890646377568381371715175233391190130896052686700941699773696737503798559366444705210907918989156659958714227911553806284829827584317491856812837076773878027948902531976851782851828778907966453369256525240545004196650478844079204128934633946462554325449608508882698599949761290061856624339283077816678434588316049724978427174141375678236660470842166757271021085154473717712706728832602385344078603418705101145889874790221291898011811923959932221790456898299847
N = p*q
phi = (p**2 + p + 1)*(q**2 + q + 1)
d = invert(e,phi)
m = good_power(c,d,N)
m = (409403877231, 10673380708147344593726104065762264760478541144788135806)
print(long_to_bytes((m[0])))
print(long_to_bytes(m[1]))
# b'_R_go'
# b'oooood_game_114514giao~'
butterfly_love
题目：
from Crypto.Util.number import getPrime, bytes_to_long
from gmpy2 import *
import os
import sys
from hashlib import sha256,sha512
flag =os.getenv("GZCTF_FLAG").encode()
class LIANGZHU:
def __init__(self):
p, q = getPrime(512), getPrime(512)
self.e = 65537
self.d = invert(self.e,(p-1)*(q-1))
self.n = p * q
def listen(self, m): return pow(m, self.e, self.n)
def say(self, c): return pow(c, self.d, self.n)
def my_print(message):
sys.stdout.write(f'{message}\n')
sys.stdout.flush()
sys.stderr.flush()
def read_str():
return sys.stdin.readline().strip()
def proof_of_work():
s = hex(bytes_to_long(os.urandom(10)))[2:]
digest = sha256(s.encode()).hexdigest()
print(f"sha256(XXXXXX + {s[6:]})=={digest}")
my_print("Give me XXXXXX: ")
#print(s,s[:6])
x = read_str()
if len(x) != 6 or x != s[:6]:
print("Wrong!")
return False
return True
def PoW():
if not proof_of_work():
exit(-1)
PoW()
Liangshanbo, Zhuyingtai = LIANGZHU(), LIANGZHU()
temp = os.urandom(32)
print('the flag and some noise:', Liangshanbo.listen(bytes_to_long(temp[:16] + flag + temp[16:])))
for _ in temp:
print('Zhuyingtai listen:', Zhuyingtai.listen(Liangshanbo.say(int(input('Liangshanbo say: ')))))
print('Liangshanbo listen:', Liangshanbo.listen(Zhuyingtai.say(int(input('Zhuyingtai say: ')))))
首先想办法求 n1，n2，先输入c= -1给oracle 1，得到
x填入 oracle 2，oracle2会将
输出，假设 n1< n2 ，最后的值就是 n1- 1，从而求出 n1
已知n1的情况下，可以送到 oracle 1，只要t< n1 则输出值为
因此，所以用多组t 操作后再 gcd 就能求出 n2，将
带入到oracle1中，得到
此时将-c代入oracle 2 得到
再通过明文线性相关攻击和HGCD解密
exp：
from pwn import *
from Crypto.Util.number import long_to_bytes
#with process(['python', 'main.py']) as sh:
def proof_of_work():
rev = r.recvuntil("sha256(XXXXXX+")
suffix = r.recv(14).decode()
rev = r.recvuntil(b" == ")
tar = r.recv(64).decode()
def f(x):
hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
return hashresult == tar
prefix = util.iters.mbruteforce(f, string.digits + string.ascii_letters, 6, 'upto')
r.recvuntil('XXXXXX: ')
r.sendline(prefix.encode())
with remote('challenge.yuanloo.com', 42376) as sh:
proof_of_work()
sh.readuntil(b'noise: ')
flag1 = int(sh.readline())
def get(n):
sh.sendline(str(n).encode())
sh.readuntil(b'hears: ')
return int(sh.readline())
a = get(-1)
m = get(a) + 1
assert get(m) == 0, "Fails about 50% of the time, try again"
n = get(get(-a)) + a
assert get(n) == 0, "Fails about 4% of the time (if the above succeeds), try again"
flag2 = get(-get(flag1))
def GCD(a, b):
def HGCD(a, b):
if 2 * b.degree() <= a.degree() or a.degree() == 1:
return 1, 0, 0, 1
m = a.degree() // 2
a_top, a_bot = a.quo_rem(x**m)
b_top, b_bot = b.quo_rem(x**m)
R00, R01, R10, R11 = HGCD(a_top, b_top)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
q, e = c.quo_rem(d)
d_top, d_bot = d.quo_rem(x**(m // 2))
e_top, e_bot = e.quo_rem(x**(m // 2))
S00, S01, S10, S11 = HGCD(d_top, e_top)
RET00 = S01 * R00 + (S00 - q * S01) * R10
RET01 = S01 * R01 + (S00 - q * S01) * R11
RET10 = S11 * R00 + (S10 - q * S11) * R10
RET11 = S11 * R01 + (S10 - q * S11) * R11
return RET00, RET01, RET10, RET11
q, r = a.quo_rem(b)
if r == 0:
return b
R00, R01, R10, R11 = HGCD(a, b)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
if d == 0:
return c.monic()
q, r = c.quo_rem(d)
if r == 0:
return d
return GCD(d, r)
print('Calculating...')
x = Zmod(m)['x'].gen()
f, g = x**65537-flag1, (n-x)**65537-flag2
print(long_to_bytes(int(x-GCD(f,g).monic())))
⭕️
题目：
from sage.all import ZZ, randint
from Crypto.Util.number import *
p = None
def generate_distortion_map(E):
if E.a_invariants() != (0,6,0,1,0):
raise NotImplementedError
return E.isogeny(E.lift_x(ZZ(1)), codomain=E)
def generate_torsion_points(E, a, b):
def get_l_torsion_basis(E, l):
n = (p+1) // l
return (n*G for G in E.gens())
P2, Q2 = get_l_torsion_basis(E, 2**a)
P3, Q3 = get_l_torsion_basis(E, 3**b)
return P2, Q2, P3, Q3
from flag import flag
flag = bytes_to_long(flag)
def generate_key(E_start, b, P2, Q2, P3, Q3):
bobs_key = flag
K = P3 + bobs_key*Q3
phi = E_start.isogeny(K, algorithm="factored")
EB = phi.codomain()
EB.set_order((p+1)**2, num_checks=0)
PB, QB = phi(P2), phi(Q2)
return bobs_key, EB, PB, QB
a = 305
b = 192
p = 2^a*3^b - 1
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)
E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2)
two_i = generate_distortion_map(E_start)
P2, Q2, P3, Q3 = generate_torsion_points(E_start, a, b)
flag_key, EB, PB, QB = generate_key(E_start, b, P2, Q2, P3, Q3)
print(EB)
print(PB)
print(QB)
"""
Elliptic Curve defined by y^2 = x^3 + 6*x^2 + (1109655386602666580941477264844188509870568726343453010771770543665511250648180561681677488303290640863245633469198578301207900328491716466654470349910400724631139969542193124833051079*i+2116239248619087101677214169270633679594454755906693836568034229947351325062332338053907457802709748610111020509037164276717020111001082512633925347579357851693517057782645336434230575)*x + (783233241190388171387544682511032475647421068250023300290363249038620119995420899574317207343308349718411589404085433006020673690798356551667106568546291827001684869794402242067695854*i+1972744566958070881282131795626840370625118459932253321456562523309337576438614381897961997884583203821363249684189786452976563714388989414218292121069137192174721660268448964759287049) over Finite Field in i of size 2638940411073262671963620699288286770183560231187222316750407556465639836010558150163225530335162533481049256757217964651333810422125728537407397155806079217346919294449255613110157311^2
(1792805099210360888864761590321391235025824991548234912676247217808406536821234881384389175924130468280991088357660252370848305634037983159579204419296531735459329230669983096853856246*i + 171253309786548245036128932419221024429140017061733162803654587078736014845338272553757000723916403099300493601067652633948439740076865619503812837361164299530464912490228468097800783 : 354858932953470647164407208876248915819655125217303333206005726572045601374950018701435041440177841288062762055220650414072032960690957944114792835539535784706989279413982852603736575*i + 652241231208054817913369235175691302162155547428861981772486556413182925887029191547328926720048813218596706336154397071250972427384520853013935344373831652140490902941929446372831718 : 1)
(2186267301001259402114997355550578512125192708867710349339620240110565042023451739162302255305174185314466942521888744412961910909391429250064295777978302914701578195376147036042606489*i + 1113400569081370973415138408967328130898700595223023714237127216136706721906751381588571638690905466982759185164650150666678077272021890081392532363649111691002821924551541633624805969 : 475011489753746240024500178367364859418901588829939924748705578009262827369222834659815495729670558797454143390912073311509838111085236909370323483802926909195458815683174215323355088*i + 925039345882842856209794407096335244092780460386698951051338086161413597699668891541282650447520394073160493795142052782764553543711321165686302397695781016000953589530090195707014184 : 1)
"""
后量子密码，具体原理还不是很清楚，先记个脚本吧
exp：
import time
from itertools import product
from helpers import possibly_parallel, supersingular_gens, fast_log3
from richelot_aux import AuxiliaryIsogeny, Does22ChainSplit, Pushing3Chain
from uvtable import uvtable
from Crypto.Util.number import *
def _do_speedup():
proof.all(False)
from sage.misc.banner import require_version
if not require_version(9,7):
p = 2^127 - 1
to_patch = [GF(3), GF(3^2), GF(p), GF(p^2)]
for x in to_patch:
type(x).vector_space = sage.misc.cachefunc.cached_method(type(x).vector_space)
from sage.schemes.projective.projective_subscheme import AlgebraicScheme_subscheme_projective
AlgebraicScheme_subscheme_projective.dimension = lambda self: 1
_do_speedup()
def CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=1):
tim = time.time()
skB = []
expdata = [[0, 0, 0] for _ in range(b-3)]
for i in range(b%2, b-3, 2):
index = (b-i) // 2
row = uvtable[index-1]
if row[1] <= a:
expdata[i] = row[1:4]
bet1 = 0
while not expdata[bet1][0]:
bet1 += 1
bet1 += 1
ai,u,v = expdata[bet1-1]
bi = b - bet1
alp = a - ai
@possibly_parallel(num_cores)
def CheckGuess(first_digits):
scalar = sum(3^k*d for k,d in enumerate(first_digits))
tauhatkernel = 3^bi * (P3 + scalar*Q3)
tauhatkernel_distort = u*tauhatkernel + v*two_i(tauhatkernel)
C, P_c, Q_c, chainC = AuxiliaryIsogeny(bet1, u, v, E_start, P2, Q2, tauhatkernel, two_i)
split = Does22ChainSplit(C, EB, 2^alp*P_c, 2^alp*Q_c, 2^alp*PB, 2^alp*QB, ai)
if split:
Eguess, _ = Pushing3Chain(E_start, tauhatkernel, bet1)
chain, (E1, E2) = split
P3c = chainC(P3)
Q3c = chainC(Q3)
if E2.j_invariant() == Eguess.j_invariant():
CB, index = E1, 0
else:
CB, index = E2, 1
def apply_chain(c, X):
X = (X, None)
for f in c:
X = f(X)
return X[index]
P3c_CB = apply_chain(chain, P3c)
Q3c_CB = apply_chain(chain, Q3c)
Z3 = Zmod(3^b)
CB.set_order((p+1)^2, num_checks=1)
P_CB, Q_CB = supersingular_gens(CB)
P3_CB = ((p+1) / 3^b) * P_CB
Q3_CB = ((p+1) / 3^b) * Q_CB
w = P3_CB.weil_pairing(Q3_CB, 3^b)
for G in (P3_CB, Q3_CB):
xP = fast_log3(P3c_CB.weil_pairing(G, 3^b), w)
xQ = fast_log3(Q3c_CB.weil_pairing(G, 3^b), w)
if xQ % 3 != 0:
sk = int(-Z3(xP) / Z3(xQ))
return sk
return True
guesses = [ZZ(i).digits(3, padto=bet1) for i in range(3^bet1)]
for result in CheckGuess(guesses):
((first_digits,), _), sk = result
if sk is not None:
bobskey = sk
break
bobscurve, _ = Pushing3Chain(E_start, P3 + bobskey*Q3, b)
flag = bobscurve.j_invariant() == EB.j_invariant()
if flag:
print(long_to_bytes(bobskey))
def generate_distortion_map(E):
if E.a_invariants() != (0,6,0,1,0):
raise NotImplementedError
return E.isogeny(E.lift_x(ZZ(1)), codomain=E)
def generate_torsion_points(E, a, b):
def get_l_torsion_basis(E, l):
n = (p+1) // l
return (n*G for G in E.gens())
P2, Q2 = get_l_torsion_basis(E, 2**a)
P3, Q3 = get_l_torsion_basis(E, 3**b)
return P2, Q2, P3, Q3
a = 305
b = 192
p = 2^a*3^b - 1
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)
E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2)
two_i = generate_distortion_map(E_start)
P2, Q2, P3, Q3 = generate_torsion_points(E_start, a, b)
# 定义系数 A, B, C，这里需要将你提供的大整数转换为有限域 Fp2 中的元素
A = Fp2(1109655386602666580941477264844188509870568726343453010771770543665511250648180561681677488303290640863245633469198578301207900328491716466654470349910400724631139969542193124833051079*i+2116239248619087101677214169270633679594454755906693836568034229947351325062332338053907457802709748610111020509037164276717020111001082512633925347579357851693517057782645336434230575)
C = Fp2(783233241190388171387544682511032475647421068250023300290363249038620119995420899574317207343308349718411589404085433006020673690798356551667106568546291827001684869794402242067695854*i+1972744566958070881282131795626840370625118459932253321456562523309337576438614381897961997884583203821363249684189786452976563714388989414218292121069137192174721660268448964759287049)
# 定义椭圆曲线 E_B
EB = EllipticCurve(Fp2, [0, 6, 0, A, C])
EB.set_order((p + 1)^2, num_checks=0)
PB_x = Fp2(1792805099210360888864761590321391235025824991548234912676247217808406536821234881384389175924130468280991088357660252370848305634037983159579204419296531735459329230669983096853856246*i + 171253309786548245036128932419221024429140017061733162803654587078736014845338272553757000723916403099300493601067652633948439740076865619503812837361164299530464912490228468097800783)
PB_y = Fp2(354858932953470647164407208876248915819655125217303333206005726572045601374950018701435041440177841288062762055220650414072032960690957944114792835539535784706989279413982852603736575*i + 652241231208054817913369235175691302162155547428861981772486556413182925887029191547328926720048813218596706336154397071250972427384520853013935344373831652140490902941929446372831718)
PB_z = Fp2(1)
QB_x = Fp2(2186267301001259402114997355550578512125192708867710349339620240110565042023451739162302255305174185314466942521888744412961910909391429250064295777978302914701578195376147036042606489*i + 1113400569081370973415138408967328130898700595223023714237127216136706721906751381588571638690905466982759185164650150666678077272021890081392532363649111691002821924551541633624805969)
QB_y = Fp2(475011489753746240024500178367364859418901588829939924748705578009262827369222834659815495729670558797454143390912073311509838111085236909370323483802926909195458815683174215323355088*i + 925039345882842856209794407096335244092780460386698951051338086161413597699668891541282650447520394073160493795142052782764553543711321165686302397695781016000953589530090195707014184)
QB_z = Fp2(1)
PB = EB(PB_x, PB_y, PB_z)
QB = EB(QB_x, QB_y, QB_z)
CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=24)