Why is double encryption that's equivalent to single encryption no better than single encryption?

This is simply saying that if a cryptosystem has a functional composition that is
$$ h_{k}(x) = f_{k_1}(g_{k_2}(x)) $$
then you can find a key for single encryption that works as the double encryption.
For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.
To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:
$$P = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\2 & 4 & 1 & 3 & 5 \end{pmatrix} \text{ and } Q = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \end{pmatrix}$$ The compositon of the two keys is
$$R =QP = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\4 & 2 & 5 & 3 & 1 \end{pmatrix}$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.
Now turn back to DES:
Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the
subgroup generated by the set of DES permutations is greater than $10^{2499}$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.
If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^{28}$ steps showed by Judy H. Moore and Simmons (paywalled).
Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.

The academical works on DES closure

1982 - D. Coppersmith, “In Defense of DES”, personal communication‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) (pay-walled), and pay-wall free.
They introduce a novel cycling closure tests which gave evidence that the
set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES (pay-walled)
1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES (pay-walled)
1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.

‡ This work claimed to be
described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!


The Gaussian function over a lattice, if you define it with or without the scaling factor $1/s^n$, is not a probability distribution, since it does not sum to 1. In order to construct a probability distribution, that samples points proportionally to the Gaussian function, one has to rescale anyway by dividing by the sum of the Gaussian over all lattice points (even though this is an infinite sum, it is well defined and one can compute sharp bounds on it). So any scaling factor you apply to the Gaussian function will be cancelled out by this normalization anyway, so you might as well define the Gaussian without it.


How does HTTPS transfer the symmetric key?

That depends on the cipher suite. If the master key is encrypted at all then it is usually encrypted using RSA, which can be identified by ciphersuites starting with RSA_. This requires that the certificate that contains the public key allows encryption.

An other way to establish the master secret is by using Diffie Hellman key agreement. This usually is ephemeral-ephemeral key agreement; DHE_ or ECDHE_ ciphersuites. The ephemeral-static key agreements (DH_ and ECDH_) require certificates containing a Diffie-Hellman public key and these are rare.

Nowadays many certificates only allow authentication, not encryption. They are used together with the aforementioned DHE_ and ECDHE_ ciphersuites. In TLS 1.3 the RSA_ ciphersuites are discontinued as they do not provide forward security: if the private key is ever obtained by an adversary then all the data of all the TLS sessions becomes available to that adversary.

Note that there are even other ways of authentication possible. The method of using RSA encryption is mainly used for older versions of SSL and TLS. So that description you have is 1. completely over simplified and 2. outdated. Read the TLS 1.2 specification if you want to know more.


How much original entropy is lost if a part of the hash is known?

A good hash function like SHA-512 is thought to behave like a random oracle and reveal nothing about it's input, however if the source has less potential entropy (fewer bytes) than the hash output size then this can be exploited as a potential search problem.

If the original source has fewer bytes than the hash output size, and this number of bytes is a computationally feasible search problem (i.e. < 80 bytes) then revealing k bytes of the hash is equivalent to revealing up to k bytes of the input source, since the candidate preimages of the output can be found.

Thinking about the scenario in which fewer bytes of the hash are revealed than there are bytes of entropy in the input source, there will be many inputs which map to the same abbreviated hash output. Ideally however these inputs would be a random distribution from the input source and not reveal any of the source entropy until the hash output size was equal to the input size.

Extending this idea further it's obvious that something about the input entropy is revealed, since as the number of bytes revealed approaches the number of bytes input the number of possible preimages is reduced which reduces the entropy until the stage that there is none and we have (ideally) only one preimage.

I modelled this and found experimentally that for SHA512 the amount of entropy about the input which is lost for each byte of the hash function output known is approximately (ideally) one byte. This makes sense in the context of the definition of a cryptographic hash algorithm.

e.g.

Input value with 6 nibbles of potential entropy: $9840563$

First 6 SHA512 nibbles: $8ae967$

$8: 1049140 \approx 2^{20}$

$8a: 65275 \approx 2^{16}$

$8ae: 4099 \approx 2^{12}$

$8ae9: 270 \approx 2^{8}$

$8ae96: 13 \approx 2^{4}$

$8ae967: 1 = 1$


How to perform decryption in this single-bit PKE scheme?

To decrypt, you basically take the $g^y$ component and raise it to the secret key, obtaining $g^{yx}$. Now, if this value is equal to the second component of the ciphertext, you can see that $M$ must be 0, since $g^{yx} = h^y$; otherwise, $M$ is 1.

Regarding the proof: yes, it would be very similar to ElGamal, since you have to construct the challenge ciphertext using a DDH tuple.


LPN is code-based problem, not a lattice problem. These are quite similar, but are defined with respect to different notions of "distance" (Hamming vs $\ell_p$-norm). In general while there are broad parallels between the worlds of lattices and codes, these parallels are not exact.

A particular example is the hardness of computing the "smallest element" of code/lattice. For codes it is the minimum distance problem, for lattices it is the shortest vector problem. Stronger hardness results are known for MDP (SVP's best hardness results require randomized reductions, MDP's are deterministic). Other mathematical problems can vary wildly in difficulty --- the "sphere packing" problem for codes is much simpler than for lattices.

Of relevance to cryptography are worst-case to average-case reductions. This has been a large motivating factor for lattice cryptography since its inception in the 90's, but similar results for codes were only developed last year (and I believe the results themselves are somewhat weaker, but am not an expert). This paper states that its the first construction of collision-resistant hash functions from $\mathsf{LPN}$, which might help highlight the technical difference in the state of the art for lattice-based cryptography vs. code-based cryptography (for the construction of certain primitives).


I think you're confusing some things here.

The usual TLS-handshake with ECDHE (which you really should use, unless you have very good reasons) has two public keys. One of them is signed by the CA, the other one is generated on-the-fly.

And before proceeding, please note: (Perfect) Forward secrecy (PFS, not security usually) only means that you don't compromise secrecy of future sessions if a long-term key is leaked, meaning PFS won't protect you against man-in-the-middle attacks if your long-term key is compromised, but very well against passive eavesdroppers.

So the usual key-exchange protocol makes use of the Diffie-Hellman protocol to let both parties agree on a common secret. The values exchanged for this sub-protocol are called public keys and if not authenticated may be subject to a man-in-the-middle attack, but the use of DH prevents passive eavesdropping, thereby yieldin the requested forward secrecy. Those public keys are also completely random (not a random bitstring though).

Now to prevent man-in-the-middle attacks each party signs their DH public keys using the key corresponding to the one in their valid CA signed certificate. If this key is leaked, the contents of future communication are not leaked unless the attacker uses a MitM attack, so PFS is preserved and MitM are prevented if the signature key is not compromised.

TL;DR: There are two public keys, one is long-term and one is short-term, the long-term one is CA authenticated and authenticates the short-term one thereby preventing MitM attacks and the short-term one yields the desired PFS property.


Digital identification using steganography, can it be broken?

tl;dr: That depends entirely on the watermarking scheme.

Longer version: That depends entirely on the watermarking scheme used, specifically on the perceptability and robustness of the watermark. If it's supposed to be visible and robust, degrading the quality as Dmitry Khovratovich suggested will retain the watermark but might achieve the effect he describes.

If the mark is too perceptable though it might be possible to remove it. According to Ross Anderson (read below for link):

  For example, where the mark was added by either increasing or decreasing the luminoscity of the image by a small fixed amount, this caused the peaks in the luminoscity graph to become twin peaks, which meant that the mark could be filtered out over much of many images.

Provided that original copies only differ in the watermarked regions, pauluss86's solution is the most sure-fire way to get rid of them.

The following is the answer I originally set out to write but quickly got out of context. I retain it because of some interesting background information.

There's been a question on Security.SE that discusses stenography detection in images, so that's a good place to start. But more to the point, Ross Anderson's excellent book Security Engineering has an entire chapter dedicated to copyright and DRM (links to 1st edition, 2nd edition is out). So let's take a look at that (page 711 of the 2nd ed.):

  The DVD consortium became concerned that digital video or audio could be decoded to analog format and then redistributed (the so-called 'analog hole'). They set out to invent a copy generation management system that would work even with analog signals. The idea was that a video or music track might be unmarked, or marked 'never copy', or marked' copy one only'; compliant players would not record a video marked 'never copy' andwhen recording one marked 'copy once only' would change its mark to 'never copy'.

So kind of like how the "do not track" button works in browsers. One thing jumps out though: The watermark (the 'copy' flag) has to be resilient enough to be preserved through the conversion from digital to analog, which means soft degrading (like converting to another format) would also leave it untouched. The text goes on to say

  SDMI also uses a fragile watermark that's damaged by unauthorized processing.

but it's important to note the SDMI forum no longer exists. According to the Wikipedia page linked,

  On October 15, 1999, Eric Scheirer, later a digital music analyst for Forrester Research, wrote an editorial for MP3.com titled "The End of SDMI" which declared that the group's true goal to fold the technology industry into an alliance that would guarantee the record industry's near monopoly over musical content had failed. [...] The SDMI has been inactive since May 18, 2001.


What will browser show when a user access website and website present certificate of some other domain with same top level domain

A well designed browser should display a warning page whenever there is a problem with a certificate for the asked paged.

Firefox and Chrome will provide a way to manually bypass the page.


XChacha20poly1305 vulnerability to known plaintext attacks

Using crypto_secretstream that should be fine. It generates a random nonce for each message. Reusing a key in that context is fine.

Original answer, before edit follows:

Yes, that's bad. You have to use a unique IV/nonce for each document.

A stream cipher, such as ChaCha, which is combined with the plaintext using XOR reveals the keystream to anyone who knows the plaintext. That allows them to decrypt other documents. And even if they do not know the plaintext, there can be attacks.

Every document has to have some unique identifier that you can use as a nonce. It does not have to be secret or unpredictable.


Why require that public and private key each have length at least the security parameter?

You're probably familiar with the convention of giving input $1^n$ to an algorithm as a way to indicate "this algorithm is allowed to run in polynomial time in $n$." Suppose you are writing about an encryption scheme and want to be very precise about this. You would write:

$\textsf{KeyGen}(1^n) \to (sk,pk)$
$\textsf{Enc}(1^n, pk, m) \to c$
$\textsf{Dec}(1^n, sk, c) \to m$

