Table of Contents

10月小结 #

github号被封了，抑郁了。被阿美莉卡狠狠卡脖子了

图床全线崩溃

求求你给我解封了吧

求求你了求求你了（塔菲求饶.jpg）

华子杯 #

next-prime-task #

生成机组数据发现对N直接开方得到可以得到p或q的近似值pd

多次测试后发现这个pd和p绝对值的差不会大于1000于是对pd减去1000后爆破得到p1 nextprime得到p2

抽象…

from Crypto.Util.number import *
from gmpy2 import next_prime, iroot
from flag import flag
assert flag[0:4]==b'flag'

m = bytes_to_long(flag)
assert size(m)<500

p = getPrime(512)
q = next_prime(p)

n = p * q
print('n=', n>>520)
e = 0x10001
c = pow(m, e, n)
print('c=', c)

'''
n= 28576274811010794362153160897556935178530640825011441539841241257190782139295561904323347128956873569754645071205043238985141474388531008367238218822591
c= 49502875285578675438052554215266678403659290915102322948363030271494959804587081871467110614683972929037615883922743651431683465100061968204901334627149795829429950385848753728500177164800064208215503246868631076011505268371936586645321659884527055007299822625570713613996139223348709621258028349513737798120
'''

from Crypto.Util.number import *
from gmpy2 import *
# n= 16212823795921249015201513720149784272087058934998256111313253824205027920859214121063981513487904645940216957428441144762656821271607914704124385625054
# c= 42623448757142425965793058163308735025128962287288212456406034320792801149338160716972860425304842585118914774556604523599336877170146028573856917845178178543459331490175081849764083076168568374304256040399932392040329806010797252107241692940719624357821612728032794873653073208064739506588169944780568217733
e = 0x10001
n= 28576274811010794362153160897556935178530640825011441539841241257190782139295561904323347128956873569754645071205043238985141474388531008367238218822591
c= 49502875285578675438052554215266678403659290915102322948363030271494959804587081871467110614683972929037615883922743651431683465100061968204901334627149795829429950385848753728500177164800064208215503246868631076011505268371936586645321659884527055007299822625570713613996139223348709621258028349513737798120

N = n<<520
pd = iroot(N,2)[0]

p1 = pd -10000

for i in range(1000):
    p1 = next_prime(p1)
    p2 = next_prime(p1)
    tmp = (p1*p2)>>520
    if(tmp == n):
        print(tmp - n)
        print(i)
        n1 = p1*p2
        phi = (p1-1)*(p2-1)
        d = inverse(e,phi)  
        m1 = pow(c,d,n1)
        print(long_to_bytes(m1))

EC_Party-I-chall #

狠活

hitcon2022 Chimera

将order的一个小因子除掉再乘以E(C)，可能会产生kp mod n的情况，这会让sagemath报错，我们得以看到kp的值：

试试脚本

ge/structure/element.c:15686)
  File "/usr/lib/python3/dist-packages/sage/schemes/elliptic_curves/ell_point.py", line 679, in _add_
    raise ZeroDivisionError("Inverse of %s does not exist (characteristic = %s = %s*%s)" % (x1-x2, N, N1, N2))
ZeroDivisionError: Inverse of 399142328555769122684976351600136585680104999923110415867753480206443969280985877697850841401824368944437043138064030332535786936031074694422398245233538680969600520572361311820112559527089421156024161654714350513598626449030622660 does not exist (characteristic = 762981334990685089884160169295988791471426441106522959345412318178660817286272606245181160960267776171409174142433857335352402619564485470678152764621235882232914864951345067231483720755544188962798600739631026707678945887174897543 = 37474009785980474658135106783131904659818035950984079581009709986840194575036321428945132957079423328996508289872067*20360280080732821723376422808980005582531004028308560803397168572148594993701208369640640375361387495696068328462829)

嚯嚯好家伙，还真有 kp mod n的情况，太震撼了

gcd一下就有

dq = inverse_mod(2,oq) 可以直接算dq

dp和2互素了我愿意称之为ecc rabin 构建公式

$$ f = (3x^2+a)^2-2x(4(x^3+ax+b))-C[0]4(x^3+ax+b) $$

只看出来是个对x求偏导后的式子，没看懂为啥这样，摆了

偷个脚本

from Crypto.Util.number import *

a,b,n,C = 138681122158674534796479818810828100269024674330030901179877002756402543027343312824423418859769980312713625658733, 4989541340743108588577899263469059346332852532421276369038720203527706762720292559751463880310075002363945271507040, 762981334990685089884160169295988791471426441106522959345412318178660817286272606245181160960267776171409174142433857335352402619564485470678152764621235882232914864951345067231483720755544188962798600739631026707678945887174897543, (19591102741441427006422487362547101973286873135330241799412389205281057650306427438686318050682578531286702107543065985988634367524715153650482199099194389191525898366546842016339136884277515665890331906261550080128989942048438965, 728465071542637655949094554469510039681717865811604984652385614821789556549826602178972137405550902004858456181137844771163710123158955524137202319902378503104952106036911634918189377295743976966073577013775200078470659428344462772)
E = EllipticCurve(Zmod(n),[a,b])
C = E(C)
order = 762981334990685089884160169295988791471426441106522959345445792076415993922016249232021560266153453470937452118572318136597282436269660557904217923887981072203978473274822142705255987334355747997513083011853917049784914749699536828

