Question regarding multiple SHA-256 rounds on a Bitcoin Brain Wallet passphrase… I am attempting to come up with a way of memorizing a seed that could lead to any number of brain wallets for bitcoin.  I need multiple wallets because a) I don't want all my eggs in one basket, and b) I want to be able to import small amounts from time to time.

Let's say I came up with a passphrase, and assume it's long enough to be secure.  If I was to concatenate a value at the end of the phrase, and increment this each time, it could lead to an infinite amount of brainwallets, ie.

SHA256(passphrase.'1')
SHA256(passphrase.'2') etc...

The only disadvantage I see with this approach is that if somebody, at some point in the future was to stumble upon the seed to the private key (keylogger, brute force etc.), it would be trivial to access all the other wallets.

So I was considering using two rounds of SHA256 instead, but adding a second phrase to the hash value of the first round, like this -

SHA256(SHA256(passphrase.'1').'second phrase')
SHA256(SHA256(passphrase.'2').'second phrase')

I would the use the resulting hash as the input to the brain wallet.

This would mean concatenating ASCII text to the hex of the first SHA256 operation.  The reason that I don't want to use the actual numeric value is that I need something that can be done easily over a unix command line (I'm not sure how to do 256-bit math operations).  I don't want any custom software involved because there's not that much room in my brain. This would hopefully eliminate the worry that somebody could reverse-engineer the process by which I generate the brain wallets.

I'm worried that if I use the ASCII text to generate a second key, I'm somehow compromising the SHA256 process and making everything less secure.

Is there reason for me to be worried or is my approach secure?

This would hopefully eliminate the worry that somebody could reverse-engineer the process by which I generate the brain wallets.

By Kerckhoffs's principle, you should assume that the adversary already knows the algorithm, and the only thing unknown are the secret keys – in your case, the passphrases.

