What motivated the creation of RSA and ECDH?

What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure?

The New Directions In Cryptography paper introduced the idea of public-key cryptography (though it had been proposed by Merkle before), and public-key cryptography was intended to solve two major problems: The key distribution problem, and the problem of authentication which is now referred to as "digital signatures".

Besides the general excitement of an entire new field of research being opened up, one of the motivations for RSA was to define a primitive that solved both problems of key distribution (or public-key encryption) as well as digital signatures. This is actually easy to see from just the title of the original RSA paper: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems".

Their paper explicitly states this (emphasis mine):

  ... This method provides an implementation of a “public-key cryptosystem,” an elegant concept invented by Diffie and Hellman. Their article motivated our research, since they presented the concept but not any practical implementation of such a system.

Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure?

So as you can see, the answer to this question is "no" - it was simply a matter of accomplishing the feat at all, in general. The question of a given amount of security for a given amount of efficiency doesn't arise until after you at least have working examples of the concept.

Or was it because it was designed for other purposes which couldn't be accomplished with Diffie-Hellman?

As shown in the previous quotation, yes. Though, the world would later develop techniques that allow public-key encryption and digital signatures without requiring a trapdoor function/permutation.

As for the second part of your question, this other answer attempts to go into detail.

But basically, Diffie-Hellman works (as in correctness is guaranteed) for any finite cyclic group, (only a semigroup is actually required as inverses and identities are not used). There are generic attacks that apply irrespective of the actual group that you use, but for a given group there might exist attacks that are more efficient than the generic attacks. In finite field Diffie-Hellman (e.g. classic or "regular" Diffie-Hellman) there are non-generic attacks that do not apply or not known to have equivalents in the elliptic curve setting.


What is an impure NIST true random number generator?

The NIST source you link to is SP 800-90B. If you look at the other two publications in the series: 90A and 90C, you can find explanations of how you can use a TRNG to instantiate a DRBG or requirements on how to condition the entropy.

Here is what section 7.1 of 90A says about entropy input to a DRBG:

  Ideally, the entropy input will have full entropy; however, the DRBG mechanisms have been specified to allow for some bias in the entropy input by allowing the length of the entropy input to be longer than the required amount of entropy (expressed in bits). The entropy input can be defined to be a variable length (within limits), as well as fixed length.

So you can use a TRNG with 50% entropy rate to initialize a DRBG, you just need a longer input.

90C defines the assumptions more exactly in section 4.2:

  An entropy source output string containing $2n$ bits of entropy can be conditioned into a string of $n$ bits that contains full entropy output1 using an approved conditioning function, where $n$ is the length of the output block of the approved derivation function (see SP 800-90B). Note that in SP 800-90C, a derivation function2 is used as a conditioning function.
  A DRBG that has been instantiated at a given security_strength can be used to produce security_strength/2 bits of full entropy output if constructed as specified herein.

The approved conditioning functions are listed in 90B, after the section you quote. Anything else would fall under non-approved, but something sufficiently standard would be fine if you do not mind diverging from what NIST says.

So a half-entropy TRNG is very useful. You just need to take the entropy rate into account when using it.


PBEWithHmacSHA512AndAES_128 and AES Modes like GCM

Why the byte [] of key is 9 bytes? (When I give input as Pree@2017 the
  key generated is 9 bytes - I have check the length of
  pbeKey.getEncoded() and its 9.

The length of "Pree@2017" is 9 chars.
The reason why you are getting the original password is described here

  When you generate a SecretKey using the SecretKeyFactory
  PBEWithHmacSHA256AndAES_128 you will get an instance of
  com.sun.crypto.provider.PBEKey and this class has the "special
  feature" that it returns the original "key" (aka password) when
  calling getEncoded() and not the cryptographic key material. If I
  understand it correctly the key derivation will not be made by the
  KeyFactory but by the Cipher itself.

  Therefore you should not try to convert the SecretKey instance into a
  SecretKeySpec instance; instead just use the generated SecretKey
  instance in the correct cipher instance:

Cipher c = Cipher.getInstance("PBEWithHmacSHA256AndAES_128");
c.init(Cipher.ENCRYPT_MODE, secretKey);


Lagrange Interpolation for finite field GF(2^8), for Secret Reconstruction

I now see your problem; it's more fundamental than what my previous answer assumed.  You state:

Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case

where you interpret "should work" as "coming up with the exact same answer".
Actually, that's not the case.  Your original example appears to be designed in the infinite field $Q$ (or some superfield); you then use the exact same shares, reinterpret them as $GF(2^8)$ points (in some unspecified representation), and then are confused that answers you get aren't precisely the same.
$Q$ and $GF(2^8)$ are both fields, but they are about as unlike as fields can get.  For example:

$2+2=4$  (in the field $Q$)
$2+2=0$  (in the field $GF(2^8)$)
$3 \times 3 = 9$  (in the field $Q$)
$3 \times 3 = 5$  (in the field $GF(2^8)$, in the most common representation)

Your original shares $(1, 17)$, $(2, 34)$, $(3, 61)$ were computed in $Q$; if they were computed in $GF(2^8)$, they would have lhad different values.  Therefore, it is not suprising that if you reconstruct them in a field other than what they were computed in, you'll come up with a different answer.  I recomputed your shares using the original polynomial (assuming a polynomial representation of $GF(2^8)$), and came up with the values $(1, 13)$, $(2, 26)$, $(3, 29)$
To test your code, you'll need to come up with your own shares, computing in the field you're using to reconstruct.
(You'll also need to fix up your multiplication logic, in case one of the shares happen to be the value 0)


Public key homomorphic encryption based on secret key homomorphic

What you found out is really close to the result you want. In fact, your $SOMETHING$ will be $m_1R_2+m_2R_1+R_1R_2$.

The only missing step is giving out an encryption of $SOMETHING$ as the first component of your ciphertext.

In order to do so, notice that you can easily multiply $a_1$ by $b_2$, since $b_2$ is a bit:
$a_1 \times b_2 = a_1$ if $b_2 = 1$, and $0$ otherwise. (this $0$ can be computed as $a_1⊕a_1$, and $b_2$ is a public value)

Now, $a_1 \times b_2$ encrypts $m_2 R_1 + R_1 R_2$. By symmetry, you can remove $a_2 \times b_1$ that encrypts $m_1 R_2 + R_1 R_2$.

Finally, notice that $a_1 \times a_2$ encrypts $R_1R_2$.

We are now ready to give $a_1\times b_2 + a_2\times b_1 - a_1 \times a_2$ which encrypts $m_2R_1+R_1R_2+m_1R_2+R_1R_2-R_1R_2=SOMETHING$.

Your final homomorphic multiplication for your public key scheme is thus:

$$(a_1,b_1)\times(a_2,b_2) = (a_1\times b_2 + a_2\times b_1 - a_1 \times a_2,\, b_1 \times b_2)$$


Can repeatedly encrypting a message with a secure cipher ever produce the original input like what happens in ROT13?

If the ciphertext is the same size as the plaintext, then yes with 100% probability.
There are only finitely many values the ciphertext can take. So repeatedly encrypting the ciphertext, means that a value must repeat eventually. If this cycle doesn't include the original message, then there is some ciphertext that has an ambiguous decryption (because two plaintexts encrypt to it). Since we know this isn't the case, the original message must be in the cycle.

You can easily tweak this argument to ignore padding (just take the padded message as your original message).
If the encryption scheme requires an IV/nonce, then this argument only applies if you reuse the same IV for each encryption, in other words, after the first encryption, the ciphertext size is constant.
I highly doubt there's a way to show this with an authenticated encryption scheme.


When adding two points on an elliptic curve, why flip over the x-axis?

If we did not make the final reflection, point multiplication would not be associative, we would not have a group, and we thus could not define a scalar multiplication the way we do, with the property $n\cdot A+m\cdot A=(n+m)\cdot A$ .

If operation $+$ is a group law, the operation $\boxplus$ defined on that group by $A\boxplus B=-(A+B)$ (which is what removing the reflection does) is generally not associative, because $$(A\boxplus B)\boxplus C=-(-(A+B)+C)=A+B-C,$$ while $$A\boxplus(B\boxplus C)=-(A-(B+C))=-A+B+C.$$ The only groups where $\boxplus$ is associative are those with 1 or 2 elements.

Associativity of point addition on an elliptic curve in fact is a non-trivial and fragile property. Messing with how we do point addition in almost any way (changing sign as proposed, using a curve with a different equation like an astroid..) breaks that property.

Comments by entrop-x and Rosie F provide an intuitive explanation: if three points $A$, $B$, $C$ on the curve are such that "point addition of $A$ and $B$ without final reflection yields $C=A\boxplus B$", then that statement holds for all 6 permutations of $A$, $B$ and $C$, and it can be reworded as "$A$, $B$ and $C$ are collinear" without consideration of the order of the points. In a group with law $+$, the simplest relation between 3 variables with that invariance under order is: $A+B+C=0$, and then we have $A+B=-C=-(A\boxplus B)$ (where the $-$ sign designates taking the opposite for law $+$ ), hence the final reflection to change $\boxplus$ into a group law $+$.

That intuitive explanation can be extended to justify that full point multiplication is associative!


why do files downloaded with http and https have the same size?

[After your edit I can confirm that the browser does the whole encryption in the background - you only get the "normal" HTTP connection to see and the downloaded files appear as big as the unencrypted files - even if the encrypted files are only marginally bigger. You don't ever see the encrypted version without some addition work. You can use a secure connection like a normal one.]

Here a explanation why the exchanged data is slightly bigger than with unsecured connections: Ciphertext is mostly only slightly larger than the plaintext, not a significant part if the plaintext is already pretty large. At first (with for example TLS) we create a session which exchanges some data to authenticates the connection and generate a secure session key. This takes not much bytes, maybe a kilobyte. After that only a IV (ca. 16 bytes) and the padding (ca. 1 to 16 bytes) needs to be exchanged - only below ca. 4 percent size increase with 1 kilobyte exchanged plaintext. With bigger file sizes this will be even lower.


Is $E′(k,m)=E(0^n,m)$ semantically secure?

The algorithm $E'(m)=E'(k,m)=E(0^n,m)$ is defined with a hard-coded key, thus the key is part of the algorithm definition of $E'$.

Because of Kerckhoff's principle we generally assume the attacker to know our algorithm definition.

Because of this, the attacker can just try decrypting the challenge ciphertexts of the eavesdropper security game himself (or try encrypting the challenge messages himself if encryption is deterministic).

The choice of the messages $0^n$ and $1^n$ is entirely arbitrary and any message would suit the purpose here with these two having the advantage of the shortest possible description (instead of something like $0^{n-1}||1$).


Considering a key of 128bit and a message of 128bit, is it possible to recover the key (e.g. if the message is all zeros)?

Yes, but only by brute-force. That is when given a $(m,\tau)$ message-tag pair for a deterministic MAC (such as CMAC), you can always brute-force the key $k$ to get $\tau=\operatorname{MAC}_k(m)$. However with keyspace $\mathcal K$, this will take $|\mathcal K|/2$ MAC calls on average, which is $2^{127}$ evaluations which are usually assumed to be infeasible.

  Which is the suggested minimum message length compared to the key length?

There is no minimum message length. In fact, quite the opposite is true, MAC security degrades with message length. However, short messages may be more susceptible to replay attacks, but it's the task of the higher-level protocol to deal with them.

  Do you suggest some requirements in order to avoid forgery attacks?

The security bound for CMAC as a MAC is

  $$\mathbf{Adv}^{\textsf{MAC}}_{\operatorname{CMAC}(\pi)}(\mathcal A;q,ln)\leq \frac1{2^n}+\mathbf{Adv}^{\textsf{PRP}}_\pi(\mathcal B;\sigma)+\frac{2.5(\sigma+1)^2+1.5q^2+2q^2l^2}{2^n}$$

for an adversary, $\mathcal A$ making $q$ signature queries each of length at most $ln$ bits - with $n$ being the block size of the underlying block cipher $\pi$ - resulting in a total of at most $\sigma$ different evaluations of the block cipher $\pi$.

$\mathbf{Adv}^{\textsf{MAC}}_{\operatorname{CMAC}(\pi)}(\mathcal A;q,ln)$ is the chance that an adversary $\mathcal A$ can forge a tag for a message where they did not query the signing oracle beforehand and using at most $q$ queries each of length at most $ln$ bits.

$\mathbf{Adv}^{\textsf{PRP}}_\pi(\mathcal B;\sigma)$ is the probability that the block cipher $\pi$ can be distinguished from a random permutation using $\sigma$ encryption queries.  This bound was proven (written slightly differently) in "Formal Security Proof of CMAC and Its Variants" by Baritel-Ruet, Dupressoir, Fouque, and Grégoire in 2018 (PDF).


What is the more accurate way of stating the correctness of a PK encryption scheme?

Deciding among a or b is a matter of choice of definition of public-key encryption. Clearly a is desirable, and b is a fallback in order to allow some interesting cryptosystems. The definition is chosen according to the cryptosystem studied, as in c.
As pointed by poncho in comment, in b as it stands, the meaning is that for all keys and messages, there's negligible probability that decryption does not yield the original message. The encryption algorithm is re-expressed as a deterministic algorithm with an extra input $r$ for the random allowing to achieve CPA security, and it's really meant that
$$\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m, r))=m]\quad=\quad1 - \operatorname{negl}(k)$$
where the probability is computed over all inputs $r$ randomizing the encryption. Such tolerance for rare failures is necessary for some cryptosystems, e.g. those based on Hidden Field Equations.
There is at least one other popular alternative to b: we can require that all except vanishingly few keys allow certain encryption and decryption of all messages $m\in M$. We thus compute the probability that there exists a message $m$ and random input $r$ making encryption/decryption fail over the set of keys produced by $\operatorname{Gen}(1^k)$ (or even more precisely, over the set of random inputs to that algorithm re-expressed as a deterministic one with random input $r$). That's the definition of public-key encryption given by Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography 2nd edition. Their rationale is allowing RSA with a probabilistic prime test. They explicitly choose to ignore the exceptions.
Update: in IMC 3rd edition, that changed slightly. The probability is computed over the randomness of $\operatorname{Gen}$ and $\operatorname{Enc}$. I think it will stick as the standard definition of public-key encryption.
Yet other cryptosystems are correct with a only, e.g. RSA with proven primes, or ECIES when working with families of curves and generators of proven order.


