RSA decryption python [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

Want to improve this question? Guide the asker to update the question so it focuses on a single, specific problem. Narrowing the question will help others answer the question concisely. You may edit the question if you feel you can improve it yourself. If edited, the question will be reviewed and might be reopened.

Closed last year.

Improve this question

How to find p,q,a if they random? i have this script

from Crypto.Util.number import getPrime

p,q = getPrime(256), getPrime(256)
n = p*q
a = getPrime(128)
c1 = (p-a)**2>>128
c2 = (q+a)**2>>128
e = 65537
ct = pow(int.from_bytes(b'qupiya{fake_flag}','little'), e, n)
print(f"{n=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{ct=}")
print(f"{a=}")
print(f"{q=}")
print(f"{p=}")

and i need to decrypt this: n=6512617643749294302589095438675618776167938720843890101758895197157390356137924323241304471444329557183412977161734627116921570790884877938134980599305707 c1=10907285669560468551647268462406489962787063891723057307575398016663082759381321634953803867684535258520696953786905 c2=33582698092528772294080029653133275670665396243438255829051457928307809349340703410415434062259818693740005488773964 ct=2127264588321127239854001986698891905875335763381083235961453034717795577362487952867927688262105005181067989744994023793619461569137294308259815910038249

I tried all tools to crack RSA but no one in database

What is the context? Is this a real world RSA decryption or a cryptographic challenge? As one is significantly more difficult to crack than the other. — EuanG
– EuanG, Commented Nov 5, 2024 at 17:24
This is obviously a capture-the-flag contest. As such, you must do some thinking about the problem, about what you're given. For example, have you expanded the expressions for c1 and c2, added c1 to c2, and multiplied out c1 * c2? I don't know if that will help, but just by looking the problem those are things I would try. — President James K. Polk
– President James K. Polk, Commented Nov 5, 2024 at 17:34
its CTF task, script is for example how admin encrypted qupyiya{} and i need to decode it with his output, i need to find p,q,a — joram
– joram, Commented Nov 5, 2024 at 18:02
I tried some of the things I mentioned and none of them led to any obvious solutions. Next thing I'd look at is the high-order bits of c1 and c2, especially since a is only 128 bits. — President James K. Polk
– President James K. Polk, Commented Nov 5, 2024 at 18:29

Frank Yellin · Accepted Answer · 2024-11-06 16:43:58Z

2

This looks like a homework problem. So I'll only give you the basic outline of how to do it, but you need to do the work yourself.

You have c1. You should have no problem figuring out what p-a is. There is only one square between c1 << 128 and (c1 + 1) << 128. Likewise, from c2 you can figure out what q + a is. So add these two numbers you know what p + q is. Let's call that sum s

So you know the product of the two primes n and the sum of the two primes s.

Let's let s = p + q. The function f(x) = x * (s - x) has its minimum value when x = 0, and then increases monotonically until x = s // 2. So do a binary search until you find the value of x such that f(x) = n. You now have the two prime factors, x, and s - x.

@PresidentJamesKPolk gives an even better solution at this point, He points out that given p + q, it's simple to find p - q. Then solving for p and q is trivial.

(p + q)**2 - 4*n = (p + q)**2 - 4pq = (p - q)**2

Once you have p and q:

    d = pow(e, -1, (p - 1) * (q - 1))
    message = pow(ct, d, n)
    message.to_bytes(64, 'little')

(When writing your code, be sure to use integer arithmetic. math.isqrt, // instead of /, etc).

As a verification that you've got the right answer, the two primes are 609...863 and 106...389

edited Nov 6, 2024 at 16:43

answered Nov 5, 2024 at 17:35

Frank Yellin

11.6k1 gold badge15 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

joram Over a year ago

But i don't know how to find p,q,a, this is just example how admin encoded message in qupiya{here} and he send me output with n,c1,c2,ct. I don't know how to find p and q from n

Frank Yellin Over a year ago

Please re-read what I wrote. You have c1, c2, and n. You have everything you need to figure out what p and q are. With a square root you can figure out p - a. With another square root you can figure out q + a. With an addition you know p + q. You know p * q = n. And with a binary search you know p and q individually.

joram Over a year ago

so i have this script: ''' GNU nano 8.1 a.py import math number = 10907285669560468551647268462406489962787063891723057307575398016663082759381321634953803867684535258520696953786905 sqrt_result = math.isqrt(number) print(f"Root: {sqrt_result}")''' where i got c1 output but i have not matching number at 3302618002367283855723434500877437128530975413802836839908 * 3302618002367283855723434500877437128530975413802836839 908 with c1 output

Frank Yellin Over a year ago

Joram. You are trying to get me to write code for you and I'm not going to do it. You're supposed to be learning. You know what (p-a)**2 >> 128 is. Think. How do you determine what p-a is? If I told you I've got a 2 digit number, and the first two digits of its four-digit square was 51, how would you figure out what my number was?

Frank Yellin Over a year ago

@PresidentJamesK.Polk. Nice! I wished I'd thought of that. I'll edit my answer to include that.

|

Collectives™ on Stack Overflow

RSA decryption python [closed]

1 Answer 1

7 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Related