RSA

[flava]

Anyone have any ideas for a quick way to find d where de % m = 1 and m = (p -1)(q - 1)?

[thedotmaster]

Anyone have any ideas for a quick way to find d where de % m = 1 and m = (p -1)(q - 1)?

Should have asked me this 6 months back when I was studying this kinda crap
Hmph. Sorry, not a clue.
I'm presuming you're studying A Level maths? (if you're in the UK)

[flava]

Not in the UK, sorry bro. There's no real reason for doing it, except to tell people I can encrypt things crazy good. If you're interested though, this is my current code for finding d. I don't have access to C++ though so it's written in Python.

Code: Select all

# Find d
mult = 1
d = 1

while ((d*e) % m) != 1 & bool(d == math.floor(d)):
    d = ((int(m)*mult) + 1) / (e ** mult)
    mult += 1
    if d == 0:
        mult = 1
        e = find(e) # Gets the next prime number after the current e

[thedotmaster]

Hm, by "de" are you talking about that graph formula? I remember using it as part of a formula when I did maths. I can't remember the term though.

[flava]

E is just a randomly picked prime number used to encode; C = P^e % n. At the moment e is 103769. However, my system has been finding d for 12+ hours and this is getting ridiculous...

[myhexhax]

You can rewrite de%m=1 as d=(1+nm)/e. You can just keep incrementing n until you find an integer solution for e. If you're using large primes, you'll have to visit Mr. Euclid and use the extended Euclidean algorithm to find the GCD.


Scroll down to "Extended Euclidean Algorithm" on this page: http://matdonline.free.fr/RSA-Diffie-Hellman-explained-in-5-minutes.htm

[flava]

Got it. More on how this works out when I get home.