Now suppose you know (or insist) that $|pk| \ge n$ and $|sk| \ge n$, and that $n$ can be efficiently computed by looking at $pk$, $sk$.
Then $1^n$ can be omitted as input from $\textsf{Enc}$ and $\textsf{Dec}$ without loss of generality: these algorithms have enough information and running-time budget to efficiently reconstruct the string $1^n$ if needed.
In short, this requirement simplifies the notation without sacrificing any rigor.
It would have also worked to insist that $|sk|, |pk|$ are $\Omega(n^c)$, so that any polynomial function of $|sk|$ is also a polynomial function of $n$.
Basically, $|sk|, |pk|$ can't be exponentially smaller than $n$.
(The fact that $\textsf{KeyGen}$ is a polynomial time algorithm already means that $|sk|,|pk|$ can't be exponentially larger than $n$.)


Can any message be decrypted using a given ciphertext and an appropriate key?

Your question is unclear and your mathematical expressions are not equivalent.
Given a key and a potential ciphertext, is there a corresponding plaintext?
In other words, can decryption fail?
For authenticated decryption, the answer is an obvious yes: almost all ciphertexts are invalid. You need to know the secret key to produce a valid ciphertext. Without knowing the key, with very high probability, you can't generate a ciphertext that includes a valid authentication tag.
For unauthenticated decryption, it depends. A stream cipher has no invalid ciphertexts: you just xor the stream with the ciphertext and you get a plaintext. CBC-with-padding has invalid ciphertexts with common padding modes. Also, for CBC, not all bit-strings are valid ciphertexts regardless of padding: only bit-strings that consist of a whole number of blocks have a chance of being valid.
An encryption scheme where an adversary can generate ciphertexts with a probability of validity that is neither 1 nor infinitesimal is problematic because it opens the way to padding oracle attacks.

If all bit-strings are valid ciphertexts, as with stream ciphers, then forging ciphertexts is trivial and won't provide the adversary with any useful information.
More generally, if the set of possible ciphertexts that's independent of the key, the adversary can't learn anything by forging ciphertexts because using a forged ciphertext won't reveal any secret information.
If there's no way to forge a valid ciphertext with non-negligible probability without knowing the key, as with authenticated encryption, then an adversary can't learn anything by forging ciphertexts because the only information the adversary will get is “no, you didn't manage to forge a valid ciphertext”.
In between, there is a very dangerous spot where forging ciphertexts can reveal information. The details vary depending on the exact algorithm, but the general principle is that the adversary captures known ciphertext, tweaks it, sends it to a key holder and observes whether the recipient determines that the ciphertext is valid or not. Repeating this with different tweaks may allow the adversary to decrypt the ciphertext.

Given a potential ciphertext and a plaintext, is there a key that turns this ciphertext into this plaintext?
In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.
A scheme where for any plaintext-ciphertext pair, there exists a matching key, is either a one-time pad or a deviation from it that I think only adds useless complexity.
Given a potential ciphertext, is there a key that makes it valid?
This question is only meaningful for schemes where the space of valid ciphertexts depends on the key.
In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.
Your formalizations

$$\forall C \in \mathcal{C}: |\{M'| \exists K \in \mathcal{K}: Enc_K(M') = C\}| = |\mathcal{M}|$$
My reasoning until now is that this should be equivalent to
$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$

Not quite: if the second proposition is true, that means that every plaintext-ciphertext pair has a corresponding key. But even if this is true, there could be plaintext-ciphertext that are matches by multiple keys. This doesn't happen in realistic message encryption scenarios, but it can happen in some cryptographic schemes where the encryption is only a part of a bigger whole, for example a voting or commitment protocol.

$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$
And if this was false, the opposite must hold:
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \not \exists K \in \mathcal{K}: Enc_K(M)=C$$

i.e.
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \forall K \in \mathcal{K}: Enc_K(M) \ne C$$
Or in plain English, there exists a plaintext-ciphertext pair which no key matches. As we saw above, this is true of most encryption schemes.

Since all messages $M \in \mathcal{M}$ and keys $K \in \mathcal{K}$ can be used to create ciphertexts in $\mathcal{C}$, this would mean that there exist messages $M_1, M_2, M_1 \ne M_2$ which, given a key $K$, are encrypted to $Enc_K(M_1)=Enc_K(M_2)=C$, which defies the required injectivity of $Enc$. Therefore, the proposition must be true. Is it?

I don't see what reasoning led you from the statements above to this last paragraph. You changed from having a fixed plaintext and a fixed ciphertext and varying the key, to having a fixed ciphertext and key and varying the plaintext. Since the decryption function exists, $Enc_K$ (i.e. $M \mapsto Enc_K(M)$) is injective for every $K$. But $K \mapsto Enc_K(M)$ for a given $M$ does not need to be injective (though it usually is unless the message space is limited to very short messages).


Does CBC encryption of a hash provide authenticity?

No, the scheme described in the question does not provide integrity.

A forgery is possible when the message's size is allowed to vary (which is presumably the case since some padding is used), and the adversary can choose some segment of the message with knowledge of the message before that segment. That is, a message $M=M_b||M_c||M_d$ with the beginning $M_b$ of the message known, and chosen $M_c$.

The adversary chooses any $M_x$ she wants, computes $$M_c=M_x||H(M_b||M_x)||\operatorname{Padding}(M_b||M_x||H(M_b||M_x))$$
then let the legitimate sender do his job, which will produce the ciphertext $E_K(M||H(M))$ with $M$ starting in $M_b||M_c$. Notice that by construction, $M_b||M_c$ is block-aligned, and padded so that removal of the padding will leave $M_b||M_x||H(M_b||M_x)$. Now the adversary truncates the ciphertext after that block, and has a forgery that is accepted as the ciphertext for $M_b||M_x$.

Underlying problem: the same key is used for confidentiality and integrity.

Example where this would matter: The message $M=M_b||M_c||M_d$ is a program. $M_b$ is a header imposed by the operating system. The process of producing a program normally produces $M_b||M_d$ where execution starts after $M_b$ thus at the beginning of $M_d$, but the adversary has modified this process to produce $M_b||M_c||M_d$, so that execution starts at $M_c$, thus at $M_x$ which is under full control by the adversary. When executed, $M_x$ examines if $M_d$ is present, if yes executes $M_d$, else performs some nefarious action. The legitimate user produces a program $M$, checks that it performs normally (perhaps using some executable analysis tool that concludes $M_c$ will always jump at $M_d$ and disregard analysis of the rest of $M_c$), then authenticates and enciphers it into a cryptogram. Problem is: it is enough to truncate that cryptogram to produce an acceptable cryptogram which carries $M_b||M_x$, which is happily executed by the operating system but performs some nefarious action.

Note: The stated conditions are sufficient for the attack, but not necessary. For example, when $H=\operatorname{SHA-256}$, an attack can be carried if the adversary can choose some segment $M_c$ of the message with knowledge of the hash and length of the portion of the message before $M_c$.

Nitpick: It is meant PKCS#7 padding, for PKCS#5 padding applies only to 8-byte blocks.


Is there a real purpose to use Twofish, Serpent or Threefish instead of AES?

Serpent is straightforward to implement with side-channel resistance due to the bit-sliced design. Because AES incorporates an S-Box that is most simply implemented as a lookup table, implementations of it tend to be prone to side-channel attacks.

Threefish was designed for the SHA-3 competition, and was intended to be a part of a sort of package of cryptographic primitives, including encryption, hashing, and a MAC. If you wanted a crypto library that didn't require implementing a whole host of different algorithms, Threefish might be a good choice.

One compelling reason to use AES is that many modern CPUs support the AES-NI instruction, which will make encryption with AES almost certainly faster than any other algorithm. A faster algorithm is mostly always better, but unless you are encrypting large amounts of data you will likely never even notice the difference. It might save a couple of cents on your power bill since AES-NI requires fewer CPU cycles.

Of course, as a user, these implementation details may be invisible. And the libraries you mentioned already implement a whole host of different algorithms, so that advantage is negligible in the situation you are concerned with.

Offering multiple options is generally better than a single option (within reason - too many choices is bad). It's a bit like asking why a restaurant has more than one item on the menu. Some people might not care for that one item, for arbitrary reasons.

For a point-by-point overview of why Rijndael was selected as AES instead of Serpent or Twofish, you can investigate these other related questions


CPA vs CCA attack of an encryption scheme

To answer the question, its necessary to invoke the following security definition, which requires that for any encryption scheme $\pi$ to have indistinguishable encryptions under chosen ciphertext attack (viz., for the scheme to be CCA secure), the following condition, which I'll describe, must hold in the so called "CCA distinguishing game" (throughout, I'm using the notation of Katz and Lindell, and the CCA property is more expansively described in their text Intro to Modern Cryptography, 2nd ed. CRC Press):

$\textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1] \leq 1/2 +  \text{negl}(n)$

Here $\textbf{Pr}[E=e]$ denotes the probability that experiment $E$ has outcome $e$, and $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1$ denotes the outcome where the CCA adversary $\mathcal{A}$ wins the CCA distinguising game ($K$ is an encryption key of length $n$ and $\text{negl}(n)$ is a "negligible'' function in $n$). Also, throughout we assume $\mathcal{A}$ is PPT.

(this definition needs to be expanded to allow for encrpytions and decryptions of multiple messages in an analogous vein to the "Left-Right" or LR-Oracle CPA security game described here - https://cseweb.ucsd.edu/~mihir/cse207/w-se.pdf, but the above definition is sufficient for illustration purposes)

So to restate, the CCA security definition requires that the above condition for the scheme $\pi$ must hold in the CCA distinguishing game $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n)$ in order for the scheme to be CCA secure. The rules of the game are that the adversary $\mathcal{A}$  has oracle access to the encryption and decryption functions, and it proceeds by her selecting 2 equal length messages $m_0$ and $m_1$  and submitting them to the encryption oracle, which flips a coin and based on the outcome sets a bit $b$ to either 0 or 1. Based on the value of $b$, the oracle encrypts either $m_0$ or $m_1$ and returns the resulting ciphertext $c$ to $\mathcal{A}$ (which is also called the challenge ciphertext). $\mathcal{A}$ can continue to invoke the encryption and decryption oracle on any messages other than the challenge ciphertext. At the end, $\mathcal{A}$ outputs a bit $b^{\prime}$. The adversary wins the game, which is denoted by the condition $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1$ when $b^{\prime} = b$.

Now consider a CPA secure counter mode encryption scheme such as AES-128-CTR. $\mathcal{A}$ can choose messages $m_0 = 0^{128}$ and $m_1 = 1^{128}$ and submit them to the encryption oracle. Suppose that the oracle sets $b = 0$ and returns the challenge ciphertext $c$. The adversary can then flip the first bit of c resulting in a ciphertext $c^{\prime}$. Since $ c^{\prime} \ne c$, $\mathcal{A}$ can legitimately submit this to the decryption oracle which returns the plaintext $10^{127}$, at which point $\mathcal{A}$ outputs $b^{\prime} = 0$ and can trivially win the game every time thereby violating the CCA security condition $\textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1] \leq 1/2 +  \text{negl}(n)$