Therefore, the adversary by definition knows that you are generating the brain wallet passphrases by $w_i = h( h(k_1 || i) || k_2)$ (where $h(x)$ is something like $Hex(SHA2(ASCII(x)))$. So the only things your attacker has to "reverse-engineer" are the two passphrases $k_1$ and $k_2$.

For now, SHA-2 is assumed to be preimage-resistant, which means that the best way of finding $k_1$ and $k_2$ is to simply guess them and see if the result matches any captured output (or, if there is no captured output, see if the result helps unlocking any of your wallets).

Generating different $w_i$ with the same passphrases does not significantly help the attacker to break it, but if he breaks one, also all the others are broken. The encoding (hex, ascii, anything else) doesn't matter for the security, too.

If your two passphrases are good (i.e. having more than 100 bits of entropy together), an attacker has little chance of successing with this brute-force.

If your passphrase is bad (and this includes all passwords with less than 10 characters, or longer ones which can be found in dictionaries), your derivation can be brute-forced easily. Also, if other users are using your scheme too, and by chance have the same password, they'll have the same $w_i$s, which might be usable by an attacker.

Your scheme could be made better by using a slow password hash, and including a salt input which is unique to you, like your email address. The output of this slow hash you can then process with the counter to get the actual $w_i$.

If the attacker has a key-logger and captures your passwords, everything is already lost.


Elliptic curves on finite fields I've been reading: https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf

On page 22 it shows an eliptic curve over F17.

I have added the orange lines and labels.

Do the orange lines illustrate that a line through points at P(2,10) and Q(5,9) also intersects the "curve" at -R(12,1)?

i.e. Does the finite field version graphically match an elliptic curve over real numbers, with the provisos that the finite field curve is discontinuous and that lines wrap?

Or am I hopelessly confused about elliptic curves on finite fields (as I expect).

P.S. If this is an accurate graphical representation, how do I illustrate tangents to the discontinuous curve?

P.P.S. There are multiple lines which contain three points.  X, Y and -Z, in purple, are another (below).

You are correct about the graphical representation. A line in the finite field $\mathbb{F}_p$ is not $y=ax+b$ but "informally" $y \equiv ax+b \pmod p$, so the line "repeats" itself. For the tangent, you refer to the algebraic formula to trace the line.
Have a look at the third figure here.


Why is double hashing universal hash function still a universal hash function? Here is the definition of universal hash function for $h \in H$ (family of universal hash function)

$$\forall x, y \in U x \neq y : Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{m}$$

Double hashing is the following

$$h_a , h_b \in H$$

$$h_i(x, m) = (h_a(x) + i \times h_b(x)) \mod m $$

Is there a proof that shows that double hashing two universal functions with arbitrary $i$ will produce another universal function?

If

$$ k = (h_a(x) + h_b(x))$$

Can't we say that there is $k + 1$ more ways of collision?

$$ 5 = 0 + 5, 1 + 4, 2 + 3, 3 + 2, 4 + 1, 5 + 0 $$

Is there a proof that shows that double hashing two universal functions with arbitrary $i$ will produce another universal function?

If $i$ is fixed, then no, $h_i$ need not be universal.

For a simple counterexample, consider $U$ which consists of 2 elements and $H$ which consists of 1 element $h$, with $\alpha$ and $\beta$, with $h(\alpha) = 0$ and $h(\beta) = 1$.  It is easy to see that $H$ is universal.

However, if we select $i = m-1$, then $h_i(x, m)$ is not universal (as it is 0 for both possible inputs $x$).

Now, let us consider where $i$ is uniformly distributed; that is, the family $H'$ that $h_i(x, m)$ belongs to contains all $i$ values.

Then, if $m$ is composite, the answer is still no.  Similar counterexample: suppose $a$ is a proper factor of $m$; then, consider the $H$ which consists of 1 element $h$, with $h(\alpha) = 0$ and $h(\beta) = a$

Then, $h_i(\alpha, m) = h_i(\beta, m)$ with probability $a/m$; not universal.

On the other hand, if $m$ is prime, then $h_i$ will necessarily be universal (and we need not assume that the $h_b$ side is universal); this can be shown for any two distinct inputs $\alpha, \beta$ with a simple case analysis (where the probability in both those cases is $\le 1/m$):

If $h_b(\alpha) = h_b(\beta)$, then the probability is $\le 1/m$ (because of the universality of $h_a$)
If $h_b(\alpha) \ne h_b(\beta)$, then there is a unique value $i$ with $h_a(\alpha) + i h_b(\alpha) = h_a(\beta) + i h_b(\beta) \mod m$, and as there are $m$ possible values of $i$, $i$ will be that unique value with probability $1/m$


Length of prime number used in Pedersen Commitment I am writing a program using a Pedersen commitment scheme and all I'm missing is an appropriate length for my prime $p$. I have heard that a length of $2^{80}$ is ok, is that correct?

If you mean a prime in the neighborhood of $2^{80}$, well, that is incorrect.  A prime that small will allow someone to commit to a value, and then reveal another one.

A Pederson commitment is a value $g^x h^r \bmod p$, where $g$, $h$ and $p$ are public values, $x$ is the value being committed to, and $r$ is a random value.  To reveal the commitment, you publish $x$ and $r$.

To reveal a second value $x'$, one way to do this is compute a value $r'$ with $g^x h^r \equiv g^{x'} h^{r'}$, this is equivalent to $h^{r'} \equiv c$, where the attacker can compute $c \equiv g^{x - x'}h^{r}$.  If the attacker can solve his discrete logarithm to the base $h$, we can recover $r'$ and reveal his second value $x'$.

Now, for primes of 80 bits in length, this discrete logarithm is easily solved.  To make it impractical, you need a prime at least 1024 bits in length, preferably at least 2048 bits.

On the other hand, if you mean a prime that's $2^{80}$ bits in length, that is, around $2^{2^{80}}$, well, you'll find that is an impractically large prime to work with; computing $g^xh^r$ would be infeasible.


Why should CAST5 and 3DES not be used for encrypting files over 4GB? On https://www.gnupg.org/faq/gnupg-faq.html#define_cast, it says that

  Like 3DES, its 64-bit block size means it should not be used to encrypt files larger than 4Gb in size…

How and why does the block size affect the security of the cipher?

If you use a key for close to $2^{n/2}$ blocks in CBC mode, then the chance of getting a collision in the ciphertext is getting rather high because of the birthday paradox. As the ciphertext is used as a vector for the next calculation, and since that vector should be unpredictable, you would likely lose confidentiality.

Note that the author seems to have put his mark at about $1 / 148$ as the chance for a collision to occur (see the calculation by fgrieu in the comments). That may be either too low or too high depending on the context. That is if bytes are meant instead of bits, otherwise it would be $1/9445$ - a somewhat more sensible value most of the time, but you would be left with only 512 MiB for a single key.


Why do we apply the concept of circuit in homomorphic encryption schemes? I am a beginner to the concept of homomorphic encryption. One thing that makes me very confused is why we use the circuit concept or approach to homomorphic encryption. Gentry's paper does not discuss it in detail. Are there any papers or books could make me have a better understanding of it?

(I mean the circuits part.)

We use circuits because they are universal (any function you want to compute can be expressed as a circuit) and because they are convenient (because we know how to solve the problem of fully homomorphic encryption for circuits but not for other models).  In particular, circuits are in some sense simple: all you need to do is find a way to implement an AND gate and a NOT gate, and that's enough to be universal.  This helps avoid inessential detail and helps us focus on the core of the problem.


Can we construct a simulation sound NIZK (Non Interactive Zero-Knowledge) proof? A single theorem adaptive non-interactive zero-knowledge proof (P, V) for a language L is a proof system that satisfies

Completeness: If a string $x \in L$ (and P has the witness), the verifier V will accept with high probability.
Soundness: If $x \notin L$, the verifier V rejects with high probability.
Zero-knowledge: there exists a simulator M on input $x \in L$, outputs the ensemble which is computationally indistinguishable with the output of the protocol.

Since it is adaptive, $x$ is chosen based on the common reference string.

Single theorem implies that a common reference string is used to prove a single theorem $x$. If we use same string to prove more than one theorem, zero-knowledge property may not be preserved.

Simulation soundness is defined as given a list of simulated proof's to the adversary, adversary should not be able to produce a valid proof for any theorem $x \notin L$

If there exists a single-theorem adaptive NIZK, can we construct a simulation sound NIZK?

Yes.

If there exists a single-theorem adaptive NIZK proof system for NP, then there exists a multi-theorem adaptive NIZK proof system for NP. This was proven in the seminal paper of Feige, Lapidot, and Shamir.

The idea is the following: if you have a single-theorem NIZK proof system for NP, then you have a single theorem NIWI proof system for NP. NIWI (non-interactive witness indistinguishable proofs) are strictly weaker than NIZKs, so this is immediate: the WI property states that the verifier cannot distinguish which witness is used by the prover, when there is more than one witness, and this is trivially implied by zero-knowledge, which states that a simulator can simulate the proof without knowing any witness. Now, if you have a single-theorem NIWI, you have a multi-theorem NIWI. This is because unlike ZK, WI is an indistinguishability notion, and therefore we can use an hybrid argument: suppose a prover performs $n$ sequential NIWI proofs (with the same CRS), either all with witness $w_0$, or all with witness $w_1$. Suppose also that an adversary can distinguish whether $w_0$ or $w_1$ was used in these $n$ proofs, with non-negligible probability. Then there must be one of the proofs for which the distinguishing advantage of the adversary was non-negligible (otherwise, a sum of $n$ negligible advantages would still be negligible), hence this adversary already breaks single-theorem NIWI. This shows that single-theorem NIWI implies multi-theorem NIWI.

Now, if there exists a multi-theorem NIWI and one-way functions (which are implied by single-theorem NIZKs for NP anyway), then there exists a multi-theorem NIZK. The idea is to artificially add a second witness that can be used to perform the proof honestly; this second witness will only be used by the simulator. Namely, add to the CRS a random bitstring $y$ of length $2k$, for some security parameter $k$, and instead of proving a statement $S$, prove "either $S$ is true, or I know a string $x$ of length $k$ such that $y = \mathsf{PRG}(x)$" (PRG is a pseudorandom generator, whose existence is implied by any one-way function). In any real run of the protocol, no such $x$ exists, so the proof remains the same (it shows that $S$ is true); but to simulate the protocol, the value $y$ added to the CRS is computed as $y = \mathsf{PRG}(x)$ for a short $x$, and $x$ is given to the simulator (by the security of the PRG, this is indistinguishable from the real CRS). The simulator can then use $x$ to simulate the proof, and it cannot be distinguished from the honest prover by the witness-indistinguishable property of the proof system. Hence, the protocol is zero-knowledge.

If there exists a multi-theorem adaptive NIZK proof system for NP, then there exists a simulation-sound NIZK proof system for NP. This was shown in the seminal paper on simulation-sound NIZKs.

This is a bit more complex (and in fact, the above paper directly shows that single-theorem NIZK implies simulation sound NIZK). In the simplified scenario of one-time simulation sound NIZKs, however, there is a very simple construction given in Appendix B of this paper: given a word $x$, to prove that there exists $w$ such that $R(x,w) = 1$, prove instead the following: either $\exists w, R(x,w) = 1$, or $\exists r, c = \mathsf{Com}(x;r)$. Here, $c$ is a commitment to $0$ added to the CRS; in honest runs of the protocol, therefore, this proof is equivalent to just showing $\exists w, R(x,w) = 1$. In a simulated proof, however, the simulator will instead generate $c$ as a commitment to $x$. This way, $c$ allows to cheat in the proof for the word $x$, but cannot help with cheating in the proof for any other word, hence it is easy to see that the proof system remains sound even if the adversary can see a simulated proof for the word $x$. From there, techniques exist to boost one-time simulation soundness to unbounded simulation soundness, but that would bring us a bit too far.


Can somebody explain the major contributions of the tenants of the Gödel Prize 2013? As you may know, the Gödel Prize 2013 will be awarded this year to cryptographers (see this ACM press release). The people awarded are Antoine Joux, the team of Dan Boneh and Matthew K. Franklin.

Can somebody explain their contribution to cryptography ?

Joux's work is really summarized by this answer already on Crypto.SE. He discovered a way to generalize Diffie-Hellman to multiple (more than 2) parties. In particular though, he presented a single round protocol for key establishment between 3 parties. Something that until then was thought to be impossible.

Boneh and Franklin developed the first fully functioning identity based encryption (IBE) scheme. The premise of IBE is that your public key should be your public identifier (such as your email address) instead of simply a large number. Then, to say send you an encrypted email, the sender only needs to know your email address.  IBE has led to other really cool constructions such as functional encryption and attribute-based encryption. For more on IBE, see What is Identity-Based Encryption (IBE) and why is it “better”?


Deriving Keys for Symmetric Encryption and Authentication So here's the concept. Rather than storing 2 keys and using a random IV, which presents its own problems (key rotation, ensuring no key is used in more than 2^32 cycles, sharing the keys, etc), is it OK to derive the cipher key, authentication key and IV from a master key? It wouldn't stop the need for key rotation policy (changing the key every 30 days), but it would greatly simplify it. So here's the concept:

MasterKey = 256 - 512 bits of CS random entropy

Then, on encrypt:

Salt = 256 bits of random entropy
Derivation = PBKDF2(SHA-512, MasterKey, Salt, 10000, 640bit)

CipherKey = Derivation[0:256bit]
AuthKey = Derivation[256bit:512bit]
IV = Derivation[512bit:640bit]

Then, the Salt is all that's shared in the ciphertext package: Salt || CipherText || AuthText...

The few points here:

That MasterKey should be high entropy (at least the number of bits of Cryptographically Secure random as the longest required key).
The salt should be as strong as practical as well (CS as well), since salt collisions will automatically become cipherkey, authkey and IV collisions.
The maximum length of a single derived key should be less than the blocksize of the PRF used in PBKDF2 (to reduce exposure of the master key if a derived key is found).

For example, if you used MD5 (bs of 128 bit) to generate a 256 bit key, if that 256 bit key was found (brute force, or other weakness), the entire 128 bit output of a PBKDF2 round would be found. Therefore, the entire PBKDF2 output would not need to be brute forced, but only a single round of it (still hard, but much easier). But if the BS is larger (sha512 vs 256bit key), then finding a derived key would only give you 1/2 the output of a round, making the search much harder (since there are a LOT of inputs that would generate the same 1/2 output)...

The iteration count feed into PBKDF2 should be high enough to provide a proof of work on the derivation, but is obviously application dependent.

Based on my understanding, it demonstrates good forward security (not perfect, but good) in that if you are able to find the CipherKey or AuthKey of a particular message, they would not be applicable to future or past messages. You would need to use that information to brute force the derivation, which would be non-trivial in the least. So therefore, as long as the master key is not compromised, the individual derived keys should be safe and practically independent of each other.

Am I on track here? Or is there something that I'm missing?

Yes, this is a fine approach.  This sort of technique is known as "key separation".

Since your master key is a cryptographically secure key, you do not need to use a large iteration count.  Also, you could use any PRF, in place of PBKDF2.  (The iteration count is normally used if you are applying PBKDF2 to a passphrase, instead of a cryptographically secure key; but that is inherently problematic from a security perspective, so what you are doing is much better.)

For instance, you could use HKDF or AES-CMAC as your PRF.  HKDF produces an arbitrary-length output, so you can use it as a plug-in replacement for PBKDF2: Derivation = HKDF(MasterKey) and then continue as you described.  A standard way to use AES-CMAC would be to use MasterKey as the CMAC key, and use different message-inputs for each value you want to derive: e.g., CipherKey = CMAC(MasterKey, 0), AuthKey = CMAC(MasterKey, 1), IV = random() (or IV = CMAC(MasterKey, 2)).

(For more on key separation, the tag wiki for key-derivation has a very brief set of keywords that might help you find more.)

Credits: Thanks to @CodesInChaos for suggesting HKDF as one reasonable way to do it.


How to obtain KCV from the key Simple question: we have AES 128 encryption and a key. How can we calculate the key check value (KCV)?

One example: key is 48C3B4286FF421A4A328E68AD9E542A4 and KCV should be 77DC84.

I am trying it out in C#, but there are just to many 'unknowns' for a newbie in cryptography...

Edit: there was a question why I need it - let's say that I have a bunch of key-KCV combinations, written down by multiple users in our organization, but some of the keys are invalid (employee wrote 8 instead of B, 1 instead of 7, etc...). So I needed a program, which changes some bytes in the key and then calculates the KCV. If the key has one wrong byte, then it is calculated in 2ms, for two wrong bytes 5seconds, for three wrong bytes an hour and half, and so on...

To calculate the KCV for AES, you take the first three bytes of the encryption of zero under your key.

Indeed, the case you've given is precisely this - the zero vector encrypted under the key 48C3B4286FF421A4A328E68AD9E542A4 is 77dc841daeb43315fed9acdf2f965f45, which restricts to 77dc84.

In your question you say you already have AES-128 encryption, at which point calculating the KCV shouldn't be a problem. I won't ask why you're calculating a KCV, but be warned that there may well be better ways to achieve your actual goal. The other article with this tag provides a reasonable discussion about the benefits of them.


What is 'key agility' in relation to symmetric-key encryption? I sometimes see, in discussions of symmetric ciphers, reference to the 'key agility' of a particular algorithm. It seems to be related to the difficulty of switching encryption keys, but I don't understand more than that.

Can anyone give a good explanation of 'key agility' and some contexts in which it is important?

Here's what I can say about the general meaning of it:

It means that the amount of preprocessing of a key is small. So the amount of time from generating/importing a new key to actually starting encrypting is neglegible.
It means that the amount of state a cipher uses is small. The state of a cipher generally is the key or preprocessed key schedule plus the actual block. If this is small it means that you can potentially fit many keys in the CPU cache.

Note that if you have either an extreme of 1 or 2 you can live with just one. If preprocessing takes a long time but the generated key schedule is small you can simply do it once and store it with the key. If preprocessing is very cheap but the state is very large you can do it on-the-fly.

To give an example of the key agility of my own cipher (broken link to pdf), here's why:

The key schedule only consists of permutations of the key - this means it's just memory loads and can be done on the fly.
The full state is only twice the block size - so 128 bytes.

As for why it's important, an example would be a busy HTTPS server. It has to handle many connections at once, and (if everything is done right) each connection has it's own associated keys. Being able to use many keys at once, and preferably to generate and use keys on the fly (ephemeral keys) is a huge bonus in performance and security.


Using a single key pair for man-in-the-middle attack on Diffie-Hellman Assume that a man-in-the-middle attack on the Diffie-Hellman key exchange protocol is possible, for which the adversary generates two public–private key pairs for the attack.

Could the same attack be accomplished with one pair?

For the attack to work the attacker - say Malory - needs to establish a secret with the party that starts the key agreement, say Alice. After that Malory needs to establish a secret with the party providing the intended service, say Bob.

Assuming that we are talking about ephemeral (non-static) keys then there is nothing preventing Malory to use the same Diffie-Hellman key pair for both Alice and Bob. The established secrets will still differ of course, as the secret also depends on the key pairs generated by Alice and Bob.

Alice was already expecting to use the same domain parameters and key size as Bob. Otherwise she would not be able to establish a secret with Bob directly.

So yes, Malory - the man-in-the-middle - can use a single key pair for this. Malory could even use a single static key pair for all the connections to Bob (assuming that Bob accepts the same public value for multiple connections and doesn't keep a log).

Note that we presume here that the key pair of Alice or Bob is not also used for authentication, because that would prevent man-in-the-middle attacks in the first place.


Why are modes of operation used, what attacks do they prevent? I know you always need to use a mode of operation when using a block cipher, AES for example, and Wikipedia has a good explanation for what modes of operation are
Now I know if i do not use a mode of operation every time i encrypt the same plain text (abc) with the same key (klm) i get the same cipher text (zyx). the IV in a mode of operation prevents this from happening. But since abc always maps to zyx with the key klm there are some attacks to figure out what key is used.

What attacks can be used against only block ciphers?
What credible sources explain this?

Block ciphers map bit strings of fixed length to other bit strings of the same length. Hence, using only the block cipher primitive, you can't encrypt more than one block (typically 16 bytes), which is of course undesirable.
The straight-forward (but bad!) way around this limitation would be to split up the message into chunks of block length and individually encrypt those: this is exactly the description of electronic code book mode (ECB), which is easily seen to be broken under modern security requirements (specifically, it fails indistinguishability under a chosen-plaintext attack since equal plaintext blocks map to equal ciphertext blocks).
Hence, other constructions suggest themselves. A good block cipher mode should fulfill at least the following requirements:

Each block must be encrypted in a different way. Since we want to reuse the same encryption function every time, the variation needs to be introduced somewhere else: For instance, cipher block chaining incorporates the preceding ciphertext block (which is pseudorandom if the cipher is secure) to mask each plaintext block, hence each $\mathit{block}$ is encrypted using the slightly modified cipher $\mathit{block}\mapsto F_k(\mathit{prev\_block}\oplus\mathit{block})$, thus satisfying the requirement.
Note that in CBC, the first block has no $\mathit{prev\_block}$, hence we need to substitute something else for it — this is what is known as an initialization vector (IV). One might be tempted to just use some fixed value, like $0$, but this is bad: The first block is not masked, hence an attacker can detect if two messages' prefixes are equal by comparing their corresponding ciphertexts' first blocks. This breaks indistinguishability under a chosen-plaintext attack (for multiple encryptions).

Encryption must be nondeterministic due to the problem described in the previous paragraph. The easiest way to achieve this for CBC is to just plug in some random value for the IV and transmit it alongside the message. Just like the pseudorandom ciphertext blocks, the randomized IV masks the first plaintext block (and therefore all subsequent since each block depends on its predecessor), hence it hides equal messages and effectively avoids the problems that a fixed IV has.

(Note that while the example describes CBC, about the same arguments could be made for any other block cipher mode.)


Is there any way to check signed documents in a group of people without knowing who signed which? Let's say there are 3 people A, B, C. Everybody knows their public keys. They sign documents/messages and normally we can know who signed which by checking with their public keys.

Is there any way to check these signatures without knowing who signed which? I just want to know these messages is signed with one of these people.

This method may involve making them sign known messages or making some preparation before the signing process. I am just trying to be sure, if the message is sent one of these people with electronic signature without knowing the identity of the sender.

There is more than 1 way to do it.
You can use Group signatures or Ring signature which allow anyone in a predefined collection to sign a message on behalf of a group. Group signatures require a group manager who creates the group and can de-anonymise the signer.
Ring signatures do not have such an entity and the signer cannot be de-anonymised.
There are variations of ring signatures like the linkable ring signature where the signer cannot be de-anonymised but signatures by a signer can be linked, i.e looking at 2 signatures $s1$ and $s2$, it can be determined if the same signer created them or not. More in the wikipedia article.

You can also use threshold signatures as M-of-N, i.e. M out of N parties have to sign and M <= N. In your case M will be 1 and N will be 3. One such scheme is BLS signature, section 5.3


Upper bound for the length of non-interactive zero-knowledge proofs of knowledge In a hybrid protocol $\pi$ for which I want to proof uc-security in the absence of corrupted parties, there is an ideal functionality $\mathcal{F}_{SMT}$ for secure message transfer that leaks the message length to the attacker.

Also, there are non-interactive zero-knowledge proofs of knowledge that are built using $\Sigma$-protocols and the Fiat-Shamir heuristic.

In this protocol there is an exchange of messages via $\mathcal{F}_{SMT}$ that include an instance and a corresponding NIZK proof of knowledge.

The instance includes some constant-size values, a commitment to a value (which is also assumed to be of constant size) and a list of party identifiers of variable size $l$, with $0 < l \leq MAX$.

I still can make some changes to the protocol, e.g. to add padding of messages.
Ideally, I want this kind of message to be of constant size. Therefore, I want to find an upper bound for the length of the possible proofs in this protocol and use this to pad all messages to the same, constant size.

So my question is: How do I find this upper bound for NIZK proofs constructed as mentioned above?

As Natanael pointed out, if you are willing to make very strong assumptions, SNARGs can be used to give proofs of constant size, independent of the size of the statement to be proven. However, these proof systems are in general not UC-compatible (see e.g. this paper). You have two natural alternatives:

1) use NIZKs with "almost optimal size", i.e., of size $w + \mathsf{poly}(k)$, where $w$ is the witness size, and $\mathsf{poly}(k)$ is a fixed polynomial in the security parameter. Such NIZKs exist from the LWE assumption (by combining this recent breakthrough and this paper), or from more exotic assumption. This is the generic, "heavy hammer" approach, if you really want to avoid thinking about how to concretely implement your NIZK.

2) Alternatively, you can use the right approach: look at the concrete statement you want to prove, write a NIZK for this statement, and look at its size.


