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


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


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

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


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

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


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.


13

The purpose of a hash in this scenario to be able to uniquely identify an entity. It's not strictly unique, only probabilistically unique. Hashes are not reversible functions, so your client can't know the data that was encoded with it. It could be guessed by brute force and maybe some know attacks to the hash assuming the type/format of data is known, ...


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

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

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


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

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


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


8

WEP uses the stream cipher $RC4$ for confidentiality and the CRC-32 checksum for integrity. All data frames sent by a router in a WEP protected network are encrypted. When a router sends a packet, the following steps are executed. The router picks a $24$-bit value called the initialization vector $IV$. A new $IV$ is used for every packet. The $IV$ is ...


7

Whenever Alice and Bob wants to agree on a same private key, the most popular method is to use Diffie-Hellman. It works as follows: Two public values are first chosen lets say $n=13$ and $g=17$. (These are usually very large prime numbers and known to everyone using that protocol). Alice chooses a Private Value $a = 3$ and Bob chooses a Private Value $b = 7$...


7

Compressing encrypted data doesn't work. Encrypted data looks pseudorandom, therefore if you try to compress it, you'll find that the compression is ineffective. Try it. You'll see. It's a very simple experiment -- give it a try.


7

If you want a practical answer: with Intel SGX, the answer seems to be a qualified yes, but software development is likely to be more painful. (Similar with a TPM, though that will be even more annoying.) See, e.g., https://security.stackexchange.com/q/2459/971. If you want a theoretical answer: in theory, you could use various cryptographic schemes for ...


7

A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish the generator's output from a truly random string). Note that allowing the generator to toss coins makes the whole thing uninteresting, as you could simply ...


6

Suppose you use a one-time pad with English text, and you use it twice. Now, you can get $(m_1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus m_2$. English text has an entropy of something like 1.3 bits per letter. The XOR of two messages has 2.6 bits per letter. There are 26 letters in the alphabet, so this gives $\log_2 26 = 4.7$ bits per letter. This ...


6

Most private key algorithms rely on infeasibility of certain computations like factorisation of a number into its prime factors given the current computing infrastructure. At the same time, most of them are also computationally intensive when used for encryption and decryption and therefore the entire message stream is not encrypted using the private keys. ...


5

There can be more than one ciphertext that maps back to the same plaintext. In mathematical terms, the encryption algorithm must be injective so that you can recover the plaintext for the ciphertext, but this does not prevent the ciphertext from encoding more information than the plaintext. As a concrete example, consider modes of block cipher operation ...


5

The distinction you want to make between the key and the algorithm proper is not based on whether most of the operation is contained in one or the other, but on where the complexity lies. I am not talking about algorithmic complexity here, but complexity in its everyday meaning: difficulty to understand and reason about. The algorithm proper is complex and ...


5

The problem is known as timed-release cryptography. For some references/introduction look at: "Time-lock puzzles and timed-release Crypto" by R.R. Rivest, A. Shamir, and D. A. Wagner (1996) Our motivation is the notion of "timed-release crypto", where the goal is to encrypt a message so it cannot be decrypted by anyone, not even the sender, until a pre-...


5

First, a point of terminology: what you describe is symmetric encryption, and a key that's shared between participants is usually known as a secret key; “private key” usually means the part of a key in public-key cryptography that only one participant knows. There are two ways of disseminating a secret key: it can be transported in some physically secure ...


5

In set theory $B^A$ denotes the set of functions from $A$ to $B$. Thus, an element $f\in B^A$ is a function $f:A\rightarrow B$. In your specific case $\{0,1\}^k$ is the set of functions from the natural number $k$ -- a set with $k$ elements -- to $\{0,1\}$. An element $M\in\{0,1\}^k$ is then a $k$-tuple of zeros and ones, i.e., a binary string of length $k$,...


4

The thing is that even if you know nothing about $m_1$ and $m_2$, you might be able to recover them both from $m_1 \oplus m_2$. Actually, for many cases, it is very simple. Here's a simple visualization.


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