## RSA

The fear of every surveillance society: citizens protecting their own privacy with strong cryptography

### RSA

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

flava
New User

Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)

### Re: RSA

flava wrote: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)

thedotmaster
Contributor

Posts: 984
Joined: Sun May 04, 2008 4:39 pm
Location: North West UK
Blog: View Blog (1)

### Re: RSA

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 dmult = 1d = 1while ((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`
Viking at heart.

flava
New User

Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)

### Re: RSA

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.

thedotmaster
Contributor

Posts: 984
Joined: Sun May 04, 2008 4:39 pm
Location: North West UK
Blog: View Blog (1)

### Re: RSA

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...
Viking at heart.

flava
New User

Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)

### Re: RSA

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.

gniripsni ewa si rehte eht morf cisum siht
myhexhax
Poster

Posts: 217
Joined: Tue Sep 16, 2008 2:19 pm
Location: Between the ether and the information superhighway
Blog: View Blog (0)

### Re: RSA

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

flava
New User

Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)