What makes an open source encryption algorithm safe? Take for example the popular AES algorithm where we have a combination of substitution, shift row, mix column, and add key steps involved in encrypting plain test.

All of the mathematical operations within the s-boxes, shift row, and mix column should be known to the attacker, correct? I understand they could be hard to calculate but aren't they static operations for the most part? Since they can literally see the implementation of the calculations in the code to see how all the bits were changed around. The only step that is therefore hard to break is the add key stage, where we XOR our key with blocks of bytes.

The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key? Since the implementation details are known of how the substitution, shift row, and mix column steps work, whats the point of using them in the encryption scheme?

The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key?

Suppose all we had was secret keys and the XOR operation.  Well, actually, it is possible to build a secure cipher out of that, called the one time pad.  One time pads offer perfect secrecy, but suffer from fatal practical flaws:

The keys must be as long as the messages.
You must never use the same key to encrypt two different messages, or it becomes very easy to break.

So we can look at your question from this angle: the extra complexity in modern ciphers is the price that we pay to remove those practical disadvantages.  It's what allows us to use a single 128-bit key to safely encrypt gigabytes of data, time and time again.

The other thing that I'd highlight is this: you're assuming that just because you know what operations an algorithm does, it's automatically easy to undo those operations.  But one of the core assumptions of modern cryptography is that this is false: there are operations that are easy to do but costly to undo.  The prime example is that multiplication is easy (runs in polynomial time), but factorization is costly (doesn't run in polynomial time).  It's possible to prove that, if such one-way functions exist, then cryptographic algorithms can be built and fully disclosed, whose security depends exclusively on the secrecy of the key.

So if the designers of AES chose their operations right, then AES encryption and decryption are:

Easy for parties who know the secret key;
Costly for parties who don't.

Whether this is true for actual algorithms like AES and why, well, that is the hard part, and can't be answered in a brief question/answer format like this.


Protocol for Randomized Oblivious Transfer? If we define Oblivious Transfer as following:

Alice inputs $(x_0,x_1) \in F^2$, where $F$ is a field, and Bob inputs $b\in\{0,1\}$, then Alice gets a dummy output(for which she knows nothing about b), and Bob gets $x_b$. Now if we use a Random functionality R, which requires no input but output random bits $(z_0,z_1)\in F^2$ to Alice and $(c,z_c)$ to Bob, where $c \in \{0,1\}$ is also a random bit.

How can I design a protocol, so that it will realize OT securely with access to R only once at the beginning of the protocol?

I am thinking that the protocol should be as following:

First, Alice inputs $(x_0,x_1)$, then she gets $(x_0 \oplus z_0,x_1 \oplus z_1)$ as output, thus learning nothing. Now Bob gets $(c,z_c)$, treat $c$ as his input $b$, then he can recover $x_c$ from $(x_0 \oplus z_0,x_1 \oplus z_1)$.

I don't know if it will work, or maybe I am working in the wrong direction?

No, as written, your protocol doesn't work -- the problem is that Bob is supposed to be allowed to choose $b$, your protocol selects a random one for him.

However, it is close -- here is a modification that I believe does work:

First, suppose Alice has her values $(x_0, x_1)$, and Bob has his bit $b$.

They run their Random functionality R, and so Alice gets the values $(z_0, z_1)$, and Bob gets the values $(c, z_c)$.

Now, Bob sends the Alice the bit $e$ defined as $e = b \oplus c$; Alice sends back a pair of values $(y_0, y_1)$ defined as $(y_0, y_1) = (x_0 \oplus z_e, x_1 \oplus z_{1 \oplus e})$.

Bob then computes $z_c \oplus y_b = x_b$.

I claim that Alice gets no information about the value of $b$, and that Bob gets no information about the value of $(x_{1 \oplus b})$, and thus this is a valid Oblivious Transfer function.


Does a big salt have the same memory effects as Bcrypt? Citing Thomas Pornin on the question Why can't one implement bcrypt in Cuda?:

  bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly accessed and modified throughout the algorithm. Due to the size of the table, each core will have to store it in the GPU main RAM, and they will compete for usage of the memory bus.

