Author  RSA code help 
jessbuggy Member
Posts: 24 Location: Canada
Joined: 07.08.06 Rank: Newbie  
Hey can anyone help me figure out the message or private key to this? The text should be a string of 10 numbers.
e = 26873742772114714559016512605122018630042573142795331681 and
n = 250667950383024127175758975286886854448906162829528977505673.
Using the above public key, the encrypted message is
y = 89419104039777899693824253807903057115093936402169650310559
Jessie 

Author  RE: RSA code help 
Arabian Banned
Posts: 332 Location: inside you.
Joined: 22.09.10 Rank: Apprentice  
The algorithm for decrypting RSA is
message = (ciphertext^private key) mod public key
If the message is simply a number, there's no way of knowing which one is correct, and you'd be wasting time and resources. The only way to do this is with a private key which you do not have. Srsly man. Are you kidding? You want us to help you play guess the 10 character number using an even greater BigInt type of unknown length and scope? Are you high?
G'bye y'all! I was an asshole, So korg banned me. 

Author  RE: RSA code help 
jessbuggy Member
Posts: 24 Location: Canada
Joined: 07.08.06 Rank: Newbie  
Naw i am so close.
I just need to solve this
d*e = 1 mod 250667950383024127175758975285859208799367340511611609081348
I just don't know how to use the extended euclidean algorithm to solve for d.
Jessie 

Author  RE: RSA code help 
Arabian Banned
Posts: 332 Location: inside you.
Joined: 22.09.10 Rank: Apprentice  
D * E = 1 % huge number
equals 1. Do you understand the concept of modulus? What you just gave us would make D = 1 and E = 1 an imperative. i hope you just miswrote your equation.
Ferma'ts little Theorem
Euler's Theorem
G'bye y'all! I was an asshole, So korg banned me.
Edited by Arabian on 150212 00:26 

Author  RE: RSA code help 
jessbuggy Member
Posts: 24 Location: Canada
Joined: 07.08.06 Rank: Newbie  
yes. You should be able to get d if you have n, p, q, e and z though.
p=398298174278735021000250551827
q=629347475260087296917117872499
e = 26873742772114714559016512605122018630042573142795331681
n = 250667950383024127175758975286886854448906162829528977505673.
cypher text = 89419104039777899693824253807903057115093936402169650310559
if n=p*q and z = (p1)(q1)
My research has been telling me that extended euclidean algorithm and something called chinese remainder theorem can solve for d. Because e is relatively prime to z
http://courses.gdeyoung.com/pages/encryption/rsa.php#coder
Jessie 

Author  RE: RSA code help 
Arabian Banned
Posts: 332 Location: inside you.
Joined: 22.09.10 Rank: Apprentice  
A: How do you know the Primes used in the public key generation and why didn't you include that information in the first post?
B: m1 = c**dp (mod p), m2 = c ** dQ (mod q)
h = qInv * (m1 w22; m2) (mod p) (if m1 < m2 then some libraries compute h as qInv * (m1 + p w22; m2) (mod p))
m = m2 + (hq)
where P and Q are primes and Qinv = q ** 1 (mod p).
G'bye y'all! I was an asshole, So korg banned me.
Edited by Arabian on 150212 00:32 

Author  RE: RSA code help 
jessbuggy Member
Posts: 24 Location: Canada
Joined: 07.08.06 Rank: Newbie  
I factored n to get p and q
But what... did you just type lol I don't understand. Can you tell me what you get for d?
Jessie 

Author  RE: RSA code help 
jessbuggy Member
Posts: 24 Location: Canada
Joined: 07.08.06 Rank: Newbie  
sorry, i'm a girl in the arts and so I have no clue how to do this kind of math.
Jessie 

Author  RE: RSA code help 
Arabian Banned
Posts: 332 Location: inside you.
Joined: 22.09.10 Rank: Apprentice  
p=398298174278735021000250551827
q=629347475260087296917117872499
e = 26873742772114714559016512605122018630042573142795331681
n = 250667950383024127175758975286886854448906162829528977505673.
cypher text = 89419104039777899693824253807903057115093936402169650310559
compute totient value: phi = (p  1)(q  1)
Let your X value = the coprime 1 < X < phi.
D = e (mod phi(n))
thus your public key = (n, e), and private = (n, d)
[EDIT]: Implying i care if you're female or not. Your gender and genitalia have nothing to do with your ability to do math other than the socialization uniquely thrust upon you that tells you you shouldn't
G'bye y'all! I was an asshole, So korg banned me.
Edited by Arabian on 150212 00:48 

Author  RE: RSA code help 
jessbuggy Member
Posts: 24 Location: Canada
Joined: 07.08.06 Rank: Newbie  
alright. scratch that. I suck at math. Please help me? I can't understand wikipedia explanations
Jessie 

Author  RE: RSA code help 
Arabian Banned
Posts: 332 Location: inside you.
Joined: 22.09.10 Rank: Apprentice  
I'd create an array of possible coprime solutions to check your answer against just because the massive integer that phi will still be.
EDIT: Compute (p  1)(q  1). Let that be phi  your totient value.
Choose any coprime such that 1 < coprime < phi and let that be E.
Compute the modular multiplicative inverse (E mod (phi * n))
That is your private key D.
That's pretty simple. If you don't know what mod means, it's % in most programming languages and `mod` or mod in most functional languages.
G'bye y'all! I was an asshole, So korg banned me.
Edited by Arabian on 150212 00:54 

Author  RE: RSA code help 
Beat_Slayer Member
Posts: 12 Location: In front of the computer
Joined: 15.01.12 Rank: Monster  
Well here goes two links that make and help the process of understanding the calculation of the variables needed.
https://www.cs.drexel.edu/~introcs/Fa11/notes/10.1_Cryptography/RSA_Express_EncryptDecrypt.html
https://www.cs.drexel.edu/~introcs/Fa11/notes/10.1_Cryptography/RSAWorksheetv4d.html
Cheers


Author  RE: RSA code help 
jessbuggy Member
Posts: 24 Location: Canada
Joined: 07.08.06 Rank: Newbie  
yay i got it. All i had to do was plug it into wolfram alpha
the plaintext is 3731812345
Jessie 
