## WeirderRSA - 175 (Cryptography)

### Problem

Another message encrypted with RSA. It looks like some parameters are missing. Can you still decrypt it?

Message

### Hint

Is there some way to create a multiple of p given the values you have?

Fermat's Little Theorem may be helpful.

## Solution

### Overview

Perform a partial key exposure attack on the given parameters

### Details

We are given a text file with the following parameters:

e = 65537

n = 211767290324398254371868231687152625271180645754760945403088952020394972457469805823582174761387551992017650132806887143281743839388543576204324782920306260516024555364515883886110655807724459040458316068890447499547881914042520229001396317762404169572753359966034696955079260396682467936073461651616640916909
dp = 10169576291048744120030378521334130877372575619400406464442859732399651284965479823750811638854185900836535026290910663113961810650660236370395359445734425

c = 42601238135749247354464266278794915846396919141313024662374579479712190675096500801203662531952565488623964806890491567595603873371264777262418933107257283084704170577649264745811855833366655322107229755242767948773320530979935167331115009578064779877494691384747024161661024803331738931358534779829183671004


We are given a text file with the following parameters:

e = 65537

n = 211767290324398254371868231687152625271180645754760945403088952020394972457469805823582174761387551992017650132806887143281743839388543576204324782920306260516024555364515883886110655807724459040458316068890447499547881914042520229001396317762404169572753359966034696955079260396682467936073461651616640916909
dp = 10169576291048744120030378521334130877372575619400406464442859732399651284965479823750811638854185900836535026290910663113961810650660236370395359445734425

c = 42601238135749247354464266278794915846396919141313024662374579479712190675096500801203662531952565488623964806890491567595603873371264777262418933107257283084704170577649264745811855833366655322107229755242767948773320530979935167331115009578064779877494691384747024161661024803331738931358534779829183671004


It appears that we are given several parameters for Chinese Remainder Theorem (CRT) decryption of RSA. RSA-CRT decryption is identical to standard RSA decryption, except that instead of using a single private key , we use

If used correctly, this allows for speedup when compared to normal RSA decryption, since two smaller modular exponentiations are performed with significantly smaller exponents.

Unfortunately, we are not given . However, since we are given , we are essentially given an entire portion of the private key - effectively compromising the security of the cryptosystem.

Howgrave-Graham showed that as long as we know the lower half of the Least Significant Bits (LSBs) of , and is of size poly(log(N)), we can obtain the factorization of the modulus in polynomial time.

We know from RSA-CRT that

Rearranging the equation: we arrive at

, meaning that evenly divides .

This can be rewritten as:

, where and , since is a multiple of

Solving for , we obtain

Since , it is completely feasible to try every in the range of until we obtain a value of such that , in which case we know that we have obtained the prime factor and thus the factorization of .

I wrote the following python script to perform the task:

import binascii
import string

e = 65537
N = 211767290324398254371868231687152625271180645754760945403088952020394972457469805823582174761387551992017650132806887143281743839388543576204324782920306260516024555364515883886110655807724459040458316068890447499547881914042520229001396317762404169572753359966034696955079260396682467936073461651616640916909
dp = 10169576291048744120030378521334130877372575619400406464442859732399651284965479823750811638854185900836535026290910663113961810650660236370395359445734425

c = 42601238135749247354464266278794915846396919141313024662374579479712190675096500801203662531952565488623964806890491567595603873371264777262418933107257283084704170577649264745811855833366655322107229755242767948773320530979935167331115009578064779877494691384747024161661024803331738931358534779829183671004

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise 'Modular inverse does not exist.'
else:
return x % m

def factorize():
for k in range(2,e):
p = (e * dp - 1 + k) // k #Solves for p
if N % p == 0:
return p
return -1

p = factorize()
q = N // p

phi = (p - 1) * (q - 1)
d = modinv(e,phi)
print(binascii.unhexlify(hex(pow(c,d,N))[2:]))

>>>b'flag{wow_leaking_dp_breaks_rsa?_32697643574}


Which returns the flag!

## Flag

flag{wow_leaking_dp_breaks_rsa?_32697643574}


## Resources

https://www.iacr.org/archive/crypto2003/27290027/27290027.pdf