In short, it's slow because it uses a relatively big amount of RAM. This is its advantage over PBKDF2, again from Thomas Pornin:

  Bcrypt happens to heavily rely on accesses to a table which is constantly altered throughout the algorithm execution. This is very fast on a PC, much less so on a GPU, where memory is shared and all cores compete for control of the internal memory bus. Thus, the boost that an attacker can get from using GPU is quite reduced, compared to what the attacker gets with PBKDF2 or similar designs.

As far as my understanding goes, this means both PBKDF2 and Bcrypt's password hashing features can be summarized as:

function password_hash(password, iterations, memoryUsage) {
  salt = system("cat /dev/urandom | head -c " + memoryUsage);

  for i = 0 to iterations {
    # hash() is a function like SHA256
    password = hash(password + salt);
  }

  return salt + "," + password
}

# 1 million iterations; 8KiB memory usage
password_hash("letmein", 1000 * 1000, 1024 * 8);

(Where + is concatenation.) Basically this does iterated hashing with a big salt.

I know PBKDF2 can output arbitrary key sizes for e.g. block cipher encryption purposes. I also know Bcrypt accepts iterations in the form of a log number, which makes more sense. And I've considered using HMACs instead of just hash(), but I don't see how this could be exploited, especially since we're not in the message authentication business here. So in general, isn't this equivalent to what Bcrypt and PBKDF2 do in terms of password storage security?

I've commented basically the same question on the post which I linked earlier, but didn't understand the answer, and perhaps it's better as a new question anyway.

Another question I've found is very specific for SHA3; and another once again reiterates that "bcrypt needs more RAM than PBKDF2 and is thus slower on GPUs" (once again from Thomas Pornin).

Disregarding the bigger storage required to store all those huge salts, and ignoring algorithms like Scrypt and Argon2 which use even more memory but without the additional storage requirements, the only reason I see for not wanting to do this is "you shouldn't be designing your own crypto anyway." Is that correct?

So in general, isn't this equivalent to what Bcrypt and PBKDF2 do in terms of password storage security?

PBKDF2, yes, pretty much. The only real difference is that salt/password are used the other way around, with the password mixed in at every step.

Bcrypt, however, is different.

In your case an attacker only needs a small amount of memory compared to computational resources. For example, you can imagine a long pipeline of hashing units, which each compute one block of the salt value and then pass the output onto the next unit.

In terms of tradeoffs, say you had memory to store a million hashes long (part of the) salt. Instead of using it all on the salt, you could store a 500k hash long part of it and 500k different password guesses. Then you can calculate a huge amount of work (500k squared) before you need the next part of the salt.

What bcrypt does is have a large part of memory it modifies. That means the memory cannot be shared among different password guesses. Also, the access pattern issue (which Thomas Pornin's comment raised) can play a part – if the access pattern is non-linear, tradeoffs are worse (halving the memory used can lead to a huge slowdown).

The salt storage issue Maarten Bodewes mentioned in comments is also important. A large number of large salts would be unwieldy to store. And you cannot just store some seed or you are in a way back to square one – a fast way to generate the "full" salt could be used to avoid storing it all.


Perfect security definitions In my notes, there are 2 definitions of perfect security:

"For $M \in \{0,1\}^m$, define the distribution $D_M$ on strings as follows: to choose a random member of $D_M$, choose a random $K \in \{0,1\}^n$ and output $Enc(M,K)$.  Then $Enc,Dec$ is perfectly secure if $D_M$ is exactly the same for every $M$.  That is, for every $\alpha \in \{0,1\}^*$, the probability of $\alpha$ according to $D_M$ is independent of $M$.

For every two messages, no function can tell which one has been encrypted.  That is, $Enc,Dec$ is perfectly secure if for every $M_0,M_1 \in \{0,1\}^m$ and for every $f: \{0,1\}^* \to \{0,1\}$, the following holds: consider the experiment where $b$ is randomly chosen from $\{0,1\}$ and $K$ is randomly chosen from $\{0,1\}^n$; then the probability that $f(Enc(M_b,K)) = b$ is equal to $1/2$."

I have two questions:

Could someone clarify the definition of $D_M$ (the distribution of strings?). I'm not sure I get what is meant by the "distribution of strings" and how it differs from $M$
If $M_0$, and $M_1$ are any two $m$-bit messages, how is it possible that their encryption be equal $b$? Wouldn't the number of bits in the encrypted message be $m$? if that number is for example 10 then how does $P \left ( f( \mathrm{Enc} (M_b, K)) = b \right ) = 0.5$?

If M0, and M1 are any 2 m-bit messages, how is it possible that their encryption be equal b?

The definition does not say that their encryption is equal b. It says that the function f outputs b. This function is often called distinguisher (or attacker) and he should not be able to distinguish which message M0 or M1 was encrypted. In other words there exists no distinguisher who can distinguish which message was encrypted better than with probability of guessing (0.5).


LWE versus neural nets It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$.
In LWE, we are given the problem instance $A$, and the product with errors $b$ and are challenged to produce the secret vector $s$. Is it similar to the problem in ML where we are given the coefficient matrix $A$ and the expected label $y$, can we produce a valid sample $x$?
Also, I'm wondering whether techniques we use in ML such as backpropagation can be applied to LWE as well?

This seems quite unlikely. A recent paper has suggested a Continuous LWE problem. This problem is structurally quite similar to the standard LWE problem --- it has (quantum) worst-case to average-case reductions to hard lattice problems.
In that paper they also show that a
standard problem in ML (learning mixtures of Gaussians) reduces to the continuous LWE problem. This gives you a more concrete ML problem to attack. If you could learn mixtures of Gaussians, you could reduce this to solving continuous LWE, which you could then reduce to solving worst-case lattice problems. If you can solve worst-case lattice problems, then we do not believe LWE is hard anymore.
There have also been some results showing that a broad class of learning algorithms (ones which fit into the "Statistical Query model") cannot solve certain learning problems. The LPN problem (which you can vaguely think of as "LWE with $q = 2$) has such bounds (see for example this problem). I don't know if specific ML techniques such as backpropagation fit into the SQ model though.


Proving equivalency of two security definitions of symmetric encryption schemes how to prove definition 3.8 and 3.9 are equivalence ?

picture is from book an introduction to modern cryptography (2nd edition) by j. katz and y. lindell pdf

and https://repo.zenk-security.com/Cryptographie%20.%20Algorithmes%20.%20Steganographie/Introduction%20to%20Modern%20Cryptography.pdf is link to first edition which definitions can be find on pages 63 and 64 of book as definition 3.9 and 3.10

Intuitive idea: the first definition is saying that an adversary can not do significantly better than random guessing. The second definition says that for two different inputs, the adversary would have the same probability of guessing 1. So to prove the equivalence, start with the first definition. Run this privacy experiment with two different inputs, subtract them, this is your second definition.


"Homomorphic" one way function for public/private key pairs Is there a signing scheme relying on a secret key $s_k$ and public key $p_k$ for which we can find a one way function $h$ such that we can efficiently calculate the public key associated with $h(s_k)$ from $p_k$.

For instance, with the ElGamal signing scheme, we'd be looking for a one way function $h$ such that for all $g$ and $s$ in $\mathbb{Z}/p\mathbb{Z}$ we can efficiently compute $g^{h(s)}$ from $g$ and $g^s$.

Alternatively, being able to verify that a given value is indeed the public key associated with the hash of the secret key would be enough.

(The goal is to get some kind of non interactive forward secrecy with certain properties.)

Sure.  Let (Gen,Sign,Ver) be any signature scheme, and let h be any pseudorandom generator from {0,1}k to {0,1}k+L.  (Since h is a pseudorandom generator, h is one-way.)

Gen' takes k+L random bits as input and outputs [those bits as the private key] and

[the public key resulting from running Gen on the last L of those bits] as the public key.

Sign' outputs the result of running Sign on [the message and

[the private key resulting from running Gen on the last L bits of the (k+L)-bit private key]].

(Gen',Sign',Ver) is a signature scheme such that "we can efficiently calculate

the public key associated with $h(s_k)$" without even needing $s_k$'s public key.

That makes me think you're actually after something stronger.


Determine complexity of a SAT problem Is there a standard way to determine a complexity of the specified SAT problem? I'm researching algebraic cryptanalysis and came to solving multivariate quadratic equation systems using CryptoMiniSat. However it would be nice to evaluate a complexity of the full cipher equation system. Does it only depend on the number of polynomials and variables? And is there a way to estimate the time needed for solving the equation system and what parameters do I need to know to find that out?

No, there is not.

Your question is not well-posed.  You have not specified whether you want worst-case complexity or average-case complexity, and over what class of SAT instances.  The answer will depend heavily upon those details.

If you want to know what is the world record for an algorithm for 3SAT, measured by its worst-case complexity over all possible 3SAT instances, that's a question to ask on https://cs.stackexchange.com/ or https://cstheory.stackexchange.com/ .  See, e.g., Best Upper Bounds on SAT and Measuring the difficulty of SAT instances.  But don't expect these theoretical results to necessarily have any relationship to the performance of SAT solvers in practice.


If Bob steals Alice's private key, how exactly would he read her encrypted documents? So Bob grabs Alice's secret key when she isn't looking and her encrypted files, doesn't he need to know her passphrase to read her files?

What I am reading is that no he does not need it but as far as I understand GPG, it would still ask for a passphrase to decrypt a document.  Please explain why Bob would not need to know Alice's passphrase to read her documents in a step by step example.

GPG's (or OpenPGP's) public-key file encryption uses multiple steps:

Generate a random session key
encrypt the file using this random session key
encrypt the random session key using the public key of the receiver (or using multiple keys in parallel, if the file is meant to be decrypted by multiple receivers).
store the encrypted file together with the encrypted session key.

To decrypt it, the receiver (or attacker) needs the private key corresponding to (one of) the used public key(s).

Now, Alice should have protected her private keys with a passphrase - this way, Bob would get not the private key itself, only an encrypted version of it. If so, Bob's only way for decrypting the key (and thus the file) would be to guess the encryption passphrase (which can be possible if the passphrase is not that long/complicated).

If Alice didn't protect her private keys, Bob would get the private key, and could directly use it to decrypt the session key, and thus decrypt the file.