PKCS#5 (RFC2898) is a standard for key derivation, not for key storage. Openssl can store an RSA private key either in its own format (default) or in PKCS#8 format. You can convert a key using the openssl pkcs8 command. Securitywise, there is no difference between the two.
You should rather store the password in a configuration file or make the user type it when starting the server software. Otherwise, you would have to recompile and reinstall your whole software, everytime you change the key's password or the key itself. Also, the password can be more easily protected in a single file on the server than in a source code repository.


You need to clearly distinguish between the DualEC DRBG algorithm and the elliptic curves over which it is defined.

The backdoor in DualEC DRBG needs the attacker to choose P and Q such that they know the scalar $k$ for which $P=kQ$. Pretty much any algorithm which fixes both public keys at the same time without going through private keys is fine. For example you could choose the hex expansion of $\sqrt{2}$ and $\sqrt{3}$, or SHA2(x), SHA2(x+1). This is pretty similar to nothing-up-my-sleeves numbers, but the requirements are pretty weak, since the only thing you need to prevent is the attacker knowing $k$.

Backdooring curves is an entirely different matter. You start with the conjecture that NSA knows a certain fraction of weak curves and tries to choose one of them. To avoid this, the curve must be as rigid as possible, i.e. allow as little choice to the designer as possible. This is where "safecurves" fare better than the common NIST curves. So your question about "safecurves" having this property misses the point.

The only coupling between the DualEC DRBG backdoor and the choice of curve I can think of is is choosing the curve parameters so that particular points have a known relation. I don't know if that's possible at all, but I expect this to require a lot of freedom in choosing the curve, more freedom than even the NIST curves have. Preventing this attack is easy: just include the serialization of the curve parameters in the inputs of the hash used to derive the points.


multiple keys via HKDF - whats better, one or two applications of HKDF-extract

Realistically, it probably doesn't matter, if all of your premises are accurate.

If it were me, I'd probably concatenate the inputs, then apply a HKDF to the concatenation to derive two keys -- but honestly, it's unlikely to matter.  This is very unlikely to be the weakest link in your system.  Pick something that's easy to implement and easy to understand, and move on: focus your energy on some other aspect of your system.


Benchmark differences between SHA-512 and bcrypt

SHA-512 is a cryptographic hash while bcrypt is a password hash or PBKDF (password based key derivation function).

SHA-512 has been designed to be fast. You don't want any delays when validating a signature, for instance. There is no reason for generic cryptographic hashes to be slow.

bcrypt on the other hand is a password hash that performs key strengthening on the input. Basically it does this by slowing down the calculation so that attackers will have to spend more resources to find the input by brute forcing or dictionary attacks. The idea is that although the legit users - you in this case - will also be slowed down, they are only slowed down once per password. However the attackers are slowed down for each try. The legit user is of course much more likely to input the right password first.

Furthermore bcrypt also contains a salt as input, which can be used to avert rainbow table attacks.

SHA-512 officially is not a KDF in it's own right, but it is easy to construct one out of a hash function. PBKDF2 for instance is a password hash / password based KDF. It can use any hash function as underlaying primitive. The larger function takes again a salt and a work factor as input / configuration parameters.

However, if you don't need key strengthening - i.e. the input is random enough - then you can also (almost) directly use a hash to derive the symmetric key. This is called a KBKDF (key based key derivation function). The most well known one today is HKDF which is based on HMAC, which in turn is based on a cryptographic hash such as SHA-512.

There is also KDF1 and KDF2 which can simply consist of the input secret followed by a statically counter, which is then hashed. Although it has limitations with regards to the input and output sizes, it is a secure KDF to the current knowledge - assuming that the hash is pseudo random and collision free for small input.

In some scenarios even a direct hash over the input value may suffice (taking the leftmost bits if the hash generates too many). HMAC - as for instance used by TLS - should be preferred though.

From your source (Slashdot):

  For standard containers and other (i.e. non system) partitions, TrueCrypt uses at most 2,000 iterations. What Idrassi did was beef up the transformation process. VeraCrypt uses 327,661 iterations of the PBKDF2-RIPEMD160 algorithm for system partitions, and for standard containers and other partitions it uses 655,331 iterations of RIPEMD160 and 500,000 iterations of SHA-2.

So VeraCrypt - if we may believe the source - uses SHA-512 but only as configuration parameter for PBKDF2, which is a password hash just like bcrypt. So to create a fair test: compare your bcrypt with your current work factor (not present in your question, but important) and PBKDF2 with 500000 iterations. Only then compare the speed differences.


What do numbers in a crypto algorithm stand for? Is there a convention?

In AES-256 and RSA-1024, the numbers refer to the key size. For SHA-256, it refers to the output size. Though there is no hard, fast rule. For example, in the SHA-3 family, there are hash functions with variable length output, SHAKE128 and SHAKE256. The numbers there refer to the security level.

Then again you have secp256k1, the elliptic curve used, among other places, in BitCoin. It's name stands for:

  sec comes from the standard, p means that the curve coordinates are a prime field, 256 means the prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard.

Then you have hash functions like MD5, which is the 5th version of function designed by Ron Rivest. It's output size is 128 bits. There is also the stream cipher RC4, again by Ron Rivest. There is also an RC2, RC5, and RC6, but I'm not sure where RC1 and RC3 are. :)

From the comments:

  Don't forget SHA-512/224, which is SHA-2 with an internal state of 512 bits and 224 output size, while SHA-224 is SHA-2 with an internal state of 256 bits and an output size of 224 :)


How does the secret key in an HMAC prevent modification of the HMAC?

To attack a MAC in general, the attacker needs to find a valid MAC of a message that they do not have the MAC for (or find a message collision that allows a different message to have the same MAC digest). In this case, the attacker would be appending data to the original message, not the MAC itself, and trying to obtain a valid MAC for the new message. In specific, it sounds like you are thinking of length-extension attacks.

In HMAC, the inner hash by itself would be vulnerable to a length-extension attack and the attacker could successfully calculate a valid inner hash digest without access to the key. However, the outer hash isn't vulnerable to a length-extension attack since the client performing the HMAC authentication is only going to input the fixed length string key || inner_hash into it. The attacker only controls variable-length input to the inner hash, not the outer hash.

This is more-or-less addressed by this answer to another question. Relevant excerpt:

  the role of the inner function is to provide collision-resistance (to compress a long message down to a short fingerprint, in a way so that someone who does not know the key cannot find a pair of messages with the same fingerprint), and the role of the outer function is to act as a message authentication code on this fingerprint.


Extending pseudorandom generator by one bit using exclusive-or of previous bits

This allows for an easy distinguishing attack: Let $R\colon\;\{0,1\}^n\to\{0,1\}^m$ denote a pseudo-random generator, that is, if $x$ and $y$ are uniformly distributed random variables in $\{0,1\}^n$ resp. $\{0,1\}^m$, there is no polynomial-time algorithm that distinguishes $R(x)$ from $y$ with non-negligible probability.

Let $R'\colon\;\{0,1\}^n\to\{0,1\}^{m+1}$ denote the generator whose output is extended as specified in the question. An attacker, given a black box $z$ that contains either $R'(x)$ (for $x$ uniformly random in $\{0,1\}^n$) or $y$ (uniformly random in $\{0,1\}^{m+1}$), may then calculate the parity (exclusive or) of $z$'s first $m$ bits and compare it to the last bit of $z$. If they match, the attacker guesses that $z$ is $R'(x)$, else he guesses that $z$ is $y$.

It is fairly obvious that, using this strategy, the attacker always guesses correctly when given $R'(x)$. In the other case, when given $y$, the strategy has a success probability of exactly $\frac12$, since the last bit of a random bit string is also random and may thus with equal probabilities either match (in which case the attacker guesses wrong) or mismatch (in which case the attacker guesses right) the parity.

Therefore, the attacker has a success probability of $$\frac12\cdot1+\frac12\cdot\frac12=\frac34$$
in distinguishing $R'$ from random, which is non-neglibly greater than $\frac12$.

A less direct argument is: If the extension described in the question was possible, one could iterate the construction multiple times without losing the pseudo-randomness property. However, after the first such extension, the parity of the output is always zero, hence all further appended bits are zero. Clearly, a generator whose output always ends in a string of zeroes is not pseudo-random.


In the case you choose $e$ first, you get a private exponent $d$ equivalent to the usual one. Since it is private, no vulnerability can arise. In other words, it is not possible even to distinguish whether you use standard RSA or this variant.
In the case you choose $d$ first, then $e$ may leak a lot of information. For example, in the Boneh-Durfee attack on small $d$, the bound $N^{0.292}$ is actually derived from $e$. If $e$ is larger, it is probably possible attack to attack larger $d$ than in standard RSA.
A simple attack for $d < n^{r/4}$. Consider as usual the exponents equation:
$$
ed = 1 + k(N^r-p^r-q^r+1).
$$
Consider it modulo $N^r+1$:
$$
ed + k(p^r+q^r) \equiv 1 \pmod{N^r+1}.
$$
we can see linear unknowns $d < N^{r/4}$ and $k(p^r+q^r) < N^{3r/4}$ (because $k < d$). By reducing the equation using LLL, we can get an equation with smaller coefficients, which will hold in integers:
$$
b d + ak(p^r + q^r) = a,
$$
where $a,b$ are known. Reducing the equation modulo $a$ we'll recover $d$.
Note that we get the same bound as in the Wiener's attack on standard RSA ($d < N^{1/4})$. Applying the Coppersmith-based Boneh and Durfee method will likely improve the result similarly.


Deterministic symmetric indistinguishable encryption

