Principle and practice of common defects in RSA encryption application

Resource download address ：https://download.csdn.net/download/sheziqiong/85882450
Resource download address ：https://download.csdn.net/download/sheziqiong/85882450

Preface

After understanding the basic concepts , Code can explain everything , Therefore, this paper refines the implementation method of each attack mode into a function , It will be helpful in understanding the principle , You can also call directly when necessary .

Basics

RSA Summary

Before you start, you can pass 《RSA Algorithm details 》 This article is about RSA Basic knowledge of , Including encryption and decryption methods , Algorithm principle and feasibility proof .

Application process

1. Select two larger prime numbers that are not equal to each other p and q, Calculation n = p * q .
2. Calculation phi = (p-1) * (q-1) .
3. Select any e, bring e Satisfy 1<e<phi And gcd(e , phi) == 1 .
4. Calculation e About phi Modular inverse element of d, namely d Satisfy (e * d)% phi ==1 .
5. encryption ：c = (m ^ e) % n , m = (c ^ d) % n . among m In plain text ,c For the cipher ,(n,e) Is a public key pair ,d For private key , requirement 0 <= m < n .

Understand modular inverse operation

• If (a*b)%c==1 , that a and b Each other's mold c Modular inverse element of / Number theory reciprocal , Also writing

• 

• There is a basic fact about the greatest common divisor ： Give two integers a、c, There must be an integer x、y bring ax + cy = gcd(a,c) , Based on this fact , When a,c Mutual prime is gcd(a,c)==1 when , Yes ax+cy=1 , Then there is (a*x)%c==1 , therefore x Namely a Yes c Modular inverse element of . therefore ,a Yes c There are modular inverse elements b If and only if gcd(a,c)==1 . Obviously for each group a,c , There is a family of x, In finding the modular inverse, we obtain the minimum positive integer solution x mod n .