Which hash algorithms are suitable for use with Elliptic-curve cryptography

You really have two questions, and so I'll try to address both of them; it appears that your question really is the second one, but the answer to the first one will illuminate the second one:

  The reason of my confused is why this code use [a hash function] to hash a message? is there any reason for that?

Well, we use some public key transform to transform 'the message' and the 'private key' into 'a signature'; however this transform takes input of fixed size.  That is, it cannot handle a message longer than expected (and this is pretty much true for all signature algorithms: Elliptic Curve signature algorithms, RSA, postquantum signature algorithms).

Now, we may want to sign documents considerably larger than the maximum that the raw public key operation can handle.  The internal parts of ECDSA with P256 can handle only 256 bits at a time, quite often, we want to sign something that's larger than 32 bytes.  To handle this, what we do is send the actual message through a 'hash function', that is, a transform that converts our long message into a fixed length (which the raw public key operation can handle).  We hash the message, and then hand that hash to the ECDSA internal logic.  Then, to verify a signature, the verifier hands the message it has to the same hashing logic, computes the hash, and then hands that hash to the ECDSA verification logic.

By the above description, there are a couple of things which are apparent:

The hashing logic must be public; after all, the verifier (which we can assume has the public key, but no secret knowledge) must be able to compute it.
The hash must be 'collision resistant'; that is, it should be infeasible (that is, no one can do it) to find two different messages that hash to the same value.  After all, if someone could find two messages $\text{Good Message}$ and $\text{Evil Message}$ that hash to the same value, he could take $\text{Good Message}$, convince the signer to generate a signature for it (which he might, as the message is benign), and then that signature would also be a valid signature for $\text{Evil Message}$ (because the signature only depends on the hash, and those two messages hash to the same value).

  is why this code use 'sha256' algorithm?  is there any hash algorithm customized or preferred to use with ECC?

No, there is no specialized hash algorithm for ECC.  If you look through the criteria I gave for hash functions, there's nothing specific to the public key method.  A hash function that is good for RSA will also be good for ECC.

We have a number of functions that appear to be good hash functions; SHA256 is one of them, and that happens to be want they picked.


Encrypting a TCP connection between two unknown nodes

What you are looking for is how to implement an SSL/TLS layer on top of your TCP connection. Try to use the OpenSSL library, it's the most popular implementation.


Can Diffie-Hellman generate values in a specified range?

The only values we can obtain from Diffie-Hellman are values between $0$ and a prime number.

So, if i want $255$, i can use $251$ or $257$ and work with those. This is what is called the prime modulus. Then we have the generator, that is a primitive square root of the prime modulus. This value only is the primitive square root if after doing all the maths we obtain all the values from $0$ to $251$, if we use the prime modulus of $251$.

This is the way we compute the square primitive root.

  If $p$ is prime, then $b$ is a primitive root for $p$ if the powers of $b$ include all of the residue classes mod $p$.

So, $x$ being any number, $11^x \mod 251$ equals to any number between $0$ and $251$. If we used the $257$ we need to see what if the primitive square root of this value, and substitute the $11$.


Can I break a random number into two smaller vectors and consider them as two random numbers?

Yes you can.

Suppose that you have a pseudorandom generator that, on some seed $s$, outputs $n$ pseudorandom bits, where $n$ is even. Then on a uniformly random input seed $s$, prg$(s) = r$ can be written $r_1 + 2^{n/2}r_2$, with $(r_1,r_2) \in (\{0,1\}^{n/2})^2$. I claim that both $r_1$ and $r_2$ are computationally indistinguishable from uniformly random elements from $\{0,1\}^{n/2}$.

The intuition behind this is as follows: suppose toward contradiction that some polynomial size algorithm can distinguish $r_1$ from random, when $r_1$ is computed as the $n/2$ least significant bits of prg$(s) = r$, for a uniformly random $s$. Now, you are given an $n$-bit string $r$ and must tell whether it is random or it is the output of the PRG. Just decompose $r = r_1 + 2^{n/2}r_2$, and run your distinguisher on input $r_1$: if it tells you that $r_1$ is non-random, then $r$ is non-random (as the distribution of uniformly random $n$-bit numbers is perfectly equal to the distribution obtained by picking two uniformly random $n/2$-bit numbers $r_1,r_2$ and computing $r$ as $r_1 + 2^{n/2}r_2$), hence you can distinguish outputs of the PRG on random seeds from random $n$-bit values, contradicting the fact that the PRG is cryptographically secure. The same argument shows that $r_2$ cannot be distinguished from random.

More generally, fix any size-$k$ subset $S$ of $\{1, \cdots, n\}$, for some $k \leq n$; a similar argument shows that the $k$-bit string obtained by running a secure prg on a random seed, and taking the $k$ bits of the output indexed by $S$, is computationally indistinguishable from random (and the distinguishing advantage of any polytime adversary is at most equal to its distinguishing advantage against the PRG). You can have a bunch of random-looking bit strings just by considering any partition of the bits of your PRG output.


What are the advantages of CBC over ECB?

The reason why CBC is considered better than ECB has nothing to do with situations involving an attacker with a partial ciphertext; we always assume that any attacker has full access to the ciphertext.

Instead, the problem with ECB is that it leaks information.  Specifically, if you encrypt two messages which has two blocks of plaintexts in common, then with ECB mode the corresponding ciphertext blocks will be the same.  The attacker can see that, and can immediately deduce the relationship between the plaintext blocks; even if this doesn't give him immediate information about what the plaintext block might be, it tells him something about the plaintext, and that something is more than what we'd like to give him.

This doesn't happen with CBC mode; the previous ciphertext block (or IV) is effectively random (and independent of the plaintext block), and so what is presented to the block cipher is an effectively random string; a collision there is no more likely than it would be if we were encrypting random blocks.

Here is a famous example of this; here is the original image, the image encrypted in ECB mode, and the image encrypted in CBC mode:

As you can see, you can still visually see the image in the ECB mode encryption (it helps that the image is a cartoon, and so there are large areas with the exact same color); you can't see anything in the CBC mode encryption.

Now, if we were encrypting random blocks of data, it turns out ECB mode actually does work out; with random data, you are quite unlikely to run into the exact same block of data twice, and so this 'leaking when two blocks are the same' is not an issue.  However, in the real world, we often encrypt things that are quite nonrandom; we need our cryptosystem to be able to deal with it.


Can NORX32-f be used in a Salsa20 style stream cipher?

NORX's $F^l$ is meant to behave as a random permutation (modulo some known harmless properties), given enough rounds. $F^l$ is similar to the ChaCha double-round in all but the addition operation, which is replaced by $H$, and the rotation constants.

NORX should be usable in a Salsa20/ChaCha-style mode; a break in that mode would likely spell trouble for the NORX sponge mode as well. Note that the last step, adding in the initial state, can be simply done with xor; no need to use $H$ in there. Since you lose authentication by using this mode, the cost of an independent MAC should also be taken into account.

Another option to improve NORX32's performance would be to use the parallel mode. With, say, $8$ lanes you could use AVX2 to compute all of them simultaneously. Since NORX suffers from being a purely sequential mode, this would improve performance by a factor of 2 or more. This would not, however, be an 'official' CAESAR-submitted mode.

That being said, I cannot recommend using the NORX permutation in these modes, nor can I recommend using NORX in any form whatsoever just yet. This is a cryptographic primitive in its infancy, and its strong security should not be assumed.


Is it possible that a SHA256 hash has the same hex character over and over again?

First of all, the output of SHA-256 is binary and consists of 32 bytes (256 denotes the output size in bits). What you are talking about is apparently the hexadecimal encoding of these bytes.
The possibility that you are talking about is called (1st) pre-image resistance (Wikipedia):

Given a hash value $h$, it should be difficult to find any message $m$ such that $h = \text{H}(m)$.