RSA enc/decryption with multiple prime modulus using CRT Every information I found on internet about RSA-CRT encryption/decryption uses only two primes. I'm interested in my project in doing that using multiple (up to 8) primes.

The general idea is to calculate $d_p = d\bmod(p-1)$, $d_q = d\bmod(q-1)$, and $q_\text{inv} = q^{-1}\bmod p$, where $p$ and $q$ are primes.

Encryption and decryption is based on "logical relations" between $p$ and $q$ and I'm unable to expand it to more than two primes.

Any help appreciated.

The RSA private-key operation (used for decryption and signature generation) amounts to solving for $x$ the equation $y\equiv x^e\pmod N$, knowing $y$, the factorization of the public modulus $N$ into $k\ge2$ distinct primes $N=r_1\dots r_k$, public exponent $e$ such that $\gcd(e,r_i-1)\ne1$, and that $0\le x<N$.

For an efficient implementation, we can solve this equation modulo each of the $r_i$; then use the CRT to combine solutions between products of moduli for which we already have a solution, until reaching a solution modulo $N$. The common way, implicit in PKCS#1v2.2, is:

precompute the following quantities $d_i$ (the CRT exponents) and $t_i$ (the CRT inverses/coefficients), e.g. at key generation time, including the results in the private key:

for $i\in\{1,\dots,k\}$

$d_i\gets e^{-1}\bmod(r_i-1)$, or equivalently $d_i\gets d\bmod(r_i-1)$

$m\gets r_1$
for $i$ from $2$ to $k$

$t_i\gets m^{-1}\bmod r_i$
$m\gets m\cdot r_i$

when needing to use the private key and solve $y\equiv x^e\pmod N$

for $i\in\{1,\dots,k\}$ [note: should be parallelized if possible]

$x_i\gets(y\bmod r_i)^{d_i}\bmod r_i$

$x\gets x_1$, $m\gets r_1$
for $i$ from $2$ to $k$ [loop invariant: $0\le x<m$, $y\equiv x^e\pmod m$ ]

$x\gets x+m\cdot((x_i-x\bmod r_i)\cdot t_i\bmod r_i)$
$m\gets m\cdot r_i$

Correctness follows from the loop invariant. See this question for attribution. See this other one for how the bitsize of $N$ relates to a maximum reasonable number of primes.

Artificially small example with 3 primes:

e=5
r1=931164518537359 r2=944727352543879 r3=982273258722607
N=864102436520313334659779717201860718296307527
d1=558698711122415 d2=566836411526327 d3=785818606978085
                   t2=360227672914825 t3=882117903741868
y=529481440313141057262802385309623737292746309
x1=436496882968258 x2=903092574358267 x3=806961802724
x=710532117316769399313215266414 (when i=2)
x=111222333444555666777888999000000000000000042

The effort saved compared to a standard (non-CRT) implementation is by a factor at most (and near) $k^2$, if modular multiplication has cost $\mathcal O(n^2)$ for arguments of $n$ bits. The time saved can be higher, up to a factor at most (and near) $k^3$ if parallelization is used on $k$ independent modexp units.

It is critical to make a final check that $y\equiv x^e\pmod N$, and not disclose $x$ otherwise. If this precaution was not taken, the implementation would be vulnerable to the cardinal "Bellcore" fault attack: D. Boneh, R. A. DeMillo, R. Lipton; On the Importance of Eliminating Errors in Cryptographic Computations (in Journal of Cryptology 14(2), 2001; or there).

Implementations should be adequately protected from a variety of other attacks, including timing, power analysis, and other side-channel attacks.

The question also mentions encryption, where only the public key $(N,e)$ is known, not the factorization of $N$. Hence, for that RSA public-key operation (also used for signature verification), there is no similar shortcut applying to the computation $y\gets x^e\bmod N$. However, typically, that remains of low cost compared to the RSA private-key operation, because $e$ is small.


Is using quantum computing to break passwords non-sense? I understand the concept of 'trying all possibilities at once' but can anyone explain this with respect to the fact that my PC only accepts one password at a time? There's no input field that accepts all these possibilities and the same goes for the passphrase field in encryption... Why should we be afraid of quantum computers while being on conventional computer systems?

Well, the best answer I can think of is by referring you to Scott Aaronson's wonderful blog.

Quoting the very header of the blog:

  If you take just one piece of information from this blog:
  Quantum computers would not solve hard search problems
  instantaneously by simply trying all the possible solutions at once.

So no, a quantum computer would not try to input all passwords simultaneously to the password checker: as you correctly guessed, this would be nonsense. But a quantum computer can still use the intriguing properties of quantum mechanics to perform some computations which we have no idea how to do using a classical computer, such as using Shor's algorithm to factor a big number in polynomial time, which allows for example to break the RSA cryptosystem. So, if you are on a conventional computer system, you encrypt your password (or any other sensitive data) with RSA, and send it over the network, then you should be afraid if there are (scalable, etc) quantum computers available - for anyone with such a computer will just break the ciphertext in a short amount of time, recovering the sensitive information you had hidden inside. If the password is kept locally and an adversary tries to guess it to log to some service, then a quantum computer will not help him.


Hash and salt or salt and hash? People say "hash and salt", but aren't you supposed to salt password the first, and then hash it?

So that means its called "salt and hash" right?


Can a hard drive store clear text data that is physically impossible to retrieve? I'm trying to study how HSM and TPM works when storing secret data in clear text. How can they achieve physical impossibility in retrieving secret data?

I get the point in software, if you just have input and no outputs then it should be impossible through software to retrieve something.

But, I want to know the hardware (physics) part as well. How can an IC achieve physical impossibility to retrieve data? Let's assume the data is stored in an hard drive permanently.

The normal way is to keep secret data in volatile static RAM (i.e. 6 transistors per bit, like in current CPU caches, not with capacitors like in DRAM). When the power is cut, the data is gone in a matter of microseconds. The HSM contains a small battery to keep the RAM up and running for up to a few weeks. The battery also powers an array of sensors, e.g. on temperature, light, physical integrity of the covering and so on. If anything goes amiss, the system automatically shuts down the power, and the keys are gone.

So the trick, really, is not to store the data "in an hard drive, permanently".

An amusing consequence is that if an HSM is unpowered for too much time, the keys can be lost. Pro-tip: when you ship an HSM to a factory in China, label it as "a network card". Otherwise, customs will keep it around for a month, and the keys will be lost.

The above is valid for HSM and payment terminals. Smart cards, on the other hand, employ other tricks, which are undocumented (and most of them are trade secrets).


Please explain me why we require $2^m$ & $2^{\frac{m}{2}}$ random messages Assume that a one-way Hash function is secure and the best way to attack it is by using the brute force attack. It produces an $m$-bit output. Finding a message that hashes to a given hash value would require hashing $2^m$ random messages. Finding two messages that hash to the same value would only require hashing $2^{\frac{m}{2}}$ random messages.

I know only about birthday paradox involving 23 people. How do I relate the birthday paradox with this attack?

$2^m$ requirement is for the pre-image attack. You have to hash approximately  $2^m$ messages to find the message that has the same value you were looking for if the hash function has pre-image resistance.

In a collision attack, you are looking for two messages that have the same hash value.

If you look at Wikipedia Birthday Paradox at section Cast as a collision problem, it is also generalized for the arbitrary number of days not just for 365 days. The approximation is given by

$$n \approx \sqrt{2^m}$$ and we call it generic birthday attack.

Note that: if you find an attack which is faster than generic birthday attack like SHA-1 attack you will be famous.


What makes Quantum Cryptography secure? This is my current understanding of how Quantum Cryptography works: (The first bit is Quantum Key Distribution)
Alice sends a beam of photons to Bob through a quantum channel such as an optical fiber. Each of these photons represent a bit of information (0 or 1), and have been polarised in some way (rectilinear or diagonal). Bob uses a set of polarising filters (are these called bases?) combined with photon detectors to pick up these photons. If the polarised photon from Alice passes through its corresponding filter on Bob's end, he will receive the associated bit of the photon (0 or 1). If the photon passes through a wrong filter, it has a 50% probability of getting a 0 or 1. All the photons from Alice are passed through Bob's filters, and Bob obtains a string of 0s and 1s. He then communicates over the public channel to Alice what polarisers (the filters) he used, and Alice tells him which filters are correct. As a result, both parties have a sifted key.
[This is the "BB84" protocol of C. H. Bennett and G. Brassard: Quantum cryptography: Public key distribution and coin tossing, originally in proceedings of IEEE ICCSSP; 1984]

Image source: UNS Nice (France), Department of Physics
This next part I am not too sure about. It is my understanding that this new string of 0s and 1s (the sifted key) becomes a new parameter for the encryption and decryption algorithms, allowing communication between Alice and Bob. It is my understanding that in classical cryptography, Eve intercepts the encrypted message and using their computational power, tries to figure out the key.
So in this quantum version, what makes it more secure than the classical version? As in, why can't Eve intercept this encrypted message and as usual try to figure out the key (which is a string of 0s and 1s) like in classical cryptography?
If there is a problem in my understanding, or the question is ambiguously written, please notify me. I am looking for an answer as soon as possible.

TL;DR     The answer is classical cryptography.
Besides a quantum link, secure data communication with Quantum Cryptography (more precisely, Quantum Key Distribution) uses classical links, mathematically provable classical cryptography, and a setup procedure using initially trusted material just as in classical cryptography.
To perform the same, classical cryptography uses the one-time pad; or assumes a bound of the adversary's computing power and some unproven mathematical hypothesis. But assumptions may turn out wrong, and the risk exists that future progress allows decryption of archived intercepts. Pure quantum key distribution avoids that particular risk by instead relying only on physics when it comes to unproven assumptions.

Quantum Key Distribution (QKD) is now a subfield of Quantum Cryptography (QC), which also includes:

Post-Quantum Cryptography, exploring cryptographic methods usable on classical computers that will resist attack by Quantum Computers, should they become applicable to attack today's cryptography.
Quantum Random Number Generation, which aims at producing a demonstrably secure source of near-perfect random secret non-shared bits demonstrably rooted in some identified quantum physics phenomena; these are often used as RNGs in Quantum Key Distribution, and that's consistent.
Quantum Cryptanalysis, studying attacks of any kind of cryptography with a Quantum Computer, and attacks with any kind of device against Quantum Key Distribution or Quantum Random Number Generation.

