So I was reading up on RSA public key encryption.
Did you know, I didn't know there were an infinite number of prime numbers (kinda embarrassed to say it) but looking at the proof it seems pretty clear
It is known that there are an infinity of primes, and this has been known since antiquity. In Euclid's Elements, Book IX, proposition 20, Euclid offers a proof similar to this one:
Assume there is a largest prime number. Call this number p.
Create new number q, equal to the product of all primes between 2 and p, plus 1.
Our new number q has no factors in the original set of primes (between 2 and p), because dividing by any of them would produce a remainder of 1.
From point (3) we conclude that q is either itself prime, or is composed of prime factors, all of which are larger than p.
Point (4) falsifies point (1).
Even though a proof like the above needs no specific numerical evidence, here is an example with real numbers:
Assume the largest prime is 17: p = 17.
Our new number q equals the product of all primes in the set {2 ... p} plus 1: q = 2 * 3 * 5 * 7 * 11 * 13 * 17 + 1 = 510511
According to the factoring calculator at the top of this page, q has these prime factors: 19, 97, 277.
All the prime factors of q are larger than p.
Point (4) falsifies point (1).
There are a large number of proofs of the infinity of primes, this one happens to be easy to understand.
http://www.arachnoid.com/prime_numbers/
Coool huh?
Yeah, cool.
Now how does encryption use primes as protection from cracking? That part loses me.
Chew on this awhile
Yea the link Arthur posted explains it well. Yea its amazing how people think of these mathematical equations
What is the weird e symbol and mod?
Also what's up with that three line equals?
I think the three line equals means something like "is exactly the same as"
I know my professor uses it when two things have exactly the same truth tables.
http://en.wikipedia.org/wiki/Modular_arithmetic
This might help a bit
The "three line equals" means "is congruent to". I don't see a weird e symbol, unless you mean the phi: . It's a Greek letter, brush up! (Edit: not displaying properly, but if you make a LaTeX document, type "\varphi" for the symbol. )
As for modulus, you're familiar with the idea if you've ever used the % operator: http://en.wikipedia.org/wiki/Modular_arithmetic.
For the e he speaks of look at the bold
A worked example
Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.
Choose two prime numbers
p = 61 and q = 53 Make sure that these prime numbers are distinct.
Compute n = pq
Compute the totients of product. For primes the totient is maximal and equals the prime minus one. Therefore
Choose any number e > 1 that is coprime to 3120. Choosing a prime number for e leaves you with a single check: that e is not a divisor of 3120.
e = 17
Compute d such that e.g., by computing the modular multiplicative inverse of e modulo :
d = 2753
since 17 · 2753 = 46801 and 46801 mod 3120 = 1, this is the correct answer.
(iterating finds (15 times 3120)+1 divided by 17 is 2753, an integer, whereas other values in place of 15 do not produce an integer. The extended euclidean algorithm finds the solution to Bézout's identity of 3120x2 + 17x-367=1, and -367 mod 3120 is 2753)
The public key is (n = 3233, e = 17). For a padded message m the encryption function is or abstractly:
The private key is (n = 3233, d = 2753). The decryption function is or in its general form:
For instance, in order to encrypt m = 65, we calculate
To decrypt c = 2790, we tap
.
Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real life situations the primes selected would be much larger; in our example it would be relatively trivial to factor n, 3233, obtained from the freely available public key back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.
I see you're reading up on RSA. It's neat stuff, and actually not that difficult to implement once you've read it over a few times. Took me a little while to wrap my head around modular arithmetic (pun intended)
Yes bob reading up on it a bit. I actually read up on it a while back when I was learning about encryption techniques (though I wasn't doing public key encryption), and I researched other cihper algortihms before I coded my own digital encryption software allowing me to with relative confidence keep my data safe from the average person/or even coder (I don't expect the NSA to be trying to crack my encryption using their supercomputers).
Anyways I've been reading
Crypto
"How the code rebels beat the government saving privacy in the digital age"
By Steven levy
My social security number is prime.
My social security number is prime.
Is it '2' by any chance?
SSN is a nine digit number
000000002
Mine is 607-70-1699. Go and steal my identity now.
Your SSN shows up at ***-**-**** when you type it. That's what I see when you post 607-70-1699.
optimus prime
Seventeen posts before an Optimus Prime reference was made. I'm not sure if I should be proud or disappointed.
Thanks for the SSN
I stole your identity and am now wiring $20million US dollars from your account to mine.
I also had your vacation home in the South Pacific sold and I liquidated your
hard assets, such as your
and
and since I'm now you, I took your girl too. She is smart, at first she was like I wasn't you, but i told her I would prove to her that I was you because only you would know your ssn. So after I told her your ssn she believe me that I was you.
{"name":"amy-jackson-photos-01.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/d\/1dd6dec9bb3b33af4012b32d86659391.jpg","w":750,"h":1343,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/d\/1dd6dec9bb3b33af4012b32d86659391"}
Oh by the way you are a father now, ooh thats right shes not your girl anymore, I mean I'm a father now.
Lastly I used your savings in your saving account to buy a new place for my new family. Thanks man you're the best
Thanks man you're the best
I do what I can.
and I do what I must