60

Q: If you pedal backwards on a fish, does it go backwards? A: ??? A fish is not a bicycle. Similarly, you cannot use a private key to encrypt a message or a public key to decrypt a message. They don't have the right equipment. With RSA, which is a popular public-key cryptosystem but not the only one, the private key and the public key have the same ...


50

The easiest way to think about it is to think of the contrapositive. The statement: if factoring large integers is hard, then breaking RSA is hard is equivalent to the following: if breaking RSA is easy, then factoring large integers is easy This statement has not been proven. What they're saying is, assume we have an algorithm that solves ...


32

The title and the body of your question ask two different questions: how the OS creates entropy (this should really be obtains entropy), and how it generates pseudo-randomness from this entropy. I'll start by explaining the difference. Where does randomness come from? Random number generators (RNG) come in two types: Pseudo-random number generators (PRNG),...


31

We don't know for sure that RSA is safe. It could be that RSA can be broken in polynomial time, for example if factoring can be done efficiently. What is open is the existence of a a provably secure public-key cryptosystem. We don't know for sure that such a cryptosystem exists at all; for all we know, every cryptosystem could be broken efficiently. A ...


31

The existence of a hard way does not imply there is no easy way. There may be a number of ways to break RSA and we only need to find one of them. One of these ways is factoring a large integer, so if that is easy we can do it this way and RSA is broken. This is also the only way we know yet. If it is unfeasible to do that, we can still find another, ...


28

If you want to present public key cryptography to your parents or friends, then I suggest you follow some guidelines. First, don't talk about specific functions, nobody cares about SHAxxx, keep your talk conceptual. The problem solved by public key cryptography is allowing two parties who never met before to securely exchange information in a public channel. ...


17

You seem to have misunderstood what the key is. In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver. For OTP, the key is the entire pad and, if two people wish to encrypt some message using OTP, they must ensure beforehand that they have a long enough pad to do that. For your proposed ...


15

This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ciphertext E and knows the corresponding message M can recover the secret key and thus decrypt all other messages that were encrypted with the same key. The ...


