/sci/ - Science & Math

[/sci/ !chOTiCqaR6 No.1808066]

How do the primes for public key RSA get generated?

I know you need 2 200 digit primes and they make up the private keys, and multiplied together is a 400 digit public key

but how...oh HOW do they make 200 digit prime numbers?

[Anonymous No.1808104]

Pretty easily, with computers. Mostly, to search for large primes, people just look for Mersenne primes, which are primes of the form (2^n)-1. These aren't always primes, but it's a proven way to find some prime numbers.

[/sci/ !chOTiCqaR6 No.1808103]

will bump with info graphs

[Anonymous No.1808115]

using a very powerful computer and a prime generating formula.
usually you give a program some interval, and it eliminates a bunch of obviously composite numbers from the interval and checks the rest.

[Anonymous No.1808119]

>>1808066
knowing neckbeards, they likely repeatedly generated 200 bit numbers from a cryptographic card until they found one that was prime.

[Anonymous No.1808147]

With a large enough amount of memory available, you can generate primes in O(n) time with a sieve.

Given the supercomputers available to the NSA, it's not inconceivable that they could sieve 200 digit primes.

[/sci/ !chOTiCqaR6 No.1808148]

>>1808104
that can't be the only method - there would be a limited number of mersenne primes

>>1808119
"cryptographic card" ?

I mean, Im using ubuntu linux here. Are the 200 digit primes stored somewhere on my computer or does it create them itself every time it wants to SSH ? and it does create them every time...HOW?

[Anonymous No.1808211]

WITH MATH

[/sci/ !chOTiCqaR6 No.1808226]

[/sci/ !chOTiCqaR6 No.1808367]

[Anonymous No.1808392]

it's really not that hard to generate very large prime numbers - the idea is that it's waaay harder to factor the product of those two large primes, so much so that it's practically impossible, while your computer can generate the two primes very quickly

[/sci/ !chOTiCqaR6 No.1808434]

answers I am getting so far:
>Pretty easily, with computers
>very powerful computer and a prime generating formula
>cryptographic card
>supercomputers
>WITH MATH
>your computer can generate the two primes

FUCKING HOW YOU NIGGERS

[Anonymous No.1808465]

Basically the software selects random numbers from a given domain of candidate primes (probably something with numbers divisible by small primes chopped out through sieve of eratosthenes + modular arithmetic), and it will do some primality tests on these numbers to check they are primes (or at least pseudoprime for a more efficient first check). The tests you can google yourself, things which use Fermats theorem, Rabin Miller, etc.

[Anonymous No.1808500]

>How do the primes for public key RSA get generated?

The usual mechanism is to randomly select a set of smaller primes then test whether p0*p1*...*pn+1 is prime. Testing first uses a probabilistic test (primes will never be declared composite but there's a small probability of a composite being declared prime), then uses a deterministic test on anything which survives the probabilistic test. Repeat until you get a value which is actually prime.

> Are the 200 digit primes stored somewhere on my computer or does it create them itself every time it wants to SSH

The authentication key is stored on your computer, typically in ~/.ssh/identity (private key) and ~/.ssh/identity.pub (public key).

While the authentication key has to be stored, the encryption keys may be randomly generated (web servers tend to generate a new key-pair every N minutes, serving multiple HTTPS connections with each pair; generating a new RSA key-pair per connection would be way too slow).

The symmetric encryption key is always randomly generated and is only used for a single connection.

[Anonymous No.1808520]

>>1808434
10 seconds on google
http://en.wikipedia.org/wiki/Formula_for_primes

[/sci/ !chOTiCqaR6 No.1809786]

>>1808520
woefully un-useful article

[Anonymous No.1809836]

Hey there, OP. University of Washington mathfag here.

I'm making several assumptions about your level of education in this field, so don't get offended.

Actually, the prime numbers your computer generates for RSA are not primes with 100% certainty. What your computer does is pick a number from the appropriate space (~200 digit long numbers) and run several tests that catch numbers if they are composite most of the time. If that number passes all these tests, it is assumed to be

a) prime (almost 100% of the time)
b) a pseudoprime ("fake" prime number) which is probably unfactorable anyway.

This is a good page if you're willing to take a minute and read up on it.

http://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests

[Anonymous No.1809841]

>>1809836
Here, too.

http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

[Anonymous No.1809897]

I've never heard of this before and I found it really interesting - can you good people of sci tell me more about this RSA ?

[Anonymous No.1809913]

The Miller-Rabin test is the most commonly implemented algorithm.

[/sci/ !chOTiCqaR6 No.1809972]

>>1809836
oooooo I C

so, sometimes my computer WILL use a non-prime as a key, but it is still "probably" un-factorable (ie not factorable within reasonable amount of time/computing power) - which makes me nervous.

that means that there are some pseudoprimes my computer is making that would be easier to factor than say a true 200 digit prime. .... might be factorable with a 175 digit prime..... ok


>>1809897
it goes like this. a computer gets two large primes (somewhere around 10^200) and multiplies them together (to make something like 10^400)
it then shares this number openly so that anyone can read it. the party it wants to share information with then encodes the information using the 10^400 number and sends it back. the first computer can only decode that information because of the 2 - 10^200 numbers it has.

the reason this works is because it takes a LONGER TIME to FACTOR a LARGE number than it does to find and multiply 2 large primes
see:
http://www.claymath.org/posters/primes
http://www.claymath.org/posters/primes/primes.php
http://mathcircle.berkeley.edu/BMC3/rsa/node4.html

[Anonymous No.1809999]

>>1809972
>so, sometimes my computer WILL use a non-prime as a key, but it is still "probably" un-factorable (ie not factorable within reasonable amount of time/computing power) - which makes me nervous.

Probably not. The odds that your computer grabbed a pseudoprime are pretty low. You're more likely to win the Powerball lottery. Several times in a row, actually.

[Anonymous No.1810008]

>>1809999
>that means that there are some pseudoprimes my computer is making that would be easier to factor than say a true 200 digit prime.
Also, 200 digit primes (actually all primes) are incredibly easy to factor. Think about that for a sec.