# Tag Info

77

Worst-case Hardness of NP-complete problems is not sufficient for cryptography. Even if NP-complete problems are hard in the worst-case ($P \ne NP$), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using ...

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

50

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

49

There have been. One such example is McEliece cryptosystem which is based on hardness of decoding a linear code. A second example is NTRUEncrypt which is based on the shortest vector problem which I believe is known to be NP-Hard. Another is Merkle-Hellman knapsack cryptosystem which has been broken. Note: I have no clue if the first two are broken/how ...

31

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

27

First we must assume that Eve is only passive. By this, I mean that she truthfully sends the card to Bob, and whatever she brings back to Alice is indeed Bob's response. If Eve can alter the data in either or both directions (and her action remains undetected) then anything goes. (To honour long-standing traditions, the two honest parties involved in the ...

25

I can think of four major hurdles which are not entirely independent: NP-hardness only gives you information about complexity in the limit. For many NP-complete problems, algorithms exist that solve all instances of interest (in a certain scenario) reasonably fast. In other words, for any fixed problem size (e.g. a given "key"), the problem is not ...

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

Looks like a classic application of Public Key Cryptosystem like RSA. You send your public key along, BoB encrypts your phone number from his contacts list and sends it back to you.

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

One of the most basic things you can do is a Diffie-Hellman key exchange. It does not require you to have keys set up before the communication starts as it negotiates one in a way that listeners can not derive the key themselves. See the comprehensive Wikipedia article for details. You send Bob DH parameters $p$ and $g$ ($p$ being a suitable large prime, ...

14

I have no way to learn (say) $m_1$ unless I know $m_2$. That is exactly the problem - if you re-use the same key, and someone has access to one message you encrypted in both plaintext and encrypted form, they can use that to find your key: $$(m_2 \oplus k) \oplus m_2 = k$$ As an alternative scenario, if you use the same key over and over, the ...

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 Quantum computers might have some advantage over classical computers for some cases. The most remarkable example is Shor's Algorithm which can factor a large number in polynomial time (while classically, the best known algorithm takes exponential time). This completely breaks schemes like RSA, based on the hardness of factorization. This is not necessarily ... 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

It's insecure precisely due to the reason you mention - there is some information leakage. Basically, if you have any assumptions about plaintexts (english text, files with known structure, etc), it leads to an easy statistical analysis. Probably using it twice doesn't change the practicality of the attack significantly, but using it many times with a non-...

11

Typically, there are a variety of steps in evaluating a new algorithm. They start with the quick review is it already known? does it vary only in nonrelevant ways from what is known? which is commonly enough to show vulnerabilities in many amateur attempts at encryption. The point is that there are a number of well known ways to translate strings of ...

11

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}\... 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 The taps are decided by the polynomial in a straightforward way: for$X^n$, you connect the$n$th tap. Note that in your diagram the first tap is$R4$, the 2nd is$R3$etc.. Since your polynomial is$X^5+X^2+1$the feedback is an XOR of the output of the 2nd tap ($R3$) and the 5th tap ($R0$). The "$+1$" of the polynomial ($X^0\$) is usually always there and ...

10

This is not an answer to your question. But as is often stated in crypto circles: Cryptographic protocols and algorithms are difficult to get right, so do not create your own. Instead, where you can, use protocols and algorithms that are widely-used, heavily analyzed, and accepted as secure. When you must create anything, give the approach wide public ...

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