52

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

Public-key cryptography as we know it today is built on one-way trapdoor permutations, and the trapdoor is essential. For a protocol to be publicly secure, you need a key available to anyone, and a way to encrypt a message using this key. Obviously, once encrypted, it should be hard to recover the original message knowing only its cipher and the public key :...


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

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

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

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 $\...


13

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.


12

Here are the three tests you're (implicitly) considering: Fermat: test whether $a^{n-1} \equiv 1 \pmod{n}$ Solovay-Strassen: test whether $a^{(n-1)/2} \equiv \left( \dfrac{a}{n} \right) \pmod{n}$ (where $\left( \dfrac{a}{n} \right)$ is a Jacobi symbol, which can be calculated using quadratic reciprocity via a GCD-like algorithm) Miller-Rabin: suppose $n-1 = ...


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 ...


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

For the field of A.I. and machine learning, I would recommend you to explore and learn more about these topics: Statistics Probability Stochastic processes Bayesian Data Analysis Convex Optimization Graph Theory With your math background, you could easily pick any good machine learning book and learn the required math that you don't have as you go. Kevin ...


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

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)$.


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

If you don't mind graphs with self-loops, the "easiest" expander family is probably this one, giving expanders that are 3-regular. Start with some prime number $p$, and construct vertices numbered $0$ to $p-1$. For every vertex $u \ne 0$, connect $u$ to $u-1$ and $u+1$, modulo $p$. Also connect $u$ to the unique vertex $v$ such that $uv \equiv 1 \mod p$. ...


9

The function $h$ may not be one-way anymore. We construct a counter example—a specific one way $f$ whose $h$ is not one-way anymore—in the following way. Assume $g$ is a one-way function that preserves size, and define $f$ on input $w=bx_1x_2$ in the following way, $$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$$ (...


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

Wlog let $g$ be a strong one way function, we will now construct a length preserving oneway function $f$. Since $g$ is PPT computable by assumption, there is a polynomial $p$ s.t $|f(x)| \le p(|x|)$ for all $x$ Define $$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ this function always has $|g'(x)| = p(|x|)$. and is trivially strongly one way. We now have to force ...


7

How to approach it? It's always the same answer - go back to the definitions. the definition of PRF, talks about a family of functions $\{f_k\}$. The key $k$ just selects one specific function out of this big family. Next, for $\{f_k\}$ to be a PRF family,the definition requires that any PPT algorithm $A$ will not be able to distinguish a member of the ...


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