无题

昨天跑路了！ 今天冲冲冲！😁😁😁

RSA & what

知识点:

咋天！做到共模攻击了！ 但是C太多了！

今天用

RSA 2021国赛

高位攻击

59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
    (65537, 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L)
    7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902

#sagemath

p4 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
pbits = 512
kbits = pbits - p4.nbits()
print (p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print ("x:" ,hex(int(x0)))
p = p4+x0
print ("p: ", int(p))
assert n % p == 0
q = n/int(p)
print ("q: ", int(q))

312
x: 0x9b4365759fb42a3faaf0c8888106bb9dbb1137769a37d191a7
p:  11437038763581010263116493983733546014403343859218003707512796706928880848035239990740428334091106443982769386517753703890002478698418549777553268906496423
q:  9918033198963879798362329507637256706010562962487329742400933192721549307087332482107381554368538995776396557446746866861247191248938339640876368268930589

import gmpy2
from Crypto.Util.number import long_to_bytes

p=11437038763581010263116493983733546014403343859218003707512796706928880848035239990740428334091106443982769386517753703890002478698418549777553268906496423

q=9918033198963879798362329507637256706010562962487329742400933192721549307087332482107381554368538995776396557446746866861247191248938339640876368268930589

e=0x10001

c=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
fn = (p-1)*(q-1)
d = gmpy2.invert(e, fn)
# c = pow(m,e,n)

m =pow(c,d,p*q)
print(str(long_to_bytes(m)).replace('ctf','flag'))

低指数攻击

import gmpy2

e = 3
# 读入 n, 密文
n= 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
c= 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
print 'n=', n
print 'c=', c
print '[+]Detecting m...'
result = gmpy2.iroot(c, 3)
print ' [-]The c has cubic root?', result[1]
if result[1]:
    print ' [-]The m is:', '{:x}'.format(result[0]).decode('hex')
    print '[!]All Done!'

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2021/6/1 15:16
# @Author  : upload
# @File    : [BJDCTF2020]easyrsa.py
# @Software: PyCharm
#!/bin/python3
# -*- coding: cp936 -*- import time

# -*- coding: cp936 -*- import gmpy2
# -*- coding: cp936 -*- import gmpy2
from Crypto.Util.number import *
import gmpy2


def dangerousRSA(a, b, c):
    m = 0
    while 1:
        n = gmpy2.iroot(c + m * a, b)
        if n[1] == True:
            e = int(n[0])
            print(long_to_bytes(e))
            break
        else:
            m += 1


dangerousRSA(
    123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009,
    3,
    19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893)

共模攻击

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2021/6/1 15:16
# @Author  : upload
# @File    : [BJDCTF2020]easyrsa.py
# @Software: PyCharm
#!/bin/python3
# -*- coding: cp936 -*- import time

# -*- coding: cp936 -*- import gmpy2
# -*- coding: cp936 -*- import gmpy2
from libnum import *
from Crypto.Util.number import *


def samen(a1, a2, b1, b2, c):
    def egcd(m, n):
        if n == 0:
            return m, 0
        else:
            x, y = egcd(n, m % n)
            return y, x - (m // n) * y

    k = egcd(b1, b2)
    k1 = k[0]
    k2 = k[1]

    # 求模反元素
    if k1 < 0:
        k1 = - k1
        a1 = invmod(a1, c)
    elif k2 < 0:
        k2 = - k2
        a2 = invmod(a2, c)
    e = long_to_bytes((pow(a1, k1, c) * pow(a2, k2, c)) % c)

    print(e)


samen(
    54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610,
    91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950,
    17, 65537,
    111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977)