【密码学】xyctf-babyrsamax

from Crypto.Util.number import *
from gmpy2 import *
from random import choice

flag = b'XYCTF{******}'
e = '?'
def getBabyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getBabyPrime(512)
q = getBabyPrime(512)
n = p*q
gift1 = (pow(p,e,n)-pow(q,e,n)) % n
gift2 = pow(p+q,e,n)

t = 65537
x = bytes_to_long(e)
y = pow(x, t, n)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'gift1 = {gift1}')
print(f'gift2 = {gift2}')
print(f'c = {c}')
print(f'y = {y}')

'''
n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217

'''

p-1,q-1一眼光滑，可以pollards p-1分解n，第一问的e=4096就出来了。

然后神奇的就来了别人的wp说这是rabin加密，类rsa

主要是e//4,phi互质，但算不出答案。

 但直接用扩展欧几里德求“逆元”，然后开4次方就能得到正确结果。其中的数学逻辑还需深究。

由于明文m很小，单独用p或者q也能求解。

#!python2
# -*- coding: utf-8 -*-
# @Time : 2020/9/8 20:54
# @Author : A.James
# @FileName: exp.py
import gmpy2
from Crypto.Util.number import *

def Pollards_p_1(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        res = gmpy2.gcd(a-1, N)
        if res != 1 and res != N:
            print('n =', n) 
            print('p =', res) 
            return res
        n += 1
    print('factor')
# e = 0x10001
# n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
# c = 145742860621666495489510776707734134231023214235535481878205099324276369445463746101469487674333600296204530932386373415987357363515200117271393133347844479863240936801112306080456942844796779477817786176831015954410967693647534326733641573842953783193563678040093734579772976410574013857063137696465850300484753282472377882118892522844694078667622111244886303620349388556315704648609353412177123230438077637042880490566244740468503369707900343076369151796123461132932226563486870411965536062339169788331659119981901553536009275158600580698576110294775989992794065611215170351808698605911258789407992833170968332058255364527244293283228694886707241979238145252395651417561576433516407782575454294499521347378058366557950770592472271985004818847838711060048422015207674862177145761946560579360220239667890707135827136815780729363013864130107808776517514214310689477005999830284272130148939734935547341627208913181919190392205389452185597444280635342938046191904062547803917870268485346888653569349729643793041018550170090471310374856687407102762116819004790791936814214507908374380597027347007448114684844276041116955473180015221164545212550832233007714133699817366745648092776901013502840540012912660742166994968977400188176557657864
n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217
e=0x10001
# p = Pollards_p_1(n)
p = 236438400477521597922950445153796265199072404577183190953114805170522875904551780358338769440558816351105253794964040981919231484098097671084895302287425479
q = n // p
assert p*q == n

print('phi',GCD(e,(p-1)*(q-1)))
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(y, d, n)
print(long_to_bytes(m)) 
import libnum
# b'flag{Pollard_s_p-1_&_
e=4096
print('phi',GCD(e,(p-1)*(q-1)),GCD(e,(p-1)),GCD(e,(q-1)))
d=libnum.xgcd(e,(p-1)*(q-1))[0]
print(f"d--{d}",(e*d-4)%(p-1)*(q-1))
# d=pow(e,-1,(p-1)*(q-1))
m=pow(c,d,n)
m=gmpy2.iroot(m,4)[0]
print(long_to_bytes(m))

print(libnum.xgcd(2*5,6))

d=libnum.xgcd(e,(q-1))[0]
m=pow(c,d,q)
m=gmpy2.iroot(m,2)[0]
print(long_to_bytes(m))