Exetools Simple RSA Explanation
 Register Forum Rules FAQ Calendar Mark Forums Read

 Notices HTTP connection will be closed soon. Please visit eXeTools with HTTPS in the future. https://forum.exetools.com This is the ONLY ONE domain that we use. Follow @exetools on Twitter and send me a message, I will choose whether to send the invitation code. Any password problems please mailto: 883600(at)qq(dot)com

#1
12-29-2017, 14:07
 psgama Friend Join Date: Jul 2014 Posts: 81 Rept. Given: 0 Rept. Rcvd 3 Times in 3 Posts Thanks Given: 8 Thanks Rcvd at 65 Times in 38 Posts
Simple RSA Explanation

I found this a very simple explanation of how RSA and Public / Private Keys work. The most easy to understand example I've found yet.

It is very simple to multiply numbers together, especially with computers. But it can be very difficult to factor numbers.
For example, if I ask you to multiply together 34537 and 99991, it is a simple matter to punch those numbers into a calculator and 3453389167. But the reverse problem is much harder.

Suppose I give you the number 1459160519. I’ll even tell you that I got it by multiplying together two integers. Can you tell me what they are? This is a very difficult problem. A computer can factor that number fairly quickly, but (although there are some tricks) it basically does it by trying most of the possible combinations. For any size number, the computer has to check something that is of the order of the size of the square-root of the number to be factored. In this case, that square-root is roughly 38000. Now it doesn’t take a computer long to try out 38000 possibilities, but what if the number to be factored is not ten digits, but rather 400 digits? The square-root of a number with 400 digits is a number with 200 digits. The lifetime of the universe is approximately 10^18 seconds - an 18 digit number. Assuming a computer could test one million factorizations per second, in the lifetime of the universe it could check 10^24 possibilities. But for a 400 digit product, there are 10^200 possibilities. This means the computer would have to run for 10176 times the life of the universe to factor the large number.

It is, however, not too hard to check to see if a number is prime–in other words to check to see that it cannot be factored. If it is not prime, it is difficult to factor, but if it is prime, it is not hard to show it is prime.

So RSA encryption works like this. I will find two huge prime numbers, p and q that have 100 or maybe 200 digits each. I will keep those two numbers secret (they are my private key), and I will multiply them together to make a number N = pq. That number N is basically my public key. It is relatively easy for me to get N; I just need to multiply my two numbers. But if you know N, it is basically impossible for you to find p and q. To get them, you need to factor N, which seems to be an incredibly difficult problem.
... continued in Original Article

Last edited by psgama; 12-30-2017 at 04:42.
 The Following 7 Users Say Thank You to psgama For This Useful Post: arthur plank (12-30-2017), Matan (07-20-2020), niculaita (12-29-2017), nimaarek (12-29-2017), Stingered (12-30-2017), user1 (05-21-2019), yijun (01-01-2018)
#2
12-29-2017, 20:17
 arthur plank Friend Join Date: Jan 2005 Posts: 102 Rept. Given: 28 Rept. Rcvd 22 Times in 14 Posts Thanks Given: 18 Thanks Rcvd at 52 Times in 20 Posts
Quote:
 Originally Posted by psgama ... The lifetime of the universe is approximately 1018 seconds...
An interesting read, but that extract made me realise that I'm older than the universe
#3
12-30-2017, 03:51
 psgama Friend Join Date: Jul 2014 Posts: 81 Rept. Given: 0 Rept. Rcvd 3 Times in 3 Posts Thanks Given: 8 Thanks Rcvd at 65 Times in 38 Posts
Yeah, looks like it's missing an exponent of sorts haha. Older than dirt!
#4
12-30-2017, 07:34
 Apuromafo Family Join Date: Nov 2010 Location: Chile Posts: 100 Rept. Given: 12 Rept. Rcvd 19 Times in 11 Posts Thanks Given: 140 Thanks Rcvd at 145 Times in 55 Posts
sometimes are db in web example factordb
see how factorice a big number xD
http://www.factordb.com/index.php?query=7207344977278768095299147333268995520123956637195514101358017249%E2%80%8B5557738778497
 The Following User Says Thank You to Apuromafo For This Useful Post: tonyweb (01-06-2018)
