RSA

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

RSA

Post by flava on Sat Jul 25, 2009 6:49 pm
([msg=27433]see RSA[/msg])

Anyone have any ideas for a quick way to find d where de % m = 1 and m = (p -1)(q - 1)?
Viking at heart.
User avatar
flava
New User
New User
 
Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)


Re: RSA

Post by thedotmaster on Sun Jul 26, 2009 11:14 am
([msg=27468]see Re: RSA[/msg])

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 :P
Hmph. Sorry, not a clue.
I'm presuming you're studying A Level maths? (if you're in the UK)
Image
User avatar
thedotmaster
Contributor
Contributor
 
Posts: 984
Joined: Sun May 04, 2008 4:39 pm
Location: North West UK
Blog: View Blog (1)


Re: RSA

Post by flava on Sun Jul 26, 2009 4:07 pm
([msg=27489]see Re: RSA[/msg])

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. :mrgreen:

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
Viking at heart.
User avatar
flava
New User
New User
 
Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)


Re: RSA

Post by thedotmaster on Sun Jul 26, 2009 7:10 pm
([msg=27503]see Re: RSA[/msg])

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.
Image
User avatar
thedotmaster
Contributor
Contributor
 
Posts: 984
Joined: Sun May 04, 2008 4:39 pm
Location: North West UK
Blog: View Blog (1)


Re: RSA

Post by flava on Tue Jul 28, 2009 7:17 am
([msg=27574]see Re: RSA[/msg])

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.
User avatar
flava
New User
New User
 
Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)


Re: RSA

Post by myhexhax on Tue Jul 28, 2009 11:08 am
([msg=27589]see Re: RSA[/msg])

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
gniripsni ewa si rehte eht morf cisum siht
myhexhax
Poster
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

Post by flava on Thu Jul 30, 2009 1:37 pm
([msg=27674]see Re: RSA[/msg])

Got it. More on how this works out when I get home.
Viking at heart.
User avatar
flava
New User
New User
 
Posts: 31
Joined: Sun Jul 19, 2009 2:00 pm
Blog: View Blog (0)



Return to Crypto

Who is online

Users browsing this forum: No registered users and 0 guests

cron