Yes, the most common / secure deterministic encryption is SIV mode, which stands for synthetical IV mode. Here the IV that is used to randomize each message is replaced by an authentication tag (MAC) over the plaintext message. Of course, this means that identical messages will be distinguishable. But if even a single bit of the messages differ then the entire ciphertext will be indistinguishable as the MAC/IV will of course be different.

SIV or GCM-SIV mode are authenticated or AEAD ciphers. So it is also possible to authenticate additional data together with the data to be encrypted. As most authenticated modes they use counter mode (CTR mode) to provide the confidentiality of the message.

As usual, if the plaintext message differs in size then the ciphertext will differ in size as well.

Deterministic, asymmetric encryption exists as well. Here the random value for indeterministic encryption is usually simply replaced by a secure hash over the message.

Closely related are modes of operation such as Bi-IGE (bi-directional infinite garble extension). If any of the bits of the ciphertext is changed then IGE will make sure that all plaintext bits after that will become affected. Bi-IGE will do the same but in both directions - at the cost of using additional operations of the block cipher, of course.


The protocol that you described computes the XOR function $a\oplus b$ in the presence of semi-honest adversaries. However, this function completely reveals the other party's input given your own input. Thus, no privacy is actually preserved. However, this is due to the definition of the ideal functionality and not a problem with the protocol.


A plain MAC algorithm acts as a deterministic function of the key, message, and (maybe) a nonce. Every time you evaluate the function you get the same results. Mathematical functions do not know whether or not they're being evaluated for the first time.

Replay attack protection has to be employed at the level of the protocol. Software, not math, is necessary for this task. The maintenance of state is a necessary and critical part of the problem. (Including issues like keeping state after losing power, as well as ensuring atomicity and consistency when you have multiple endpoints or system-level concurrency.)

The best method to prevent replay attacks is to include a sequence number in the messages you're trying to create a tag for. (You might not need to explicitly send this over the network, though. That might be redundant.)

Prepend a fixed-width counter to all messages. Maintain a value n shared between the client and server. Every time a message is received, check that the message's sequence number is the value (n) which you expected. Look for n == 0 on the first message, n == 1 on the second message, and so on. If you receive a message with the correct sequence number with a valid tag then increment n. If you receive a message with an invalid tag or with a sequence value that you've already seen, then reject that message.

This method additionally protects against a man-in-the-middle's attempts to reorder or block messages. You don't want for an attacker to be able to change a message sequence ["On", "Off", "On"] to ["On", "On", "Off"]. Or to just ["Off"].

To illustrate how a sequence number solves that problem, imagine that the sender instead transmits the sequence ["1:On", "2:Off", "3:On"]. It should be obvious how repeated or reordered messages could be detected with only O(1) memory. Attempts to selectively block messages can (partly) be detected by looking for skipped sequence numbers.

(Although some protocols replace server-side checks for seq == n with seq >= n. Car key fobs, for example, might do this, since the user might be out of signal range when they press a button. If this method is employed, then it is important that all commands sent in a protocol are idempotent and that the user can tell what state the system is in. You can have "Lock" and "Unlock" commands, but not a "Toggle lock" command. For car key fob systems, a car should beep or flash its lights when locked.)

Attempts to block the last message(s) sent in a session can't be detected by looking for skipped sequence numbers, obviously. It's necessary to add a "End transmission" message (or message flag), since you can't distinguish between an incomplete session and a maliciously cut-off transmission otherwise.

A worse method to prevent replay attacks is to require the client to attach a random nonce to every MACed message. But then the server has to make more effort to track which nonces have been used. If the server sees a nonce it has already seen before, then it rejects the (replayed) message.

This kind of system lets you add idempotency to a system which wouldn't otherwise have it. This same method is used in web applications to prevent accidental doubly-posted messages. If a user has network issues, accidentally hits the refresh button, or hits the back button and resubmits a form, then the server will notice the reused nonce and ignore the re-submission.

This method does not detect reordered or selectively blocked messages. This is okay for the other accidental-double-post-detection system because blocked messages are not considered a realistic threat. Out of order posts are accepted as a "feature": The user can open two tabs, compose two messages separately, and submit the posts in whatever order they complete them in.

You could use it in other scenarios with out-of-order protocols, but it's tricky to get right. So it's not worth the risk or the extra investment in developer time.

An additional problem is that the "spent nonce" database can grow indefinitely large. A modified system could incorporate a timestamp into the nonce, allowing old records to be purged if a timestamp check is added.

You basically ONLY would opt to use this method instead of using sequence numbers if you have a powerful stateful server and low-end stateless clients. (Clients without non-volatile memory.)

Those (stateless) clients need a TRNG, because long random numbers are used to avoid accidentally reusing nonces. (Leading to false positive replay detection.)


Secure Secret Sharing to a Distributed Key

From what I understand, you want to share a secret to B in such a way that every single member of B is required to reconstruct the secret. In that case just use a threshold secret sharing scheme where the threshold is the number of players in B. This ensures that no subset of players in B can reconstruct the secret.
I’m not convinced you need encryption here (as secret sharing is already information-theoretically secure. But if you do, then encrypting under public key and sharing to B such that the threshold is equal to the number of shares should suffice.


Yes.

There are several different kinds of twist attacks. Curve25519 is safe against all the ones SafeCurves looks at. Specifically, the cost of a combined attack is $2^{124.3}$, which is considered safe.


What is the maximum key size for a 128 bit AES?

Despite similarities, it is really important to understand that passwords and cryptographic keys should not be carelessly conflated.  Some important contrasts:

Passwords are normally selected by human beings according to their whims.  Cryptographic keys are meant to be randomly generated by an algorithm.
Passwords are usually intended to be memorized by human beings.  A strong cryptographic key cannot generally be memorized—they're too random and complex—and thus generally stored in a secure device.  In the parlance of multi-factor authentication, passwords are "something you know" while cryptographic keys are "something you have."
Passwords have to be text that human beings can manually input into their devices.  Cryptographic keys are fundamentally binary data (despite being sometimes serialized and deserialized as text) and are generally not meant to input manually.

I say all this because your question really comes down to a lack of understanding of these differences.  AES doesn't use passwords, it uses keys.  AES-128 keys are fixed-length binary data; they don't really have "characters" because they're not text.  As others have said, the maximum key size for AES-128 is the same as the minimum and only key size: 128 bits.

Many programs that use AES-128, however, do present a password-based user interface, and maybe you've encountered one of these.  But what these programs are doing, behind the scenes, is internally transforming the user's password into a proper cryptographic key.  In those programs your password can generally be any sensible length you like, but generally then the password is the weakest link—an attacker who can guess your password doesn't need to crack the AES encryption.  So to achieve the full security strength of AES-128 in such a program you would need to choose an extremely strong password—something most users won't know how to do.  In this case I recommend looking into Diceware and their FAQ, which has some useful advice on how complex of a password to choose.


Retrieve value of private key after encryption with the public key

If an appropriate padding mechanism is used then you cannot directly encrypt the private key with the public key as the input size would be too large. If hybrid encryption is used (RSA + AES) then the answer is no.

You could possibly raise (modulo $n$) the private exponent to the power of the public exponent. So then you would need to retrieve $d$ from $d ^ e \mod n$. I don't see how you could retrieve $d$ from that, even if you take into account how $d$ and $n$ are calculated.

Note that you could not do this if you would require the CRT parameters instead of the private exponent $d$.


Role of AND operation in FHE, MPC and ZK

In general, AND gates are no big deal. In practice however, many zero-knowledge systems are based on rank-1-constraint systems (R1CS, often "arithmetic circuits" in folklore), and the concern that LowMC tries to address is linked to this practicality.  Note that I'm talking from the perspective of ZK, although the principles probably carry over to FHE and MPC.
In R1CS, you declare constraints between inputs and outputs, and these constraints are of arithmetic form. For instance, you would write "(input[0] + 1)*secret[0] = output[0]".  In most R1CS systems (read: all that I know of), it is the multiplication gates that weigh heavy in the prove/verify functions, and the additions mostly come for free.
Now, most encryption/decryption functions are defined in terms of bitwise operations, not in terms of + and *.
To prove that you know the decryption of a certain value and its associated key, you would thus need to convert all those bitwise operators into arithmetic operations.  You can imagine these equations become quite large. The main operations in this context are, as you correctly identified, AND, OR and XOR.  Depending on the convention you use, you will encode True as 1 and False as 0, or vice versa.  It is then relatively easy to see that x AND y becomes $x * y$ and x XOR y becomes $x + y - 2 * x * y$, and x OR y becomes $x + y - x * y$.
Now, there are quite some optimizations that you can carry out here. For example, if you would use a stream cipher to show decryption, then you have to XOR your cipher stream $s[..]$ with the cipher text $c[..]$.  The former is a result of your circuit, but often the latter is a public value.  If this is the case, you can make that specific XOR more efficient by doing something like
let xor = if c[i] == 0 {
    s[i]
} else {
    1 - s[i]
};

which requires no multiplications for this specific XOR.
A related optimization exists for OR: if you take the convention False as 0, True as anything else, then x OR y just becomes $x + y$, as long as your field is large enough.
TL;DR: AND becomes multiplication, multiplication costs processing time.  XOR can sometimes be optimized out a bit.  By the way, if you're interested in low-multiplier-count symmetric crypto, have a look at Poseidon too!


Layered encryption in mixnets with post-quantum cryptography

Might I suggest using traditional hybrid cryptography to cut down on the ciphertext growth size?  This is the straight-forward approach where you don't directly encrypt the message with the public key; instead, you pick a random symmetric (e.g. AES) key, encrypt the symmetric with the public key, and then AES encrypt the message with the symmetric key.

That way, the message expansion is the size of the encrypted symmetric key (which is fixed, independent of message size), and the message expansion caused by the AES encryption (which is tiny, perhaps 16 bytes).

If we estimate that an encrypted symmetric key is about 1kbyte (roughly true for NTRU), then iterating this 10 times with 10 public keys will cause a total expansion of about 10kbytes; certainly tolerable.

And, this can be done postquantum, by using a postquantum symmetric encryption (256 bit keys), and a postquantum public key encryption algorithm (that is, I haven't solved that problem for you...)


RSA: Fermat-Euler Theorem - coprimality of message and modulus

It's a consequence of the Chinese Remainder Theorem (look it up, if you don't know it) if you want to be more precise and understand it algebraically. If $n=pq$ and $de \equiv 1\;(\textrm{mod }\phi(n))$, then we also have that

$$de \equiv 1\;(\textrm{mod }p-1),\;\;de \equiv 1\;(\textrm{mod }q-1),$$

since $\phi(n)=(p-1)(q-1)$. It follows that for any integer $a$,

$$a^{ed} \equiv a\;(\textrm{mod }p),\;\;a^{ed} \equiv a\;(\textrm{mod }q),$$

which follows from Fermat's Little Theorem. Note that this also holds if $a\equiv 0$ modulo $p$ or $q$, since both sides of the equation becomes zero. Now the Chinese Remainder Theorem in the case when $p\mid a$, will translate the equation

$$a^{ed} \equiv a\;(\textrm{mod }n)$$

into the two equations

$$0^{ed} \equiv 0\;(\textrm{mod }p),\;\;\; a^{ed} \equiv a\;(\textrm{mod }q)$$

Since we know that these equations are true by Fermat's Little Theorem as well as the trivial case when the element is zero, the Chinese Remainder Theorem will say that since the equation holds in these two cases, it also holds in the original (since more technically it's an isomorphism between the original ring and the product ring). Therefore, RSA's encryption/decryption algorithm also works in these degenerate cases.