• The basic facts mentioned above are easy to understand , because a and c The greatest common divisor of gcd(a,b), therefore a and c Can be expressed as gcd(a,b) Integer multiple , that a and b Linear combination of any integral coefficients of ax+by It must also be expressed as gcd(a,c) Integer multiple , The smallest positive integer among them should be gcd(a,c). In fact, there is a definition of the greatest common divisor ：a and b Maximum common divisor of g yes a and b The smallest positive integer in the linear sum of .

  • The modular inverse is mainly based on the extended Euclidean algorithm , Post one Python Realization ：

     def egcd ( a , b ):
         if (b == 0):
             return 1, 0, a
         else:
             x , y , q = egcd( b , a % b ) # q = GCD(a, b) = GCD(b, a%b)
             x , y = y, ( x - (a // b) * y )
             return x, y, q 
    def mod_inv(a,b):
        return egcd(a,b)[0]%b # seek a model b Get the inverse element 
    

• The inverse of modules can also be directly used gmpy2 library . Such as import gmpy2;print gmpy2.invert(47,30) Obtainable 47 model 30 The inverse of is 23.

Algorithm in modular sense

(a + b) % n ≡ (a % n + b % n) % n
(a - b) % n ≡ (a % n - b % n) % n
(a * b) % n ≡ (a % n * b % n) % n
(a ^ b) % n ≡ ((a % n) ^ b) % n // Power operation 

 if  a ≡ b(mod n) , be 
1. For any positive integer c, Yes a^c ≡ b^c(mod n)
2. For any integer c, Yes ac ≡ bc(mod n),a+c ≡ b+c(mod n),
3. if  c ≡ d(mod n), be a-c ≡ b-d(mod n),a+c ≡ b+d(mod n),ac ≡ bd(mod n)

 If ac≡bc (mod m), And c and m Coprime , be a≡b (mod m）.
[ understand ： If and only if c and m Coprime ,c^-1 There is , The left and right sides of the equation can be multiplied by modulo inverses .]

 Division Rules ：
 In the mold n In the sense of ,a/b It no longer just represents the division of these two numbers , But to  a+k1*n  and  b+k2*n Any two of these two groups are divided , Make the quotient an integer 
 So it's understandable , Dividing by a number is equivalent to multiplying by its inverse 
a/b ≡ c(mod n) <=> a ≡ c*(b^-1) (mod n), among b model n The inverse of is b Negative power of .

 Fermat's small Theorem :
a Is an integer ,p Prime number , be a^p==a(mod p), If a No p Multiple , also a^(p-1) ≡ 1(mod p)	

Recommended articles Modular operation summary and Algorithm involved in modulo operation .

Euclid algorithm

Euclidean algorithm is an algorithm for finding the greatest common divisor , That is, what I learned in Middle School division . remember gcd(a,b) by a and b Maximum common divisor of , The basic principle of Euclidean algorithm is gcd(a,b)==gcd(b,a%b),(b!=0) and gcd(a,0)==a .

Python The implementation is as follows ：

#  Recursive version 
def gcd(a, b):
    return a if not b else gcd(b, a % b)

#  Iteration 
def gcd2(a, b):
    while b:
        a, b = b, a % b
    return a

extended euclidean algorithm

Extended Euclidean algorithm is based on Euclidean algorithm , Be able to find out what makes ax+by=gcd(a,b) A group of x,y.

This article The explanation was very good , Compared with the following figure and the recursive version, the implementation is easy to understand .

Python The implementation is as follows ：

#  Recursive version 
def ext_euclid ( a , b ):
    # ref:https://zh.wikipedia.org/wiki/ extended euclidean algorithm 
    if (b == 0):
        return 1, 0, a
    else:
        x1 , y1 , q = ext_euclid( b , a % b ) # q = GCD(a, b) = GCD(b, a%b)
        x , y = y1, ( x1 - (a // b) * y1 )
        return x, y, q
#  Iteration 
def egcd(a, b):
    # ref:https://blog.csdn.net/wyf12138/article/details/60476773
    if b == 0:
        return (1, 0, a)
    x, y = 0, 1
    s1, s2 = 1, 0
    r, q = a % b, a / b
    while r:
        m, n = x, y
        x = s1 - x * q
        y = s2 - y * q
        s1, s2 = m, n
        a, b = b, r
        r, q = a % b, a / b
    return (x, y, b)

Chinese remainder theorem

Wikipedia Give a concise and vivid description :

Refer to the above instructions Python Realization :

def CRT(mi, ai):
    # mi,ai Represents the modulus and the value after taking the modulus respectively , List structure 
    # Chinese Remainder Theorem
    # lcm=lambda x , y:x*y/gcd(x,y)
    # mul=lambda x , y:x*y
    # assert(reduce(mul,mi)==reduce(lcm,mi))
    #  The above can be used to guarantee mi The two are mutual 
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M / m) * gmpy2.invert(M / m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

The above procedure will mi Treat as two mutually prime , In fact, sometimes there are other situations , At this time, we need to merge the equations one by one . Referring to the figure below, I have realized a Chinese remainder theorem that works well in both cases of Coprime and non coprime （ Solving Congruence Equations ） Of Python Program .

def GCRT(mi, ai):
    # mi,ai Represents the modulus and the value after taking the modulus respectively , List structure 
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0) # If not, there is no solution 
        K = c / d * gmpy2.invert(curm / d, m / d)
        cura += curm * K
        curm = curm * m / d
        cura %= curm
    return (cura % curm, curm) #( Explain , Minimum common multiple )

The picture is taken from Chinese remainder theorem （ The situation of mutual quality and non mutual quality ） .

Common attack methods practice

The preparation of the instruments

• python
  • gmpy2 library
    • Windows： Can be obtained from https://pypi.org/project/gmpy2/#files Download the compiled installation package directly .
    • Linux： sudo apt install python-gmpy2
  • libnum library ：
    • git clone https://github.com/hellman/libnum.git && cd libnum && python setup.py install
• yafu
  • https://sourceforge.net/projects/yafu/
• RSATool2v17.exe

RSA Decrypt

If the private key is known d, Can be decrypted directly ： m=pow(c,d,n) .

If the prime number is known p and q, Then calculate the Euler function value in turn phi、 Private key d Decrypt . The simple implementation is as follows ：

def rsa_decrypt(e, c, p, q):
    phi = (p - 1) * (q - 1)
    n = p * q
    try:
        d = gmpy2.invert(e, phi) # seek e model phi The inverse of 
        return pow(c, d, n)
    except Exception as e:
        print "e and phi are not coprime!"
        raise e

Select encryption index e Time requirement phi,e Coprime , That is to say gcd(phi,e)==1 , If not satisfied, it cannot be decrypted directly .

Why do you say this ？ It's because sometimes there are strange things at first glance . such as SCTF2018 Of Crypto - a number problem , The title is

x**33=1926041757553905692219721422025224638913707 mod 3436415358139016629092568198745009225773259
tell me the smallest answer of x

among n=3436415358139016629092568198745009225773259 It can be decomposed directly to p,q, Out phi=(p-1)*(q-1) , Then I was surprised to find gcd(phi,33)==3 . At this time, if you are familiar with the encryption process , You can think of the public key e=11 , Plaintext is m=x^3 , We should find out m. And then blast x.

for i in range(1000000):
    #  Recommended gmpy2 Library operation , use pow It is not feasible for the issuing party 
    if gmpy2.iroot(m + i * n, 3)[1]:
        x = gmpy2.iroot(m + i * n, 3)[0]
        # i==243277,x==9420391510958023
        break

Query known n The decomposability of

Online query ：https://factordb.com/

api Interface ：

curl http://factordb.com/api?query=12345
response:
{
    "id":"12345","status":"FF","factors":[["3",1],["5",1],["823",1]]}

Use yafu decompose N

Application ：p,q If the difference is large or small, it can be quickly decomposed .

Usage method ： yafu-x64.exe factor(233) ,yafu-x64.exe help

Modules are not mutually prime （gcd(N1,N2)!=1）

Application ： There are two or more modules , And gcd(N1,N2)!=1 .

Multiple modules n Common prime , Then one of their prime factors can be easily obtained by Euclid algorithm gcd(N1,N2) , Then the greatest common divisor can be used to decompose the modulus to get the corresponding p and q, You can decrypt . Refer to this article for implementation Euclid algorithm Part and RSA Decrypt part .

Common mode attack

Application ： Plaintext m、 modulus n identical , Public key index e、 Ciphertext c Different ,gcd(e1,e2)==1

Using the same modulus and different public key indices for multiple encryption of the same plaintext may lead to common mode attacks . See code Notes for simple proof .

Python Realization ：

def common_modulus(n, e1, e2, c1, c2):
    """ ref: https://crypto.stackexchange.com/questions/16283/how-to-use-common-modulus-attack ∵gcd(e1,e2)==1,∴ By the extended Euclidean algorithm , There is e1*s1+e2*s2==1 ∴m==m^1==m^(e1*s1+e2*s2)==((m^e1)^s1)*((m^e2)^s2)==(c1^s1)*(c2^s2) """
    assert (libnum.gcd(e1, e2) == 1)
    _, s1, s2 = gmpy2.gcdext(e1, e2)
    #  if s1<0, be c1^s1==(c1^-1)^(-s1), among c1^-1 by c1 model n Inverse element .
    m = pow(c1, s1, n) if s1 > 0 else pow(gmpy2.invert(c1, n), -s1, n)
    m *= pow(c2, s2, n) if s2 > 0 else pow(gmpy2.invert(c2, n), -s2, n)
    return m % n

Example ：QCTF2018-XMan The trials / Xman-RSA 【 Common mode attack + Modules are not mutually prime 】

This problem makes use of common mode attack and module immutability . At first it was a character substitution , Nothing to do with this article .encryption.encrypted The file has been replaced with characters , Determine the replacement table according to the syntax , The source file obtained by repairing the file is as follows .

See the link at the end of the article for the attachment of the title .

from gmpy2 import is_prime
from os import urandom
import base64


def bytes_to_num(b):
    return int(b.encode('hex'), 16)


def num_to_bytes(n):
    b = hex(n)[2:-1]
    b = '0' + b if len(b) % 2 == 1 else b
    return b.decode('hex')


def get_a_prime(l):
    random_seed = urandom(l)

    num = bytes_to_num(random_seed)

    while True:
        if is_prime(num):
            break
        num += 1
    return num


def encrypt(s, e, n):
    p = bytes_to_num(s)
    p = pow(p, e, n)
    return num_to_bytes(p).encode('hex')


def separate(n):
    p = n % 4
    t = (p * p) % 4
    return t == 1


f = open('flag.txt', 'r')
flag = f.read()

msg1 = ""
msg2 = ""
for i in range(len(flag)):
    if separate(i):
        msg2 += flag[i]
    else:
        msg1 += flag[i]

p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1 * p2
n2 = p1 * p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)

e1 = 0x1001
e2 = 0x101
p4 = get_a_prime(128)
p5 = get_a_prime(128)
n3 = p4 * p5
c1 = num_to_bytes(pow(n1, e1, n3)).encode('hex')
c2 = num_to_bytes(pow(n1, e2, n3)).encode('hex')
print(c1)
print(c2)

print(base64.b64encode(num_to_bytes(n2)))
print(base64.b64encode(num_to_bytes(n3)))

n2,n3 It is known that , Use common mode attack to get n1, from gcd(n1,n2)==p1 decompose n1,n2, You can decrypt and get two parts msg, Just splice .

The solution script is as follows ：

# -*- coding: utf-8 -*-
# by https://findneo.github.io/

import base64
import libnum
import gmpy2


def fix_py():
    # decode encryption.encrypted
    s1 = 'abdefghijklmpqrtuvwxyz'
    s2 = 'dmenwfoxgpyhirasbktclu'
    f1 = open('encryption.encrypted')
    with open('encryption.py', 'w') as f2:
        for i in f1.readlines():
            tmp = ''
            for j in i:
                tmp += s2[s1.index(j)] if j in s1 else j
            f2.write(tmp)
# fix_py()
def common_modulus(n, e1, e2, c1, c2):
    assert (libnum.gcd(e1, e2) == 1)
    _, s1, s2 = gmpy2.gcdext(e1, e2)
    m = pow(c1, s1, n) if s1 > 0 else pow(gmpy2.invert(c1, n), -s1, n)
    m *= pow(c2, s2, n) if s2 > 0 else pow(gmpy2.invert(c2, n), -s2, n)
    m %= n
    return m


[n2, n3] = map(lambda x: int(base64.b64decode(x).encode('hex'), 16),
               open('n2&n3').readlines())
[n1c1, n1c2] = map(lambda x: int(x, 16), open('n1.encrypted').readlines())
[msg1c1, msg2c2] = map(lambda x: int(x, 16), open('ciphertext').readlines())
#  Get through common mode attack n1
e1 = 0x1001
e2 = 0x101
n1 = common_modulus(n3, e1, e2, n1c1, n1c2)
# n1,n2 There is a common prime factor p1
# n1 += n3 #  There is n3 Than n1 Small possibility , And it's true ; It seems that the sponsor changed the question halfway , hold n1 Change to less than n3 了 .
p1 = gmpy2.gcd(n1, n2)
assert (p1 != 1)
p2 = n1 / p1
p3 = n2 / p1
e = 0x1001
d1 = gmpy2.invert(e, (p1 - 1) * (p2 - 1))
d2 = gmpy2.invert(e, (p1 - 1) * (p3 - 1))
msg1 = pow(msg1c1, d1, n1)
msg2 = pow(msg2c2, d2, n2)
msg1 = hex(msg1)[2:].decode('hex')
msg2 = hex(msg2)[2:].decode('hex')
print msg1, msg2
# XA{RP0I_0Itrsigi s.y
# MNCYT_55_neetnvmrap}
# XMAN{CRYPT0_I5_50_Interestingvim rsa.py}

Small plaintext attack

Application ：e smaller , It's usually 3.

Public key e Very small , Plaintext m Not much , therefore m^e=k*n+m In the k The value is very small, even 0, Blast k Or directly open the third power .

Python Realization ：

def small_msg(e, n, c):
    print time.asctime(), "Let's waiting..."
    for k in xrange(200000000):
        if gmpy2.iroot(c + n * k, e)[1] == 1:
            print time.asctime(), "...done!"
            return gmpy2.iroot(c + n * k, 3)[0]

Example ：Extremely hard RSA

The title provides n yes 4096 Bit ,e=3.

import gmpy2,binascii,libnum,time
n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e=3
res=0
c=int(open('extremelyhardRSA.rar/flag.enc','rb').read().encode('hex'),16)
print time.asctime()
for i in xrange(200000000):
	if gmpy2.iroot(c+n*i,3)[1]==1:
		res=gmpy2.iroot(c+n*i,3)[0]
		print i,res
		print libnum.n2s(res)
		print time.asctime()
		break

Rabin Security in encryption N Can be decomposed

Application ：e==2

Rabin Encryption is RSA The derivative algorithm of ,e==2 yes Rabin Typical features of encryption , You can baidu or read https://en.wikipedia.org/wiki/Rabin_cryptosystem For detailed instructions , Only the decryption method is concerned here . Generally, it is decomposed by other methods first p,q, And then decrypt .

Python Realization ：

def rabin_decrypt(c, p, q, e=2):
    n = p * q
    mp = pow(c, (p + 1) / 4, p)
    mq = pow(c, (q + 1) / 4, q)
    yp = gmpy2.invert(p, q)
    yq = gmpy2.invert(q, p)
    r = (yp * p * mq + yq * q * mp) % n
    rr = n - r
    s = (yp * p * mq - yq * q * mp) % n
    ss = n - s
    return (r, rr, s, ss)

Function returns four numbers , Only one of them is the plaintext we want , It needs to be verified in other ways , Of course CTF Obviously flag The word .

The decryption method refers to Wikipedia , The screenshot is as follows ：

Example ：Jarvis OJ hard RSA

Problem solving script

import gmpy2,libnum
n=0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e=2
c=int(open('hardRSA.rar/flag.enc','rb').read().encode('hex'),16)
mp=pow(c,(p+1)/4,p)
mq=pow(c,(q+1)/4,q)
yp=gmpy2.invert(p,q)
yq=gmpy2.invert(q,p)
r=(yp*p*mq+yq*q*mp)%n
rr=n-r
s=(yp*p*mq-yq*q*mp)%n
ss=n-s
print libnum.n2s(r)
print libnum.n2s(rr)
print libnum.n2s(s)
print libnum.n2s(ss)

Wiener’s Attack

Application ：e Too large or too small .

Tools ：https://github.com/pablocelayes/rsa-wiener-attack

stay e Too large or too small , The algorithm can be used from e Quickly infer d Value . The detailed algorithm principle can be read ： Low decryption index attack .

from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic

def wiener_hack(e, n):
    # firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            s = n - phi + 1
            discr = s * s - 4 * n
            if (discr >= 0):
                t = Arithmetic.is_perfect_square(discr)
                if t != -1 and (s + t) % 2 == 0:
                    print("Hacked!")
                    return d
    return False

Example ：2018 Strong net cup nextrsa-Level2

n = 0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1L
e = 0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46fL
d = wiener_hack(e, n)
print d  #42043

Private key file repair

Application ： Provide a broken private key file .

Example ：Jarvis OJ-God Like RSA

Reference resources https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html Repair the file storing the private key , obtain p and q.

import gmpy2,binascii,libnum,time
from Crypto.PublicKey import RSA
with open('godlikeRSA.rar/pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    n = key.n
    e = key.e
p = 30061432003658510087798871614869318011389940352798147030129806359975911392091235344042288409629143229311060231549478211871643725394470760528211801310601767727834886942210718412087541234398453046895030858579989874035849439867334906873642352112428914855967993998732685221108379784833027771293275558876952608462050146340591449046825135890871650866799299533696175818103240024841274114925018619060818213433528894936128306780366785977567327073724428211445259983614467640785163297734447975723664659822673456683284394386723716344090232882990461174301609971805075768328757325956784604364401827152431260896927633163074694121679
q = 26136662545551829820746942051638228325025130519175536694008242208616774469870765684858288042819063837180243501117310278632509413217676559484513481677689042623348188876598901642459170232360966754692434316796014314498263800234390539118817050074978421973817764644287745302885861277447227180288605200894138168586207384484170481511828680117688324729381172912436910052489279406590356734739774635376711681212908417321705094537960645308009611045658947359297373154395500467689532455017647450616447445444254910371922944620114234547655209970657063715028350418518417105772707885648587233103869340985670430269862943630137067052883
print n==p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print e*d%phi
c=int(open('godlikeRSA.rar/flag.enc','rb').read().encode('hex'),16)
m=pow(c,d,n)
print m
# 1370223550024951160390505387130177939237950112048472397389773634788136940247048803373180904499220116137720016277614401463947529601059601275191225565163007356175594695217230371190488219356030961008234353281422568670237109241798409859772276203338663213736672988507101836099731545753186306605979236795416523018072994981230167509019379957053839561135207769133885837247551721998502691458955042383536845772871317832519566606644011038158531192089650858814552702073939336587081668849526410118259284356539710136294431275218448114094635426857980426460905608258535404240097392254948848433684475139365021846569436926295331904560877283857331146381104141185386272078892946248648795223866902960499271054375730866146508724739787771837579817109380817612386428775429383894697178101165350212843220568133053034913426083965937819287414427916848075303046293039426388342757953620799736182799948741710617974079729792088434776370340095313622264898772452440870247810948774919910578850614282925852564445288646487485017449052934955175051072066751519784123645584671119185023928739438748519535869994754998423784897445884244844154563303115861175492133906368196005147361767160830004522010287149025190543608485818909441439294996482797249312140402141744752129890112
#  Plaintext is this ,flag I don't know what it is 

LSB Oracle Attack

Application ： You can select the ciphertext and disclose the lowest bit .

In a RSA Encrypting , In plain text m, Modulus is n, The encryption index is e, The secret is c. We can construct c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n , because m Twice as likely as n, So the plaintext obtained after decryption is m'=(2*m)%n . We can also know m' The lowest point of lsb yes 1 still 0. because n Is odd , and 2*m It's even , So if lsb yes 0, explain (2*m)%n It's even , Not more than n, namely m<n/2.0 , whereas m>n/2.0 . Take an example to understand 2%3=2 It's even , and 4%3=1 Is odd . And so on , Construct ciphertext c"=(4^e)*c)%n Decrypt it to m"=(4*m)%n , Judge m" The parity of can be known m and n/4 The size of the relationship . So we have a binary algorithm , You can convert... In logarithmic time m The range approximates to a sufficiently narrow space .

More information can be found in ：RSA Least-Significant-Bit Oracle Attack and RSA least significant bit oracle attack .

Python Realization ：

import decimal
def oracle():
    return lsb == 'odd'


def partial(c, e, n):
    k = n.bit_length()
    decimal.getcontext().prec = k  # for 'precise enough' floats
    lo = decimal.Decimal(0)
    hi = decimal.Decimal(n)
    for i in range(k):
        c = (c * pow(2, e, n)) % n
        if not oracle(c):
            hi = (lo + hi) / 2
        else:
            lo = (lo + hi) / 2
        # print i, int(hi - lo)
    return int(hi)

Example ：QCTF2018-XMan The trials /Baby RSA

The title is as follows

e = 0x10001
n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0

λ nc 47.96.239.28 23333
----------------------------- baby rsa -----------------------------
Come and Decode your data
If you give me ciphertext, I can tell you whether decoded data is even or odd
You can input ciphertext(hexdecimal) now
1
odd

Problem solving script ：

# -*- coding: utf-8 -*-
# by https://findneo.github.io/
# ref:
# https://crypto.stackexchange.com/questions/11053/rsa-least-significant-bit-oracle-attack
# https://ctf.rip/sharif-ctf-2016-lsb-oracle-crypto-challenge/
# https://introspelliam.github.io/2018/03/27/crypto/RSA-Least-Significant-Bit-Oracle-Attack/
import libnum, gmpy2, socket, time, decimal


def oracle(c1):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    hostname = '47.96.239.28'
    port = 23333
    s.connect((hostname, port))
    s.recv(1024)
    s.send(hex(c1)[2:].strip("lL") + '\n')
    res = s.recv(1024).strip()
    s.close()
    if res == 'even': return 0
    if res == 'odd':
        return 1
    else:
        assert (0)


def partial(c, n):
    global c_of_2
    k = n.bit_length()
    decimal.getcontext().prec = k  # allows for 'precise enough' floats
    lower = decimal.Decimal(0)
    upper = decimal.Decimal(n)
    for i in range(k):
        possible_plaintext = (lower + upper) / 2
        # lower==0 when i<1809
        flag = oracle(c)
        if not flag:
            upper = possible_plaintext  # plaintext is in the lower half
        else:
            lower = possible_plaintext  # plaintext is in the upper half
        c = (c * c_of_2) % n  # multiply y by the encryption of 2 again
        print i, flag, int(upper - lower)
        # time.sleep(0.2)
    # By now, our plaintext is revealed!
    return int(upper)


def main():
    print "[*] Conducting Oracle attack..."
    return partial((c * c_of_2) % n, n)


if __name__ == '__main__':
    e = 0x10001
    n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
    c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
    c_of_2 = pow(2, e, n)
    m = main()
    # m = 560856645743734814774953158390773525781916094468093308691660509501812349
    print libnum.n2s(m)
    # QCTF{RSA_parity_oracle_is_fun}

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-3mAvo5NJ-1656840589479)(https://www.writebug.com/myres/static/uploads/2022/7/2/432cac49163e8c86a7fbcbce27f804ef.writebug)]

Select ciphertext attack

Application ： Any ciphertext can be constructed and the corresponding plaintext can be obtained .

That's easy to understand , In a RSA During encryption , In plain text m, The secret is c, Modulus is n, The encryption index is e, selection x To satisfy gcd(x,n)==1 So that x model n The inverse existence of , Construct ciphertext c'=c*(x^e) Make the decrypted plaintext m'=(m*x)%n , be m=m'*x^-1(mod n) . For reference. Algorithm part in the sense of module .

Broadcast attack

Application ： modulus n、 Ciphertext c Different , Plaintext m、 Encryption index e identical . It's usually e=k, And then to k Group data

Use different modules n, The same public key index e Encrypt the same information . You will get more (m^e) ==ci (mod ni), take (m^{e) As a whole M, This is the typical application of Chinese remainder theorem . According to the ` Chinese remainder theorem ` Small sections are easy to find m}e Value , When e Open directly when it is small e Just , You can use gmpy2.iroot(M,e) Method .

Python Realization ： See article Chinese remainder theorem Section .

Example ：2018 Strong net cup nextrsa-Level9

m = random.randint(0x100000000000, 0xffffffffffff)
e = 3
n1 = 0x43d819a4caf16806e1c540fd7c0e51a96a6dfdbe68735a5fd99a468825e5ee55c4087106f7d1f91e10d50df1f2082f0f32bb82f398134b0b8758353bdabc5ba2817f4e6e0786e176686b2e75a7c47d073f346d6adb2684a9d28b658dddc75b3c5d10a22a3e85c6c12549d0ce7577e79a068405d3904f3f6b9cc408c4cd8595bf67fe672474e0b94dc99072caaa4f866fc6c3feddc74f10d6a0fb31864f52adef71649684f1a72c910ec5ca7909cc10aef85d43a57ec91f096a2d4794299e967fcd5add6e9cfb5baf7751387e24b93dbc1f37315ce573dc063ecddd4ae6fb9127307cfc80a037e7ff5c40a5f7590c8b2f5bd06dd392fbc51e5d059cffbcb85555L
n2 = 0x60d175fdb0a96eca160fb0cbf8bad1a14dd680d353a7b3bc77e620437da70fd9153f7609efde652b825c4ae7f25decf14a3c8240ea8c5892003f1430cc88b0ded9dae12ebffc6b23632ac530ac4ae23fbffb7cfe431ff3d802f5a54ab76257a86aeec1cf47d482fec970fc27c5b376fbf2cf993270bba9b78174395de3346d4e221d1eafdb8eecc8edb953d1ccaa5fc250aed83b3a458f9e9d947c4b01a6e72ce4fee37e77faaf5597d780ad5f0a7623edb08ce76264f72c3ff17afc932f5812b10692bcc941a18b6f3904ca31d038baf3fc1968d1cc0588a656d0c53cd5c89cedba8a5230956af2170554d27f524c2027adce84fd4d0e018dc88ca4d5d26867L
n3 = 0x280f992dd63fcabdcb739f52c5ed1887e720cbfe73153adf5405819396b28cb54423d196600cce76c8554cd963281fc4b153e3b257e96d091e5d99567dd1fa9ace52511ace4da407f5269e71b1b13822316d751e788dc935d63916075530d7fb89cbec9b02c01aef19c39b4ecaa1f7fe2faf990aa938eb89730eda30558e669da5459ed96f1463a983443187359c07fba8e97024452087b410c9ac1e39ed1c74f380fd29ebdd28618d60c36e6973fc87c066cae05e9e270b5ac25ea5ca0bac5948de0263d8cc89d91c4b574202e71811d0ddf1ed23c1bc35f3a042aac6a0bdf32d37dede3536f70c257aafb4cfbe3370cd7b4187c023c35671de3888a1ed1303L
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)
print m == gmpy2.iroot(CRT([n1, n2, n3], [c1, c2, c3]), e)[0]

Other examples

【Jarvis OJ Medium RSA】 Parse the public key file

Use the command from PEM file （Privacy-Enhanced Mail It is used to store and send keys 、 File format of certificate and other data ） Resolve the public key pair (n,e),n It can be queried online (http://factordb.com/) To qualitative factor , decompose n obtain p and q, Then the Euler function value and decryption index can be calculated , To decrypt .

C:\Users\neo\Downloads\mediumRSA.rar
λ openssl rsa -pubin -text -modulus -in pubkey.pem
WARNING: can't open config file: /usr/local/ssl/openssl.cnf
Public-Key: (256 bit)
Modulus:
    00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
    be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----

carck.py

import gmpy2,binascii
n=87924348264132406875276140514499937145050893665602592992418171647042491658461
e=0x10001
# via http://factordb.com/
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239

d=gmpy2.invert(e,(p-1)*(q-1))
c=int(open('flag.enc','rb').read().encode('hex'),16)
m=hex(pow(c,d,n))[2:]
print binascii.unhexlify(m.zfill(len(m)+8-len(m)%8))

Resource download address ：https://download.csdn.net/download/sheziqiong/85882450
Resource download address ：https://download.csdn.net/download/sheziqiong/85882450