("difficult" is a non-technical term here, generally we use "computationally infeasible", obviously there will be messages that map to any hash value, the difficulty is finding them for a one-way hash)
No, the algorithms do not check this explicitly, because the algorithm by itself needs to be resistant against it. Furthermore, the repetition of certain bits is not that special all by itself. It would be unclear what you would need to test for.
"But would that also be possible practically" well, no, unless SHA-2 gets broken. Generally it is collision resistance that gets broken first. That means finding a hash where $\text{H}(m) = \text{H}(m')$ for any $m$ and $m'$. This is easier to attack because an attacker can try and find weaknesses in the algorithm that create an internal collision while controlling both $m$ and $m'$. SHA-256 is still considered secure in this regard.


What does Keccak being "efficiently invertible" mean?

What does "efficiently invertible" mean in this case? It isn't reversible (as in decryption), so what else could that mean?

Why is Keccak invertible? Is it by design or did they not bother as it's not important?

If you look closely, you will see it does not claim that Keccak is efficiently invertible, it says that Keccak-f is efficiently invertible.
Keccak-f is the function used to mix the internal state in the sponge construction.
Since it is a permutation, it is invertible. If you have the entire state, you can apply the inverse permutation to go backwards to the previous state.
Since the hash function does not output the entire state as the hash output, an adversary may not perform this operation when given the hash output to find the preimage, so it's not a problem for Keccak-f to be invertible (though there may be more subtle differences when using a permutation versus a function to mix the state).
So efficiently invertible means the same thing that it usually does.
As for why the designers chose it, you would probably need to ask them to get a definitive answer. It is not difficult to ensure that a function is an invertible permutation, as long as each step is invertible the entire function will be.


A secure function evaluation problem and an alternative of 1 out of n oblivious transfer?

The problem is known in the literature as private function evaluation (PFE). A sender has input (a function) $f$; a receiver has input $x$, and only the receiver learns $f(x)$.

If you are willing to leak the topology of a circuit that computes $f$ (but not the identity of the gates), then using classical garbled circuits / Yao's protocol will work. These garbled circuit constructions are known to hide the gate functionality. You just can't use the latest optimizations in garbled circuits (starting from free-XOR) since they leak which gates compute XOR and which don't.

If you are willing to leak (an upper bound on) the # of gates in a circuit that computes $f$, then you can do standard SFE of a universal circuit. A universal circuit $U$ takes as input the description of a circuit $C$, and an input $x$, and outputs $U(C,x) = C(x)$. To allow $C$ to have $n$ gates, the size of $U$ must be at least $\Omega(n \log n)$. A construction achieving that size was described by Valiant, but it is apparently a very complicated construction. There is a simpler construction of size $O(n \log^2 n)$ with quite small constants by Kolesnikov & Schneider.

Leslie Valiant: Universal circuits (preliminary report), STOC 1976
Vlad Kolesnikov & Thomas Schneider: A Practical Universal Circuit Construction and Secure Evaluation of Private Functions, Financial Cryptography 2008

There are some more recent approaches for PFE by Mohassel and Sadeghian that avoid universal circuits and have linear cost $O(n)$. As above, the protocol leaks the number of gates in the circuit computing $f$. I don't know about how these protocols stack up against universal-circuit protocols in practice. Besides the one below, there is also a followup work that achieve active security.

Payman Mohassel & Saaed Sadeghian: How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation, Eurocrypt 2013.

If you are willing to leak the fact that $f$ has some other special algebraic structure (e.g., it is a linear function) then there are certainly ways to exploit the structure for a more efficient solution.

Otherwise, if you are not willing to leak anything about $f$ then there is really nothing you can do better than 1-out-of-$n$ OT. If $f$ can be a totally random mapping, then there is no representation of $f$ that is significantly more concise than its truth table.


How is Diffle Hellman with RSA immune to man in the middle?

He [Ed: Eve] then sends his half to Alice signed and establishes a connection. Now Alice is communicating with Eve and Eve is decrypting the message and sending to Bob.

Eve can only sign with her own private key. So your attack only works if Alice accepts the signature from Eve. That means that:

Eve's public verification key needs to be trusted and
that Alice doesn't check that that public key belongs to the intended party, i.e. Bob.

Some kind of PKI is usually involved, and PKIX is the most common PKI. But you can establish trust by e.g. sending the public key and then validating the fingerprint of it over the phone. I'm not sure if you can call that a PKI because of the simplicity of the protocol and the lack of other participants.

So no, this is not the same as raw Diffie-Hellman - unless the necessary verification steps are missing, of course.


Ok, so now the question makes more sense to me.

Yes you are correct. Sadly, you cannot solve the problem without solving the DLP. This is simply because in the problem he didn't share his secret x or y. If he had shared y. You could have solved it. But your space is quite small, so it's not too hard to solve.

Public key = g^x = 7^x = 3 (mod 71)
Private key = x = 26 (since this is 7^26 == 3 mod 71) (DONT KNOW THIS)

C1 is :

C1 = g^y = 7^y = 59 (mod 71)
Private key = y = 3 (since this is 7^3 == 59 mod 71) (DONT KNOW THIS)

Message is mapped to:

m' = m mod 71
m' == 30 mod 71

Thus to find c2 you need:

c2 = m' * g^(xy)

But since you know neither x nor y you can't solve it. (of course the sample space was small so I could find it).

First find g^xy

g^(xy) = (g^x)^y = (3)^3 = 27

Your solution should thus be:

c2 == 30 * 27 (mod 71)
c2 == 29 (mod 71)

Hope that helps!


First, some notes on your choices of primitives:

AES-256: You don't need to use AES-256 unless the data you want to protect needs to remain confidential for more than 30 years
SHA-256 for authentication. Don't use plain SHA-256. Either use HMAC-SHA-256 using an encrypt-then-authenticate approach or (even better!) use AES-GCM or AES-EAX as your mode of choice as the two provide authenticated encryption (AE) and the likelihood of errors is much less.

Now to answer your questions:

If you store a key on both devices long-term-wise I think your questio means "How to securely transmit / negotiate a session key for authentication and encryption?". Well you could use ECDH to let both devices negotiate a key, but I assume this isn't possible in your case. In this case you simply generate a key at random, encrypt it using the long-term key and send it to the device, preferably using an AE mode, as you only have to manage one key then.
Who should generate a key? The one with access to the better randomness sources, usually this is the more powerful platform having more user interaction. (in your case the smartphone I think)
The answer on this depends on your situation. If the user-id is just some random number and if you're not too concerned with privacy of your users, you can send it in plain. If the user-id actually holds information (like a name) you could the connecting device send a nonce $N$ along with $Tag=H(N||ID||N)$. Then the device could try out all (4!) IDs and look for the match. This wouldn't expose the user-ids at any point in time in plain. If the user-id is low entropy and you want to protect it very hard, usage of a password hashing scheme (PHS, as function $H$ instead of SHA-256) may be an option to put more work effort to find the ID.
What you describe here is similar to the famous OTR protocol. To
perform the operation you need you'd simply use a key-based key derivation function (KBKDF/KDF) like HKDF. But be aware, as soon as the devices get out of sync (i.e. a message is lost), you'd need to renegotiate a new session. And note: using this approach doesn't provide forward-authenticity. Meaning if an old key get's stolen, all subsequent keys of the communication can be derived. In my eyes it's sufficient to use AES-GCM for the whole session and don't change with every message, as this means unneccessary performance overhead. You could simply renegotiate the connection every now and then to get a similar property.
Yes. Usually IVs are meant to be message-specific. This would result in you sending a new IV with every message. To avoid replay attacks you may also want to consider using message numbers.
If you do the setup as described at the beginning (using the password copied from the device to the phone) and you do already use authentication at this point, you're safe, assumed that the transmitted password wasn't intercepted, because an attacker can't fake the authentication tag. (excluding faking of the sender) He can't get the key on the receiving end, because this would mean he can decrypt the key, encrypted using the password which is impossible for any good password (random, 20 chars, lowercase, uppercase(, numbers))

I hope this answers your questions.


The two previous answers certainly solve the problem. Soundness of Geoffroy's protocol is fine indeed, but there is the appearance of the witness $x$ in the computation of the announcement $(A',B')$ as $B'=g^{r_x/x} h^r$. This can be avoided, however, and at the same time one can find the protocol maybe in a bit more natural way as follows.

Starting with $A=g^x h^y$ and $B=g^{1/x} h^z$, we see that $B$ is a Pedersen commitment
to the (multiplicative) inverse $1/x$ of the committed value $x$ in the Pedersen commitment $A$. So, $x$ appears both in $A$ and $B$ and these two occurrences need to be connected somehow. EQ-composition is a very effective way to accomplish this, but we cannot directly apply it to exponents of the form $x$ and $1/x$. A simple way out is to move $x$ around a bit in the equation for $B$ by raising both sides to the power of $x$, such that we get:
$$ A=g^x h^y,\qquad g=B^x h^{-zx}.$$
We can now apply EQ-composition to the factors $g^x$ and $B^x$, but one may wonder about the new factor $h^{-zx}$ which also depends on $x$. Fortunately, such a factor causes no problems because we can think of $h^{z'}=h^{-zx}$ as a factor that is independent of $x$; it's like replacing $z$ with $z'=-zx$, which is fine because this is a one-to-one transformation for nonzero $x$.

For the $\Sigma$-protocol we get:

Prover sends announcement $(a,b)=(g^u h^v, B^u h^w)$ with $u,v,w\in_R\mathbb{Z}_n$.
Verifier sends challenge $c\in_R\mathbb{Z}_n$.
Prover sends response $(r,s,t)=(u+c\,x, v+c\,y, w-c\,z\,x) \bmod n$. Verifier accepts if $g^r h^s = a A^c$ and $B^r h^t = b g^c$.

It is instructive to see why special soundness holds. So, let's consider two accepting conversations $(a,b;c;r,s,t)$ and $(a,b;c';r',s',t')$ with $c\neq c'$. Then we find:
$$\begin{array}{cl}
 &  g^r h^s = a A^c,\ g^{r'} h^{s'} = a A^{c'},\quad B^r h^t = b g^c,\ B^{r'} h^{t'} = b g^{c'}\\
 \Rightarrow& g^{r-r'} h^{s-s'} = A^{c-c'} ,\quad B^{r-r'} h^{t-t'} = g^{c-c'} \\
 \Leftrightarrow& A = g^{\frac{r-r'}{c-c'}} h^{\frac{s-s'}{c-c'}},\quad B = g^{\frac{c-c'}{r-r'}} h^{-\frac{t-t'}{r-r'}}.
\end{array}$$
Here, we are using that $r\neq r'$ holds as well: otherwise we see that $B^{r-r'} h^{t-t'} = g^{c-c'}$ is equivalent to $h^{t-t'} = g^{c-c'}$, and we would have $\log_g h = (t-t')/(c-c')$, contradicting the assumption that $\log_g h$ is unknown.
Hence, a witness is obtained as $x=(r-r')/(c-c')$, $y=(s-s')/(c-c')$, and $z=-(t-t')/(r-r')$.
Clearly, $x\neq0$ and $B=g^{1/x} h^z$ holds, as well as $A=g^x h^y$.

The same line of reasoning can be applied to show special soundness for Geoffroy's protocol.


Genuine encryption from only one source?

I think the solution to your problem is a digital signature as CodesInChaos pointed out. Here is how it would work:

When a user registers with your server they are given a token which will consist of (at a minimum) the user's id. The server also uses its private key to digitally sign the token (or more likely a hash of the token).

Now, say user1 and user2 have done this and now want to communicate. They each send their token and digital signature to the other user. They each take the token and signature that they received from the other user, and use the servers public key to verify that the signature was correct. If so they proceed to communicate.

There are some things you will want to think about before using this, however. You might want to kick people out of the network. That will require some additional work.


Computationaly hard detokenization algorithm for credit card numbers

I am assuming that the vault shall store arbitrary-length messages and associate with each message a token consisting of six decimal digits. Otherwise, as has been noted (see below), the problem is probably either impossible or trivial.

I interpret your requirements to mean that the detokenization algorithm is also available to an attacker that has gotten access to the vault, which means that the cost of detokenizing the entire vault is at most $nX$, where $n$ is the number of items stored in the vault and $X$ is the cost of detokenizing one index.

This means that the best you can do is to balance your $X$ such that $X$ is feasible, but $nX$ is economically infeasible. (Note that $n$ is very small, so it seems unlikely that $X$ cost can be feasible for you, but $nX$ cost infeasible for an attacker.)

(Note that if the vault's detokenization algorithm is not available to the attacker, your problem has a very simple solution using deterministic public key encryption: Encrypt the message using the detokenizer's public key. If you already have the ciphertext, you're done. Otherwise, pick a fresh index and store the index-ciphertext pair. The detokenizer simply decrypts the ciphertext. This is the best you can do unless the vault's tokenization algorithm also isn't available to the attacker, in which case everything is trivial.)

The system consists of an interactive algorithm $V$ and an algorithm $D$. The correctness requirement can then be stated as follows:

We can send $m$ to $V$, in which case $V$ responds with an integer $i$. As long as $V$ has been sent less than $10^6$ distinct messages, the following requirement is satisfied: For any $m'$ previously sent to $V$ to which $V$ replied with $i'$, then $i=i'$ if and only if $m=m'$.
We can send $i$ to $V$, in which case $V$ responds with $z$ or $\bot$. The response satisfies the following requirement: If $V$ previously replied with $i$ when sent message $m$, then $D$ will output $m$ on input of $z$, using expected time $X$.
We can send compromise to $V$, in which case $V$ responds with any secret keys it may have and a list $(i_1, z_1), (i_2, z_2), \dots, (i_n, z_n)$. If $V$ was sent the messages $m_1, m_2, \dots, m_k$ with replies $j_1,j_2, \dots, j_k$, then $k=n$, $i_1=j_1$, ..., $i_n=j_n$, and $D(z_i) = m_1$, $D(z_2) = m_2$, ..., $D(z_n) = m_n$.

The security requirement is the following:

If $V$ has been sent $n$ distinct messages, of which $k$ have been sent by the attacker (or can be predicted with reasonable effort) and the remaining $n-k$ are unpredictable to the attacker, then no adversary sending compromise to $V$ can recover the remaining $n-k$ messages with expected cost significantly smaller than $(n-k)X$.

The following scheme seems to satisfy these requirements. We need

a hash function $H$ (modeled as a random oracle),
a deterministic one-time symmetric encryption scheme $(\mathcal{E}, \mathcal{D})$, and
a large family of groups $\mathcal{G}$ such that we can efficiently sample a group $G$, a generator $g$ and a verifiably random element $y$ in the subgroup generated by $g$, such that $(G,g)$ are suitable for ElGamal encryption, and the best algorithm for computing logarithms smaller than $T$ in $G$ requires expected cost $\sqrt{T}$. (All reasonable assumptions.)

The interactive algorithm $V$ stores a list of tuples $(i, c, G, g, y, x, w)$:

On input of $m$ to $V$, let $K = H(m)$ and $c = \mathcal{E}(K,m)$. If $(i,c,-,-,-,-,-)$ is stored, respond with $i$ and stop. Otherwise sample fresh $i$. Sample $G$ from $\mathcal{G}$ as well as $g,y$, then choose random $r < X^2$. Compute $x = g^r$, $w=y^r K$. Store $(i, c, G, g, y, x, w)$.
On input of $i$ to $V$, if $(i, c, x, w)$ is stored, respond with $z = (c, G, g, y, x, w)$.
On input of compromise, respond with the entire list of tuples.

The algorithm $D$ on input of $(c, G, g, y, x, w)$ does:

Compute the discrete logarithm of $x$ to the base $g$. (Expected cost $X$.)
Compute $K = w y^{-r}$.
Compute $m = \mathcal{D}(K, c)$.
(Optional) Verify that $H(m) = K$.

This scheme is correct, and a five-minute analysis suggests that it also satisfies the security requirement. The only minor subtlety in the scheme is that every entry must have a fresh group, otherwise algorithms for computing many discrete logarithms in one group could allow the adversary to decrypt with expected time smaller than $(n-k)X$.

I would not actually use this scheme without a proper security analysis.

A few minor notes: The families of groups can be either based on finite fields or elliptic curves, where the latter would probably involve point counting and therefore be moderately expensive. In either case, naïve ElGamal is probably not the right scheme to use, some variant of DHIES or ECIES or something would be better.

You can make tokenization cost $T$ work as follows: Let $K' = H(m)$. Use $K'$ to generate an elliptic curve of prime order $\approx T^2$ and two verifiably random points $P$ and $Q$ on the curve. Compute the discrete logarithm $U = \log_P Q$. Then let $K = H(m,U)$. Another (simpler) option (as was pointed out in another answer) is to simply use an expensive hash function such as PBKDF2 or scrypt with appropriate parameters.


Why does bit padding work in practice in a message authentication code?

Bit padding is a padding that is always applied. So every possible message still has a canonical representation.

It is even possible to remove the padding always by removing all trailing zeros and the rightmost bit with value one.

For MAC calculation the unpadding is of course not used, but it shows that every message is still unique, even after the padding has been applied.

So if you have one message and you pad to a multiple of 8 bits (to make the example readable):

0000      -> pad -> 0000 1000

and a message that is identical to that padded message:

0000 1000 -> pad -> 0000 1000 1000 0000

as you can see the messages are still distinct after padding.


How to brute force sqlcipher encrypted file with MD5 hash of a 7 bit key?

As SEJPM already hinted at in his comment, a 7 bit key is short enough to allow a plain and simple brute-force attack because there are merely 128 different keys to be tested.

Hint: 7 bit = 1111111 = 127, + 1 for the 0000000 key = 128 possible keys.

Even when using a low-resource device, testing 128 different keys to find the correct one should be a pretty quick and easy task to handle.

If the key would be longer than that – for example: 7 bytes – the time to brute-force all keys would rise exponentially to the number of bits. Staying with the example: 7 bytes = 7 * 8 bits = 56 bits, which would mean that a plain brute-force attack would need to test up to a maximum of $2^{56}$ keys, boiling down to $7.2057594037927936e16$ (= 72,057,594,037,927,936) different passwords to check… which makes brute-forcing things rather infeasable compared to brute-forcing a simple 7 bit key.

For more information about brute-force attacks, you might want to check the Q&As listed under the brute-force-attack tag and/or read the related Wikipedia article.

How to…

Practically, you only need to create a list of all possible keys and try decrypting the ciphertext by going through that list one by one until the plaintext resembles/fits the decrypted file data you are expecting. (Since you haven’t mentioned what kind of file you are trying to decrypt, I assume you are able to compare a decryption result to see if the decrypted data indeed fits the expected plaintext.)

The steps are easy, no matter the programming or scripting language you use. In this case, you could even do this manually due to the fact that you’ld only need to test a maximum of 128 different keys:

ciphertext $\rightarrow$ decrypt using key with 7-bit-value0000000 (hex: 0x00)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, test next key.
ciphertext $\rightarrow$ decrypt using key with 7-bit-value0000001 (hex: 0x01)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, test next key.
ciphertext $\rightarrow$ decrypt using key with 7-bit-value0000010 (hex: 0x02)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, test next key.
…
ciphertext $\rightarrow$ decrypt using key with 7-bit-value1111111 (hex: 0x7F)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, either the correct decryption key is not 7 bit, or you made a mistake when creating the testing keys (Ask yourself: Are you sure you’re feeding 7-bit keys and not something else?), or you have simply missed the correct key and decryption result while comparing the decryption result with the plaintext you expect. After all, this is the maximum key value a 7 bit key can have.

That’s all there is to it.

EDIT

As you’ve updated your question and added the info that the 7-bit key is hashed using MD5… be sure not to test a pure 7-bit key but MD5(potential-key) instead. Besides that, it does not influence the approach I’ve described above.

Pseudo-code:

for(i=0;i<128;i++)
{
    t = sqlcipherDecrypt(ciphertext, MD5(potential-7-bit-key[i]));
    if(verifyDecryptionResult(t) === TRUE)
    {
        output("Found valid key:" + potential-7-bit-key[i]));
        exit;
    }
}

Where verifyDecryptionResult strongly depends on what file format you expect the plaintext to be. This function can bluntly be trying to open the decryption result with some program, or comparing the decryption result with already available plaintext, or alike functionality. Anything that helps you check if the decryption result fits what you’re looking for. Listing all options would be too broad, but this should help you grasp the general idea behind the pseudocode and how to brute-force things.


Breaking RSA with Factor in Range of $\sqrt{N}$

Although this might not be the solution you're looking for, the Coppersmith theorem offers a simple answer to this.
The (general) Coppersmith theorem states: let $f(x)$ be a monic univariate polynomial of degree $d$ with coefficients modulo a positive integer $n$. One can find all integers $x$ such that $|x| \le n^{\beta^2/d}$ and $\gcd(f(x), n) \ge n^{\beta}$ (or $f(x) = 0 \bmod b$, $b$ an unknown divisor of $n$ of size $\ge n^{\beta}$) in time polynomial in $\log n$ and $d$.
Now here we have $|p - \sqrt{n}| < n^{1/4}$. Setting $f(x) = x - \lfloor \sqrt{n} \rfloor$, this means that there is an $x_0$  bounded in absolute value by $n^{\left(1/2\right)^2} = n^{1/4}$ such that $\gcd(x_0 - \lfloor \sqrt{n} \rfloor, n) \ge n^{1/2}$ (that is, a factor of $n$), and such an $x_0$ can be found in polynomial time in $\log n$.


A similar observation as yours was the starting point for the ROCA attack. In 2016, some of the authors of the ROCA attack (with other coauthors) had published a paper a USENIX about determining the origin of RSA keys. Some SW-libraries or smart cards generate public RSA-keys with certain characteristics that allow to identify with high probability which library was used given in some cases just one and in other cases just few public RSA keys.

The five equations you found are for sure not enough to break a 1024-bit key. Your first two equations one can easily explain. Being odd is necessary. Having $N = 1\bmod 3$ can come from the fact that the implementor of the library chose to generate only primes that are $2\bmod 3$ (like I always do). The reason for this choice is that usually one first tests the prime candidate $q$ (after a pre-selection using trial division or a sieve or something more creative) with a Fermat test, before inverting $e \bmod q-1$. But if $q = 1\bmod 3$ and a public exponent $e$ is given that is a multiple of $3$ (some like $e=3$), then the inversion always fails, so that a Fermat test would have been a waste of time.

For your other three equations I cannot imagine any reason. So try to find other restrictions for the RSA-keys generated by your library. What you should look for is if for some other small primes $p$ not all values $\ne 0\bmod p$ are possible, and if maybe the set of possible values is a subgroup of the multiplicative group $\mod p$ (i.e., closed under multiplication $\bmod p$). If you find such subgroups for different primes $p_1$ and $p_2$, you should then take a look also at the values $\bmod (p_1\cdot p_2)$, and if there are more restrictions. If, for example, you see that only the values $\pm 1\bmod 7$ and $\pm 1\bmod 13$ show up, then check if all values are $\pm 1\bmod 91$ or if also $27\bmod 91$ and $64\bmod 77$ are possible (which would be worse for the attacker).

For a successful attack you would have to hope that the modulus $N$ is modulo some small primes in certain subgroups, because both primes lie in those subgroups. This does not have to be so (it's quite easy to generate RSA-keys that look like they are vulnerable to the ROCA attack, but are perfectly safe), but it is a reasonable assumption for the lack of any other reason for it.

For using Coppersmith's method one would need to know the value of one of the primes $q$ modulo a product $\Pi$ of small primes which has bitlength more than 256 (for 1024-bit modulus $N$), better at least 270. For $\Pi$ big enough, a simple application of Coppersmith takes less than a second, so one can try it for some billions of possible values of $q\bmod \Pi$ to factor $N$.

So Coppersmith's method allows to factor $N$ even if the remaining entropy for the prime $q$ is still $>100$ bit (this was verified in the certification of the Infineon key generation), as long the entropy of $q\bmod\Pi$ is low enough.


Looking to verify my understanding of RSA math

Some random comments:

  RSA's security is based on factoring primes.

Actually, it's based on the hardness of the RSA problem. It is still an open question whether its difficulty is equivalent to that of factoring.

  RSA works as follows. The ciphertext, c, is generated by raising p to the power e modulo n

At this stage, you probably don't want to go into the full details, but you should mention (perhaps in passing) that we never use 'textbook RSA' as you described, but when doing public key encryption, we perform 'padding' before doing the raw RSA operation.

You mentioned that you'll be covering OAEP later; you should give a few words to the effect that 'I'll cover this more fully later; this is a simplified version for now...'

  So encryption then is a matter of multiplying p by itself a certain number of times modulo n.

Not an issue with what you said, but (depending on the time) might want to discuss how we raise p to such enormous powers without taking an enormous amount of time; I believe that your audience should be able to follow that.

  To do this, we can use something called the totient of n, represented by $\Phi(n)$.

Actually, it is more typically represented by a lower case phi, that is, either $\phi(n)$ or $\varphi(n)$.

  To generate the public key (e), find a value of e such that the following is true:

I don't know if you want to go into these sorts of details; however it is more common in practice to select e first, and then select p and q such that $p, q \not\equiv 1 \pmod e$ (which will ensure (for prime e) that $\gcd( \phi(n), e ) = 1$)

Everything else would appear to be reasonable (if simplified...)


The programming aspect of this question should be asked on StackOverflow, but I suppose you can figure it out all on your own.

Yes, you need to generate ECC keypair if you want to use ECC algorithms. Every type of public-key cryptography suite require specifying algorithms, if your PGP keys are already using ECC algorithms (ECDH, ECIES, ECDSA), then you may reuse those depending on software support as not all libraries and apps support all formats (there are SSH, PKCS-PEM, PGP formats from what I know).

Also note that you should generate different keys for different purpose - don't reuse encryption key for digital signature and vice-versa.


Blowfish ECB mode: Tools for known-plaintext attack?

No, the most you can do is to compare ciphertext blocks for equality and link those blocks with identical plaintext. That ECB is used does not hurt the security of Blowfish by itself. Block ciphers should not be vulnerable to known plaintext attacks, and there seems to be no known attack on Blowfish in this regard.

To state it a bit more formally: that ECB is used or that plaintext is known does not make the cipher itself distinguishable from a random permutation; the repetition of ciphertext blocks only show that it likely is a permutation.

Obviously, brute forcing such a large key is out of the question. That there are attacks on 40 bit keys doesn't translate to keys over 64 bits let alone keys of more than 11 times the size.


Format of hybrid crypto envelope structure?

First, OpenPGP/GPG is not the only standard for hybrid encryption, often called enveloping. For files/messages there are also PKCS7/CMS and SMIME which are ASN.1 (plus MIME) based, XMLenc which is XML based, and JWE (JSON web encryption) which is JSON based. There are also several communication schemes (at least SSL/TLS, SSH, IPsec/IKE) which are not directly applicable here.

All of these are standards and one of the defining characteristics of a standard is that it is specified in the document(s) that specify the standard. For OpenPGP, the current standard is RFC4880 as could easily found for example in the wikipedia article which is one place someone with any initiative would look. (RFCs -- Internet 'request for comment' documents -- are actually available numerous other ways, which used to be important decades ago before the web. For more about RFCs see the wikipedia article.)

PGP's encrypted-data functionality is introduced/outlined in 2.1 (and 2.4) and recapitulated in 11.3. The core of the document is organized bottom-up: data elements and packet structure are defined in 3 and 4; specific packets are defined in 5 with pk-encrypted-key in 5.1 and old-style encrypted data in 5.7 and the new improved encrypted+MDC-data in 5.13; optional compressed-data is in 5.6 and 'armoring' in 6. Note that PGP uses a not-quite-standard mode of symmetric encryption, described in 5.7 and expanded in 13.9: CFB with IV of zeros but a nonce block prepended (which serves the same security function) and a 2-byte 'stutter' that provides a quick check for wrong key.

The main implementation (now) of OpenPGP is GnuPG which is opensource, but is a pretty big program. For learning only a small piece like this, if you know or are willing to learn Java, I recommend BouncyCastle which is also opensource and (IMHO) well-organized and coded (though not extensively commented) and being Java isn't cluttered by much of the housekeeping code needed in C or even C++. Either of those programs can also be used to create (example) messages for your code to read, or check/verify messages created by your code.

Added: since you are so intent on an example, here is one, using the 'new' (symm+MDC) format preferred by my pretty elderly GPG 2.0.14 so I don't have to bother finding the option(s?) to turn it off:

$ od -tx1 cry64585.enc
0000000 85 01 0c 03 8a 30 13 e2 06 1f b9 42 01 07 fe 22
0000020 1b 8c bd 1b d3 d7 92 72 42 ee 86 aa e6 9b e1 eb
0000040 bb bc 88 b8 48 93 bd 56 28 49 28 77 59 e9 9c 61
0000060 69 06 0a 6c 86 5e d4 c7 48 24 c1 c3 c7 7e ee aa
0000100 e4 e4 08 4d 8b 64 ce 46 3a 91 64 98 52 e1 71 bd
0000120 4f b7 64 c2 9a c0 a4 cd b2 33 6f 41 9f 4d 5d eb
0000140 5a 1d 76 b5 19 5f 11 d4 2e ea 0b 50 04 34 f9 ed
0000160 15 b0 ae 63 6b d4 1d ed 9f 2e c8 6c 4f c3 1a ab
0000200 2a 1b f7 13 39 ac 14 de 30 f7 00 0f ae 61 d7 c4
0000220 c1 cc b2 33 0f fc a8 c7 61 7f a9 f7 23 f7 18 e1
0000240 59 3c b9 a5 5f b6 fe b4 26 65 3e fb 40 43 c3 46
0000260 7d 2b 32 25 6c b7 e3 8d a4 32 fd 69 a9 dd 69 65
0000300 4f 95 55 f8 f9 dc f9 50 e1 4d fe 5c 4e be 68 6d
0000320 8f 4f a8 bb 1a 05 07 05 57 22 51 37 87 2e 54 af
0000340 1a 69 2d c6 af 03 78 9f 6c db 71 e4 38 f5 03 f6
0000360 dc 80 93 63 ce b9 bd 61 d2 7e d0 98 26 15 8c 40
0000400 e9 35 da 60 5c e5 6d 3a c8 5a 26 08 26 69 dc d2
0000420 40 01 8f ce 2c ff 95 a8 65 09 22 5d 2c 40 37 c9
0000440 ac b3 f4 64 f9 72 f1 c7 3c a5 91 46 9d a9 3f 73
0000460 39 9a 8d e2 cb 66 f7 1e a2 19 73 e1 77 e9 ab 0b
0000500 b2 91 96 0c 3d 3b 77 17 25 1d 8f ec 21 f2 0a 53
0000520 5a
0000521

The 0x10f bytes at offset zero are the pk-enc-sk packet (tag 1), and the 0x42 bytes at offset 0x10f = 0417 are the symm-mdc-data packet (tag 18).

As a bonus, here's the public key used to encrypt:

$ od -tx1 cry64585.pub
0000000 99 01 0d 04 59 3b a3 a5 01 08 00 c0 77 a2 45 43
0000020 79 91 7b 7e 7b 88 e3 2f f8 19 5a b0 6a e8 67 87
0000040 56 a3 11 96 d7 fd c5 e2 33 19 f6 9d d5 1a 48 08
0000060 38 29 71 0e 4f 98 56 e9 5d 5c 09 b0 d6 6c 92 51
0000100 33 d4 a5 65 df fd 05 57 e6 ea 32 a4 88 55 01 e4
0000120 9b 27 1e 68 8a 10 45 df 72 26 2c bd 8a d8 04 59
0000140 e7 a1 79 21 90 33 e0 b9 51 48 ab 31 04 7a 3a 61
0000160 a1 88 6a 7f 6b b4 d6 49 3d ae 40 80 f5 33 f0 5f
0000200 1c 7d ad 30 2e a8 e8 3b 24 8f ca a1 54 4c 3e eb
0000220 61 03 78 91 72 dd 36 7d da 3d 92 46 f3 ad 7c 7b
0000240 c7 39 ae f0 4e 51 fd fe dc 09 26 3f 9f b0 24 4d
0000260 f1 d5 aa f0 84 2e 18 77 a7 b2 7d 5c fa d6 2b ae
0000300 f3 55 5a f2 af c2 15 de 82 82 37 14 8f 9b 52 3b
0000320 dd 63 8e 21 53 f2 cb 6b bb 50 bd 0e 08 f6 44 eb
0000340 8a 2f 3f 15 32 1f e3 d4 32 3c 5c 23 dc 30 ea b4
0000360 0c 3e 1a 69 0d 82 6a 74 fc 2c 3e 3d 63 a8 d0 83
0000400 b7 3e 79 3a 0a 60 81 65 e2 94 17 00 11 01 00 01
0000420 b4 13 72 73 61 40 74 65 73 74 20 3c 72 73 61 40
0000440 74 65 73 74 3e 89 01 38 04 13 01 02 00 22 05 02
0000460 59 3b a3 a5 02 1b 03 06 0b 09 08 07 03 02 06 15
0000500 08 02 09 0a 0b 04 16 02 03 01 02 1e 01 02 17 80
0000520 00 0a 09 10 d1 d6 73 c6 3b ed f9 8f e2 e9 07 fd
0000540 1a 85 15 61 d4 af 7f b2 94 95 c3 c2 ca b1 eb 1a
0000560 80 31 cd bd ec 26 78 0f 0b 97 29 85 9e 92 27 1b
0000600 ad 3c 7e 3c 35 eb 59 f9 57 ce 94 9e 13 e4 d1 50
0000620 fd 82 0f 3a 1f e7 75 56 70 e3 40 bf b7 6a 00 5f
0000640 b6 e9 83 f6 ba f1 28 12 4f 10 d5 72 a3 de d1 06
0000660 90 91 b0 dd e0 f7 95 b3 be 94 9b 43 ea 56 86 d7
0000700 d4 c3 6b 66 b4 db ed 07 6a 8e b7 97 72 b2 b2 dc
0000720 b8 db 33 de a9 76 10 7e 81 ae ab f4 19 39 e7 40
0000740 86 d1 32 53 c2 c1 e4 e1 dd e5 fd c5 16 2d 76 8d
0000760 3b 31 3f b7 e4 b8 8f f9 8b 36 ae b3 67 32 6d 40
0001000 83 ee 88 3f 8c ca 63 2c 33 bb 7c 82 04 07 58 d8
0001020 40 5b ec 1a 85 58 32 88 df e0 a8 72 f8 cf 1d f8
0001040 30 86 ad 22 c6 44 17 b7 03 0b e3 f7 a6 d8 43 6c
0001060 39 ea c2 c9 b7 a3 22 09 9b 8b b8 3a ea a6 c2 77
0001100 3d 60 29 9c 4b 02 ea 27 94 b9 77 7a 60 0d af 85
0001120 42 91 7b 0d 02 f9 fc fc 59 81 d5 e4 6b c9 10 45
0001140 b9 01 0d 04 59 3b a3 a5 01 08 00 e4 4c 11 6e 79
0001160 1b 58 da d1 b9 4c c9 6f 4d bd bf ee d8 40 f9 a7
0001200 a1 0f 5d 3e 8d 35 40 d8 36 0f 08 be fd 9d 3a 1a
0001220 13 ea 8d 49 47 1f f1 bc 5a 9a f7 33 ea c8 1f 7a
0001240 41 81 47 52 46 0f 37 7d a6 41 92 ba 2a 4b a0 a5
0001260 dc 83 03 e5 5c 39 3c 96 4a 1a 6e 3c a8 1f 29 8a
0001300 9f 91 10 31 94 f6 e0 d2 b8 c3 e1 60 29 67 d0 26
0001320 13 86 61 17 5d 64 39 4d 00 14 98 1b 67 b8 d8 44
0001340 2e 22 72 a3 25 5c 90 6f 8c 89 a6 3c 97 89 b5 26
0001360 1d 01 2e f5 e5 1b 38 34 63 f7 04 20 2a ce ba 35
0001400 cd 30 f2 91 17 09 a4 e3 d1 ba f9 f6 09 b7 00 ef
0001420 a2 72 76 5b dc 2a c8 10 44 81 84 8a 36 41 79 17
0001440 07 fe 18 6e 79 da ce 3d e1 2d 7d 30 d7 25 31 27
0001460 7b ae 4c 74 d6 17 d4 1b c5 b3 51 61 7d 87 8e 4e
0001500 5a df 43 6a 3d 00 0c 0e 99 dd 98 68 60 b9 87 06
0001520 09 44 36 b7 49 99 56 b8 f3 ce 86 b7 8a 9c 28 e1
0001540 65 82 7a 27 6b 9d e9 ea c7 e8 fd 00 11 01 00 01
0001560 89 01 1f 04 18 01 02 00 09 05 02 59 3b a3 a5 02
0001600 1b 0c 00 0a 09 10 d1 d6 73 c6 3b ed f9 8f 66 8d
0001620 08 00 b4 39 f4 ed ee 3a 2b fe eb 7f 40 8a 22 96
0001640 5e cb af 92 fb f8 70 37 6f e4 84 b1 81 2f 38 05
0001660 f2 28 a9 1a b5 c4 e1 be 3c 3b 64 20 7c 6e 7a a7
0001700 60 b1 3d be 9a e3 7c 8d 61 31 27 f9 a0 e6 a1 e7
0001720 e0 49 12 d4 e5 b2 57 ca ca 51 22 4a 5f 81 0e e0
0001740 a0 c7 41 89 63 01 55 21 23 bf 41 ec 7b 03 d6 7a
0001760 3b e5 8e 80 4e 37 d5 ce be 1e ae f7 a2 7a 8e ec
0002000 b9 64 88 64 dd 1c 36 08 73 7f 0a be e2 7c 48 c9
0002020 ee 8a 9f 72 e7 69 9b 7a ea 4f 4c 0a 21 9a 2e 7c
0002040 5f a6 5f 28 9b 31 b5 b0 fd 46 07 9c 80 9a 24 b4
0002060 86 27 1d 23 12 cb 19 64 aa 4e 40 7f 90 4d f8 c9
0002100 c0 7f b7 c3 93 7f 29 dc df e6 11 4a 5a af 7a 41
0002120 f5 9c cd 17 f7 a2 56 7e b6 3e 80 91 70 e6 9d 3e
0002140 23 55 73 de f4 e7 78 bf 7f ea ed c3 ce ee 4d 77
0002160 05 c7 39 c5 a0 b8 bd 00 ff bf 48 20 e4 89 50 2a
0002200 3c 5d 39 c2 55 53 12 dc 3c be 79 65 55 f6 d6 c4
0002220 65 90
0002222

I don't see how this can possibly help you. If you think you will write a (correct) program that reproduces the above (message) output and compare, that won't work; properly designed encryption, including both the symmetric level and the public-key level (here RSA -- even the outdated RSAES-PKCS1-v1_5 aka block type 2 scheme used by PGP due to its age), is randomized precisely to prevent reproducing it.


Is AES-CBC mode not secure against chosen cipher-text attacks even if the IV is not predictable?

No, unpredictable IV won't solve the problem (cihpertext is malleable).

One example to demonstrate the insecurity:

in the CCA game, the adversary sends $m_0,m_1$ to the challenger, and  receive back the ciphertext $c=(r,s)=(r, E_k(r\oplus m_b)$), where $r$ is the random IV.

Then the adversary sends $c'=(r\oplus t,s)$ where $t$ is a random string.

The oracle will decrypts becausee $c'\ne c$, and the adversary now gets
$$
D_k(s)\oplus r\oplus t = D_{k}(E_k(r\oplus m_b))\oplus r\oplus t=m_b\oplus t
$$

The adversary then compute $m_b\oplus t \oplus t =m_b$ and can decide $b$ by comparing the result with the messages it sent.

One way to obtain CCA security is to use a message authentication code and the encrypt-then-mac procedure (authenticated encryption).


AES-GCM for Securing Bluetooth Low Energy Application

Using GCM with a long term fixed key is dangerous; if you repeat the nonce, you can leak the authentication piece.

Instead, what I would suggest is that you use AES-SIV instead.  It doesn't have the problems with repeating a nonce.  It is more complex, and slower, however it is far better suited if you have to use a long term key.


Yes, it can be decrypted easily because it will use DES (CBC) mode of operation. DES only has an effective key size of 56 bits. So the key and the can be brute forced regardless of the (PBKDF1) key derivation.

MD5, while considered broken by itself, is less of an issue when it is used within PBKDF1 - as long as the password contains enough entropy of course.

If possible you should upgrade to Password Based Encryption (PBE) using PBKDF2 and AES. Beware that PBE usually uses CBC mode encryption, so it is not suitable for transport protocols.


I have a program that uses a custom algorithm to encrypt a message

This algorithm is called a cipher. There are plenty well known ciphers that are considered secure. If you have a "custom cipher" then you're either using something of your own design. Using proprietary schemes is not recommended except for learning purposes.

  My program support multiple passes. How many iterations of these passes my program should do? Is there any ideal number in the crypto world? I have read a little about three pass protocol. Does that apply in this case?

Any modern cipher should be secure with one pass.

Most block ciphers already contain a high amount of rounds internally. If you use the same key you're basically just multiplying that amount. If a break is found for all rounds of the cipher then it probably breaks multiple passes as well.

If you want to consider choosing a number of rounds for your cipher then you need a key schedule and a way to connect the inner functions that use the sub-keys. Cipher design is a large topic of which entire books are written (such as "The Design of Rijndael", the cipher that became AES).

If the key needs to be used multiple times - in different ways - then the key can be split into sub-keys using a *key-schedule. The key schedule is internal to a cipher.

The three pass protocol doesn't seem to have anything to do with message encryption directly.

  Any issues or trade-offs can you think of with this type of approach?

Once you have a secure cipher then you can focus on the protocol and system rather than the cipher. There are plenty secure ciphers - such as AES / GCM for symmetric encryption or RSA in OAEP mode for public key encryption. The trick is to apply them well.

Note that stream ciphers or block ciphers in streaming mode may produce a key stream and XOR that with the plaintext. If you would apply those ciphers multiple times using the same key and IV then you would either completely negate encryption an even number of encryption attempts or only apply it once for an odd number of encryption attempts.

Check out how a one-time-pad works and try to apply the encryption twice to understand what I mean.

This also shows that we cannot advise how to construct multiple rounds within your cipher without understanding the design. For all we know, we could be destroying security rather than improving it.


I believe $\mathit{lHash} \mathbin\Vert \mathit{PS} \mathbin\Vert \mathrm{01}$ serves the rôle of the zero-padding in $s = (m \mathbin\Vert 0^{k_1}) \oplus G(r)$ from the formulation of RSAES-OAEP in the standard reference for its security reduction, on p. 5.  Verifying that it matches exactly what you intend is critical for the security reduction to work, in particular where it figures into Game 6 on p. 14, to provide the bounds involving $k_1$ in Theorem 1 on p. 9.

Using a label perhaps provides some kind of domain separation for different applications, in case, e.g., two application's entropy sources are both broken.


Is a zk-SNARK the hash of a Linear Interactive Proof?

The above figure illustrates the steps that one needs to take to design a zk-SNARK for an arithmetic circuit (computation). As you know, SNARK stands for Zero-Knowledge Succinct Non-interactive ARgument of Knowledge.

So to design a zk-SNARKs form LIP, first one needs to convert a LIP to a Linear Non-Interactive Proof (LNIP) system that can be done in two models including Random Oracle (RO) model and Common Reference String (CRS) model. In the RO model, one uses a hash function to remove the challenge phase (by taking hash of first message in a LIP) in a LIP, and in the CRS model there is a pre-processing (setup) phase which a third trusted party generates some common public parameters that prover and verifier use them to generate and verify a proof.

Once you converted a LIP to a LNIP, you can construct a (succinct) non-interactive argument of knowledge. A nice example can be found in https://eprint.iacr.org/2016/260 which contains the state-of-the-art QAP-based zk-SNARK.

I would recommend to look at Pinocchio zk-SNARK as well.


How can I formally verify fuzzy commitment scheme based security protocol?

This might not be the answer you are looking for, but as you are looking for a formal verification, I would advise you to take a look at Coq. Even though mainly used by Academics, it provides a logical framework and an interface to write formal and interactive proofs.

Based this language there exists some libraries dedicated to cryptographic proof :

CertiCrypt
EasyCrypt (tutorial)

Example of proof :

Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols
Formal certification of ElGamal encryption
Verification of a Cryptographic Primitive: SHA-256

PHD : Formal certification of game-based cryptographic proofs

Other formal tools (interactive provers) can be used such as Isabelle, Agda, Fstar and HOL.
And some more readings :

Computer Verification in Cryptography
Probabilistic Relational Verification for Cryptographic Implementations

Disclaimer: I use Coq on daily basis...


Elliptic ElGamal Public Key Cryptosystem doubt

In points of elliptic curve instead of $\frac {a}{b} $ you should use $a\cdot b^{-1} \pmod p$. Also: $$\sqrt3=\{i \in [0,12]|i^2=3 \pmod {13}\}=\{4,9\}$$  So $P=(6,4)$ or $P=(6,9)$ which $2\cdot P$ are $(10,8)$ and $(10,5)$ respectively. But your computation show that $2\cdot P=(12,\sqrt {23})$.

Also with $x=12$ we have't a solution for $y$ in your elliptic curve.


Can an attacker exploit the nonuniform distribution of letters in a diceware password to improve a brute force search?

But the attacker trying to break it as a normal password could assume that it is made up of English words and then they'd know that some letters and combinations of letters are more common.

They could try this, but they would be stupid to try this, because there are many fewer $N$-word diceware passwords than $M$-letter strings of English letters of the same length as an $N$-word diceware password!

Suppose you use a ten-word diceware password.  There are $7776^{10} \approx 8 \times 10^{38} \approx 2^{129.2}$ such passwords.  This is already a larger haystack than any adversary can find a single needle in.  (If passwords are hashed without salt, an extremely powerful adversary may be able to find one of many needles in a haystack that big, but you could pick $N = 20$ instead, and the service oughta salt their password hashes.)

Any distribution on sequences of $M$ independent English letters that covers more possibilities than these $7776^{10}$ diceware passwords is an even larger haystack to search for a needle in.

A smart adversary, who knows all the details of your method and just doesn't know the password you chose by that method, won't give themselves a larger haystack to search in.  A stupid adversary who does give themselves a larger haystack to search in will just waste more time searching!

For example, the distribution on $M$ independent English letters following the usual letter frequencies in English would give relatively high probability to sequences like aoqothropaaeeaetphtticawglesttgeectoyheldshnfznecr which has a lot of e's and t's and a's but not many z's, x's, q's, etc.  This is not a possible diceware password, however, even though it has the same length as a ten-word diceware password with five letters per word.  And it would give lower probability to woozydizzybuzzyfuzzyjazzymezzoexxonpizzapyrexvixen, which (with an appropriate word list) is a possible diceware password.

Let's work through a simplified example.  We'll use a dictionary of five words: cat, car, act, art, and rat.  We'll pick a single word uniformly at random from the dictionary, so that each word has equal probability 1/5, with just over two bits of entropy.

The corpus in this dictionary has letter frequencies a 5/15, c 3/15, r 3/15, t 4/15, under which distribution each letter position has under two bits of entropy.  There are $4^3 = 64$ possible three-letter words from this alphabet, of which the vast majority, 59, aren't in our dictionary.

An adversary trying to guess our password from the dictionary has a $1/5 = 20\%$ chance, of getting it right in a single trial.

This is the smartest, most efficient adversary.
An adversary trying to guess our password from the letter frequencies independently has a $\frac{1}{5}\cdot\frac{19}{225} = 19/1125 \approx 1.7\%$ chance of getting it right in a single trial.

Why?  The distribution on three-letter passwords is the product of the letter probabilities in this model.  If the adversary guesses a word in our dictionary this way, there's a 1/5 chance that it's the right password, but there's only a $19/225 \approx 8.5\%$ chance that the word the adversary guessed with these letter probabilities is in our dictionary.  With probability $206/225 \approx 91.5\%$, the adversary will be guessing passwords that you would never have chosen: they're wasting most of their time barking up the wrong trees in a much larger haystack.

This is the adversary who takes advantage of the per-letter entropy as you described.  Even if they sort by probability rather than choosing randomly, they'll first try aaa, then aac, then aat, aca, etc., wasting time on impossible passwords.  Even if every word in the dictionary happened to come first in this ordering, this adversary has no better chance than adversary (1).
An adversary trying to guess our password from the letters, ignoring the frequencies, has a $1/64 \approx 1.5\%$ chance of getting it right in a single trial.

Why?  Under this distribution, every letter has equal probability 1/4 independently, so every three-letter word has equal probability $(1/4)^3 = 1/64$, including the one we chose.  With probability $59/64 \approx 92\%$, the adversary will be guessing passwords that you would never have chosen.  They're also rummaging through a much larger haystack, but they're doing it even less efficiently than adversary (2).

This adversary just tries all combinations without regard to letter frequency.  As you can see, this adversary is slightly worse at the job than adversary (2), so knowledge of the letter frequencies helps a little bit, but they're both much worse at the job than adversary (1).

Every word you add, if drawn independently, multiplies these probabilities: pick a second word independently from the same dictionary, and adversary (1) now has $(1/25)^2 = 1/25 = 4\%$ chance of success, adversary (2) now has $(19/1125)^2 = 361/1265625 \approx .029\%$  chance of success, and adversary (3) now has $(1/64)^2 = 1/4096 \approx .024\%$ chance of success.  If you make the dictionary large enough and the sequence of words long enough that you defeat the smart adversary (1), then you also defeat the stupid adversaries (2) and (3).

  My question is, what $M$ do I need to make up the same entropy as the $N$ words?

Don't worry about $M$.  Pick $N = 10$ for diceware and you're all set.


Does ssl_rsa_with_rc4_128_md5 have known weaknesses?

In a purist cryptographic sense, there are many vulnerabilities in this cipher suite that can be (theoretically and practically) exploited. There are much stronger versions of SSL/TLS, and much stronger cipher suites that could be used.

In a practical sense, it's not the end of the world - there are far worse cipher suites (e.g. those using intentionally weaked 'export' encryption, or weak ciphers such as DES), and you probably have more to fear from malware/phishing attacks etc. wrt interacting with your bank than from someone targeting your SSL connection.

Bear in mind that the cipher suite being used is what the bank web server chose to use based on the cipher suites your web browser told it could be used - if your browser is configured to disable TLS 1.0/1.1 for example, this may be the best the server could manage (although from the use of MD5, this appears unlikely).

If you're interested in the detail, then looking at each of the parts of ssl_rsa_with_rc4_128_md5 individually:

ssl - this indicates your site is using SSL, probably SSL 3.0. This is the older, and less secure version of TLS. Most web browsers now support TLS 1.0, 1.1 and 1.2, but only the most recent versions actually enable higher than TLS 1.0 by default.
rsa - this indicates the use of RSA for the key exchange/key agreement protocol. There's probably nothing to worry about here, although the use of RSA here uses the same private key every time you communicate with the site, so anyone who can record the encrypted traffic and at a later date steal the banks private key could decrypt the traffic.
rc4 - this indicates that the RC4 cipher is being used to encrypt traffic to and from your website. RC4 is considered broken (or at least suspect) for most uses, and 'practical' attacks have been demonstrated against it's use in SSL/TLS. 'Practical' in this sense still involves a fair amount of work on the part of the attacker, and you'd have to be a high value target to make that worth it. RC4 is still very commonly used in SSL/TLS, as it is immune to other attacks (such as the BEAST attack) that affect other ciphers.
128 - this indicates 128 bit encryption keys are being used. This is a good key size for most applications, and nothing to worry about.
md5 - this indicates the use of the MD5 hash algorithm to perform functions like deriving keys and authenticating messages in the SSL protocol. MD5 is considered broken as a cryptographic hash function, but it's use in SSL is either in combination with SHA1 (another suspect, but stronger hash function) or in an HMAC like construction, which makes attacking it a lot more difficult.

Most of these issues are in the walk, don't run, to the exit category (the use of MD5 being probably the most concerning issue) - it would be prudent for your bank (and you) to start using more modern cipher suites to protect traffic.


Is MAC process different for symmetric and asymmetric?

A cryptographic MAC is always symmetric By Definition.

For those interested in its security properties, one may want to know Does data authenticity always, implicitly, provide data integrity?

The tool that provides authenticity asymmetrically is known as Digital Signature. Digital Signatures are asymmetric By Definition; they guarantees the integrity, authenticity, and non-repudiation of signed messages when the correctness of the public key of the signer is guaranteed.


How common are SEED certificates outside of Korea? When is support required?

I believe the Wikipedia article about the SEED block cipher sums it up nicely.

SEED is pretty much ubiquitous in Korea, and unused outside of the country. I'm not sure if this article is still accurate, but it does give an idea of the history of SEED in Korea: "the cost of monoculture".

If you work with Korean clients, and they demand that you support it, you should certainly implement it. Otherwise, I don't see any reason to do so.


Zero Knowledge Example using discrete log

A zero-knowledge proof is a protocol by which the Prover demonstrate to the Verifier that he knows the solution to a given problem, without giving to the Verifier any additional information about the solution -- that is, no information that the Verifier could not already obtain alone. In the case of the discrete logarithm, the y value is not part of what the Prover sends; it is a given. The base problem consists in (p,g,y) and what the Prover tries to demonstrate is that he knows the corresponding x -- but without helping the Verifier find out x.

The Verifier can always try to solve the problem by himself. This is in fact unavoidable: since a ZK proof is about proving knowledge of a solution to a given problem, anybody can, conceptually, try to solve the problem upfront, if only by exhaustive search of all possible bit patterns for a solution.

This does not count as a leak because it is not information obtained from the Prover. It is part of the context. It is information that everybody already has. The whole of ZK is about demonstrating knowledge of some value without yielding extra information that was not already public knowledge.

(Honestly I never understood why the cave example was all the rage. It is an analogy and it breaks down when looked at too closely. For instance, Victor could say to Peggy: enter the left corridor, and exit from the right one. This would demonstrate that Peggy knows how to open the door, and would be vastly simpler than the pseudo-ZK concocted for that example.)


Exploiting AES with IV similar to password and fixed key

It seems completely possible to break this scheme. Lets take 2 passwords, using some deterministic padding scheme. Now remember that the IV is XOR'ed with the plaintext before encryption:

Now it seems that the output of this XOR operation will only be different by one byte. So if you have enough passwords that are hashed then the input and therefore output of the blockcipher is likely to repeat. Due to the birthday bound repetition is likely with a chance of 0.5 after 16 tries.

One way to take advantage of this as attacker is to create a few accounts with different passwords. The output of the cipher can be retrieved using the output of the password hash, recovered later. It can simply XOR this value with the password given, which will result in the output of the cipher. Then the attacker can XOR this value with the other password hashes until it finds something that looks like a valid password strings (e.g. by detecting if there are no control characters in the output). This way most if not all passwords should be retrievable.

The fun thing with this attack is that you don't even need the key. The adversary just requires a hashing oracle (the server itself) and (parts of the) hash database.


How many points are there on the X25519 curves?

No the total number of points on the curve is still $8l$.

The curve order (total number of point on the curve) is simply the subgroup order multiplies the co-factor. This is true for all subgroups.

For the small subgroup of order $8$, its co-factor is $l$.


Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation

All functions (including permutations) mapping a finite field $\mathbb{F}_q$ to itself can be uniquely represented by polynomials (via Lagrange Interpolation, possibly followed by reduction modulo $x^{q}-x.$ When $q=2^n,$ the linear permutations $F(x)=x+a,$ for $a\neq 0,$are exactly the type of polynomial that give zero entropy in your formulation since $F(x)+x=a$ a constant.

Focusing only on $q=2^n$ due to crypto applications, we don't know explicit representation of many other permutations but some include certain monomials $F(x)=x^{e}$ with special conditions on exponent $e,$ as well as families such as Dickson's polynomials, which don't have an $x$ term in their polynomial and won't suffer the weakness of zero entropy for $F(x)+x$. As for computing what fraction of overall permutation polynomials have an $x$ in their polynomial expression, it's likely to be a difficult problem.

Edit: The below is redundant, due to your comment, the above is still relevant but I can take it to a comment if requested, it's a bit long.

If we model the map $F(x)=P(x)+x$ by a random mapping instead of a random permutation from $A=\{0,1\}^n$ to itself, then the number of points $y$ in $A$ that have no preimages, i.e., there is no $x\in A$ with $f(x)=y,$ is on average equal to $e^{-1}\#A=\frac{2^n}{e}.$

This would mean that the expected size of the range of $F$ is $$\mathbb{E}[F(A)]=(1-e^{-1}) 2^n\approx 0.6321 \cdot 2^n$$ yielding $$H(n)\approx n+\log_2(0.6321)= n-0.66172,$$
so as you predicted the  $\lim_{n\rightarrow \infty}H(n)/n=1.$

References for this type of argument include Sedgewick and Flajolet's book An Introduction to the Analysis of Algorithms, and the paper "Random Mapping Statistics" by Flajolet and Odlyzko in Eurocrypt'89, but a very readable account is in Chapter 5 of Riordan's classic book An Introduction to Combinatorial Analysis, from 1958.


Perfect Secrecy and Message distribution

I don't think the statement is true, and I will come to a counterexample later.
Formalization
One possible formalization of the statement could look like this:
Let $\mathcal{M}$ be the message space, and $\mathcal{C}$ the ciphertext space.
We define two arbitrary distributions over $\mathcal{M}$: $M_a$ and $M_b$,
where $\Pr_{m \in \mathcal{M}}[M_a = m] = p^\mathcal{M}_a(m)$ and $\Pr_{m \in \mathcal{M}}[M_b = m] = p^\mathcal{M}_b(m)$.
Additionally we need distributions over $\mathcal{C}$: $C_a$ and $C_b$ defined analogously.
An encryption scheme $\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is perfectly secret with respect to the distribution defined by $M_a$ if:
$\forall m\in\mathcal{M}, c\in\mathcal{C}. \Pr[M_a=m] = \Pr[M_a = m\ |\ C_a = c]$ and $\Pr[C_a = c] > 0$, to avoid conditioning on an event with zero probability.
We want to show that given $\Pi$ fulfills the above definition, then it also fulfills the same definition with $M_a$ replaced by $M_b$.
Attempt to Prove
I first attempted (but did not succeed) at proving the statement.
My attempt looks like this:
First show that it suffices to show that the ciphertext distributions are equal
(i.e. that $\Pr[C_a = c] = \Pr[C_b = c]$ holds).
Then show that the ciphertext distributions are equal.
However, I was not able to prove these statements.
Refutation
I believe I have found a counterexample.
Lets first look at the definition of perfect secrecy:

There are two things I would like to point out:

the definition requires independence of the message from the ciphertext for any plaintext distribution, so your statement deviates from this requirement.
the equation only needs to hold for $\Pr[C = c] > 0$

Counterexample
Let $\mathcal{M} = \mathcal{C} = \{0,1,2,3\}$.
Further, let our key-space be $\mathcal{K} = \{0,1\}$.
We define an encryption scheme that is perfectly secret for the messages $0$ and $1$, but not for $2$ and $3$:
\begin{equation*}
\mathrm{Enc}_k(m) =
\begin{cases}
k \oplus m & \text{if $m \in \{0,1\}$}\\
m & \text{if $m \in \{2,3\}$}\\
\end{cases}
\end{equation*}
Additionally, we define a message distribution as follows:
\begin{equation*}
\Pr[\mathcal{M} = m] =
\begin{cases}
\frac{1}{2} & \text{for $m \in\{0,1\}$}\\
0 & \text{for $m \in\{2,3\}$}\\
\end{cases}
\end{equation*}
We now show, that (1) $\Pi$ is perfectly secret with respect to our message distribution.
Then (2) we show that it is not perfectly secret for all message distributions.
1.
We need to show that
$\Pr[M = m] = \Pr[M = m\ |\ C = c]$.
We don't need to show this for $c \in \{2,3\}$ since for our message distribution, $\Pr[C = 2] = \Pr[C = 3] = 0$.
For $c \in \{0, 1\}: \Pr[M = m\ |\ C = c] = \frac{1}{2} = \Pr[M = m]$.
Therefore, the encryption scheme is perfectly secret for the given message distribution.
2.
However, given a message distribution that assigns $2$ or $3$ a non-zero probability, the scheme is trivially not perfectly secret:
$\Pr[M = 2] \neq 0 = \Pr[M = 2\ |\ C = 3]$
Therefore the scheme is not perfectly secret for all message distributions, and thus the statement does not hold in general.
Appendix
For completeness here is the decryption algorithm:
\begin{equation*}
\mathrm{Dec}_k(c) =
\begin{cases}
c \oplus k & \text{if $c \in \{0,1\}$}\\
c & \text{if $c \in \{2,3\}$}
\end{cases}
\end{equation*}
and the key generation:
\begin{equation*}
\mathrm{Gen}() = k \stackrel{sample}{\leftarrow}\{0,1\}
\end{equation*}


The common way is to use a PRF for encryption is the CTR mode which is introduced by Whitfield Diffie and Martin Hellman in 1979;

Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

This is a must-read paper that provides insight into the cryptography during 1970s. CTR mode doesn't need a PRP it can be work with a PRF and actually have better security bounds with the PFF( PRF-PRP switching lemma). To use the CTR mode with a PRF;

Choose a uniform random key on a key $k$

Choose a uniform random nonce ( counter-based are ok)

Generate the keystream $s_i$ as
$$s_i = PRF(key,nonce,i)$$

Encrypt the plaintext bit $p_i$ as $$c_i = p_i \oplus s_i$$

Like everything in cryptography, the CTR mode has advantages and disadvantages and the golden rule never uses an $(IV,key)$ pair again.
A well-known example is the ChaCha20 stream cipher based on the presumed ChaCha20 PRF.
CTR mode is CPA secure. To show the CPA security we need to play the Ind-CPA game.

Set the security parameter $1^n$
Call $Gen(1^n)$ to generate a key $k$
Provide $1^n$ to the adversary and Oracle Access to $E_k(\cdot)$
The adversary outputs the message $m_1$ and $m_2$ of the same length
Uniformly select a bit $b$ and send the ciphertext $c = E_k(m_b)$.
Adversary continue to using the oracle
Adversary outputcal_ $b'$
If $b=b'$ then output 1, else output 0.

Then, a scheme $\pi$ ( here CTR) is said to have Ind-CPA if
$$\Pr\left[ \operatorname{PrivK}^{CPA}_{\mathcal{A},\pi}\right] \leq \frac{1}{2} + \operatorname{negl}(n)$$
The proof is long to write here. See the Theorem 3.33 on the 3rd edition of Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell
CTR mode is malleable, i.e. it cannot achieve CCA security. For this either use it together with a MAC like HMAC or use it in Authenticated Encryption mode fashion.

If pseudorandom functions (PRFs) are deterministic in nature, how can encryption schemes using PRF be CPA secure?

Yes, they are deterministic, however, the way we use them for encryption and decryption is probabilistic encryption. This is achieved even with the fixed key by using an IV/nonce per message. This is the sole reason that the advantage of the adversary is negligible.


Two different keys decrypting same content

Most public key encryption schemes, such as PGP, support this.

When you are encrypting  a message to Bob, in fact you are encrypting the message with a random key using a symmetric cipher, then including the key encrypted to the public key of Bob.

$$E_{\text{PK}}(\mathit{Bob}, \mathit{key}) \Vert E_{\text{Symmetric}}(\mathit{key}, \mathit{message})$$

where $\Vert$ denotes concatenation.

If you encrypt the message to Alice and Bob, you are encrypting the same random key to each of their public keys:

$$E_{\text{PK}}(\mathit{Alice}, \mathit{key}) \Vert E_{\text{PK}}(\mathit{Bob}, \mathit{key}) \Vert E_{\text{Symmetric}}(\mathit{key}, \mathit{message})$$

Each of them can decrypt the message.


Actually Universign produces "Evidence Records" as described by RFC 4998. Evidence Records in turn rely on standard time stamps which RFC 3161 is about. Evidence Records can embed several nested time stamps; this is used for long-term archival, when you want time stamps to remain verifiable beyond the end-of-validity of the certificate of the time stamp authority, or even when one of the hash functions which were originally used becomes broken. Evidence Record Syntax (ERS) includes provision for regular maintenance, namely spraying a new layer of paint (a new time stamp) whenever needed.

As a general basis, a time stamping authority (TSA) works like this: it receives a document hash, and applies a digital signature on a structure which contains the hash value and the current date -- the date is measured by the TSA, not provided by the client. The signature, when verified, "proves" that the TSA was involved, and since we trust the TSA for having a well-maintained clock and never signing any structure for which it did not write the current date itself, this proves that the document hash existed since the announced date (at least). Hash functions being nominally impervious to preimages, this in turn demonstrates the existence of the document at that date.

The cornerstone of the trust is the "honesty" of the TSA, which, administratively speaking, goes through certifications. Various institutional bodies verify, through audits and procedures and mountains of paper which required whole forests to be cut down, that the TSA has been developed and is maintained with enough security, in a way which can be audited. In the case of Universign, they can boast such certifications as can be obtained from French government; in effect, France says: "their time stamps are good enough, that they can be used as proofs in legal proceedings, the burden of proof lying on whoever is arguing against the validity of said time stamps". This can be assumed to more or less extend to the rest of Europe, at least in the near future (the legal systems for electronic signatures and time stamps are slow to spread, but Europe is trying to push them in an harmonized way -- as always, things work differently in America, so the legal status of Universign timestamps in a US court is much less guaranteed).


You could, indeed, form a Merkle tree where each internal node is formed from the hash of 3 (or more) lower level nodes.  However, because it hurts signature size (which is the main expense of Merkle trees), we never do it.

In a Merkle signature, we reveal the preimage to the leaf node (which may involve a Winternitz signature), and also the authentication path; that is, the internal values of the nodes that are hashed along the path between the leaf and the root.

For example, in this three level Merkle tree:

We reveal $H(Y[2])$, from which the verifier can compute the value $A[0]$.  And to prove that it is the correct value, we reveal the values $auth[0]$ (so that the verifier can compute $A[1]$), the value $auth[1]$ (so that the verifier can compute $A[2]$), and the value $auth[2]$ (so that the verifier can compute $A[3]$, which is the root value).  The verifier would then compute the computed root value from the expected value in the Merkle public key; if it compares, then either this was signed by the correct private key, or someone managed to find a preimage for either $A[0], A[1], A[2], A[3]$.

So, this Merkle tree can sign up to 8 signatures using a signature size of 3 hashes (plus whatever hashes the lower level Winternitz uses).  In general, a Merkle tree of height $h$ can sign $2^h$ messages by revealing $h$ internal nodes.

Now, let us consider a Merkle tree where each internal node is 3 lower level nodes hashed together.  In this case, every part of the authentication path must consider of 2 revealed nodes (as the verifier needs to be able to recompute that hash value of the internal node).  So, we get a Merkle tree of height $h$ that can size $3^h$ messages, however each such message reveals $2h$ internal nodes.

It turns out that, for any desired total number of messages, the Merkle tree of degree 3 has a total authentication path that is at least as most (and usually more) than a Merkle tree of degree 2.

In addition, you asked:

  how can new keys be added?

In a single level Merkle tree, we can't.  Because the public key at the root is a complex function of all the leaf nodes, we need to compute all the leaf nodes (and the value of all the internal nodes) at key generation time.

However, we can get around this by using a two (or more) level Merkle tree.  That is, we generate two Merkle trees, a top level one, and a bottom level one.  And, we sign the root of the bottom level tree with the top level.  We then use the bottom level one to sign actual messages (and the signature of this joint system would be the Merkle signature of the bottom level tree, along with the signature of the bottom level tree with the top level tree).  We keep on signing the bottom level tree as new messages until that runs out.

Then, once that runs out, we generate a fresh bottom level Merkle tree, and sign that with the top level Merkle tree (which has signed only one value so far, and so can sign a second message).  We can keep on signing; if both the top level and the bottom level trees are of height $h$, then we can sign a total of $2^{2h}$ messages, and only have to generate a total of $2^{h+1}$ leaf nodes (and internal nodes) when we generate the initial public key.

This does increase the signature size (because of the internal Winternitz signatures); however it does allow us to create a signature scheme that can sign a large number of messages, but doesn't require a huge amount of time to generate the public key.