In other words, it's not purely a consequence of Fermat's Little Theorem, but you can use it in the subcases that the CRT translation will give you.


There are several questions hidden in your question.

You'll have to distinguish between the polynomial ring $\mathbb Z_2[X]$, and the factor field $GF(2^8) = \mathbb Z_2[X]/F$ (where $F$ is any irreductible polynomial of degree 8).

In $\mathbb Z_2[X]$, the only polynomial which is a factor of all others is the trivial polynomial $1$. (In general, in a (unitary) ring the set of elements with this property are called units, and this ring has just the trivial unit one.)

In $GF(2^8)$ (like in any field), every non-zero element is a unit and thus a factor of every other element, but we normally don't call them "polynomials".

But the original question actually asks something else:

  What polynomial when factored over the field $GF (2^8)$ based on the irreducible polynomial that is used in Rijndael will factor into all the polynomials in the field?

The expression "factors into" can be understood as "is a multiple of" ... and "when factored over $GF(2^8)$" could be understood as "when seen as a polynomial with coefficients in $GF(2^8)$ (i.e. an element of $GF(2^8)[X]$, and then factored (into its prime divisors)". But then the expression "into all the polynomials in the field" makes no sense, as a field element is either $0$ (which is not a factor other than for itself) or a unit (which is a factor for everything), and you likely don't want $0$ as the result.

Quite likely the original question was something else, but I have no idea, what.


Is there any way to hire someone to generate a sufficiently small hash of a value + nonce, without knowing value nor nonce?

Here's the obvious answer that avoids multiparty computation (which tends to be expensive):

Given your $X$, select a random value $N1$, which would be 256 bytes long for keccak_256 and 48 bytes long for SHA-256, and compute the intermediate hash state of $Hash(X || N1)$.

If your hash function is SHA-256, this is an intermediate hash of 64 bytes (1 SHA-256 block), which requires a single hash compression function evaluation (yielding a 256 bit intermediate state)
If your hash function is keccak_256, this is an intermediate hash of 272 bytes (2 Keccak-256 blocks), which requires two permutation evaluations (yielding a 1600 bit intermediate state).  We use two permutations for Keccak because the permutation function is invertible, and so if we used only a single block, the hireling could invert the permutation and recover $X$ and $N1$

We give the intermediate hash state to your hireling, who searches fir an N2 such that Hash(X || N1|| N2) is a small value; he can do this because both hash functions can be expressed as functions of the intermediate state and the rest of the message.
Once he has found such an N2, he sends it back to you. This gives you the value $nonce = N1 || N2$ you're looking for.

This solves the issue; the hireling cannot convert the hash state back into $X$, and since he does not know the value of $N1$, he doesn't know the full value of none.


Hash collisions in sha512 hash of secp256k1 public keys

The output of the SHA512 is 512-bit, so there are at most $2^{512}$ different outputs.

For random inputs, the expected hash collision with 50% probability is $\sqrt(2^{512}) = 2^{256}$ by Birthday Paradox ($\sqrt(n)$).

The public keys of secp256k1 have 64-byte = 512-bit. To calculate SHA512  hash the input values are padded so that the input size is always multiple of 1024. After $2^{256}$ SHA512 hash of the public keys, we expect to find collisions with 50% probability.

SHA512: For finding a collision with birthday attack for SHA512 is almost impossible. You will need immense time, storage, and power for $2^{256}$ input values.
SHA256: For finding a collision with birthday attack for SHA256 is almost the same as breaking AES-128 by brute force, need for $2^{128}$ hash values. If we assume that the BitCoin miners top peak performance is $\approx 2^{91}$ hashes in a year, you will need $2^{37}$ years with the same computing platform and power consumption.


Reduction of Integer factorization to Discrete logarithm problem

Here is a quick summary:

First direction, from discrete logs modulo $N$ to factoring. Assume that there is a fixed basis $g$ for the method that computes logs. Choose a random $x$ modulo $2N$ and compute $y=g^x\pmod{N}$, then ask for the logarithm of $y$. Let $x'$ denotes the answer to the discrete log problem. If $x=x'$ restart, else $x'-x$ is a multiple of the order of $g$ modulo $N$. Once this is known, apply the randomized method described as answer to Is it possible to determine the group order by knowing the "public" and "private" key exponents in an RSA group? and factor $N$.
Second direction. If the factorization of $N$ is known, then $y=g^x\pmod{N}$ implies $y=g^x\pmod{p}$ for each prime factor $p$ of $N$. As a consequence, computing discrete logarithms modulo $p$ gives $x$ modulo the order of $g$ modulo $p$ (this is $p-1$ is $g$ is a multiplicative generator modulo $p$). Assuming for simplicity that $N$ is squarefree, it now suffices to paste together all the partial solution using the chinese remainder theorem and you get the logarithm modulo $N$. Note if the chinese remainder theorem does not give a solution because the logarithms modulo the various orders are incompatible, it means that the original problem does not have a solution.

On squarefreeness. Without the squarefree assumption on $N$, you need to compute logarithms modulo powers of $p$. This is not harder than computing logarithms modulo $p$ but requires some technicalities.


How is a generator found for a group, both in case of DH & ECDH?

In the case of Diffie-Hellman Key Exchange (DHKE or DH) in the multiplicative group $\mathbb Z_p^*$, the recommendable practice is to pick a prime $p$ and generator $g$ from RFC 3526, which gives these parameters for bit size $k$ of $p$ in $\{1536,2048,3072,4096,6144,8192\}$. These $(p,g)$ obey the criterion below:

$p$ is a prime such that $q=(p-1)/2$ is prime, that is $p$ a safe prime. Since the order of an element $g$ of the group is a divisor of $p-1$, that order can only be $1$, $2$, $q$, or $2\,q$, which simplifies finding¹/checking the order of a candidate $g$:

If $g\bmod p=1$, then the order of $g$ is $1$.
If $g\bmod p=p-1$, then the order of $g$ is $2$.
If $g^q\bmod p=1$, then the order of $g$ is $q$, half the group order. Such $g$ are used in RFC 3526.
Otherwise (that is if $g^q\bmod p=p-1$ ), the order of $g$ is $2\,q$, that is $g$ is a generator of the whole group. There is no good reason to prefer such $g$, and they have the drawback that given $a=g^x\bmod p$, it's trivial to tell if $x$ is even or odd by checking if $a^q\bmod p$ is $1$ or not.

It is picked $g=2$, because

It's proven that any choice of $g$ of a given order does not make the discrete logarithm problem much easier.
That's the smallest positive $g$ usable, thus the natural choice.
It allows a sizable speedup in the modular exponentiation: most of the modular multiplications in square-and-multiply binary exponentiation can be avoided.

The low-order 64 bits of $p$ are set. This can be used to simplify Montgomery modular multiplication. Combined with (1) and $p>7$, that implies $p\bmod24=23$, and the order of $g=2$ is $q$. Notably, that goes against a check in OpenSSL.

The high-order 66 bits of $p$ are set, making $p$ near a power of two. This can be used to simplify modular reduction modulo $p$, by making it easy to find a most likely correct new digit/limb for the quotient in Euclidean division in base $2^b$ for $b\le32$ (and somewhat higher).

The next high-order bit of $p$ is clear, making $p$ not so close to a power of two that the Special Number Field Sieve applies.

The other bits make $p$ a nothing-up-my-sleeves number: for a $k$-bit modulus, it is used $p=2^k-2^{k-64}-1+2^{64}\,\left\lfloor2^{k-130}\pi+i\right\rfloor$ with the smallest $i$ such that $p\bmod3=2$ [which for a given $k$ determines $i\bmod 3$ ], $p$ is prime, $q=(p-1)/2$ is prime, and $2^q\bmod p=1$.

Of course, $k$ is chosen as a compromise between speed and security of DH. $k=2048$ is considered a minimum today. Message size grows as $k$. Execution time grows as $k^3$ in naive implementations of DH using textbook multiplication and secrets the size of $p$. While performance can be considerably improved by using better multiplication algorithms, and smaller secrets, DH in $\mathbb Z_p$ with secure-enough parameters is outperformed by a competent implementation of ECDH, see next section.
Note: An alternative practice, with no direct benefic in DH but common in signature because it allows a drastic reduction in signature size, is to use $(p,g)$ making the powers of $g$ modulo $p$ a Schnorr Group of order a prime $q$ of size much smaller than $p$, yet enough for security. We first choose prime $q$ with about twice as many bits as the desired security level, and $p=2\,q\,r+1$ for (even) $r$ making $p$ a prime of suitable size (e.g. 256-bit $q$, 3072-bit $p$). We pick some $h$ (e.g. $h=2$), compute $g\gets h^r\bmod p$, and check that does not happen to be $1$.