15

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate polynomial $p(x_1,\dots,x_n)$ such that $f(x_1,\dots,x_n) = p(x_1,\dots,x_n)$ for all $x_1,\dots,x_n$, where arithmetic is done modulo two (i.e., over the field $\...


15

A common metaphor I hear used is manufacturing a bunch of padlocks, keeping all the keys, and sending out open padlocks to anyone who wants one. Then anyone with such a padlock can send you secret messages by putting them in a box and then using one of your padlocks to lock it before sending it to you. No-one but you has the keys, so even the sender can't ...


14

The security of RSA relies on the fact that the best known way to compute $\phi(n)$ is to prime factorize $n$. For $n=pq$, where $p$ and $q$ are large, distinct primes, this is very hard. If instead $n=p^2$, then one could quickly find $p$ by calculating a square root. Then one could calculate $\phi(p^2)=p^2-p$ and break the encryption completely.


14

There is no strong technical reason. We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA. So why RSA? As far as I can tell, non-technical historical reasons dominated. RSA was patented and there was a company behind it, marketing and advocating for RSA. Also, there were good libraries, and RSA was easy to understand and ...


14

Yes — in fact, the very first public-key algorithm that was invented outside an intelligence agency worked like that! The first publication that proposed public-key cryptography was "Secure Communications over Insecure Channels" by Ralph Merkle, where he proposed to use “puzzles”. This is a key agreement protocol. Alice sends $n$ encrypted messages (called ...


14

Public key cryptography means that the entire communication between both parties is public, including the setup. Contrast this with the case of two parties $A,B$ meeting in secret, agreeing on some keyword, and using this keyword to encrypt future communications. Clearly, if $A,B$ decide on the encrpyption scheme in public, something has to be kept private (...


12

Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US. UP: If $x \in L$, then there is exactly one "proof" ("witness", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs". US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be ...


12

MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $w$. The basic idea is simple, you represent a large integer with multiple fixed-width words where the i-th word is the i-th "digit" in base B where $B = 2^w$. For example, most current machines ...


11

In addition to SBareS's answer, let me mention that the formula $\varphi(pq) = (p-1)(q-1)$ only works if $p \neq q$: $\varphi(p^2) = p(p-1)$. Therefore if $p = q$ then decryption wouldn't be the inverse of encryption (unless you use the correct formula for $\varphi(n)$.


11

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator No, no and once again no. I'm concerned that this is what you're being taught. The absolutely fundamental concept of a one time pad and the notion of mathematically provable perfect secrecy is that the pad material is truly random. And it must never ever be reused, even ...


10

One additional way to look at it, is that breaking RSA requires only a special case of factoring, which may or may not be easy regardless of the general question of factoring. As a simple example, consider the case that factoring is indeed difficult, but only for numbers with $3$ different factors. Factoring composite numbers with only two different factors ...


10

This is known as a one-way permutation. The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements. There are various candidate constructions for one-way permutations, e.g., based on raising to the third power modulo an RSA modulus or other schemes.


10

Diffie–Hellman lacks a crucial feature: authentication. You know you are sharing a secret with someone, but you can't know if it's the recipient or a man in the middle. With RSA, you may have a few trusted parties who store public keys. If you want to connect to your bank, you can ask the trusted party (let's say Verisign) for the bank's public key, as ...


10

Cryptosystems which are algebraic in nature are amenable to algebraic cryptanalysis. If you are trying to design a secure cryptosystem for actual use, there is one important maxim that you should keep in mind: Don't design your own cryptosystem! It is easy to design weak cryptosystems. Off-the-shelf cryptosystems have withstood breaking attempts by the ...


10

Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions $f:\mathbb{F}^n\rightarrow\mathbb{F}$ of the form: $$f(x_1,...,x_n)=\sum\limits_{i_1+...+i_n\le d}\alpha _{i_1,...,i_n}\cdot x_1^{i_1}x_2^{i_2}...x_n^{i_n}$$ where $\alpha _{i_1,...,i_n}\...


10

Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again? Yes, they can. A key exchange protocol like (the "textbook" version of) DH is secure against eavesdropping (i.e., simply observing what is being transmitted on the channel), but completely breaks down against man-in-the-...


9

In the crypto community, this task is known as delegated computation, or verifiable delegation. You wish to let the server (the "cloud") to do the work for you, but you also want the cloud to give you some proof that it actually performed the computation (and didn't just output a random output, and ran away with your money). A pointer, off the top of my ...


7

The RSA method works regardless of the size of the individual primes $p,q$. The reason that we would want $p$ and $q$ to be of roughly equal size is that one method of breaking RSA is factoring $n = pq$, and the running time of some factoring methods (notably ECM, the elliptic curve method) depends on the size of the smallest prime factor of $n$. Therefore ...


7

As Yuval points out, contemporary crypto systems are not based on NP-complete problems. NP-hardness is a worst-case notion of hardness. A problem might be NP-hard but easy to solve in many cases, or on average, or even in most cases. A crypto systems that was easy to crack on average would not be useful. We want crypto systems that are hard to crack in ...


7

In theory, yes, a peer-to-peer validation network could be used to enforce any unique content (not just money) assuming a sufficiently large validation network. "Sufficiently large" is the catch. Bitcoin validates transactions by having the network nodes "vote" on the transaction's validity. According to Satoshi's proposal: The system is secure as long ...


7

There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated numbers is to mask the true state. Here's how it works. You take your $b$-bit number $x_t$ to be the true state at time $t$, but the number your RNG generates is $...


7

It means that the RSA problem seems (at this time) to be more specific than factoring. So the RSA problem is this: knowing a semiprime $pq$ and some exponent $e,$ and a value $v,$ find the $m$ such that $v \equiv m^e \mod pq$. (I actually got this wrong in my original answer, so that my phrasing of the RSA problem was equivalent to factoring up to some PP ...


Only top voted, non community-wiki answers of a minimum length are eligible