The thought experiment in the seminal BB84 article quoted in the question can lead to practical QKD. I explain how and give links, but no math. That's out of ignorance on the quantum side, laziness on the information-theoretic side, and the 30000 characters limit as an excuse.

A. Issues prevent direct use of sifted bits
The question summarized only a subset of the article, and stops at obtaining sifted bits. These are squarely unsuitable for direct use, and do not achieve Quantum Key Distribution (QKD), for three main reasons:

Errors creep in the sifted bits

The many imperfections of the model (heavily simplified compared to the actual hardware and the known laws of quantum physics, even at the time the article was written) are such that, without Eve messing, sizably many sifted bits differ at Alice's and Bob's end. Sifted bits are thus unusable as key to a cipher, for decryption would likely fail.

The sifted bits are not nearly secret enough

An eavesdropper can gain sizable knowledge about the sifted bits. That makes them unacceptable for direct use as a keystream, for Eve's partial knowledge puts confidentiality in jeopardy. Quoting the article, the best assurance given by the quantum model of the adversary is only:

it can be shown that no measurement on a photon in transit, by an eavesdropper who is informed of the photon's original basis only after he has performed his measurement, can yield more than 1/2 expected bits of information about the key bit encoded by that photon

Who are these sifted bits shared with?

The first part of the article, and the question, assume the classical channels are

susceptible to eavesdropping but not to the injection or alteration of messages

Without such insurance, Alice and Bob would be unsure about who their sifted bits are really shared with! It could be that Eve rather than Bob is who receives Alice's photons and "communicates over the public channel to Alice", thus that Alice shares sifted bits with Eve. Bob faces a similar issue if Eve really is who sent him photons and "tells him which filters are correct". This allows a Man-in-the-Middle attack when data transmission time comes.

B. Classical cryptography rooted in information theory fixes them all

Secret-Key Reconciliation protocol remove errors, and more

Coding theory and error detection and correction are used to build a secure Secret-Key Reconciliation protocol additional to sifting, also running over the classical channels. Its objectives are to

remove or fix errors in the sifted bits, with bounded low odds of the contrary;
obtain an upper bound on the actual error rate, which is attributed to Eve spying the quantum channel;
obtain and minimize an upper bound on the information leaked by running the protocol over the classical channels, that Eve is assumed to scrutinize;
deduce a lower bound of what entropy (if any) remains in the rest; if there is less than some headroom, QKD failed.

Such reconciliation protocol can lose little-enough entropy as to be usable in practice, and be information-theoretically provable, but no simple such one is known. A most scrutinized milestone is the cascade protocol in Gilles Brassard and Louis Salvail's Secret-Key Reconciliation by Public Discussion, in proceedings of Eurocrypt 1993.

Privacy Amplification distillates a shared key

The entropy demonstrably remaining after reconciliation (if any) is distilled into bits with close to perfect entropy. A classical cryptographer would use a hash, but provable information theory has nothing to offer in that category. ID Quantique's 2020 whitepaper gives a rudimentary Privacy Amplification Protocol, but that's only for illustration.
Further, for use as an ever-flowing source of near-perfect random secret shared bits, it must be removed from the outcome enough bits to renew the setup key (see 3 below). Articles scrutinizing this circularity go under variations of the name Universally Composable Quantum Privacy Amplification.

Classical setup key and cryptography make the classical channels secure

The method proposed by the article is the most common:

Alice and Bob have agreed beforehand on a small secret key, which they use to create Wegman–Carter authentication tags

That's similar to the low-tech key ceremony of classical cryptography: Bob physically meets Alice, each throws a hex dice 20 times, and writes the outcomes as 20 characters, forming two lines on paper. Chemical carbon copy ensures Alice and Bob keep identical notes. They are sealed in two opaque tamper-evident envelopes to ensure secrecy until use. Bob protects his envelope while he gets back. Alternatively, Alice does the whole job, and a trusted courier hands Bob the envelope against signature.
For each of the two classic communication channels, the half of the setup key generated by the sender on that channel is used as the key to an information-theoretic Message Authentication Code (like Universal hashing of Mark N. Wegman, J. Lawrence Carter; New hash functions and their use in authentication and set equality, in Journal of Computer and System Sciences, 1981), computed over all the data sent on the channel for sieving and reconciliation. That MAC (one of the two "tags" in the article) is sent on the conventional channel it protects. The receiver can recompute and check it, and this gives demonstrably bounded odds of forgery. Our example's 80-bit half key demonstrably gives 40-bit security: better odds than one in a trillion against undetected forgery, which satisfies any rational person.
Setup key transfer must ensure integrity, but  it can be differed to a moment when secrecy is no longer required, like in classical asymmetric cryptography. However, setup key halves must then be conveyed separately in each direction, after reconciliation, but before the key established by QKD can be trusted. That's inconvenient, and common practice is to keep the setup key secret: ID Quantique's 2020 whitepaper states that it is made

use of a pre-established secret key in the emitter and the receiver, which is used to authenticate the communications on the classical channel. This initial secret key serves only to authenticate the first quantum cryptography session. After each session, part of the key produced is used to replace the previous authentication key.

Note: This did not cover a number of things needed for a working QKD, and possible pitfalls:

How does Bob conclude that a photon did not pass thru a polarizing beam splitter, which is an absence of event? If that's by timing, how do Alice and Bob get a common timing reference precise enough? At a coarser level, how do Bob and Alice agree on common indexing of expected photon events?
How much exploitable information leaks thru classical side-channels not accounted for in the reconciliation's estimate of remaining entropy, e.g., due to timing variations in the sifting or reconciliation protocol, varying light intensity, electromagnetic leakage, etc.?
How much other headroom is necessary for the test at end of reconciliation to robustly cover the imperfections of the quantum model, including those sneakily introduced by a creative adversary? How can it be safely arranged a retry should that test fail?
How is the setup key stored secretly in the QKD devices? How is it kept in synchronization under down-to-earth constraints like power failure?
Uncaught design errors or runtime faults (accidental or deliberate) in the implementation, which relies on conventional electronics, processors, and software, are possible pitfalls.

C. Quantum Cryptography from Quantum Key Distribution
Like conventional cryptography, quantum cryptography aims to transmit arbitrary data with confidentiality and integrity (underestood to include assurance of origin and destination). Each of these two goals can be reached in two ways, both using classical cryptography over classical channels, using the outcome of Quantum Key Distribution as key:

Provably secure conventional cryptography rooted in information theory

The One Time Pad (or an essentially equivalent variant) for confidentiality, using the random bits of QKD as keystream.

Security relies heavily on the quality of the Privacy Amplification of B.2, and on the soundness of the insurance given by the Secret-Key Reconciliation protocol of B.1. Throughput is bounded by the sift rate diminished by what's eaten by the tasks in B.
An information-theoretic message authentication code for integrity and origin, keyed from the QKD flow, as in B.3 above. That tolerates small imperfections in Privacy Amplification.

Conventional symmetric cryptography without mathematical proof

Some symmetric cipher for confidentiality, regularly re-keyed using the keystream of QKD. That's the only method to boost an otherwise insufficient rate of QKD. Also, it adequately mitigates small imperfections after Privacy Amplification.

A typical choice is the block cipher AES-256, perhaps with an operating mode like CTR. That's pragmatic and makes a lot of sense: AES-256 is rubber-stamped by civilians and military, is largely conjectured adequately secure from brute force attack for decades including using quantum computers, and against side-channel attack assuming regular key change with classical key derivation, which QKD can supplement or replace.

Some standard Message Authentication Code for integrity, e.g., HMAC-SHA-512, probably regularly keyed from the QKD; giving up on using an information-theoretic MAC could make sense when reusing a commercial classical cryptography device without modification.

Authenticated encryption (perhaps AES-GCM), which is a modern way to integrate a symmetric cipher and a standard MAC.

The above techniques are believed secure, or even mathematically provable for those of C.1. The technically difficult points are the prior QKD, and correct implementation as for conventionally applied cryptography: Random Number Generator, side channels and fault attacks, integration in a protocol...

D. Operational constraints of Quantum Cryptography
There are severe limitations to QKD, at least as widely available:

Incompatibility with network gear along the fiber (standard optical amplifiers or other standard repeaters as used in long fiber cables, switches, and routers directing data to the right user). Solutions exist only at the laboratory level. Commercial offers are restricted to point-to-point communication, or/and use conventional cryptography beyond that.
Small range, and (when not assisted by conventional cryptography not mathematically proven) low bandwidth, with a compromise between the two. For example, the Cerberis3 QKD System is specified for 1.4 kbit/s over 50 km, and less at the maximum range of 75 km. For direct line-of-sight ground-satellite by night, a 2017 paper reports ~12 kbit/s at 645 km to ~1 kbit/s at 1200 km. In lab conditions with supercooled photon detector it is reported