In the case of ECDH, that is DH in the group of points of an Elliptic Curve over some finite field $\mathbb F_{p^d}$ for prime $p$, the recommendable practice is to pick a standard curve and generator from some reference. A common one is SEC2, which includes the NIST curves of FIPS 186-4. Another is Curve25519. Yet another is RFC 5639, which gives the Brainpool curves.
Restricting to $d=1$ (that is curves on $\mathbb F_p$ for some large prime $p$, though not as large as needed for security of DH in the group $\mathbb Z_p^*$ ), practice is to use curves of prime order $q$, such that any point except the neutral $\infty$ has order $q$. It's proven that the choice of generator (aka base point) does not make the discrete logarithm problem much easier. How the generator is actually chosen varies. Sometime it's secret, lost, rediscovered, see this.
When we can't or didn't chose the curve to be of prime order, practice it to use a curve of known order of the form $h\,q$ where $q$ is prime and $h$ is as small as possible. This makes it easy to check the order of a point, and ascertain it's a multiple of $q$ (or exactly $q$, which is typical).
How a curve's order is found (aka point counting) is quite involved. That's one good reason why we have standard curves.

¹ A general method to find the order $i$ of an arbitrary $g$ in $\mathbb Z_p^*$ with $p$ prime is to test $i$ in increasing order among the divisors of $p-1$ (the order of such $\mathbb Z_p^*$ ), and stop at the first $i$ with $g^i\bmod p=1$. This generalizes to any group, and is applicable when we know the factorization of the group order.


Is there a way to turn a PGP key into its semi-prime counterpart?

The OpenPGP message you posted is a signature, not a key. As it was issued by GnuPG, I assume you're using GnuPG anyway. To export your public key, run gpg --armor --export [key-id]. --armor wraps the output in a base64-like encoding (like the signature block you provided in your question), otherwise you'll get binary output. If you don't know your key-id, you can look it up through gpg --list-keys, possibly followed by a search pattern on a user ID you added -- for example your mail address.

The public key also contains user IDs, certifications, subkeys, ... and can be rather lengthy. The beginning of my own public key export:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1

mQQNBFDaK/sBIADm2gjnw7aPoNIoCy7gj85btwZU+zGkvtGonznlLrXELdU6zR3u
VHNCn9vAl6OoU32r+suFvGdX+7MjiPbGKwJFOvICpAVh6bV55+hdqJbS02cpPmJH
1BrrUAmm6ZVEybGd+II1pTI6Mt/SAI1E/59VIBdC/1AwsxQtCTFeyaLqTdyd1FhQ
chkjcvdRHLb4cEqldAGqBL7SbiSNOP3p+vX8iwRN6PQ/erAGseawHnunuNIna+tA
t4te/MkI2uxT0KjsfF/NWHCB2aXt++egP8jGSaHRsVOlfHRVA3hHcUDlnW9DZRvG
QabHFcZvfcXAlNIRYKUzDIHEwpavAmHeGNhc2GNmDcDRF56741grVLNQT58vxK5o
dBLlC8ANckvE5ymdIKVPm+t5q10kFOAATcnmDV0oBt+15vzI3f+88yCoY904UWdY
[...]

If you want to dump the RSA primes, use the pgpdump tool (not included with GnuPG and has to be installed separately, but should be available readily packaged for all relevant distributions). To print the primes, you can directly pipe GnuPG's --export output into pgpdump (consider storing the output to a file or piping intoless`, as the output can get really long):

gpg --export[key-id] | pgpdump -i

To understand the output of pgpdump (and the structure of OpenPGP messages), read RFC 4880.


The message bit should be just that, a single bit, and $v$ should be a single integer modulo $q$. I am not sure how you’re getting $v$ to be a vector. Note that $b^t x$ is an inner product (mod $q$), so it is also a single integer mod $q$.


Well, as SEJPM and Mok-Kong Shen pointed out, it's described in FIPS 197, but let's explain it in details:

Here's the Key Expansion algorithm pseudo-code from FIPS 197:

Where

$Nk$ is the number of $32$-bit words that composed the key
$Nr$ is the number of rounds
$Nb$ is the number of columns in the state block (which is always $4$).
$word$ is a $32$-bit word (can be seen as an array of $4$ bytes).
$w$ denotes a $4$-byte word array where the number of elements is equal to $Nr + 1$ (because AES uses a different key at each round)

For a $256$-bit key, we have $Nk = 8$ and $Nr = 14$ according to FIPS 197.

When you are asking

  Should I expand it how usual but instead beginning in the second
  round beginning in the third round?

Don't you mean the fourth round? Let me explain.

As you can see with the above pseudo-code, the first loop just copy the secret key at the beginning of the array $w$. Then, we get into the second loop to compute rounds key which are derived from the given one.

So for a $128$-bit key, you start to derive round keys as soon as $i=4$ but only when $i=8$ for a $256$-bit key (because the key is longer).

Also, as mentionned in FIPS 197, note that the routine isn't the same regarding to the key length (which is $Nk$) because there are arithmetic conditions between $i$ and $Nk$ to get into different branches of the algorithm.
For example, only $256$-bit keys will satisfy the condition else if (Nk  >6 and i mod Nk = 4).

Hope it's more clear now.


Why does 3DES need private key to decrypt?

Yes, 3DES is a symmetric cipher and you use a secret key for both encryption and decryption with it. However, that is not the same thing as the keys used in RSA or other public key cryptography – you cannot (and should not) use either of them for 3DES.

Since you are using S/MIME, you are actually using public key encryption. Any reference to 3DES is about the symmetric part of a hybric cryptosystem. That is, you use the public key encrypt/generate a secret key that encrypts the actual message. So you need the private key to decrypt it.


DES 48-bit round keys replaced with 48-bit block keys

Let the DES-variant's key $k=sk_0|sk_1|...|sk_{15}$, where each $sk_i$ denotes a 48-bit subkey and "|" concatenation. Due to the Feistel nature of DES, a sufficient condition for $sk_i$ is that for $i \in [0,15]$, subkeys $sk_i = sk_{15-i}$. They will work as each others' complements and encryption will become identical to decryption. There will be $2^{48*8}=2^{384}$ such sets, or keys $k$. Relatively speaking this is still far less than the number of weak keys in original DES, due to the large number of freely selected key bits.
The semi-weak key definition makes sense only in the original DES, where the round keys depend on the secret key: both the definition of weak and semi-weak keys aim at producing identical round keys for encryption and decryption; the weak keys are sufficient to accomplish this by themselves, as semi-weak keys come in sets.

P.S. I have hard time imagining any other purpose for this kind of cryptosystem than purely educational


Do I still need SHA256 if I already had a AES 256 key that is 44 characters long?

You don't say how SHA-256 is used in the PHP system, so there's really no way to know how "secure" it is.  At a guess, SHA-256 is being used as a key derivation function (KDF) on the input key material, so whether it provides any additional security will depend on the source of the input key material.  Of course, SHA-256 isn't great as a KDF - one would normally use something like HKDF (e.g. as documented in RFC 5869).

  a system that generates 256-bit long key

How this is generated is going to materially impact how secure your scheme is.

If it is generated by a cryptographically-strong random number generator (CSPRNG), then using a KDF on it is generally considered to be unnecessary.

If it is generated by a Diffie-Hellman key exchange, then it's important to use a KDF on the raw DH output.

If it's generated any other way, your whole scheme is likely to be insecure, whether or not SHA-256 is used.

But this is all based on a guess of how the various algorithms are used.

To get a better answer, you really need to tell us what the requirements are for your licensing system, what the thread model is (note that if this is a mobile app, they are considered to be run in an untrusted environment that an attacker has full control over, and various obfuscation and white-box crypto techniques are normally used too) and the details of the scheme.

  I am still new to the area of cryptography

Cryptography is one of the areas where it's always better to "buy" rather than "build" - don't roll your own.


RSA PKCS#1 v.15 Signature verification computational complexity explanation?

Apparently the _sign is much more computationally complex than the _verify.

For RSA, this is typically the case.

For the signature verification operation, the computationally expensive part is the computation of $M^e \bmod N$ (for some $M$); where $e$ is a public value, which is typically fairly small (65537 is the most common value).

For the signature genearation operation, the computationally expensive part is the computation of $M^d \bmod N$ (for some $M$); where $d$ is a private value that's close to the size of $N$.

The computation of $M^x \bmod N$ takes time roughly proportional to the log of $x$; and so we're talking about of log2 of 16 (for signature verification) versus a log2 of 2048 (for signature generation), and so by this simple-minded analysis, we'd expect that verification be about a 100 times faster.

Now, during signature generation, an implementation can use the "Chinese Remainder Theorem" to cut this time by maybe a factor of 4 (this optimization cannot be used during the signature verification, as it requires knowledge of the factorization of $N$); this would reduce the expected ratio to about 25, which is roughly what you see.

For RSA, $d$ must be large (small values of $d$ are known to cause weaknesses); on the other hand, we don't mind if the attacker can guess $e$ (we'll publish it in the public key, hence he doesn't have to guess), and so there is no drawback in making is small.  Actually, an $e=3$ can actually be secure; however some people don't like it as it can be fragile if you don't get the padding right.


Security of a cipher with some imperfection in round function

If an all-zeroes block creates all-zeroes for every key that's definitely an issue. It's not necessarily likely to be serious, but could leak data about the plaintext and does not qualify as a secure block cipher.
However, the solution is fairly simple... simply XOR one of k1 or k2 with a constant value to turn your all-zero block into something that'll produce a better result. Personally I'd XOR with the current round number in each round because that'll prevent your algorithm from accidentally ending up with another input that produces the same issue.


HMAC Key Sizes for MD5, SHA1, SHA224|256|384|512

I'm trying to find an authoritative source for the HMAC Key sizes for each of the hashing algorithms below

Good question.  It turns out that TLS always uses the same length of key as the hash function length (so HMAC-SHA384 would use a 48 byte key).

However, I also can't find any RFC which actually states this.  Neither RFC5246 (which acknowledges HMAC-SHA384 and HMAC-SHA512 as potential MAC algorithms, but doesn't define any ciphersuites that use them) nor RFC5289 (the earliest RFC I can find which actually does define a ciphersuite with HMAC-SHA384 as a MAC algorithm) actually address it.

I suspect that's just something that fell through the cracks; RFC5246 only defined it for those MACs which were actually defined ciphersuites at that time; the author of RFC5289 apparently overlooked the issue.


Unlike some crypto tasks like encryption+authentication combining compression+encryption have nothing in common/non synergies, so combining them into one algorithm offers no advantages.

In practice this means you first compress your data, and then encrypt it, because encrypted data is uncompressable. That way you cleanly separated the separate concerns, and you can vary them independently.

A good point to combine them is at the protocol/fileformat level. For example TLS supports compression and encryption, as do most archive formats(zip, rar, 7z,...).

