mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2004-04-04, 21:42   #1
flava
 
flava's Avatar
 
Feb 2003

2·59 Posts
Default RSA implementation

Hi,

It is not exactly a programming question, but here it goes:
I am writing (for fun) a secure "messenger" program via TCP/IP. I make it like this:
-generate two randomish 2048 bit "primes" p1 and p2; p1*p2 = N
-find E < (p1-1)*(p2-1) so GCD(E, (p1-1)*(p2-1)) = 1
-calculate D so D*E = 1 mod (p1-1)*(p2-1)
-send the pair (E,N) to the other client who generates a random 1024 bit key K for symetric encryption and sends back C=K^E mod N
-the first client calculates K1 = C^D mod N (K1 = K) so both of clients have the key and can use it to encrypt/decryptwhatever and however they want

(if the 2048 and 1024 sizes above make you think I'm paranoid ... I am :))

Now comes the question. I don't know how to generate the two primes. I can generate two strong pseudoprimes, but can't proove them prime unless I use Primo (which I can't launch automatically). Every encryption lib/source code I found on the net actually generates strong pesudoprimes too. Is there a program that can prove a prime of this size that can be launched automatically, read the prime from a parameter or file and write the result somewhere (file)?
flava is offline   Reply With Quote
Old 2004-04-05, 02:03   #2
jocelynl
 
Sep 2002

2×131 Posts
Default

Hi Flava,

Have you tried LLR? It find prime of the form k*2^n-1
at n=2048 it take half a second on most cpu to test
but k must be lower then 2^n for the test to work.

Joss
jocelynl is offline   Reply With Quote
Old 2004-04-05, 02:07   #3
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

Proving it's prime is too slow for this type of thing. Running a couple of iterations of a probablistic test is good enough. You'll have a higher chance of both computers being struck by lightning in that second that generating a composite.
ColdFury is offline   Reply With Quote
Old 2004-04-05, 02:11   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

108910 Posts
Default

Quote:
Originally Posted by flava
I don't know how to generate the two primes. I can generate two strong pseudoprimes, but can't prove them prime unless ...
You don't REQUIRE primes. Any numbers that are not obviously non-primes are more than sufficient.
Wacky is offline   Reply With Quote
Old 2004-04-05, 08:39   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001101110102 Posts
Default

Quote:
Originally Posted by flava
(if the 2048 and 1024 sizes above make you think I'm paranoid ... I am :))
Wow!

If the weakest defense of your scheme is such that you need multi-kilobit moduli so that the RSA doesn't become the easiest point to attack, I'm impressed.

Please let us know what other mechanisms you are using to guard the rest of your defensive perimeter. I'm quite sure they will make fascinating reading.


Paul
xilman is offline   Reply With Quote
Old 2004-04-05, 15:25   #6
flava
 
flava's Avatar
 
Feb 2003

11810 Posts
Default

Thank you guys for the leads. I will let it use strong pseudoprimes.

Paul, I am not trying to establish a secure perimeter, I'm just trying to implement a class that will allow me to use secure communication via TCP/IP. It can be used later to do file transfers, messaging, whatever...
Symetric encryption/decryption works at comparable speed if you use a 128bit key or a 1024 bit key (at least it looks this way to me). In order to transmit securely the 1024 bit key in the first place, the modulus needs to be at least 1024 ... so why not 4096. Generating two 2048 bit pseudoprimes takes at worst one minute and can be done in advance by clients waiting for an incoming connection. Calculating the two PowModN takes about two seconds, that's not too bad for establishing a secure connection. I think factoring the 4096 bit modulus would be almost as hard as doing cryptanalysis on the 1024 bit key.
flava is offline   Reply With Quote
Old 2004-04-05, 16:27   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Angry

Quote:
Originally Posted by flava
Thank you guys for the leads. I will let it use strong pseudoprimes.

Paul, I am not trying to establish a secure perimeter, I'm just trying to implement a class that will allow me to use secure communication via TCP/IP. It can be used later to do file transfers, messaging, whatever...
Symetric encryption/decryption works at comparable speed if you use a 128bit key or a 1024 bit key (at least it looks this way to me). In order to transmit securely the 1024 bit key in the first place, the modulus needs to be at least 1024 ... so why not 4096. Generating two 2048 bit pseudoprimes takes at worst one minute and can be done in advance by clients waiting for an incoming connection. Calculating the two PowModN takes about two seconds, that's not too bad for establishing a secure connection. I think factoring the 4096 bit modulus would be almost as hard as doing cryptanalysis on the 1024 bit key.
I will try to be gentle in my reply.

(1) OpenSSL already does what you want. Why reinvent the wheel?
(2) A 1024 bit symmetric key is crazy. If some outside, but knowledgable
3rd party saw your software using keys this large they might question whether you know what you are doing. I certainly would.
(3) Why not 4096? ... Bandwidth, Padding, Key Generation Time
(4) Your comparison between a 4096 bit RSA key and a 1024 bit symmetric
key shows that you clearly lack an understanding of what you are doing.
(no offense intended)
(5) You fail to state what secure properties you want for your 'secure communication'. Do you require implicit/explicit key authentication? Forward
Secrecy? Guarding against unknown keyshare? Guarding against MIM?
Many key agreement/key establishment protocols require *temporary*
session keys as well as permanent keys. Exactly what use is a system that
requires over 1 minute to establish temp keys?
(6) Symmetric encryption does NOT take the same time for 128 and 1024 bit
keys.
(7) Do you have any clue as to the level of effort required to break even 128
bit symmetric keys?
R.D. Silverman is offline   Reply With Quote
Old 2004-04-05, 18:55   #8
flava
 
flava's Avatar
 
Feb 2003

2×59 Posts
Default

Quote:
Originally Posted by Bob Silverman
I will try to be gentle in my reply.
No need to be gentle, you won't hurt my feelings.

Quote:
Originally Posted by Bob Silverman
(1) OpenSSL already does what you want. Why reinvent the wheel?
Because I enjoy writing it myself.

Quote:
Originally Posted by Bob Silverman
(2) A 1024 bit symmetric key is crazy. If some outside, but knowledgable
3rd party saw your software using keys this large they might question whether you know what you are doing. I certainly would.
I really don't care what a third party imagines I'm doing. I have the legal right to use whatever thechnique I want as long as I don't export, sell or distribute it.

Quote:
Originally Posted by Bob Silverman
(3) Why not 4096? ... Bandwidth, Padding, Key Generation Time
The bandwith is not an issue, the modulus and private key are not transmited very often. As for key generation, it can be done in a preemptive manner.

Quote:
Originally Posted by Bob Silverman
(4) Your comparison between a 4096 bit RSA key and a 1024 bit symmetric
key shows that you clearly lack an understanding of what you are doing.
(no offense intended)
No offense taken. You make easy assumptions on what I understand or not understand though. Even if 1024bit symmetric key and 4096 bit modullus RSA can not be compared, thay are both more than safe given today techniques and computer power.

Quote:
Originally Posted by Bob Silverman
(5) You fail to state what secure properties you want for your 'secure communication'. Do you require implicit/explicit key authentication? Forward
Secrecy? Guarding against unknown keyshare? Guarding against MIM?
Many key agreement/key establishment protocols require *temporary*
session keys as well as permanent keys. Exactly what use is a system that
requires over 1 minute to establish temp keys?
I did not intend to state any of those. My question was about proving numbers prime. If I needed help with authentication thechniques, I would have asked. There is more than plenty documentation on the net about it and about the other techniques you quote.

Quote:
Originally Posted by Bob Silverman
(6) Symmetric encryption does NOT take the same time for 128 and 1024 bit
keys.
Indeed, but if you use a n-DES the increase in computing time is linear (in our case n = 8)


Quote:
Originally Posted by Bob Silverman
(7) Do you have any clue as to the level of effort required to break even 128
bit symmetric keys?
I do.

Last fiddled with by flava on 2004-04-05 at 18:56
flava is offline   Reply With Quote
Old 2004-04-06, 00:33   #9
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

Quote:
Originally Posted by flava
Thank you guys for the leads. I will let it use strong pseudoprimes.
I was trying to figure out the impact if p1 and/or p2 were composite. Since a gcd check is performed when E is calculated, and the relative primality seems to remain intact thru the encryption/decryption process, I don't see any damage there. Perhaps if you were unlucky enough to select two composites that shared a factor then it might mangle messages instead of encrypt them.

If someone tried to crack the encryption by factoring N ino p1*p2, would they bother looking for factors less than 2k bits, in the slim hope that they were composite? Would they use a factoring method like trial factoring or ECM that might "accidentally" find smaller factors?

hmmm, does your strong pseudoprime test give you a minimum size for possible factors? Because the bit-length of the smallest factor would become your effective key size.

Here's a funny thought; Let's say their algorithm found a factor of p1, would it be smart enough to check the primality of the remaining composite? Or would it treat the composite as p2, and try to crack the encryption using those values? How ironic if they failed because they knew too much about your encryption method. Of course a simple printout of the 'primes' found would show the bit-length disparity and give it away.
Maybeso is offline   Reply With Quote
Old 2004-04-06, 01:10   #10
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

Quote:
Indeed, but if you use a n-DES the increase in computing time is linear (in our case n = 8)
Iterated DES is subject to man-in-the-middle attacks and such. Use a modern algorithm instead of bending a 35 year old in ways it wasn't designed to.
ColdFury is offline   Reply With Quote
Old 2004-06-11, 02:12   #11
Terrence Law
 
May 2004

1128 Posts
Arrow

You can test RSA buttons.

You can break factor codes and change the wire settings...

You can replace another green flat piece onto the monitor. www.eggplant.com

By performing the iterations, you can successfully test it.

You can use the source code to see the information session to be curious.

Relax while you listen and read.

Make another suCH rsa program for ECM and curvings and sieving.
Terrence Law is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Wii U, good concept, bad implementation? jasong jasong 6 2013-10-23 18:34
SQUFOF implementation alpertron Factoring 15 2010-04-12 19:16
ECM/FPGA Implementation rdotson Hardware 12 2006-03-26 22:58
need C implementation of divb(r,k) Leith Miscellaneous Math 4 2005-01-18 23:14
Different types of factoring, implementation dsouza123 Factoring 12 2003-08-08 11:35

All times are UTC. The time now is 21:08.

Tue May 11 21:08:34 UTC 2021 up 33 days, 15:49, 0 users, load averages: 1.83, 2.10, 2.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.