# fac ord_p*ord_q
# o = order // 8452217
# print(C*o)
# for i in range(1,10000):
#     tt = (order//i)*C

# 399142328555769122684976351600136585680104999923110415867753480206443969280985877697850841401824368944437043138064030332535786936031074694422398245233538680969600520572361311820112559527089421156024161654714350513598626449030622660
# p = GCD(n,kp)

p = 37474009785980474658135106783131904659818035950984079581009709986840194575036321428945132957079423328996508289872067
q = n//p
assert p*q == n
Ep = EllipticCurve(Zmod(p),[a,b])
Eq = EllipticCurve(Zmod(q),[a,b])
#print(Ep.order())
#print(Eq.order())
op = 37474009785980474658135106783131904659818035950984079581012533947688268013671227793391417023914911897089093262951596
oq = order // op
dq = inverse_mod(2,oq)
mq = dq*Eq(C)

print(Ep(C))
R.<x> = PolynomialRing(GF(p))
f = (3*x^2+a)^2-2*x*(4*(x^3+a*x+b))-C[0]*4*(x^3+a*x+b)

for i in (f.roots()):
    print(long_to_bytes(crt([int(i[0]),int(mq[0])],[p,q])))
print('done')

# 3crab1n_s0unds_go0d

香山杯 lift #

import os
import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag
def pad(s,l):
    return s + os.urandom(l - len(s))
def gen():
    g = getPrime(8)
    while True:
        p = g * random.getrandbits(138) + 1
        if isPrime(p):
            break
    while True:
        q = g * random.getrandbits(138) + 1
        if isPrime(q):
            break
    N = p ** 5 * q
    phi = p ** 4 * (p - 1) * (q - 1)
    d = random.getrandbits(256)
    e = inverse(d, phi)
    E = e * g
    hint = gmpy2.gcd(E, phi)
    return N, E, hint

flag = pad(flag,64)
m = bytes_to_long(flag)
n,e,hint = gen()
c = pow(m,e,n)
print(f'hint = {hint}')
print(f'n = {n}')   
print(f'e = {e}')
print(f'c = {c}')
hint = 251
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

因为

$$ \phi(n)=p^4*(r_1 r_2g^2)=0(\ mod \ p^4) $$

所以

$$ ed-1=k\phi(n)=0 mod \ p^4 $$

此时256大小的d就可以用small root求出来了

求得p和q后，因为e和phi（p）phi（q）

不互素，这里的情况和*CTF 2021 little case 类似，decrypt2处理

$$ phip = p ^ 4 * (p - 1) $$

一开始没想通，但其实和decrypt里面是一样的

用AMM应该也可以解

exp

from Crypto.Util.number import *
import itertools




hint = 251
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162
e //= hint
RP.<x> = PolynomialRing(Zmod(n))
f = e*x -1
f = f.monic()
x0 = f.small_roots(X = 2^256,beta = 0.4)
print(x0)

x0 = 39217838246811431279243531729119914044224429322696785472959081158748864949269

p4 = GCD(x0*e-1,n)
# 23153425300889483483553551112335873301449089474555179592930187730428387181422112282990079197590872977617830286073037301064978277511828551780538222539198674709759058026997715121

# print(gmpy2.iroot(int(p4),int(4)))
# (mpz(69367143733862710652791985332025152581988181), True)
p = 69367143733862710652791985332025152581988181
q = n // p ^ 5

phi = p ^ 4 * (p - 1) * (q - 1)
d=  inverse(e,phi)
# 39217838246811431279243531729119914044224429322696785472959081158748864949269


cp = c % p^5
cq = c % q

e = e*hint

def decrypt2(p,c,e):
    phip = p ^ 4 * (p - 1) 
    
    w = GCD(e,phip)
    p1 = phip // w
    b = inverse(e,p1)
    
    g = get_oneroot2(p,w)    
    m = pow(c,b,p^5)
    mps = [ZZ(m*g^i) for i in range(w)]
    return mps

def get_oneroot2(p,w):
    while 1:
        Zp = Zmod(p^5)
        g = Zp.random_element()
        g = g^(p^4*(p-1)//w)
        for i in divisors(w):
            if(i != w):
                g2 = g^i
                if(g2 ==1):
                    break
        else:
            # break
            return g


mps = decrypt2(p,cp,e)




def get_oneroot(p,w):

    while 1:
        Zp = Zmod(p)
        g = Zp.random_element()
        g = g^((p-1)//w)
        for i in divisors(w):
            if(i != w):
                g2 = g^i
                if(g2 ==1):
                    break
        else:
            return g

def decrypt(p,c,e):
    phip = p-1
    w =  GCD(e,phip)
    p1 = phip//w
    b = inverse(e,p1)
    
    g = get_oneroot(p,w)
    m = pow(c,b,p)
    return [ZZ(m*g^i) for i in range(w)]

mqs = decrypt(q,cq,e)


            
for mp, mq in itertools.product(mps, mqs):
    m = crt([mp, mq], [p^5, q])
    msg = long_to_bytes(int(m))
    if (b'flag' in msg):
        print(msg)

安卓动态调试 #

jeb-demo-4.16.0

照着看雪的教程改一下就能跑
机器：oneplus7T
OS：lineageOS

调了两个没混淆的题，没什么意思，github图床炸了，不放图了