If we want pure QKD, it is lost the convenience of Public-Key Infrastructure based on digital certificates issued by certification authoritie(s).
No interoperability between vendors (closest I could find is Toshiba's call for arms towards that, in a Feb. 2017 newsletter).
No extensive data on operational availability of QKD links are available, especially under varying temperatures; it is reasonable to fear low Mean Time Between Failure for some parts, e.g., photon detectors after temperature cycling.
To my knowledge, no device employing QKD has obtained so far (Aug 2017) a public security certification covering QKD. Fact-checking this datasheet for a "Certified Common Criteria & FIPS 140-2 Level 3" product with "Support for QKD" available as an upgrade, I conclude the only quantum-related feature covered by certificates is an RNG, and the FIPS 140-2 security policy's only mention of QKD is:

The Quantum Key Channel serial port connects to a separately available ID Quantiqe (sic) Cerberus quantum key distribution server (not a supported FIPS140-2 Level 3 mode of operation under this certification).

E. Security of Quantum and conventional cryptography

How Quantum Key Distribution implementations fail

The security of QKD is rooted in parts of cryptography that are mathematically proven secure; and a physical model of how photons (possibly other quantum physics objects) behave per modern physical theory, which exquisitely matches experimental results and allows theoretical proofs.
However, a large fraction of particle physics and electromagnetism, and all of gravity/relativity, is typically brushed aside from the analysis; and the hypothesis of proofs do not fully model the equipment used, which has allowed some credible attacks, like phase-remapping.
Worst, adversaries think outside of the box and actively modify the quantum experiment so that the model is no longer a close fit. Like Eve blinds the photon detector! Quoting Lars Lydersen, Carlos Wiechers, Christoffer Wittmann, Dominique Elser, Johannes Skaar, and Vadim Makarov: Hacking commercial quantum cryptography systems by tailored bright illumination, in Nature Photonics Letter 2010:

we demonstrate how two commercial QKD systems id3110 Clavis2 and QPN 5505, from the commercial vendor's ID Quantique and MagiQ Technologies, can be fully
cracked. We show experimentally that Eve can blind the gated detectors in the QKD systems using bright illumination, thereby converting them into classical, linear detectors. The detectors are then fully controlled by classical laser pulses superimposed over the bright continuous-wave (c.w.) illumination. Remarkably, the detectors exactly measure what is dictated by Eve.

A joint 2010 press release with the company whose QKD device was hacked mentions that it was

developed and tested a countermeasure. [..] “Testing is a necessary step to validate a new security technology and the fact that this process is applied today to quantum cryptography is a sign of maturity for this technology,” explains [..] CEO of [..company..]

That's an arms race, similar to what has been ongoing for 40 years in Smart Cards, often used nowadays for convenient cryptographic key distribution. Eve has blueprints for other attacks:

inducing Alice to make errors by blinding her side rather than Bob's;
probe the (assumed random and secret) orientation of Alice and/or Bob polarizers by remotely sending photons (perhaps entangled, and with whatever characteristic best fits the job) in-between the individual photons sent (typically regularly) by Alice;
predicting Alice's or Bob's RNG from the earlier output (to reach the record rates reported in D.2, several gigabit/second of assumed perfect randomness are consumed by Alice; that's hundreds of times more than common quantum sources);
classical TEMPEST information leaks or induced-faults targeting the state of the quantum gear, the current setup key, or the QKD outcome.

Quantum and Classical assumptions compared

Conventional cryptography achieves the equivalent of QDK only by relying on some mathematically unproven hypothesis. For symmetric (secret-key) cryptography, that can be broadly described as the hardness of solving some combinatorial problem. Further, asymmetric (public-key) cryptography is required for turning a channel with integrity into one with confidentiality (something QKD can do), and that relies on the hardness of solving some other problem; examples include integer factorization, discrete logarithm, or RLWE.
There is wide consensus, but no mathematical proof, that (ignoring implementation issues) current conventional cryptography is currently secure; and that symmetric cryptography needs at most a doubling of the key size to become secure against future quantum computers hypothetically usable for problems of cryptographic interest. Which key size is required for which of the various problems used in asymmetric cryptography is an active research topic.
The security of QKD relies on physical hypothesis, where the security of conventional cryptography relies on mathematical hypothesis. Both kinds of hypotheses are not mathematically proven. But both are firmly established (at least when we restrict conventional cryptography to its symmetric branch). Any insecurity (beyond, inevitably, the humans involved) is likely to lie elsewhere: oversimplified theoretical model, undetected mistakes, or backdoors in the implementation. The complexity of QKD makes these mishaps more likely.

Quantum Key Distribution's strongest point

QKD gives insurance that classical cryptography does not. Arguably, if a data transfer protected by QKD is secure when it takes place, and uses only mathematically proven cryptography, then no future progress will decipher that data. The argument is that even if the photons sent on the quantum channel could be stored (a trick that has been pulled) at the time of the communication in hope of decryption in the future, the photons would not reach the quantum receptor, QKD would fail (with high insurance), actual data encryption would not occur, and the data would be safe.
By contrast, the channels of classical cryptography can be passively eavesdropped on and stored for hypothetical future decryption using superior technology. That's reasonable: even perfect forward secrecy won't resit a break of the symmetric cipher. Intercepts kept from the past that used a well-documented cipher with less than about 100-bit key are decipherable today with enough resources, 3DES (64-bit block, 111-bit key) will likely succumb, AES-128 can assuming mere stability of technical progress, AES-192 too if further assuming quantum computers usable for cryptanalysis, AES-256 also if we stop wondering about how and when.

F. Use cases for commercial Quantum Cryptography
The justified scientific recognition and the press coverage of QKD/QC helps sales, and is enough for targeting some markets:

Experimental study of QKD/QC, which is of high scientific and educational value from both experimental quantum physics and applied cryptography/cryptanalysis/auditing/hacking perspectives.
A segment of the computer security market: purchase-decision-makers in quest of prestige, reassurance, or theatrical effect. Quantum can be to crypto what gold is to audio, and silver to bullet.
The funneling out of money for a plausible cause. Expensive security equipment is good at that, usefulness is secondary, unconventionality no obstacle: see ADE 651.
Cover for a backdoor. QKD equipment is sold to supply keys for the encryption of sensitive data. Knowing an easily exploitable vulnerability in the QKD implementation (e.g., leak of the shared key on classical channels, perhaps subtly by timing variation in sifting or reconciliation, accidentally or deliberately) can break an otherwise secure encrypted link.
Cover for a trojan. QKD equipment has reasons to be in a secure perimeter. Its cabinet is thus ideal to physically sneak-in a microphone, camera, spy gadget, or side-channel attack device (being physically connected to the targeted security equipment helps immensely).

It is harder to find a security problem that today's QKD can solve (and penetrate the bulk of the market); many conditions must be met:

The confidentiality of some data to be transferred from point to point is of vital importance (at time of transfer, or later).
And the One Time Pad (which has successfully been used in that situation) is not an option; perhaps the means that must transport the shared key of QKD with at least integrity won't transfer a 1TB memory stick full of randomness with integrity and confidentiality, or the data of vital importance is larger than 1TB; see Johny Mnemonic.
And QKD is left usable despite D.1, D.2 (excluding the bandwidth issue which is adequately taken care of by C.2), D.4, D.5, and D.6.

Assuming the above, then it is rational to think about using commercial QKD as a supplement to classical cryptography; fortunately, we are not bound to choose between the two and can get the best of both worlds on security, when it is acceptable to get the worst on availability.
Classical cryptography featuring perfect forward secrecy and robust cipher with large block and the key is widely available. On the communication link it uses, it can be inserted an independently sourced commercial QKD equipment, of course with independently managed setup keys for each of the two encryption means as in any sound use of multiple encryption. An auditor can ensure confidentiality is at least as good as without QKD by merely ruling out a trojan (see F.5), for a fee. Perhaps the reduction in simplicity and assurance of working on D-day is worth the price and added confidence in long term confidentiality; however, tarnished it is by the use of classical cryptography without mathematical proof to reach acceptable throughput.
But it would be entirely irrational to rely solely on QKD, given its immaturity, unconvincing security argument against adversaries not bound by the narrow physical hypothesis made, deep complexity when we account for the arsenal of classical cryptography necessary to make it work at all, the tainted security track record for these reasons, poor auditability and recognition by practitioners, and the requirement for the same inconvenient setup key management as classical cryptography.

Operational summary
Quantum Key Distribution (a subfield of Quantum Cryptography) in principle performs the same tasks, and uses the same operational procedures as conventional cryptography, with no operational simplification whatsoever. In particular, the need for initially trusted material established by inconvenient human means remains.
QKD relies on physics rather than mathematics when it comes to an unproven hypothesis. That's a remarkable achievement and paradigm shift. But if that's a benefit, it is intangible and did not help QKD get a clean security track record, much less be widely recognized as useful by practitioners.
Integration of QKD in current networks is utterly impractical: QKD currently requires a dedicated fiber with a practical range limit ≪500 km, or direct line of sight with no sunlight, rain, or fog. That can only be extended with trusted facilities at each intermediary endpoint. Practical throughput is low, except when supplemented by conventional cryptography (then losing some of the aforementioned intangible benefits).
Commercial QKD equipment is complex, in part because it relies heavily on many classical mathematically provable cryptographic techniques. It is expensive, big, power-hungry, in low demand and stock, of unproven field reliability, seldom used in practice, and not recognized by security certification authorities.
QKD removes the risk that future technological progress allows compromise of intercepts made earlier. It is worth consideration in complement (not replacement) of carefully vetted classical cryptography with independent secure setup procedure, for data which confidentiality is of utmost importance (especially if that's for decades), if we trust couriers for setup keys but not for the one-time pads traditionally used for perfect secrecy in that situation.


Figuring out seed/internal state from HMAC-MD5 output Here is the scenario i'm imagining, I use the python random library to generate x-bit key that I use to generate a HMAC-MD5 output. Every HMAC-MD5 has uses a different random number as its key.

My question is if I can get a large number of HMAC-MD5 output, is there anyway I can figure out the internal state being used by the random function or the module itself?

If you could do that, then you could publish a paper about how you did it in a top-tier cryptography journal!

Currently, MD5 remains unbroken against preimage attacks.  Even if the underlying compression function turned out not to be a PRF, which would render moot the standard security reduction of the PRF-security of HMAC over a Merkle–Damgård hash function like MD5 to the PRF-security of the underlying compression function, it would be a remarkable feat to actually recover the key.

You have a much better bet trying to guess the state of the Python random number generator, which is probably the notoriously bad Mersenne twister.  Finding how to do that is left as an exercise for the reader!


NIST HMAC Test vectors I am searching test vectors of the HMAC-SHA256 primitive to verify the correctness of an implementation.

Without hesitation I go on the NIST website to see what they offer.

While reading the corresponding file (HMAC.rsp from hmactestvectors.zip) I can see that  the given test vectors associated to the SHA256 hash function are computed with different key sizes: $40$, $45$, $64$ and $70$ (in bytes).

I was a little surprised about this because according to the RFC 4868, the key used should be composed of $32$ bytes:

  While no fixed key length    is specified in [HMAC], this
  specification requires that when used as    an
  integrity/authentication algorithm, a fixed key length equal to    the
  output length of the hash functions MUST be supported, and key lengths other than the output length of the associated hash function MUST NOT be supported.

On the other hand, I read:

  However cryptographic keys (for symmetric algorithms like HMAC) longer
  than 128 bits don't really add security, so there is no actual need to
  go to a full block-length key

(see What are requirements for HMAC secret key?)

That's why these test vectors are getting me confused:

According to the RFC mentioned above, the key used should be a $256$-bit key.
It seems that most of the time, HMAC is computed with a $128$-bit key.

But NIST test vectors are using longer keys than the output length (ie $256$ bits because SHA256 is used). Still according to RFC 4868:

  key lengths less than the output length decrease security strength,
  and keys longer than the output length do not significantly increase
  security strength

So why did the NIST use these key sizes to compute their test vectors? Is it because HMAC algorithm is mainly based on a hash function and it's this feature that requires special assessment? There is also this document which specifies the procedures involved in validating implementations of HMAC but I don't see anything that justify the choice of the key sizes.

To verify the implementation in question is it possible to find other test vectors? Can I consider that if the ones given in RFC 4868 are verified then it's well implemented?

RFC4868 is not the HMAC RFC, which is actually RFC 2104. 4868 refers to the use of HMAC within IPSEC, which is why there is a key length restriction.

The maximum length key that can be used internally with HMAC-SHA256 is equal to the block size, 64 bytes or 512 bits. This can be useful in cases where the key is not full entropy such as the shared secret generated by a Diffie-Hellman key exchange; an ECDH secret of 512 bits has around 256-bits of security.

If the key length exceeds the block length, it must be first hashed to get it to fit within the block, this is the reason for the 70 byte test value, to make sure that implementations can properly handle it. The other lengths in the NIST vectors are one equal to the block length, and 2 arbitrarily shorter lengths. If an implementation can handle all 4 test values, it is generally safe to assume it can handle a 32-byte key as well.


How to calculate bit strength of Integer Factorization Cryptography (IFC) such as RSA using Python I would like to know how to calculate the bit-strength of Integer Factorization Cryptography (IFC) such as RSA by using Python. I gathered it is based off the complexity of factorizing the modulus (public key). I want to be able to calculate the bit strength of arbitrary key-lengths of RSA for example, such as 4096 which is not given by NIST etc.

This is similar to this question Security strength of RSA in relation with the modulus size, where the answer is provided by using Mathematica.

The fastest publicly known algorithm for factoring is the General Number Field Sieve (GNFS). This has the complexity defined in L-notation. The formulae includes little-o 1, which I'm not sure how to fit into the calculations, in the Mathematica example it is left out (treated as being equal to 1).

Here is the relevant Mathematica code:

  I generated these numbers with the following Mathematica code:

({#, N@Log2@g[#]} &) /@ {1024, 2048, 3072, 7680, 15360}

  where g is defined as:

g[b_] := Exp[(64/9 * Log[2^b])^(1/3) * (Log[Log[2^b]])^(2/3)]

If I understand correctly taking log2 of the exp would cancel out, so the result it's equivalent to just:(64/9 * Log[2^b])^(1/3) * (Log[Log[2^b]])^(2/3).

I have tried the following Python code but it seems to be way off.

import fractions
import math

ln = math.log

n = pow(2, 1024)  ## change for other RSA key-sizes

a = fractions.Fraction(1,3)
c = pow(fractions.Fraction(64,9), fractions.Fraction(1,3))
# c = 1.9229994270765445

def g(a, c, n):
  return math.exp(c * pow(ln(n), a) * pow(ln(ln(n)), 1 - a))

x = g(a, c, n)
# x = 1.3158442944491604e+26
s = ln(x)
# s = 60.1416909264604

The result for 1024 is 60.14, whereas NIST says 80, and Mathematica got 86.77. The results for other key-sizes are all way off.

This is the results from Mathematica (3rd column) which are very close to NIST (1st column).

Strength  RSA modulus size   Complexity bit-length
  80        1024              86.76611925028119
 112        2048              116.8838132958159
 128        3072              138.7362808527251
 192        7680              203.01873594417665
 256       15360              269.38477262128384

My results from my Python code are (10243, 60.14), (2048, 81.02), (3072, 96.16), etc.

I thought maybe this is due to rounding errors, but using WolfRamAlpha (I don't have Mathematica which is why I'm trying to use Python instead) I get the same results as Python.

This is what I put into WolfRamAlpha:

(64/9 * Log[2^1024])^(1/3) * (Log[Log[2^1024]])^(2/3)

Decimal result is 60.14169092646040456.... Pretty much same as my Python code. How did NIST and referenced answer get such different results. My code looks equivalent to me. I don't see my mistake.

What am I doing wrong?

(From comment so question can be closed properly)

log2 is log base 2. $log(exp(x))$ would cancel, but $log2(exp(x))$ is x times 1.44270 approximately, which gives the expected results


security of multiplicative secret sharing I was having a read of this question: "Is multiplicative secret sharing secure?"
posted in 2013 which asks if the simple multiplicative scheme is secure.
Everyone agreed that it was information theoretic secure, however I am not so sure that this is the case. In particular, if the secret is 0 then does that not mean that a participant's share is 0? If this is the case than a participant with a share of 0 instantly knows the secret is 0.

Am i missing something here?

And is this the correct way to post this or would I be better off leaving a comment on the post in question?

There is no 0 in the multiplicative group $\mathbb{Z}_p^*$. By the definition of a group, every element must have an inverse. Thus, the unity in a multiplicative group is 1 and there is no 0.


How to find the public key in RSA? Finding the public key given the private key $d$ and the prime numbers $p$ and $q$.

$$p = 3092551601$$

$$q = 3490383433$$

$$d = 10719928016004921607$$

Since this is RSA, here is my thinking.

In order to find the public key $e$ it must satisfy this equation

$$d\cdot e=1 \mod \varphi(n)$$
Since I am looking for $e$,
$$(e \cdot 10719928016004921607) \mod 10794190867245091200=1$$
However, after this step is where I am lost.

I tried using basic mathematics but it gives me the inverse of $d$. Plus, I don't think that using brute force is the right way to learn or understand this question.

You indeed need the inverse of $d$, but it's the so-called modular (multiplicative) inverse.

This can be done with the Extended Euclidean algorithm. You basically compute the greatest common divisor of $d$ and $\varphi(n)$ (you know already that it's going to be 1) and use the intermediate results to get the value of $e$.

The following simple Java program implements this algorithm, prints the result ($e = 8601051999309708343$) and proves it's indeed the multiplicative inverse (modulo $\varphi(n)$ of $d$.

List<BigInteger> q = new ArrayList<>(), r = new ArrayList<>(), s = new ArrayList<>(), t = new ArrayList<>();
q.add(BigInteger.ZERO);
r.add(new BigInteger("10719928016004921607"));
r.add(new BigInteger("10794190867245091200"));
s.add(BigInteger.ONE);
s.add(BigInteger.ZERO);
t.add(BigInteger.ZERO);
t.add(BigInteger.ONE);
int i = 0;
do {
    i++;
    BigInteger[] results = r.get(i - 1).divideAndRemainder(r.get(i));
    q.add(results[0]);
    r.add(results[1]);
    if (results[1].compareTo(BigInteger.ZERO) == 0) {
        break;
    }
    s.add(s.get(i - 1).subtract(q.get(i).multiply(s.get(i))));
    t.add(t.get(i - 1).subtract(q.get(i).multiply(t.get(i))));
} while (true);

BigInteger lastS = s.get(s.size() - 1);
System.out.println(lastS.mod(r.get(1)) + ", " + lastS.multiply(r.get(0)).mod(r.get(1)));

It takes 15 steps to get to this result, it's rather hard to do that by hand.


Why is ElGamalEngine in bouncy castle restricting input data to be less than the length of the group parameter p? I am currently using the ElGamalEngine of bouncy castle to implement exponential ElGamal for the purpose of making ElGamal additively homomorphic. To do this i raise the message to be encrypted to the generator g and modulo it with the group parameter p, like this:

private BigInteger g;
private BigInteger p;

public BigInteger raiseGenerator(long message)
{
    return g.modPow(BigInteger.valueOf(message), p);
}

In non-exponential ElGamal i would encrypt message, but to make it exponential i encrypt g^message%p. I use the following values of g and p:

private static BigInteger g512 = new BigInteger("153d5d6172adb43045b68ae8e1de1070b6137005686d29d3d73a7749199681ee5b212c9b96bfdcfa5b20cd5e3fd2044895d609cf9b410b7a0f12ca1cb9a428cc", 16);
private static BigInteger p512 = new BigInteger("9494fec095f3b85ee286542b3836fc81a5dd0a0349b4c239dd38744d488cf8e31db8bcb7d33b41abb9e5a33cca9144b1cef332c94bf0573bf047a3aca98cdf3b", 16);

With some values of message I get org.bouncycastle.crypto.DataLengthException: input too large for ElGamal cipher.

The reason this exception is raised is because of the following condition in the processBlock function of ElGamalEngine in bouncy castle.

if (input.bitLength() >= p.bitLength())
{
    throw new DataLengthException("input too large for ElGamal cipher.\n");
}

This is the same p as shown in the code above. The input can obviously have the same bit length as p because g^m%p can have almost the same numerical size as p and therefore also the same bit length.

Why is the input data restricted this way?

As an additional question: Is it possible to make ElGamal exponential using bouncy castle?

Originally we had restrictions like this in place as the alternative was emails about bugs in ciphers like RSA resulting from people not understanding the implications of modular arithmetic (if you are going to push right to the boundary you really have to understand what's going on). Having said that, I actually think we'd outgrown this by the time ElGamal appeared (around BC 1.12).

Oh dear, looks like there's another test further down. Perhaps partially outgrown would be a better way of putting this.

Okay, this is now fixed and checked in it should appear on github shortly.


encrypting data signals using the time variations between two independent coupling functions There was a recent article about a new encryption technique that encrypts "using the time variations between two independent coupling functions".

What is this technique they are referring to?

I found the paper.

At a glance, this seems to be a solution in search of a problem. Unless I've missed something, there is essentially no attempt in their paper to cryptanalyze such a construct. Nor do they appear to build upon, relate to, or even reference any preexisting concepts in modern cryptography or information theory such as computational indistinguishability or semantic security.

They also highlight some "advantages" of their system that, to someone with moderate familiarity of cryptography, seem pointless. For instance, statements like

  It results in an unbounded number of encryption key possibilities...

are indicators that the authors aren't familiar with the actual threats facing current cryptosystems. The entire space of 256-bit keys will never be enumerated in the lifespan of the universe, assuming our current understanding of information theory and physics are even remotely accurate. Nobody is clamoring for new cryptosystems with arbitrarily-large keys.

In my (admittedly non-expert) opinion, I find it highly implausible that any widely-used cryptosystem will ever be built upon the ideas in this paper.