How does asymmetric crypto work? For example, if you use PGP in emails, you generate a private key that is known only to you and a public key, which is available to everyone. Is there a simple way to explain, why you need a private key and why no one can decrypt the message with just the public key? I think of an explanation like for example with prime numbers:  If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors. Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. (See  for more information.) The product of the two prime numbers can be used as a public key The primes themselves as a private key. So the private key is the knowledge of two very large prime numbers  for easy understanding lets take the simple example (very large) prime numbers: 3 and 5:  private key: the knowlege of 3 and 5 the public key is just those numbers multiplied: 15 you cannot find out 3 and 5, so the message encrypted with 15 is ...  Here is a quite good explanation already, but it is not clear enough:  Can you please add an example with those numbers?
46859
I've always been interested in encryption but I have never found a good explanation (beginners explanation) of how encryption with public key and decryption with private key works.  How does it encrypt something with one key and decipher it with another key?
33990
There exist certain attacks that can be used against RSA keys whose prime factors are of specific forms, such as one by Coppersmith.  How common are these RSA keys?  If you generate primes randomly, is there a realistic risk of choosing a weak prime number?  Does this risk, if realistic, vanish if you always choose $p$ and $q$ to be safe primes?
45596
What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?  I'm aware that I can find any number of articles on the Internet that explain how the RSA algorithm works to encrypt and decrypt messages, but I can't seem to find any article that explains the algorithm used to generate the p and q large and distinct prime numbers that are used in that algorithm.
106095
Im really into cryptography and to find the private key of a message I need to use modular arithmetic. I understand how modular arithmetic using a clock with whole numbers. But I get really stuck when I get to fractions, for example:     1/3 mod 8   How do I find a modular of a fraction? Is there a method for finding this?  Thanks in advance!
800
One time pad required a truly random key. Why canwt it be a psudo-random key? For example, if the key distribution is that for each bit the probability to get 1 is 0.6 and the probability to get 0 is 0.4, and the eavesdropper knows it, how can he decrypt the message (assuming that the key length is at least as big as the message length)? Thank you
108285
Background info: I am planning on making a filehost with which one can encrypt and upload files. To protect the data against any form of hacking, I'd like not to know the encryption key ($K$) used for a file, so the user will have to asymmetrically encrypt $K$ and send it as well. The reason for this double encryption is that you can still share (individual!) files with other accounts by encrypting $K$ with the public keys of those users, too.  My problem is: How can a user can get a public and private key without the server saving/knowing the private key and without the user having to remember a passphrase of 250 hex characters?  Question: Is there a way to derive a key pair from a password, like PBKDF-2 does for symmetric encryption? Suggestions on rearranging the cryptographic steps in an easier way are welcome, too.  Alternatively: It is also possible to encrypt the private key with a PBKDF-applied password and store it on the server, but I'd like to keep things 'simple'. ;)  Note: At this point I don't care if it requires RSA, ECC or an obscure cryptography scheme.
45067
I'm trying to understand the working of RSA algorithm. I am getting confused in the decryption part. I'm assuming   $$n = pq$$ $$m = \phi(n) = (p - 1)(q - 1)$$  E is the encryption key $\gcd(\phi(n), E) = 1$  D is the decryption key, and  $DE = 1 \mod \phi(n)$  $x$ is the plain text  Encryption works as ($y = x^E \mod n$) and decryption works as ($x = y^D \mod n$)  The explanation for why the decryption works is that since $DE = 1 + k\phi(n)$,  $$y^D = x^{ED} = x^{1 + k \phi(n)} = x(x^{\phi(n)})^k = x \mod n$$  The reason why last expression works is $x^{\phi(n)} =  1 \mod n$ ? According to Eulers theorem this is true only if $x \text{ and }\phi(n)$ are coprimes. But $x$ is only restricted to be  $0 &lt; x &lt; n$  and $\phi(n) &lt; n$. So $x$ should be chosen to be coprime with $\phi(n)$?  Help me clear out the confusion!
29341
D-wave systems has released . This means in theory, that all asymmetric encryption algorithms — such as RSA — are now useless due to the speed at which quantum computers can factor.  Has RSA been cracked yet? If not, why hasn't it?  The reason for our company's concern is an upcoming product that relies heavily on cryptography, and a significantly large number of hackers may attempt to break it. If the code was found to be insecure, it would be a huge problem for our company, our users, and anyone on the Internet if RSA was found to be insecure.   Update: article on D-Wave recent announcement
15506
It's been over 30 years since Rivest, Shamir and Adleman first  described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for around 40 years&mdash;possibly longer.  It's fair to assume that, during those 40 years, certain three-letter organisations have employed their vast resources toward "breaking" RSA.  One brute-force approach may have been to enumerate every possible key-pair such that, upon encountering a message known to be  encrypted with a particular public-key, they need merely lookup the associated private-key in order to decrypt that message.  Signatures could be forged similarly.  How reasonable is this hypothesis?  How much computing resource would have been required over those 40 years to enumerate every possible {1024,2048,4096}-bit key-pair?  I think it best to avoid discussion and leave the question of whether the spooks could have harnessed such resource as an exercise to the reader.
46470
I quote Bobby's question here since I encountered the same one...    Consider the following protocol for two parties to flip a fair coin.   Trusted party $T$ publishes her public key $K_{pub}$ $A$ chooses a random bit $b_A$, encrypts it under $K_{pub}$, and announces the ciphertext $c_A$ to $B$ and $T$ $B$ does the same and announces a ciphertext $c_B$ (where $c_B \neq c_A$) $T$ decrypts $c_A$ and $c_B$, and announces the results. Both parties $XOR$ the results to obtain the random value $b_A\oplus b_B$.   It was shown that  was not appropriate for the encryption scheme.  seems to fail to work also. Since $c_A=m^e \mod N$. Then if $m=1$, $c=1$. If $B$ receives $A$'s cipher he will know the exact value of $m$.   So what should the appropriate encryption scheme be?
7698
Is it possible to encrypt a message in such a way that multiple keys can independently decrypt it?  In other words:  Having knowledge of $key_1, key_2 ...key_N$, which are different symmetrical keys, is it possible to generate a ciphertext that can be independently decrypted using either $key_1$ or $key_2$ or $key_N$, in such a way that the length of the ciphertext is less than directly proportional to $N$?
42310
It's pretty easy to generate a Curve25519 private key: generate 32 random bytes of data and then do:  e[0] &amp;= 248 e[31] &amp;= 127 e[31] |= 64   You can then generate a public key by doing  on the private key. For example, here's a random keypair I just generated:  public: e40ed268dff20db8497d0691421d00b086aad1efedcd5bd223d9eb6c0b85665f secret: e3c0e8b20ba7894882ddb37522dbe90867befcf9f31a5ce29c0d7997e0bd856d   The whole safety of public key encryption is that it is hard to take a public key and reverse the operation. Elliptic curve cryptography, as I understand it, relies on the fact that a  is hard to find. In particular, for a given large b and g, it is hard to find an integer k such that  $b^k = g$  How does that equation relate to Curve25519? Specifically, if I had a public key like the one above, how would I express, in math terms, the problem I need to solve to find the private key? How does it relate to the equation I see from time to time - $y^2 = x^3+486662x^2+x$, and the number $2^{255} - 19$?  I am guessing it is not as simple as "the private key is k and the public key is b and/or g" in the equation above. I'm also a little confused because the keys would appear to have roughly the same number of digits, which would seem to imply that there aren't many feasible values for k?
111629
While studying the RSA algorithm I referred to some books and some sites such as  and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d and e are multiplicative inverse of each other, can't we keep {e,n} as private key and use the other as public key? Is it a standard rule to choose the {d,n} as the private key?
93181
In various articles it is mentioned that for secure communications, the recommended key sizes are 128-bit key size for symmetric encryption (which makes it $2^{128}$ possible keys?) and 2048-bit key size for asymmetric encryption ($2^{2048}$ possible keys?).  Why do they differ so greatly? It seems like I am missing a very big part of the equation.
33716
The question is about the encryption equation in asymmetric encryption.  For $c\equiv m^e\bmod n$, prove that for every unique $m$ there is a unique $c$.  Here $n=pq$ where $p$ and $q$ are primes larger than $m$ and the exponent $e$, is $\geq3$ and coprime with $p-1$ and $q-1$.  Thanks!
69235
I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on mathematical facts, others are just instinctive approximations (such as square roots).  Don't such 'tricks' exist for factorization of a product of 2 large primes. For example, the first thing to do would be to figure out the possible last digits of the answer. We stick to decimal numbers, but a computer could do this in a number system of any base (even 999). Based on previous numbers, can an algorithm be written to 'predict' the factorization based on the individual digits in various number systems.
8545
I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic.  I understand that many security experts out there might get angry just by the discussion of these things, but I hope you can spare me :)  My Questions:  Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing prime keys up to 2^2048 ?  I understand this would take an immense amount of time to do, but it would only be done once.  Given the public key, you would be able to look up what the two primes are, and hence retrieve the private key instantly.  When I consider who might break such a code, I am primarily thinking about NSA and other Governments that might have spent years in research and have the resources and interest in doing so.  Breaking an 256 AES would then be easier, as AES keys are often generated using the RSA private key.  Would it be possible to build such an index ? How long would that take in permutations, and perhaps with the fastest computer in the world ?  I hope we can have a nice chat about this. We are just discussion theory here. I hope you can offer me some insight on this topic.  Thanks!