Crypto - Pascal RSA

74 solves | 100 points

Description

RSA Encryption with Pascal's Triangle! Has to be secure right...

Downloads

683B
main.py
Open
639B
challenge.txt
Open

Solution

Here is what we are given:

# Inside challenge.txt
# p = 751921
# enc = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
# N = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447

triangle =[[1]]
flag = open('flag.txt','rb').read()

from Crypto.Util.number import getPrime,bytes_to_long
from math import gcd
p = getPrime(20)
while len(triangle[-1]) <= p:
    r = [1]
    for i in range(len(triangle[-1]) - 1):
        r.append(triangle[-1][i] + triangle[-1][i+1])
    r.append(1)
    triangle.append(r)
code = ''
for x in triangle[-1]:
    code+=str(x%2)
d = int(code,2)
while True:
    P = getPrime(512)
    Q = getPrime(512)
    if gcd(d, (P-1)*(Q-1)) == 1:
        N = P*Q
        e = pow(d,-1,(P-1)*(Q-1))
        break
enc = pow(bytes_to_long(flag), e, N)
file = open('challenge.txt','w')
file.write(f'p = {p}\nenc = {enc}\nN = {N}')

First, we try to understand what the first part of the code does. To simplify the process, we will use a print statement at the end of the first part and comment out the other parts. We also used a smaller bit number for the getPrime() function so that it is more simple. The simplified code is this:

The output we get is:

So without analyzing the rather complex while loop, we figured that the first part of the code is for generating a pascal triangle and the height of the triangle is p+1.

The next few lines of code tells us how the RSA private key d is calculated.

What the program does is that the parity of the numbers in the base of the pascal triangle is concatenated as a binary string which forms the private key in base 2. So in the case of the triangle above, the binary string is 110011 which is equivalent to d = 51.

So the given code calculates the private key for us, means we are done? No! The given code uses a 20-bit prime number which means that it will take us forever to generate the pascal triangle (not to mention we will probably run out of memory to store the pascal triangle first). But luckily for us, we do not need to generate the entire pascal triangle to know the parity of the binomial coefficient C(n, p).

As explained by Arturo Magidin from math.stackexchange.com, to determine if C(n, p) is odd, we just need to know whether there is at least one carry when adding p and n in base 2. This can be simplified into the code as such.

With the private key d and public key N, we can easily decrypt the RSA cipher text.

Flag: flag{1ts_ch00se_a11_a10ng??}

Last updated