看鸡块神的博客复现一下，学到了很多东西
*easy_log
题目：
from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
from os import urandom
from random import randint
from collections import namedtuple
from signal import alarm
Point = namedtuple("Point", "x y")
O = "Origin"
def point_addition(P, Q, n):
if P == O:
return Q
if Q == O:
return P
x = (P.x * Q.y + P.y * Q.x - P.x * Q.x) % n
y = (P.x * Q.x + P.y * Q.y) % n
return Point(x, y)
def double_and_add(k, P, n):
Q = P
R = O
while(k > 0):
if k & 1:
R = point_addition(R, Q, n)
k >>= 1
Q = point_addition(Q, Q, n)
return R
with open("flag.txt", "rb") as f:
flag = f.read()
assert len(flag) == 50
flag = urandom(randint(38, 48)) + flag
flag = flag + urandom(118 - len(flag))
flag1, flag2 = bytes_to_long(flag[:68]), bytes_to_long(flag[68:])
n = 0x231d5fa471913e79facfd95e9b874e2d499def420e0914fab5c9f87e71c2418d1194066bd8376aa8f02ef35c1926f73a46477cd4a88beae89ba575bb3e1b04271426c6706356dd8cd9aa742d7ad0343f8939bfd2110d45122929d29dc022da26551e1ed7000
G1 = Point(0xf22b9343408c5857048a19150c8fb9fd44c25d7f6decabc10bf46a2250a128f0df15adc7b82c70c0acaf855c0e898b141c9c94ba8aef8b67ea298c6d9fd870ea70e1c4f8a1b595d15373dc6db25a4ecddf626a64f47beba5538b7f733e4aa0c4f1fd4c291d, 0x8d3264514b7fdbce97fbaedb33120c7889a1af59691a1947c2c7061347c091b0950ca36efaa704514004a988b9b87b24f5cebf2d1c7bef44ff172519e1a62eb62cde234c94bd0ab39375d7ddb42e044090c8db46d3f965ef7e4753bc41dac3b8b3ae0cdb57)
G2 = Point(0x81919777837d3e5065c6f7f6801fe29544180be9db2137f075f53ebb3307f917183c6fc9cdfc5d75977f7, 0xd1a586d6848caa3a5436a86d903516d83808ce2fa49c5fb3f183ecb855e961c7e816a7ba8f588ef947f19)
f1 = double_and_add(flag1, G1, n)
print(f1)
alarm(30)
if flag1 != int(input()):
exit()
p = int(input())
assert isPrime(p) and p.bit_length() == 400
f2 = double_and_add(flag2, G2, p)
print(f2)
这道题的n是一个合数，分解如下：
[(2, 12), (5, 4), (15271784978279, 1), (10714146599832792643, 1), (222696442740376752383, 3), (899889935029682511225429150065010811552017719005924136271659166808024139, 1), (899889935029682511225429150065010811552017719005924136271659168643090431, 1)]
思路就是使用分成多个小数然后做crt(这步只是单纯的crt)，得到：
这种形式的式子，再分别算出他们的
分别对应着在，最后做crt即可
先测试一下每个factor的阶
print(double_and_add(15271784978279 - 1, G1, 15271784978279))
# Point(x=0, y=1)
print(double_and_add(10714146599832792643^2 - 1, G1, 10714146599832792643))
# Point(x=0, y=1)
print(double_and_add(222696442740376752383^2 - 1, G1, 222696442740376752383))
# Point(x=0, y=1)
print(double_and_add(899889935029682511225429150065010811552017719005924136271659168643090431 - 1, G1, 899889935029682511225429150065010811552017719005924136271659168643090431))
# Point(x=0, y=1)
这就可以测试出阶不是就是
现在的问题就是如何得到，其实就是Pohlig_Hellman+BSGS
这块原理不懂的可以去看看我之前写的离散对数|Chestnut's blog
原文写的是Pohlig_Hellman+discrete_log，这次不使用的原因：
这不是一条常规的椭圆曲线，要用discrete_log必须要做映射，这道题就不用这么麻烦了
exp：
from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
from collections import namedtuple
Point = namedtuple("Point", "x y")
O = "Origin"
def point_addition_Qp(P, Q):
if P == O:
return Q
if Q == O:
return P
x = (P.x * Q.y + P.y * Q.x - P.x * Q.x)
y = (P.x * Q.x + P.y * Q.y)
return Point(x, y)
def double_and_add_Qp(k, P):
Q = P
R = O
while (k > 0):
if k & 1:
R = point_addition_Qp(R, Q)
k >>= 1
Q = point_addition_Qp(Q, Q, )
return R
def point_addition(P, Q, n):
if P == O:
return Q
if Q == O:
return P
x = (P.x * Q.y + P.y * Q.x - P.x * Q.x) % n
y = (P.x * Q.x + P.y * Q.y) % n
return Point(x, y)
def double_and_add(k, P, n):
Q = P
R = O
while (k > 0):
if k & 1:
R = point_addition(R, Q, n)
k >>= 1
Q = point_addition(Q, Q, n)
return R
def lift_to_pk(p, G, kG):
order_p = p ^ 2 - 1
QPP = Qp(p)
P_Qp = Point(QPP(G[0] % p ^ 2), QPP(G[1] % p ^ 2))
Q_Qp = Point(QPP(kG[0] % p ^ 2), QPP(kG[1] % p ^ 2))
nP_Qp = double_and_add_Qp(order_p, P_Qp)
nQ_Qp = double_and_add_Qp(order_p, Q_Qp)
secret_p = ZZ((-nQ_Qp[0] / nQ_Qp[1]) / (-nP_Qp[0] / nP_Qp[1]))
return secret_p % p
def bsgs(G, kG, p, order):
t = int(sqrt(order)) + 2
dic = {}
tG = double_and_add(t, G, p)
atG = Point(0, 1)
for a in range(t):
dic[atG] = a
atG = point_addition(atG, tG, p)
bG = kG
_G = double_and_add((-1) % order, G, p)
for b in range(t):
if (bG in dic.keys()):
return t * dic[bG] + b
bG = point_addition(bG, _G, p)
def pohlig_hellman(G, kG, p, order):
factors = list(factor(order))
moduli = []
remainders = []
print(f"[+] Running Pohlig Hellman")
print(factors)
for i, j in factors:
mod = i ** j
g2 = double_and_add (order // mod, G, p)
q2 = double_and_add (order // mod, kG, p)
r = bsgs(g2, q2, p, mod)
remainders.append(r)
moduli.append(mod)
return crt(remainders, moduli)
G1 = Point(0xf22b9343408c5857048a19150c8fb9fd44c25d7f6decabc10bf46a2250a128f0df15adc7b82c70c0acaf855c0e898b141c9c94ba8aef8b67ea298c6d9fd870ea70e1c4f8a1b595d15373dc6db25a4ecddf626a64f47beba5538b7f733e4aa0c4f1fd4c291d, 0x8d3264514b7fdbce97fbaedb33120c7889a1af59691a1947c2c7061347c091b0950ca36efaa704514004a988b9b87b24f5cebf2d1c7bef44ff172519e1a62eb62cde234c94bd0ab39375d7ddb42e044090c8db46d3f965ef7e4753bc41dac3b8b3ae0cdb57)
G2 = Point(0x81919777837d3e5065c6f7f6801fe29544180be9db2137f075f53ebb3307f917183c6fc9cdfc5d75977f7, 0xd1a586d6848caa3a5436a86d903516d83808ce2fa49c5fb3f183ecb855e961c7e816a7ba8f588ef947f19)
n = 0x231d5fa471913e79facfd95e9b874e2d499def420e0914fab5c9f87e71c2418d1194066bd8376aa8f02ef35c1926f73a46477cd4a88beae89ba575bb3e1b04271426c6706356dd8cd9aa742d7ad0343f8939bfd2110d45122929d29dc022da26551e1ed7000
primes = [(2, 12), (5, 4), (15271784978279, 1), (10714146599832792643, 1), (222696442740376752383, 3), (899889935029682511225429150065010811552017719005924136271659166808024139, 1), (899889935029682511225429150065010811552017719005924136271659168643090431, 1)]
kG = Point(x=2224276869527908469738142640324051586650164162458890190326617872567588843883404684013209198264358968626023542526675981164004662169904085819896583412198882367292994147501900860390967832920988460593858191215086432463293101505512285280149038483611, y=1897504218456167105276802271695484916264714305056080197995509459081477275706953410193678808765972307489078607776999696280473752058490856800492182555246356035940993464140010512627381487982859068123972131059519394567499382311519938893552997158117)
ps = []
ord_p = []
for p, exp in [(15271784978279, 1)]:
ps.append(p - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p - 1))
for p, exp in [(10714146599832792643, 1)]:
ps.append(p^2 - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p^2 - 1))
for p, exp in [(222696442740376752383, 3)]:
ps.append(p^2 - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p^2 - 1))
for p, exp in [(899889935029682511225429150065010811552017719005924136271659168643090431, 1)]:
ps.append(p - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p - 1))
m = crt(ord_p, ps)
print(m)
# 8291093632205330754442060286842544743344821451894268935950949621376765012618290131797098830463136456017508420660006277048857581929486220875900976371442815134
print(len(bin(8291093632205330754442060286842544743344821451894268935950949621376765012618290131797098830463136456017508420660006277048857581929486220875900976371442815134)[2:]))
# 522
这样只能算出522bit的，但是f1大概是544bit(8*68)，所以数量级还是不太够的，使用p-adic
来求出，先把鸡块神的exp放在这
def point_addition_Qp(P, Q):
if P == O:
return Q
if Q == O:
return P
x = (P.x * Q.y + P.y * Q.x - P.x * Q.x)
y = (P.x * Q.x + P.y * Q.y)
return Point(x, y)
def lift_to_pk(p, G, kG):
order_p = p^2 - 1
QPP = Qp(p)
P_Qp = Point(QPP(G[0] % p^2), QPP(G[1] % p^2))
Q_Qp = Point(QPP(kG[0] % p^2), QPP(kG[1] % p^2))
nP_Qp = double_and_add_Qp(order_p, P_Qp)
nQ_Qp = double_and_add_Qp(order_p, Q_Qp)
secret_p = ZZ((-nQ_Qp[0]/nQ_Qp[1]) / (-nP_Qp[0]/nP_Qp[1]))
return secret_p % p
for p, exp in [(222696442740376752383, 3)]:
ps.append(p)
ord_p.append(lift_to_pk(p, G, kG))
详细解释一下，这是用p-adic求出下的dlp
先说下常规的dlp中如下：
通过上述方程求出模p下的x
exp:
R = Zp(rr, prec=2)
x = (R(ks[i]).log() / R(69).log()).lift()
结合这两张图或许就能弄清楚p-adic的原理了
其实只需要知道对于，利用它可以求出的dlp
回到这道题中，在ECC中的p-adic应用就类似于smart attack
参考：ECC笔记|独奏小屋
解释一下每一步代码的作用
QPP = Qp(p)
P_Qp = Point(QPP(G[0] % p^2), QPP(G[1] % p^2))
Q_Qp = Point(QPP(kG[0] % p^2), QPP(kG[1] % p^2))
是为了把域提升到
nP_Qp = double_and_add_Qp(order_p, P_Qp)
nQ_Qp = double_and_add_Qp(order_p, Q_Qp)
#######################测试阶
print(double_and_add(p**2,nP_Qp,p**2))
Point(x=0, y=1 + O(222696442740376752383^20))
确保点在，并且发现点的order变成p^2，也就达到了，这样才能完成对数映射，使对 ，有：
最后放在一起进行crt就行了
exp：
from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
from collections import namedtuple
Point = namedtuple("Point", "x y")
O = "Origin"
def point_addition_Qp(P, Q):
if P == O:
return Q
if Q == O:
return P
x = (P.x * Q.y + P.y * Q.x - P.x * Q.x)
y = (P.x * Q.x + P.y * Q.y)
return Point(x, y)
def double_and_add_Qp(k, P):
Q = P
R = O
while (k > 0):
if k & 1:
R = point_addition_Qp(R, Q)
k >>= 1
Q = point_addition_Qp(Q, Q, )
return R
def point_addition(P, Q, n):
if P == O:
return Q
if Q == O:
return P
x = (P.x * Q.y + P.y * Q.x - P.x * Q.x) % n
y = (P.x * Q.x + P.y * Q.y) % n
return Point(x, y)
def double_and_add(k, P, n):
Q = P
R = O
while (k > 0):
if k & 1:
R = point_addition(R, Q, n)
k >>= 1
Q = point_addition(Q, Q, n)
return R
def lift_to_pk(p, G, kG):
order_p = p ^ 2 - 1
QPP = Qp(p)
P_Qp = Point(QPP(G[0] % p ^ 2), QPP(G[1] % p ^ 2))
Q_Qp = Point(QPP(kG[0] % p ^ 2), QPP(kG[1] % p ^ 2))
nP_Qp = double_and_add_Qp(order_p, P_Qp)
nQ_Qp = double_and_add_Qp(order_p, Q_Qp)
secret_p = ZZ((-nQ_Qp[0] / nQ_Qp[1]) / (-nP_Qp[0] / nP_Qp[1]))
return secret_p % p
def bsgs(G, kG, p, order):
t = int(sqrt(order)) + 2
dic = {}
tG = double_and_add(t, G, p)
atG = Point(0, 1)
for a in range(t):
dic[atG] = a
atG = point_addition(atG, tG, p)
bG = kG
_G = double_and_add((-1) % order, G, p)
for b in range(t):
if (bG in dic.keys()):
return t * dic[bG] + b
bG = point_addition(bG, _G, p)
def pohlig_hellman(G, kG, p, order):
factors = list(factor(order))
moduli = []
remainders = []
print(f"[+] Running Pohlig Hellman")
print(factors)
for i, j in factors:
mod = i ** j
g2 = double_and_add (order // mod, G, p)
q2 = double_and_add (order // mod, kG, p)
r = bsgs(g2, q2, p, mod)
remainders.append(r)
moduli.append(mod)
return crt(remainders, moduli)
G1 = Point(0xf22b9343408c5857048a19150c8fb9fd44c25d7f6decabc10bf46a2250a128f0df15adc7b82c70c0acaf855c0e898b141c9c94ba8aef8b67ea298c6d9fd870ea70e1c4f8a1b595d15373dc6db25a4ecddf626a64f47beba5538b7f733e4aa0c4f1fd4c291d, 0x8d3264514b7fdbce97fbaedb33120c7889a1af59691a1947c2c7061347c091b0950ca36efaa704514004a988b9b87b24f5cebf2d1c7bef44ff172519e1a62eb62cde234c94bd0ab39375d7ddb42e044090c8db46d3f965ef7e4753bc41dac3b8b3ae0cdb57)
G2 = Point(0x81919777837d3e5065c6f7f6801fe29544180be9db2137f075f53ebb3307f917183c6fc9cdfc5d75977f7, 0xd1a586d6848caa3a5436a86d903516d83808ce2fa49c5fb3f183ecb855e961c7e816a7ba8f588ef947f19)
n = 0x231d5fa471913e79facfd95e9b874e2d499def420e0914fab5c9f87e71c2418d1194066bd8376aa8f02ef35c1926f73a46477cd4a88beae89ba575bb3e1b04271426c6706356dd8cd9aa742d7ad0343f8939bfd2110d45122929d29dc022da26551e1ed7000
primes = [(2, 12), (5, 4), (15271784978279, 1), (10714146599832792643, 1), (222696442740376752383, 3), (899889935029682511225429150065010811552017719005924136271659166808024139, 1), (899889935029682511225429150065010811552017719005924136271659168643090431, 1)]
kG = Point(x=2224276869527908469738142640324051586650164162458890190326617872567588843883404684013209198264358968626023542526675981164004662169904085819896583412198882367292994147501900860390967832920988460593858191215086432463293101505512285280149038483611, y=1897504218456167105276802271695484916264714305056080197995509459081477275706953410193678808765972307489078607776999696280473752058490856800492182555246356035940993464140010512627381487982859068123972131059519394567499382311519938893552997158117)
ps = []
ord_p = []
#
for p, exp in [(15271784978279, 1)]:
ps.append(p - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p - 1))
for p, exp in [(10714146599832792643, 1)]:
ps.append(p^2 - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p^2 - 1))
for p, exp in [(222696442740376752383, 3)]:
ps.append(p^2 - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p^2 - 1))
for p, exp in [(899889935029682511225429150065010811552017719005924136271659168643090431, 1)]:
ps.append(p - 1)
ord_p.append(pohlig_hellman(G1, kG, p, p - 1))
for p, exp in [(222696442740376752383, 3)]:
ps.append(p)
ord_p.append(lift_to_pk(p, G1, kG))
m = crt(ord_p, ps)
print(m)
print(double_and_add(m, G1, n) == kG)
# 3592546015395039919887293342353263546202391102114673020757423219465064490744698208336753221222680544517208870580277861521886831942329468552820982393893546758562974
# True
补充：鸡块神最后说了一个曲线方程插值法，我从rec师傅的博客找到了，代码如下：
from Crypto.Util.number import *
# from pwn import *
from tqdm import tqdm, trange
# from math import sqrt, prod
from collections import namedtuple
Point = namedtuple("Point", "x y")
O = "Origin"
def point_addition(P, Q, n):
if P == O:
return Q
if Q == O:
return P
x = (P.x * Q.y + P.y * Q.x - P.x * Q.x) % n
y = (P.x * Q.x + P.y * Q.y) % n
return Point(x, y)
def double_and_add(k, P, n):
Q = P
R = O
while (k > 0):
if k & 1:
R = point_addition(R, Q, n)
k >>= 1
Q = point_addition(Q, Q, n)
return R
p = 899889935029682511225429150065010811552017719005924136271659168643090431
G1 = Point(0xf22b9343408c5857048a19150c8fb9fd44c25d7f6decabc10bf46a2250a128f0df15adc7b82c70c0acaf855c0e898b141c9c94ba8aef8b67ea298c6d9fd870ea70e1c4f8a1b595d15373dc6db25a4ecddf626a64f47beba5538b7f733e4aa0c4f1fd4c291d, 0x8d3264514b7fdbce97fbaedb33120c7889a1af59691a1947c2c7061347c091b0950ca36efaa704514004a988b9b87b24f5cebf2d1c7bef44ff172519e1a62eb62cde234c94bd0ab39375d7ddb42e044090c8db46d3f965ef7e4753bc41dac3b8b3ae0cdb57)
G2 = Point(0x81919777837d3e5065c6f7f6801fe29544180be9db2137f075f53ebb3307f917183c6fc9cdfc5d75977f7, 0xd1a586d6848caa3a5436a86d903516d83808ce2fa49c5fb3f183ecb855e961c7e816a7ba8f588ef947f19)
from itertools import product
R, (x, y) = GF(p)["x", "y"].objgens() # try on each p, since we need to compute kernel basis
xt, yt = 2, 2
monomials = [x**i*y**j for i, j in product(range(xt+1), range(yt+1))]
kG2 = [double_and_add(randint(0, p), G2, p) for _ in range(len(monomials)+1)]
A = matrix(GF(p), [[monomial(x, y) for monomial in monomials] for x, y in kG2])
coefs = A.right_kernel().basis()
for coef in coefs:
f = sum([fi*monomial for fi, monomial in zip(coef, monomials)])
print(coef)
print(f)
# (1, 0, 899889935029682511225429150065010811552017719005924136271659168643090430, 0, 1, 0, 1, 0, 0)
# x^2 + x*y - y^2 + 1
*OhMyTetration
题目：
from Crypto.Util.number import bytes_to_long
from secret import LotteryCenter, FLAG
import signal
def handler1(signum, frame):
raise TimeoutError("You took too long to make a decision. The boss is not patient.")
def handler2(signum, frame):
e = '''
Before I can react, a heavy hand clamps onto my shoulder. The boss's face is dark with rage. "What the hell did you do?!"
I stammer, "I just thought the numbers could be luckier..."
"OUT!" he roars, dragging me toward the door. "And don't come back unless you've got the money to replace this thing!"
'''
raise TimeoutError(e)
x = bytes_to_long(FLAG)
assert x.bit_length() <= 512
descrption = """
You step into the Lottery Center, the bell above the door rings softly as you enter. The air is stale, with an old fan humming above. The walls are lined with lottery posters and flashing numbers. At the counter, a middle-aged man in a dark suit is busy sorting through some papers, unaware of your presence.
The atmosphere is quiet and slightly unsettling. You glance around the room — a corner has an old lottery machine, still occasionally making a "clicking" noise. There's a poster on the wall showing today's lucky numbers, but they seem somewhat blurry.
"""
print(descrption)
lotteryCenter = LotteryCenter()
menu = """
You're left with a few choices:
1. Talk to the Boss.
2. Pick Your Lucky Number.
3. Choose Your Bet Size.
4. Look Around.
"""
signal.signal(signal.SIGALRM, handler1)
signal.alarm(600)
while 1:
print(menu)
choice = input("What do you do? ")
if choice == "1":
# Choose my favourite number.
print(f"You approach the counter. The boss looks up briefly, then says in a low voice, \"Today's lucky number is {lotteryCenter.P}. Trust it, it will bring good luck.\"")
elif choice == "2":
g = int(input("You decide to pick your own lucky number: "))
if lotteryCenter.defineG(g):
print("You successfully pick your lucky number.")
else:
print("You can't pick that number.")
elif choice == "3":
if lotteryCenter.g==None:
print("You should pick your lucky number first.")
else:
times = int(input("You decide to pick your bet size: "))
assert times>0
ticket = lotteryCenter.tetration(times, x)
# Calculate the tetration g^g^...^g(times)^x.
# For example, P=23, g=3, tetration(3, 2) = 3^(3^(3^2)) % 23 = 12.
print(f"You take the ticket with the number {ticket} from the machine, feeling a slight chill in the air. The boss looks at you for a moment longer, his expression unreadable. Then, with a slow smile, he finally speaks, his voice low but clear:")
print("\"Good luck... I hope today is your lucky day.\"")
break
elif choice == "4":
print("The boss seems distracted — perhaps counting cash or sorting through stacks of old receipts, his back turned just enough. Seizing the moment, I slip around to the back of the lottery machine, my fingers hovering over the controls. A quiet smirk tugs at my lips as I mutter under my breath ...")
lotteryCenter.P = int(input("I don't think the boss's lucky number is lucky enough: "))
assert lotteryCenter.P>1
x = int(input("\"Yes!\" I whisper, overriding the preset algorithm with my own: "))
g = int(input("You decide to pick your own lucky number: "))
times = int(input("You decide to pick your bet size: "))
assert times>0
signal.signal(signal.SIGALRM, handler2)
signal.alarm(10)
try:
if lotteryCenter.defineG(g):
ticket = lotteryCenter.tetration(times, x)
print(f"You take the ticket with the number {ticket} from the machine secretly.")
else:
print("Oops! The lottery machine whirs weakly as I finish tampering with its settings — then suddenly, the screen flickers violently before dying with a pathetic click. A thin wisp of smoke curls from the vents.")
except TimeoutError as e:
print(e)
finally:
signal.alarm(0)
break
else:
print("Nothing here.")
print("\nYou exit the Lottery Center, the door closing softly behind you. The bell rings once more, leaving you standing outside, holding the ticket — unsure if you've just stepped into a stroke of luck... or something else entirely.")
简化一下问题就是：
求解x
由于， 并且很光滑，我们就可以发送它的低阶因子当作g，然后将求出的x做crt
因子位数很少，使用bsgs
exp:
def bsgs(g, Gi, h, qi):
m = int(sqrt(qi)) + 3
dic = dict()
for a in trange(m + 1):
dic[pow(g, 2*pow(Gi, a*m, q), p)] = a # p的阶等于p-1=2q ，所以要乘个2
for b in trange(m + 1):
t = pow(h, 2*pow( Gi, -b, q), p)
if t in dic:
return dic[t]*m + b
return None
# 这道题的g和Gi相等
for i in range(len(fac)):
Gi = powmod(G, (q-1)//fac[i], q)
k.append(bsgs(g, Gi, c[i],fac[i])) # satisfy Gi^ki = m^(ti*ai) % q
print(k)