But compression can hurt security: Typical encryption is designed to hide everything about the data, except its length. Compression depends on the data itself and affects the length of the data. That means that it can leak information about the data through the length bypassing the encryption. This is particularly severe if you compress data chosen by the attacker and secret data within the same context. This lead to the CRIME attack against TLS compression.


You really only need to do step 1. If each party has shares of x and y (say $x_i,y_i$) then $z_i=x_i+y_i$ is a valid sharing of $z=x+y$.

What you are doing is used to multiply shares. Multiply, share the shares, reconstruct. In that case everything you said is correct. The reason this is needed in multiplication of shares and not addition can be seen by looking at the polynomials that were used for sharing. In the case of additions, the coefficients add pairwise, thus the individual coefficients of the resulting polynomial which shares $z$ has independent coefficients and has the same degree. In the case of multiplication, the degree goes from $t$ to $2t$ and the coefficients are not not pairwise independent.


Why must we hash lot of times in rainbow tables?

The comments attempt to answer by looking at the details of how rainbow tables work; however if you examine the problem they're attempting to solve, you can see that they would require a large number of hash computations, no matter how they operate internally.

Now, rainbow tables are a generic way to find preimages to an arbitrary function; that is, given a function:

$$Y = H(X)$$

where $H$ is a deterministic function.  Then, given a value $Y$, it tries to find an $X$ that satisfies the above equation.  It does this by evaluating $H(X_i)$ when building the rainbow table, and encoding all those into the table.  Then, given a specific $Y$, we search through the table to see if there was an $X_i$ that we evaluated that happened to hash to $Y$.

Here's the rub; the rainbow table method is generic; it does not attempt to examine the internals of $H$.  So, the obvious question is: if we give it a hash value $Y$ where we did not evaluate the corresponding $H(X)$ during the build phase, how can it work?  Well, obviously it can't.  That means that, if we build a rainbow table that covers a dictionary of a trillion possible passphrases, that means that the we need to evaluate $H$ for those trillion possible passphrases.  That is, building a rainbow table is going to be expensive, and unless we can rely on some cryptographical weaknesses of $H$ or some other special property, there isn't anything we can do about it.

So, since rainbow tables do not decrease the amount of work, does this mean that they are useless?  No, it doesn't.  For one, we need to build the table once.  Yes, that is expensive, but looking up an entry in a rainbow table is cheap. Once we've evaluated those trillion hashes, we can later reuse that rainbow table many times to attack many hashes (and we don't need to know those values when building the rainbow table).

In addition, the other obvious question is "if that's what rainbow tables do, why don't we just build a large table of $(X_i, H(X_i))$ pairs, when we get a hash, we can then just look it up.  Yes, that would work; however if we expressed that table in the obvious way, it'd be huge -- disk space is getting cheap, but not that cheap.  Rainbow tables are essentially a clever way of making up such a table, but in a way that makes the table much smaller (that is, take up less disk space) than what you'd expect.


RSA finding the inverse of the public exponent

The answer comes from Euler's Theorem. Note: math below is done modulo $N$ unless otherwise specified and draws heavily from group theory.

That theorem says that any element of a group (say $m$) raised to the order of the group, in this case $\phi(N)$ is congruent to $1$ (i.e.,  $m^{\phi(N)}\equiv 1\bmod{N}$). Furthermore, this holds for multiples of $\phi(N)$ (i.e., $c\cdot\phi(N)$ where c is an integer).

In the case of RSA, you find $e,d$ such that $ed\equiv 1\bmod{\phi(N)}$. Note then that $ed=c\cdot\phi(N)+1$, where $c$ is some integer.

Thus $c^{d}=m^{ed}=m^{c\cdot\phi(N) + 1}=m^{c\cdot\phi(N)}\cdot m^1$. From the Euler's Theorem, $m^{c\cdot\phi(N)}=1$, so that term goes away and you are left with the original message.


Contruct a protocol to determine if three secret keys are different, without revealing any of them?

You should easily be able to do this using a generic multi-party computation framework. For more info on what frameworks are available see Practical implementations of Multiparty computations.

From what I have seen, VIFF is pretty easy to get up and running to experiment with.


Scrypt as a KDF with one-time high-entropy input

If you have a high entropy input, then scrypt isn't a good choice. It's purpose is to compensate for the low entropy of a password. Don't ask the user for memory/cpu factors, you don't need them if the input is high entropy. You don't need a salt either.

Simply use an input of at least 16 bytes from a secure random number generator.

I recommend using one of the following:

PBKDF2 with a single iteration. This is actually what scrypt uses internally to consume the input and produce the output.
HKDF - It's a very nice and simple design, standardized by NIST, has a RFC. Implementing it on top of HMAC-SHA-2 is trivial. It's my first choice as a KDF if the input has high entropy.


Comparison on Gentry's Fully homomorphic Encryption?

Yes, it is possible. I remember at least of the article Low Depth Circuits for Efficient Homomorphic Sorting in which comparisons are discussed.

Encrypt you $\ell$-bit integers $a$ and $b$ bit by bit generating to $\ell$-dimensional vectors $(a_1, ..., a_\ell)$ and ($b_1, ..., b_\ell)$.

Than, to test homomorphically whether $a \le b$, do

$$C_{LT} =  \sum_{k=1}^{\ell} (f(a_k, b_k) \cdot \prod_{k<t<\ell}g(a_t, b_t))  \mod 2$$

Where $f(a_k, b_k) = b_k \cdot (a_k + 1) \mod 2$ is "less than" for bits and $g(a_t, b_t) = b_t + a_t + 1 \mod 2$ is a "equal to" for bits.

Notice that the product from $k$ to $\ell$ can be performed in depth $\log(\ell - k)$ instead of in depth $\ell - k$.

You will probably find other results about homomorphically comparison by searching for articles that cite the one I put here.


How can uniformity of hash functions (e.g. SHA-256) be proved?

Uniformity is a tricky one. SHA-256 (as well as SHA-3 for that matter) follows a heuristic approach. That is, the design is not based on a hardness assumption (for example, the factoring or discrete-log assumption) but on criteria that have only been verified empirically. As such, also the study of uniformity is an empirical study. The development of SHA-1/SHA-2 was not a public process (it was developed by the NSA and NIST) and no rationale as to design choices were given. What you usually do in this case is to run statistical tests and see if any of them indicate any weaknesses. For example, a simple test would check that every single output bit is set to 1 with probability 0.5. A suite of statistical tests that, I believe, was used in the evaluation of AES was published by NIST (http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html).

If you want to go into more detail I would have a look at the SHA-3 competetion. Here, every candidate had to provide an elaborate and convincing case for why this candidate is a good pseudorandom function. You can find the documents for Keccak (the new SHA-3) on http://keccak.noekeon.org/files.html. The Keccak reference has a whole section on the analysis of Keccak as a pseudorandom function.


A problem exists with the security proof in the secure AND example in the malicious model

If I understand correctly, you consider an adversary $\mathcal A$ corrupting $P_2$ in the real world, and which ignores $P_2$'s input $y$ and just outputs $0$ regardless of the value $x$ sent by $P_1$, is that right? And you claim that this adversary is not simulatable.

Well, of course this adversary is simulatable: the simulator sends whatever to the trusted party, receives whatever, and outputs $0$.

The proof, by the way, shows more: it shows how to construct a simulator for any adversary, as follows. In the real world, the adversary receives $x$, performs whatever computation based on $x$, $y$, and its auxiliary output $z$, and outputs the result. The simulator sends $1$ to the trusted party, receives $x$, performs the same computation as the real-world adversary, and outputs its result.


Are there any practical examples of breaking a system using linear attacks?

The most well known example of a cipher practically broken with linear attacks is by no doubt DES, a cipher with 56-bit key and 64-bit block. Equipped with a cluster of PCs in the year 1994, Mitsuru Matsui has experimentally found a secret key after 10 days of the analysis (the data generation took additional 40 days on the same machine set).

By that time the behaviour of linear attacks was not well understood, but eventually a simple concept emerged. Given $N$ (plaintext,ciphertext) pairs of 64-bit blocks, a cryptanalyst obtains a list of candidate keys ordered by their likelihood to be the right key. There are estimates of the probability $P$ that the right key is among top $R$ candidates. Clearly, $P$ increases as $N$ or $R$ grows, and it is in fact the success rate of the attack under parameters $(N,R)$.

A comprehensive treatment of this subject has been given by Junod in his PhD thesis, where  Figure 3.3, p.80, provides a plot of the success rate given fixed $N =2^{40}..2^{45}$. Both theoretical and implementation details are given in Section 3.2 of the same text.


There are three issues in your proposal, which I'll go over one by one; I hope this will clarify the concept.

The first issue is that the purpose of a zero-knowledge proof is not only to prove knowledge of some information without disclosing it, but something much, much more powerful: the goal is to prove that you know some information$^1$ without disclosing anything at all beyond the fact that you know this information. The point here is that you have no idea what your opponent is going to do with the information you leak about your secret value. It might well be that even some apparently harmless leakage can allow your opponent to do something unexpected and bad. Consider the authentication protocol you suggest, with a hash function $H$: here, given a secret value $v$, you leak $H(v)$. This is clearly not "no information", and you have no guarantee that this $H(v)$ cannot be used to do something bad. So, the way we define zero-knowledge proofs aims at anticipating every possible scenario, as follows: we say that the protocol is zero-knowledge if there exist an efficient algorithm that could produce an interaction with the verifier which is indistinguishable from an honest interaction, but without knowing the secret value. The intuition between this definition is that if the transcript of the interaction cannot be distinguished from something that could have been produced without even knowing the secret value, then it cannot convey anything useful about this value to the verifier (of course, defining that formally requires some care). Your protocol clearly does not satisfy this.

The second issue is the generality of the functionalities we want to consider in general. In your example, you actually assumed that you were only proving that you know the same value as the one already held by your opponent (since she must hash the value herself to compare). But this is not a very useful situation in general. A much more general setting would be for example the following: some public ciphertext $c$ is known, and you want to prove to an opponent that you know its plaintext, but without disclosing the actual plaintext. Here, your hash-then-send simple approach does obviously not work at all. In fact, zero-knowledge proofs deal with even much more general situations than this, allowing to prove wide classes of statements about secret values, which can be hashed, committed, encrypted, signed, or whatever you like.

Eventually, the third issue is that a zero-knowledge proof of knowledge must, well, prove knowledge. A protocol proves knowledge of a value if given the code of the prover, it is actually possible to extract this value efficiently (this is the formal definition of "knowledge" in cryptography). This is also clearly not possible in your example. In fact, your protocol does not prove knowledge of the secret value $v$ at all, since the prover would just have to know $H(v)$ to complete it - which, as you pointed out yourself, does not imply that he knows $v$, since $H$ is one-way.

Let's go over an actual example, to make all of that more concrete.

Take a finite group $G$ of prime order $p$ (I assume some familiarity with basic algebra here). Fix a generator $g$. Consider now another group element $h$. The goal of the prover is to demonstrate to the verifier that he knows a secret value $x$ such that $h = g^x$ (note that such an $x$ exists since $g$ is a generator, but finding it given $h$ might be hard - it's the discrete logarithm problem). This is very useful for authentication: $h$ will be the "public identity" of the prover, and demonstrating knowledge of $x$ such that $g^x = h$ can be used to authenticate him as the owner of the "private identity" associated to $h$ (its exponent in base $g$). Take one second to convince yourself that no simple "hash based" solution does work here.

Here is a protocol that actually works:

The prover picks a random exponent $r$ and sends $R = g^r$ to the verifier.
The verifier picks a random exponent $e$ (the challenge) and sends it to the prover.
The prover computes and sends $d = ex+r$ to the verifier.
The verifier checks that $h^e\cdot R = g^d$.

Take a few seconds to check that the protocol is correct, meaning, if the prover plays honestly, the check of the verifier will succeed.

Why is this zero-knowledge$^2$? Because one can generate a transcript that is perfectly indistinguishable from an honest transcript of this protocol, but without knowing anything about $x$: pick $(e,d)$ at random, then set $R \gets g^d/h^e$, and output the transcript $(R,e,d)$. Note that this can be easily checked to give a transcript uniformly distributed over all transcripts satisfying $h^e\cdot R = g^d$ - i.e., uniformly distributed accross all honest transcripts. Therefore, interacting with the prover in this protocol does not convey any information at all about $x$ (since a transcript following the exact same distribution could have been generated without knowing $x$).

Why does this prove knowledge of $x$? To show this, I must show that given the code of a prover that succeeds in this proof, I can efficiently recover $x$ - hence showing that this prover actually knows $x$. I do it as follows: I run the prover code, to get $R$. Then, I put a breakpoint in the code, fork it, and run it twice on two random different challenges $(e_0,e_1)$ that I choose. The first copy of the code outputs $d_0$, and the second copy of the code outputs $d_1$. Since this is the code of a successful prover, I know that the check passes$^3$, hence I have $(R, e_0, e_1, d_0, d_1)$ such that:

$h^{e_0}\cdot R = g^{d_0}$

$h^{e_1}\cdot R = g^{d_1}$

which gives after a few easy manipulations $g^{(d_0-d_1)\cdot(e_0-e_1)^{-1}} = h$

Therefore, the value $x$ we are looking for is just $(d_0-d_1)\cdot(e_0-e_1)^{-1}$, and we have successfully extracted it. This concludes the proof.

(1) actually, that's only for the specific case of zero-knowledge proofs of knowledge; in full generality, there are two variants of zero-knowledge proofs, which can be used either to show that some statement is true (existential proof), or that you know a proof of some statement (proof of knowledge). I focus on the latter since it seems to be the one you read about.

(2) in fact it's not truly zero-knowledge, formally it only satisfies a weaker definition known as honest-verifier zero-knowledge, but I omitted this point to simplify.

(3) I'm again hiding some technicalities here, since usually we can only assume that the prover succeeds with some noticeable probability, but it does not make a major difference.

EDIT - Answering questions from the comments

From MechMK1:

  Perhaps my understanding of the matter is not good enough, but I am intrigued by the question asked "Why can Alice not simply enter one end of the tunnel and come out the other?". As far as I can tell, this is not directly answered.

First, note that this cave illustration is not meant to be a real zero-knowledge proof, but is rather a scenario given for illustration purpose that conveys some intuition about a zero-knowledge proofs. There will always be some way in which the intuitive scenario does not properly explain all of the concept.

That being said, let's answer "Why can Alice not simply enter one end of the tunnel and come out the other?" (edit: as I noticed afterward, my explanation below basically expands upon the comment to OP's question made by Roman). Recall that to prove that a zero-knowledge proof convey no knowledge, we have to simulate a valid-looking transcript without knowing the actual secret witness. How can it be done with the cave experiment? An answer is given in the actual paper this illustration is taken from: How to Explain Zero-Knowledge Protocols to Your Children, which I encourage you to read for more discussions about this. Basically, you can record a video tape of someone being asked a random side of the tunnel to show up from; the person doing it, who cannot pass through the door, will just have initially picked a side at random and went there. When the person is lucky and just get out from the right side, keep the recorded video; when he is not, delete the video and try again. In the end, what you have is a recording which is perfectly indistinguishable from an actual recording of people doing the real zero-knowledge experiment.

Now, you could argue that this is a bit fishy, perhaps we could craft a valid-looking video of someone entering from one side and leaving from the other side using video editing, hence the alternative proposal can be "simulated" as well. This is were we reach the limit of this illustration. Actually, the original protocol which inspired this illustration is the zero-knowledge protocol for graph isomorphism. It goes as follows: you are given two graphs, $G_0,G_1$ (the "entries of the cave"), and you claim that they are isomorphic (i.e. "you are able to walk from one to the other"). The protocol works as follows:

The prover knows a secret permutation of the vertices of $G_0$ that maps to the vertices of $G_1$, that's his witness. He picks a bit $b$ at random, and a random permutation $\pi$, and sends $G = \pi(G_b)$ (i.e., he "enters the cave through a side picked at random")
The verifier picks a bit $b'$ and sends it (i.e., she "asks the prover to come out of some random side that she picks")
The prover must reveal a permutation $\pi'$ that maps $G_{b'}$ to $G$ (this is either $\pi$, or $\pi$ composed with the secret permutation). I.e., he uses his secret witness ("the key of the door") to "arrive" at the side chosen by the verifier.

