20040404, 21:42  #1 
Feb 2003
2·59 Posts 
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 < (p11)*(p21) so GCD(E, (p11)*(p21)) = 1 calculate D so D*E = 1 mod (p11)*(p21) 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)? 
20040405, 02:03  #2 
Sep 2002
2×131 Posts 
Hi Flava,
Have you tried LLR? It find prime of the form k*2^n1 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 
20040405, 02:07  #3 
Aug 2002
2^{6}·5 Posts 
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.

20040405, 02:11  #4  
Jun 2003
The Texas Hill Country
1089_{10} Posts 
Quote:


20040405, 08:39  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10100110111010_{2} Posts 
Quote:
If the weakest defense of your scheme is such that you need multikilobit 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 

20040405, 15:25  #6 
Feb 2003
118_{10} Posts 
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. 
20040405, 16:27  #7  
Nov 2003
1D24_{16} Posts 
Quote:
(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? 

20040405, 18:55  #8  
Feb 2003
2×59 Posts 
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Last fiddled with by flava on 20040405 at 18:56 

20040406, 00:33  #9  
Aug 2002
Portland, OR USA
2·137 Posts 
Quote:
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 bitlength 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 bitlength disparity and give it away. 

20040406, 01:10  #10  
Aug 2002
2^{6}·5 Posts 
Quote:


20040611, 02:12  #11 
May 2004
112_{8} Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Wii U, good concept, bad implementation?  jasong  jasong  6  20131023 18:34 
SQUFOF implementation  alpertron  Factoring  15  20100412 19:16 
ECM/FPGA Implementation  rdotson  Hardware  12  20060326 22:58 
need C implementation of divb(r,k)  Leith  Miscellaneous Math  4  20050118 23:14 
Different types of factoring, implementation  dsouza123  Factoring  12  20030808 11:35 