Wheel factorization: Efficient?

[3.14159]

Probability of the number not really being prime.

How many tests are done? I'm guessing.. 50.
Also: I do know an applet that provides a cheap simulation of RSA key generation, also provides a cheap simulation of encryption.

Here it is.

Applet for prime-generating:

Here it is. (It says it's crypto practice using applets.)

[CRGreathouse]

Originally Posted by 3.14159

How many tests are done? I'm guessing.. 50.

25 would be sufficient if an enemy handed you the supposed prime, at that error tolerance. 7 would be sufficient for a random 512-bit primes* according to Damgård-Landrock-Pomerance.

* 512-bit primes generating a 1024-bit key are the minimum required for modern security. For a 2048-bit key with 1024-bit primes, 3 or 4 tests would suffice.

[3.14159]

25 would be sufficient if an enemy handed you the supposed prime, at that error tolerance. 7 would be sufficient for a random 512-bit primes according to Damgård-Landrock-Pomerance. So 50 is off by 100% to 600%.

Off by a factor of 2 to 7?

An example encryption: 12567 --> 211295745591 --> 2241528539259169170987271045307742926880092206585363020076052605925009129640969172636961058727725654469153396.

[retina]

Originally Posted by 3.14159

How many tests are done? I'm guessing.. 50.

What are you basing your guess on?

Like I mentioned it depends upon the number size. I used a table. It starts at 160bits since I was not interested in smaller numbers.

k(bits) : MR tests
160 : 34
161-163 : 33
164-166 : 32
167-169 : 31
170-173 : 30
174-177 : 29
178-181 : 28
182-185 : 27
186-190 : 26
191-195 : 25
196-201 : 24
202-208 : 23
209-215 : 22
216-222 : 21
223-231 : 20
232-241 : 19
242-252 : 18
253-264 : 17
265-278 : 16
279-294 : 15
295-313 : 14
314-334 : 13
335-360 : 12
361-392 : 11
393-430 : 10
431-479 : 9
480-542 : 8
543-626 : 7
627-746 : 6
747-926 : 5
927-1232 : 4
1233-1853 : 3
1854-oo : 2

[3.14159]

* 512-bit primes generating a 1024-bit key are the minimum required for modern security. For a 2048-bit key with 1024-bit primes, 3 or 4 tests would suffice.

Based on the factoring progress, I think a 1024-bit key might be factored soon enough, unless interest remains on the Cunningham project forever.

[retina]

Originally Posted by 3.14159

I think I've seen encryptions with 128 bits, but I think that was using SSL. Also: 512 bits ≈ 155 digits?

You are confusing ECC and symmetric crypto with RSA.

[3.14159]

Also: A simple encryption: Try finding the cipher:

Hello -->19925626416901921153862395493065804612143354989442736293065804612143354989442736293642482459687520062956914986149.

[retina]

Originally Posted by 3.14159

Based on the factoring progress, I think a 1024-bit key might be factored soon enough, unless interest remains on the Cunningham project forever.

Have you ever estimated the effort increase required for 1024 bits compared to 768 bits? Without some major advance in factoring theory I doubt that "soon" will be soon at all.

[CRGreathouse]

Originally Posted by 3.14159

Off by a factor of 2 to 7?

Yes -- although I happened to remove that phrase in my edit to the post (because of the uncertainty in key size).

You never seem to tire of that owl.

Incidentally, I took the key sizes from the 2003 RSA schedule of recommendations, which has 1024-bit RSA expiring at the end of this year. (It's slightly complicated, look it up if you care.) 2048-bit is recommended until 2030.

[3.14159]

Incidentally, I took the key sizes from the 2003 RSA schedule of recommendations, which has 1024-bit RSA expiring at the end of this year. (It's slightly complicated, look it up if you care.) 2048-bit is recommended until 2030.

Classic case of people making unrealistic predictions. Moore's law is a flawed fiction.

[CRGreathouse]

Originally Posted by retina

Have you ever estimated the effort increase required for 1024 bits compared to 768 bits? Without some major advance in factoring theory I doubt that "soon" will be soon at all.

I guess it all depends on how long the data needs to stay secure and who you need to protect against. 768-bit keys could still be used, in a pinch, for data that goes stale fast. But if you need the data to be secure for years and think that the NSA wants it... 1024 is clearly inadequate.