Now, this video-recording illustration is actually an intuitive explanation of how to prove that the above is zero-knowledge - you can create a valid-looking transcript by replaying the protocol many times, and discarding the runs where $b' \neq b$. At the same time, "Why can Alice not simply enter one end of the tunnel and come out the other?" is clear here: that would correspond to revealing the path from one side to the other -- i.e., giving away the secret permutation. But again, it's obviously much less clear that this is not a valid solution in the illustrative example, which is a limitation of this example (and one of the reasons why I do not like it much).

From NieDzejkob:

  "The intuition between this definition is that if the transcript of the interaction cannot be distinguished from something that could have been produced without even knowing the secret value, then it cannot convey anything useful about this value to the verifier". The prover establishes a TLS tunnel with the verifier, and sends the secret through it. Nobody can learn anything from the transcript, and yet this will clearly let the verifier learn the secret. Am I missing something?

A comment related to my footnote (2): actually, the transcript guarantees that nothing leaks not only to external people, but also to the verifier himself, if it is indistinguishable from a transcript that could have been produced as the result of an interaction with this verifier. In the proof I've given, the transcript was simulated assuming that the verifier samples the challenge $e$ honestly, which he might not do in reality. Hence, the proof I've given does in fact only show that the protocol is zero-knowledge against verifiers that honestly sample $e$ at random. But general techniques exist to transform this protocol into one that can actually be proven zero-knowledge against arbitrary verifiers, even cheating ones.

Now, back to your question: when doing so, the simulated transcript would not  look indistinguishable from an honest transcript from the viewpoint of the verifier himself, since the simulated transcript would not include this TLS channel transmitting the secret value. An actual proof of zero-knowledge property must produce a simulated transcript that the verifier himself cannot distinguish from a transcript that could have been produced as a result of an interaction with himself. Hence my previous comment on the fact that, for simplicity, what I had in fact proven previously does only guarantee zero-knowledge against verifiers who sample their challenge $e$ honestly, since it's how it's done in the simulated transcript. But as I said, there are methods to simulate against arbitrary verifiers.


Now that quantum computers have been out for a while, has RSA been cracked?

RSA has not been cracked.  No one has demonstrated practically viable computing that's anywhere in the realm of breaking RSA.  There is no reason to change any of your practices.

The first thing to understand is that D-Wave has a long history of
repeatedly making bogus claims to the popular press.  Experts in quantum computing have been criticizing and debunking D-Wave's claims for years.  (Try clicking each of the last seven words, for examples.)  So, this is not a company with a lot of credibility.

The latest news is that D-Wave has published a paper in Nature that describes very limited progress towards quantum computing.  It is not a full-fledged quantum computer.  It can't do general-purpose computation; it can only solve one algorithm.  In particular, it can't be used to factor numbers or break RSA.  It can't handle realistic problem sizes; it only has 8 qubits, so it can only solve toy-sized problems (problems that you could have solved with pencil-and-paper anyway).  There is no evidence that it is faster than classical algorithms.  It's not faster than existing classical computers.  It does represent a step forward, but it's a limited step.

Researchers have been studying quantum computing intensely over the past decade or so.  There has been some progress, but it has been slow, and building a working quantum computer will require us to surmount some fundamental challenges (e.g., decoherence) that today no one knows how to deal with.  D-Wave gets a lot of press (mostly because they make irresponsible statements to the press to hype their work beyond its true importance), but others have made more significant contributions.

You use the phrase "commercially viable quantum computer".  That's not a useful phrase.  Please understand that D-Wave has not demonstrated a viable quantum computer.  D-Wave may have sold something to one or two customers, but that doesn't mean they have licked the quantum computing problem or that their claims therefore necessarily have any validity.  Snake oil salesman managed to sell their stuff to plenty of customers, too, but their claims were invariably bogus.

If someone did build a working quantum computing that scaled to an unlimited number of qubits, and solved the decoherence problem, that'd be different: in that case, we'd have to move away from RSA, pronto.  But we're a long ways away from that.  Right now, it's an open question whether we'll see such a quantum computer in our lifetimes (or even if it will ever be possible to build one) -- quantum computing experts like to debate questions like those over drinks.  I suspect, if general-purpose quantum computing is possible, we'll have plenty of warning before quantum computers that can threaten RSA become readily available.

So, in short, no, you don't need to change your strategy or drop RSA.  I wouldn't.  Continuing to use RSA is perfectly reasonable and in line with industry practices.