#5
12-31-2017, 11:35
 psgama Friend Join Date: Jul 2014 Posts: 81 Rept. Given: 0 Rept. Rcvd 3 Times in 3 Posts Thanks Given: 8 Thanks Rcvd at 65 Times in 38 Posts
Anyone know how to correctly convert the base64 encoded P and Q values back to a proper integer?

I am trying to use the systems.numerics biginteger format and the output isn't looking correct. My Byte Arrays are coming back correctly from my RSAGetP function, as if I convert the array back to base64 format it matches the original RSA XML

Code:
```  Private Sub Button2_Click(sender As Object, e As EventArgs) Handles Button2.Click
Dim PBytes() As Byte = RSAGetP(txtPrivateKey.Text)
Dim PValue As New BigInteger(PBytes)
Dim QBytes() As Byte = RSAGetQ(txtPrivateKey.Text)
Dim QValue As New BigInteger(QBytes)
Dim MBytes() As Byte = RSAGetM(txtPrivateKey.Text)
Dim MValue As New BigInteger(MBytes)
TextBox1.Text = PValue.ToString
TextBox2.Text = QValue.ToString
TextBox3.Text = MValue.ToString
End Sub```
Solved the issue with the following function. The Byte Order is backwards to what Biginteger wants

Code:
```    Function PrepareRSA(Bytes() As Byte)
Array.Reverse(Bytes)
If (Bytes((Bytes.Length - 1)) > 127) Then
Array.Resize(Bytes, (Bytes.Length + 1))
Bytes((Bytes.Length - 1)) = 0
End If
Return Bytes
End Function```

Last edited by psgama; 12-31-2017 at 13:52.
 The Following User Says Thank You to psgama For This Useful Post: niculaita (12-31-2017)
#6
01-01-2018, 10:27
 cnbragon Friend Join Date: Nov 2010 Posts: 26 Rept. Given: 1 Rept. Rcvd 1 Time in 1 Post Thanks Given: 3 Thanks Rcvd at 1 Time in 1 Post
Have you already convert the base64 to hex string?
#7
01-03-2018, 05:01
 psgama Friend Join Date: Jul 2014 Posts: 81 Rept. Given: 0 Rept. Rcvd 3 Times in 3 Posts Thanks Given: 8 Thanks Rcvd at 65 Times in 38 Posts
Thought I'd post a couple Windows RSA tools here.

A compiled version of Yafu and Msieve tool for factoring RSA Moduli.

YAFU tool

Run the the appropriate Tune File and then either Factor32 or Factor64.bat

A compiled tool that I partially built in VB.net for decoding Base 64 moduli / Primes to Big Integers, Generating XML Encoded RSA Keys and Encrypting / Decrypting. Also has a function built in to randomly check for prime collisions against a moduli (Not likely to ever succeed due to the slowness of generating RSA keys via System.Security.Cryptography and the number of primes existing for larger key lengths. Unless you're really lucky!)
RSA Tools

Last edited by psgama; 01-03-2018 at 07:49.
 The Following 3 Users Say Thank You to psgama For This Useful Post: Spiderz_Soft (01-03-2018), tonyweb (01-06-2018), zeuscane (01-03-2018)
#8
07-20-2020, 17:52
 zzfeed Friend Join Date: Apr 2012 Posts: 63 Rept. Given: 67 Rept. Rcvd 18 Times in 10 Posts Thanks Given: 22 Thanks Rcvd at 27 Times in 16 Posts
Quote:
 Originally Posted by psgama Thought I'd post a couple Windows RSA tools here. A compiled version of Yafu and Msieve tool for factoring RSA Moduli. YAFU tool Run the the appropriate Tune File and then either Factor32 or Factor64.bat A compiled tool that I partially built in VB.net for decoding Base 64 moduli / Primes to Big Integers, Generating XML Encoded RSA Keys and Encrypting / Decrypting. Also has a function built in to randomly check for prime collisions against a moduli (Not likely to ever succeed due to the slowness of generating RSA keys via System.Security.Cryptography and the number of primes existing for larger key lengths. Unless you're really lucky!) RSA Tools