When to use RSA and when ElGamal asymmetric encryption

Actually, for most applications where we want to use asymmetric encryption, we really want something a bit weaker: key agreement (also known as "key exchange"). When RSA or ElGamal is used for that, one party selects a random string, encrypts it with the public key of the other party, and the random string is used as a key for classical symmetric encryption. Therefore, we must add Diffie-Hellman to the list. You can imagine Diffie-Hellman as a kind of asymmetric encryption in which you do not get to choose the random value you are encrypting: less versatile than ElGamal, yet sufficiently powerful for most protocols where asymmetric encryption is used. SSL/TLS and S/MIME happily use RSA and Diffie-Hellman in practice. Diffie-Hellman, like ElGamal, relies (more or less) on the difficulty of breaking discrete logarithm, and is internally relatively similar to ElGamal.

Among differences between RSA, DH and ElGamal, one can find:

DH and ElGamal accept elliptic curve variants. They rely on hardness of discrete logarithm on elliptic curves, which is distinct from discrete logarithms modulo a big prime. Elliptic curve variants can use smaller fields, so while the mathematics are a bit more complex, performance is better.
RSA encryption (with the public key) is faster than the corresponding operation with ElGamal, or half of Diffie-Hellman. On the other hand, RSA decryption (with a private key) is a bit slower than ElGamal decryption or the other half of Diffie-Hellman (especially the elliptic curve variants).
An RSA-encrypted message is larger than an ElGamal-encrypted message or half a Diffie-Hellman, provided that elliptic curves are used for the latter.
Historically, RSA was patented in the US, while ElGamal was not -- which is why OpenPGP specified ElGamal usage, and GnuPG tends to favour it over RSA (the RSA patent expired a decade ago, so this is no longer an issue).
RSA is described by a clear standard, which is free (as in "free beer"), and says precisely where each byte should go. That's very good for implementers: it reduces the possible mishaps. On the other hand, the Diffie-Hellman standard (or that one for the elliptic curve variant) is not free, and, in my experience, less clear. There is no established standard at all for ElGamal, except the bits about it in OpenPGP, which do not deal with ElGamal "in general".

What protocol designers should do is to make some provisions for algorithm agility: the protocol should work with various algorithms, with fields indicating which algorithm is actually used. Algorithm agility helps quite a lot with dealing with future cryptanalytic advances, and with regulatory requirements.


$\newcommand{opn}{\operatorname}$
Formally, a digital signature scheme is a triple of algorithms $(\opn{KeyGen},\opn{Sign},\opn{Verify})$ where the first two are probabilistic and the last is deterministic such that the following logical statement holds except in a negligible amount of cases:
$$\forall \lambda\in\mathbb N:\forall (pk,sk)\gets \opn{KeyGen}(1^\lambda):\forall m\in\mathcal M:\opn{Verify}(pk,m,\opn{Sign}(sk,m))=1$$

That is, by its very definition, the receiver can verify the signature of a message using a public key associated to a specific private key. If you are looking for standard security definitions, have a look here.

So, how can we instantiate these triples? As you already know RSA, I shall discuss this using RSA-Full Domain Hashing (RSA-FDH), which is conceptually the easiest, provably secure signature algorithm.

$(pk,sk)\gets\opn{KeyGen}(1^\lambda)$, this is the non-deterministic algorithm, that given a security parameter $n$, returns a public ($pk$) and a private key ($sk$) for use with the cryptosystem. For RSA this would be $(n,e)$ as the public key, with $n$ having length $\lambda$-bits, as well as a note on which hash algorithm is to be used. The private key would be the public key with $d$ added.
$\sigma\gets\opn{Sign}(sk,m)$, this is the (potentially) non-deterministic algorithm that given a secret key $sk$ and a message $m$, returns a signature $\sigma$. For RSA-FDH this would be $\sigma =H(m)^d\bmod n$ with $H:\{0,1\}^*\to\mathbb Z_n$ being essentially a hash function that outputs a hash as large as $n$. Practically one can use SHAKE128 (the arbitrary-length version of SHA3) here.
$b=\opn{Verify}(pk,m,\sigma)$, this is the deterministic algorithm that given a public key $pk$, a message $m$ and an alleged signature $\sigma$ on $m$ decides whether $\sigma$ is indeed a valid signature, produced using the private key associated to the given public key on the given message. The result is a yes/no answer, encoded as 1/0 in $b$. For RSA-FDH this would be $\sigma^e\bmod n\stackrel{?}{=}H(m)$.

As for the correlation between a signature and a sender, assuming we have a trusted binding between the public key and the sender and assuming the sender hasn't leaked their private key, only they could potentially have created a valid signature for the given public key, meaning we can be sure this message is from them.


The Analysis of BLAKE2's Modes of Operation paper gives a PRF bound for keyed BLAKE2b with a key of size $k$, under the assumption that the underlying block cipher is ideal (Corollary 3):
$$
\text{Adv}^{\mathrm{PRF}}_{\text{BLAKE2b}}(\mathcal{D}) \le \frac{q^2}{2^{1024}} + \frac{2q^2}{2^{512}} + \frac{q}{2^{256}} + \frac{q}{2^k}\,.
$$
Here, $q$ is the complexity of the distinguisher, i.e., calls to the hash function.

Given this PRF bound, the MAC security of BLAKE2b with output size $t$ can be derived as
$$
\text{Adv}^{\mathrm{MAC}}_{\text{BLAKE2b}}(\mathcal{D}) \le \frac{q^2}{2^{1024}} + \frac{2q^2}{2^{512}} + \frac{q}{2^{256}} + \frac{q}{2^k} + \frac{q_v}{2^t}\,,
$$
where $q_v$ represents the number of forgery attempts.

Seeing this, two things look clear:

It is pointless to have a key over $256$ bits, since security begins degrading by other means by that point.
The tag size influences the probability that a forgery succeeds; thus, it cannot be small enough that an attacker can succeed 'by chance'.

All in all, the same recommendations for HMAC also apply to keyed BLAKE2. A 256-bit key with a 128-bit tag seems like a reasonable choice for most purposes.


Maximum secret key length from a time series shared signal

What can be the largest possible secret key?

Any size. You can use the entropy as input for a DRBG (deterministic random bit generator) or KDF (key derivation function) and generate as many bits you want out of that.

  Will the entropy and secrecy of system depends on this length?

No.

  Assumption: Maximum length hence is $N_S$ bits of secret keys

No, it isn't. That's just the input data that contains a certain amount of entropy - or at least that's what we'll assume for the sake of argument.

  Is this the best key?

No $N_S$ (or any specific part of $N_S$) is not the best key. You want to explicitly extract the randomness from your data. $N_S$ may be biased.


Proof of ignorance to prevent "double-spend"?

From the linked paper on Proofs of Ignorance:

  Intuitively, it seems impossible, since one can always pretend to be ignorant. We explore the settings in which one could give a convincing proof of ignorance. As a thought experiment, suppose that Alice holds a locked box and wants to convince Bob that she does not know the contents inside the box. In general, Bob has no reason to believe Alice unless Alice provides some evidence on how she got the box
  in the first place. Suppose Bob trusts that Charlie gives locked boxes without revealing its contents and suppose that Alice is able to prove that she got the box from Charlie, then Bob might be convinced of Alice’s assertion.

The paper's concept of a proof of ignorance is only applicable to certain settings where a player can prove that they never had the information to begin with. It doesn't offer a way for a player to prove that they've forgotten some information they knew at some point. I don't think there's any sure way that you could prove that.

If you know the knowledge is intended for Bob from the start, could you not encrypt it directly to Bob? If you and Bob had a pre-shared key, then you could symmetrically encrypt the knowledge with that key, or if Bob had published a public key, then you could asymmetrically encrypt the knowledge with that key. Alice wouldn't be able to make any sense of the information, but could still be able to relay the encrypted information to Bob.

There are some possible reasons that the encryption-based scenario wouldn't work for your case:

You don't know yet who will be "Bob" when you give the information to Alice (maybe Alice chooses who Bob will be), and Alice needs to be able to complete the process without your involvement.
Your only communication channel to Bob is a one-shot communication through Alice, so you can't share a key with each other ahead of time or after the fact.

If the encryption-based solution doesn't work for you, then this question otherwise seems like a more specific version of How to use proof of lack of knowledge?. That question is to prove a lack of knowledge, and this question is about proving a lack of knowledge that was previously held.

I provided an answer to that question based on incentives, but that answer is less than perfect for this scenario because it also incentivizes Alice to retain the information and claim the bounty.


Advanced Electronic Signature: PKCS#7 to PFX Conversion

A PFX file is better known as a PKCS#12, the "Personal Information Exchange Syntax".  It is used either as a trusted certificate store or as a key store. When it is used as a (private) key store it generally contains entries with a private key and the certificate chain associated with it (leaf certificate, CA certificates and root certificate usually).
If your key is in a hardware token then generally you cannot extract it. So your software needs to reference it some way or other. For this another standard from the PKCS range is commonly used, namely PKCS#11. PKCS#11 is also known as Cryptoki. Microsoft unfortunately has a bad track record when it comes to keeping to standards and uses a CSP (Cryptographic Service Provider). PKCS#11 libraries and CSP's are token specific and should be available from the vendor.
To use the device your software should support a PKCS#11 interface or it should use the Microsoft Cryptography API in a generic way (it is possible to use the "managed" classes, but then you'll be stuck with a software-only implementation). OpenSSL also has a PKCS#11 engine if that's your poison.

PKCS#7 is the "Cryptographic Message Syntax". It is used to sign / encrypt data. However, because it can also carry certificates it is sometimes used as a certificate store as well. It is not a key store, so the private key won't or shouldn't be in it.

X.509 is a standard of certificates and CRL's. It can specify a lot of things, but it cannot be used to specify where the private key is stored. As such the last part of the question is unclear and cannot be answered in my opinion.


Openssl & RSA : how many public exponents are possible?

The public exponent of a RSA key is, nominally, an odd integer $e \geq 3$. Any such integer can be used with RSA, although not necessarily with any modulus $n$: $n$ and $e$ must be such that $e$ and $\phi(n)$ are relatively prime to each other. This is why $e$ cannot be even: $\phi(n)$ is even, so it can never be prime to another even number. Apart from that, any odd integer can be theoretically encountered as a public exponent (not $1$, but some implementations will accept it nonetheless, although it is very weak).

A specific implementation of RSA may be more restrictive. OpenSSL appears to have, by default, the following limitations:

The modulus $n$ must not be larger than 16384 bits.
The public exponent $e$ must not be greater than $n$.
If $n$ is larger than 3072 bits, then $e$ must fit in 64 bits.

These conditions (especially the third) are fairly arbitrary, but so it is. In fact, you want to be even more restrictive, because of interoperability. For instance, the default RSA implementation in Windows (CryptoAPI) cannot process RSA public keys where the public exponent does not fit on 32 bits.

There is no known security advantage to large public exponents over small public exponents. However, there is a quite plain performance advantage to using small exponents, and the smaller the better. Which us why $e = 3$ should be preferred. Using $e = 65537$ is a well-entrenched tradition, for no real good reason (even with $e = 65537$, RSA public-key operations are still quite fast, so it does not matter much in practice).

"65537" was selected for several reasons:

Its binary representation contains mostly zeros, which gives a small performance advantage in a square-and-multiply algorithm (you still need to do 16 squarings, but only one non-squaring multiplication).
It is prime, which is good for some key generation algorithms: for a RSA key, you need to generate two big primes $p$ and $q$, such that $e$ is relatively prime to $p-1$ and $q-1$. By choosing $e = 65537$, you can generate $p$ and $q$ without caring about $e$, and just start over if the "relatively prime" condition turns out not to be fulfilled (happens with probability $1/65537$ for each prime, so quite rarely).
It is bigger than $3$, which appeases people.

None of these reasons is really strong. Public-key operations in RSA are fast anyway; and $e = 3$ is the fastest you can get. If you really need ultimate performance for public-key operations, then $e = 65537$, while being about the best 17-bit exponent you can find, is still substantially slower than RSA with $e=3$. Not that it really matters most of the time (private-key operations are where performance issues usually are; and if you really need the extra cycles for public-key operations then you should use Rabin signatures, not RSA).

Prime generation can take into account the public exponent, e.g. you can generate candidate $p$ values as $p = 3r+2$ where $r$ is an odd random integer; this ensures that $p$ will not be a multiple of $3$ and that $p-1$ will be relatively prime to $3$ too. This process can be extended to ensure that not only $p-1$ will be relatively prime to your pulbic exponent of choice, but also that the candidate $p$ will not be a multiple of 2, 3, 5, 7, 11, 13... which will make bad candidate pruning faster.

The qualms some people have about $e = 3$ are the consequences of an old piece information that got corrupted along the way and turned into a myth. See this answer for details.


How to determine the signature type of RSA with a hash function?

It is extremely likely to be either RSA with PSS padding or RSA with PKCS#1 v1.5 padding, the latter being the most likely.

Although there are many signature schemes, PKCS#1 v1.5 seems to be the most used. When many crypto libraries were devised it was the only scheme that was described by the RSA labs (that created the PKCS standards), so many older libraries forgot to document it. There are however other schemes, such as the aforementioned RSA-PSS and RSA with (partial) message recovery, defined in ISO/IEC 9796-2.

If you sign two times and the output is twice the same then it is not PSS and PKCS#1 v1.5 would be the main suspect:

  RSASSA-PSS is different from other RSA-based signature schemes in
     that it is probabilistic rather than deterministic, incorporating a
     randomly generated salt value.

Both PSS and PKCS#1 v1.5 are defined in RFC 3447. And yes, the hashing itself is almost always included in the method, so usually you just feed it the message itself.

Both PSS and PKCS#1 v1.5 first perform modular exponentiation which produces a signature size that is bounded by the size of the modulus. However, after that the function I2OSP is performed, which makes the signature the same size as the modulus in bytes. As the modulus defines the key size, the signature is the same size as the key size in bytes.

So you cannot use the resulting signature size to determine the signature algorithm.

If you have the RSA public key you could perform a raw modular exponentiation (called textbook RSA, "none with RSA", "raw RSA" or similar) with the public exponent on the (decoded) signature. Then you could compare the result with the padding format. Usually it is easier to just try PKCS#1 v1.5 and PSS though.

Base 64 converts a signature to the base 64 alphabet, expanding the size with about 33/37% compared to the key size, assuming that the string is encoded as ASCII or compatible.


The reduction will not work. The reason is that any $E$ that is LoR indistinguishable has to be randomized. But then, the adversary's output might be different from the outcome of the oracle, even if it evaluates the correct $x$ (the one picked by the adversary).

In fact, there is a family of $E$'s that is predictable but still LoR indistinguishable. For example consider a public-key encryption scheme that is LoR indistinguishable and let $E(x)=(\mathit{Enc}(\mathit{pk},x),\mathit{pk})$. Then also $E$ is LoR indistinguishable. However, you can easily find pairs $(x,E(x))$ since with one query you can retrieve the public key.


What type of hash functions provides non-malleability of hash digests?

Commitment functions should be at least hiding and binding, and in your case, you want non-malleable.

Using a hash function as a commitment does require addition assumptions on the hash that are not covered by (second) pre-image and collision resistance for both non-malleability (as you point out) and hiding: the hash can be assumed to not reveal the entire pre-image but partial leakage is not covered by pre-image assumptions. See section 1.3, "a false solution" in this paper.

Non-malleability with hash functions like SHA256 (based on Merkle-Damgaard) can be defeated with a length extension attack. If you commit to $x$ with $Hash(x)$ it is possible for me to commit to $x'=x\|a$ without knowing your $x$ (technically it is a padded version of $x$). If you reveal $x$ first, then I can reveal $x\|p$.

Using a MAC does not provide hiding as MACs are not designed with this property.

All of this said, in practice with a hash function like SHA256, it will likely function ok if you are committing to fixed length messages. This is not provable but no known malleability is known and the hiding property of SHA256 is thought to be sufficient.


How to use a random 32 byte sequence as a curve25519 public key

Indeed, you seems to be right since when taking a look at the BC code, we find in the Curve25519FieldElement object that:

if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0)
{
    new IllegalArgumentException("x value invalid for Curve25519FieldElement");
}

So in BouncyCastle it appears that you have to make sure that x.CompareTo(Q) < 0, which effectively means that you should restrict your x coordinate to something below the $Q$ value, however this is not the group order, but the field order, which is $2^{255}-19$. This is normal, since this represents an element of the Field...

Now, you've remarked that the Curve25519 has been designed to accept all 32 byte public keys as a valid point encoding:

Firstly, a value on 32 bytes is within $\{0,1,\ldots,2^{256}-1\}$, that is $2^{256}$ possibilities, while the field order is $2^{255}-19$, which means that you only have $2^{255}-19$ elements in your field...

But now, the function Curve25519 is actually defined in the paper thanks to the theorem 2.1 as being a function that producing $s$ (in little endian) out of an integer $n$ and a point $Q$ (both encoded in little endian), such that $s$ is the unique $s\in F_{2^{255}-19}$ such that $X_0(nQ)=s$  for the function defined as $X_0:E(F_{(2^{255}-19)^2}) \to F_{(2^{255}-19)^2}$ such that $X_0(\infty)=0; X_0(x,y)=x$, if we let $q\in F_{2^{255}-19}$ and $n$ be an integer for all $Q\in E(F_{(2^{255}-19)^2})$ such that $X_0(Q)=q\bmod 2^{255}-19$, and here this modulo reduction is why you are having a problem, I think.

This is actually pretty well explained in the paper:

  Fix $q\in\{0,1,\ldots,2^{256}-1\}$ and $n\in 2^{254}+8\{0,1,\ldots,2^{251}-1\}$. By Theorem 2.1, there is a unique integer $s\in\{0,1,\ldots,2^{255}-20\}$ with the following property: $s=X_0(nQ)$ for all $Q\in E(F_{(2^{255}-19)})$ such that $X_0(Q)=q \bmod 2^{255}-19$.

Here your public key is the value $q$ and $n$ is the secret key.

Which means that we actually have collisions in the Curve25519 function, which are handled within the function. I imagine that BouncyCastle, depending how they've implemented this, might be converting the computed values into Curve25519FieldElement only AFTER having passed the values through the Curve25519 function...

So I think you are probably providing the public key in a wrong way, using the wrong object to store it... Which is not a problem when used as the output of the Curve25519 function, but is a problem when using your own values.

You might want to compute for your point $P$ the output of $X_0(\underline{1}\cdot \underline{P})$ and then encode that value as a public key, to have the correct format.


Suppose an RSA public key is still $(e, N)$ and the private key is still $d$. We have $Enc = (m*e) \text{ mod } N$ and $Dec = (c*d) \text{ mod } N$. The correctness of the scheme depends on the fact that $Dec(Enc(m)) = (m*e*d) \text{ mod } N = m \text{ mod } N$. This implies $e*d = 1 \text{ mod } N$. It is thus trivial to compute the private key given only the public key (i.e. compute $d = e^{-1} \text{ mod } N$). Hence this scheme is completely broken.

Note that this scheme only works if $e$ and $N$ are coprime otherwise no $d$ such that $e*d = 1 \text{ mod } N$ exists.


Can anybody please explain why is the probabilty of finding a desired message for random chaining values equal $2^{-224}$?

The second paragraph of section 2 of the quoted paper tells the domain of the function $\mathcal F:\{0,1\}^{32}\times\{0,1\}^{256}\to\{0,1\}^{256}$.

Under the reasonable assumption that for fixed second input ($h_{i-1}$ in the question's statement), $\mathcal F$ behaves as a random function of the first input ($M_i$ in the question's statement), then for each value of the first input the probability that the output matches a fixed target value ($h^*_i$ in the question's statement) is $p=2^{-256}$. That will be repeated for the $n=2^{32}$ possible first inputs.

One way to conclude is to know that if an event has probability $p$ of occurring at each (independent) experiment, then the expected number of events for $n$ experiments is $n\,p$, and the probability of at least one event is barely below that value $n\,p$ as long as it remains small. Here $p=2^{-256}$, $n=2^{32}$, $n\,p=2^{32-256}=2^{-224}$ (as asserted in the question's statement). That's very small, thus the approximation made is valid.

The more mathematical way: the probability of no match for one first input is $1-p$. The probability of no match after $n$ inputs is $(1-p)^n$. The probability of at least one match after $n$ inputs (as discussed in the question's statement) is $1-(1-p)^n$. Using that $1-(1-p)^n=1-e^{n\log(1-p)}$, that $\log(1-p)=-p+o(p)$ (using little-O notation), that $e^x=1+x+o(x)$, it comes that $1-(1-p)^n=n\,p+o(n\,p)$. Hence $1-(1-p)^n$ is about $n\,p$. The error made with this approximation is always by excess. When $n\,p<0.3$, the relative error is less than $16\%$. For lower values of $n\,p$, that upper bound of the relative error becomes barely above $n\,p/2$.

Other useful data points are that if $n$ is large, then $n\,p=1\implies1-(1-p)^n\gtrapprox1-e^{-1}\gtrapprox63\%$; and $n\,p=2\implies1-(1-p)^n\gtrapprox1-e^{-2}\gtrapprox86\%$ This explains the "high probability" after about $2^{224}$ random values of $h_{i-1}$ in the question's statement.


As per section 9 of the paper, the encoding used is required for the security of the scheme.

The encoding operation may introduce some randomness, so that
different applications of the encoding operation to the same message
will produce different encoded messages, which has benefits for
provable security.  For such an encoding method, both an encoding and
a verification operation are needed unless the verifier can reproduce
the randomness (e.g., by obtaining the salt value from the signer).
For a deterministic encoding method only an encoding operation is
needed.

Two encoding methods for signatures with appendix are employed in the
signature schemes and are specified here: EMSA-PSS and EMSA-PKCS1-
v1_5.

The paper then goes into further detail on these two encoding methods.
You would be compromising the security proof of the scheme if you did not use the encoding, however you could feasibly apply the encoding after hashing the message.  Per the paper:

Without compromising the security proof for RSASSA-PSS, one may
perform steps 1 and 2 of EMSA-PSS-ENCODE and EMSA-PSS-VERIFY (the
application of the hash function to the message) outside the
module that computes the rest of the signature operation, so that
mHash rather than the message M itself is input to the module.  In
other words, the security proof for RSASSA-PSS still holds even if
an opponent can control the value of mHash.

The fabulous answer here goes into detail regarding one attack the encoding prevents, and provides links to other attacks on wide deterministic RSA signature signature schemes.
Section 2 of the original paper by Bellare & Rogaway outlines several advantages of the encoding scheme.


Any reason to use Shamir given faster XOR threshold secret sharing algos?

Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)?

The algorithm being referred to is in this paper, and I believe that the speed benefits are at best marginal, if not nonexistent.

As for the speed benefits being marginal, well, normally we use secret sharing as a part of an overall algorithm achieving something else, and the time taken by the secret sharing algorithm is dominated by something else, and so the time taken doesn't really matter.

As for the speed benefits being marginal, well, that's because Shamir's method really is quite efficient; the generation of a share (once you've generated the randomess) is $k-1$ field multiplications and $k-1$ field adds; if you use the field $GF(256)$, this can be done with $2k-1$ table lookups, $k-1$ adds and $k-1$ xors.  The recombination step (once you've converted the id's into coefficients) is $k$ field multiplications and $k-1$ field adds; similarly cheap.

Now, you ask, why does the paper claim to do so much better than Shamir?  Well, that's because they were testing it against a Secret Sharing implementation that was never designed for performance.  If you look into the implementation of SSSS, you'll see that it uses the GMP bignum library to perform the operations.  Since the internal operations it uses are cheap (exclusive-or and shift left by one), the vast bulk of the time is spent in memory management (allocating and freeing memory).  Furthermore, the field multiply implementation it uses is a generic one; if one is greatly concerned with speed, one could do better by optimizing for a specific field size (as I mentioned, a moderate sized field such as $GF(256)$ can be done quite fast using log and antilog tables).

Now, to be clear, I'm not saying that the SSSS implementation is bad; what I am saying that performance wasn't very high on the developers list.  However, if speed is considered important, one can do quite a lot better.

As for your overall question, 'given that there are alternatives to Shamir, why do people generally stick with it?', well, I suspect that it's a combination of Shamir is good enough (a good implementation should run in a time that's competitive to Kulihara, and in any case, an I mentioned, we generally don't care), and that Shamir was the first (and people tend to stick with what's first - remember, people are still using RSA, even though we have better alternatives available).


Can you help me understand ECC Cryptography and it's algorithm?

One can go on and on if to define and describe Elliptic Curve. I will rather suggest for you to get hold of a decent book and read for yourself. If you an issue with understanding any algorithm or basic of Elliptic Curve, I will be more than happy to help you there. For starter, you can always look at Silverman's book titled The Arithmetic of Elliptic curves. Else just go to Galbraith's webpage on Elliptic Curve Cryptography. There are bunch of nice books listed.


Why are the outputs of the md5sum tool and Crypto++'s MD5 different?

The echo command appends a new line at the end, by default. The -n option omits this character. Compare these two executions:

> echo -n "test123" | md5sum
cc03e747a6afbbcbf8be7668acfebee5

> echo "test123" | md5sum
4a251a2ef9bbf4ccc35f97aba2c9cbda

So the difference between the hash values is simply caused by the new line character.


Is it true that Serpent and twofish are much stronger than AES?

SHORT: This is kind of true. However, things are bit different now. Better protection against brute force is inaccurate claim.

At the time Rijndael (AES) won the competition, it was faster, and sufficiently strong. After the competition, Rijndael (AES) has gotten faster (AES-NI and other hardware improvements). Also Rijndael (AES) has also gotten significant amount of analysis, but it has not been broken in a practical way. Therefore, Rijndael (AES) has been shown to be quite good pick.

The other AES finalists are also believed to be very good, but as they've not been as standardized they will lack interoperability. Also, we've gotten very good in making Rijndael implementations during the last two decades. Because Serpent and Twofish have gotten less attention, it may be harder to find as good implementations of these algorithms than it is to find very good AES implementation.

The difference in en/decryption speed between these algorithms does not translate into any meaningful difference in protection against brute force attacks.

For more information, see also earlier answer by B-Con to similar question regarding advantages of Rijndael against Twofish and Serpent at: https://crypto.stackexchange.com/a/5290.


Shortest key in symmetric algorithm used only once is unsecured?

If we don't know anything about the original n bit message, we can guess the message with probability $1/2^n$ which for anything but very small values of n quickly becomes zero.
However if we xor the message with a single bit (repeating it n times) we only have 2 possible keys: 1 and 0. And the xor result is either the original message or it's negation. Therefor given a cipher text we have exactly two possibilities for plain text. And even if we know nothing about the plain text and can't validate our guess we can still guess with 50% chance of success.

Guessing the plain-text with 50% likelyhood is not secure by any means.

Obviously even with a very limited understanding of plain text, we would be able to determine which of the 2 options is correct.

Note security proofs for One-Time-Pad do not apply as we are repeating the key in the same message. This is no better than repeating it in later messages.


Complexity of arithmetic in a finite field?

Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$).

If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be asymptotically lowered by using Toom-Cook multiplication or Fast Fourier Transform (with fast algorithms for the final modular reduction, whose name currently evades me), down to about $O(n(\log n)^2)$. However, for numbers of the size used in cryptography (say, 2048-bit integers), these methods tend not to be worth the effort, and plain Montgomery multiplication is faster. At least so goes the usual wisdom; each new hardware architecture may challenge such results. For modular divisions, the fastest algorithm is the extended binary GCD algorithm, which is quadratic.

One must note that even if Montgomery's multiplication and extended binary GCD are both in cost $O(n^2)$, the former tends to be, in practice, several dozen times faster than the latter, for numbers of the same size, because Montgomery's multiplication can rely on the hardware native multiplication opcode and process bits by chunks of 32 or 64, while binary GCD is a bit-by-bit algorithm.

If $q$ is a power of 2 ($q = 2^n$), then field $\mathbb{F}_q$ is the quotient field obtained by taking polynomials in $\mathbb{F}_2[X]$ modulo a given irreducible polynomial $P$. Since all finite fields of same cardinal are isomorphic, one can choose the polynomial $P$ to be almost empty, i.e. a trinomial ($P = 1 + X^a + X^n$) or a pentanomial ($P = 1 + X^a + X^b + X^c + X^n$). This allows for a linear reduction modulo $P$. In practice, multiplication will be done with Karatsuba's algorithm with complexity about $O(n^{1.585})$.

Also, in a binary field, squaring (and extracting a square root) can be done very efficiently, with $O(n)$ complexity. This is the Frobenius endomorphism, and is used to speed up computations on a special kind of elliptic curves called Koblitz curves. Squarings and square roots can be even further optimized to become "free" using normal bases, but this makes multiplication widely less efficient, so this is not considered to be a net gain in the general case.

Besides the Handbook of Applied Cryptography (especially chapters 2 and 14), a good reference is chapter 2 of the Guide to Elliptic Curve Cryptography, which covers finite field arithmetics -- and, lo! chapter 2 of that book is the "free sample" chapter that can be downloaded as a PDF from the Web site.


Entropy is a function of the distribution. That is, the process used to generate a byte stream is what has entropy, not the byte stream itself. If I give you the bits 1011, that could have anywhere from 0 to 4 bits of entropy; you have no way of knowing that value.

Here is the definition of Shannon entropy. Let $X$ be a random variable that takes on the values $x_1,x_2,x_3,\dots,x_n$. Then the Shannon entropy is defined as

$$H(X) = -\sum_{i=1}^{n} \operatorname{Pr}[x_i] \cdot \log_2\left(\operatorname{Pr}[x_i]\right)$$

where $\operatorname{Pr}[\cdot]$ represents probability. Note that the definition is a function of a random variable (i.e., a distribution), not a particular value!

So what is the entropy in a single flip of a coin? Let $F$ be a random variable representing such. There are two events, heads and tails, each with probability $0.5$. So, the Shannon entropy of $F$ is:

$$H(F) = -(0.5\cdot\log_2 0.5 + 0.5\cdot\log_2 0.5) = -(-0.5 + -0.5) = 1.$$

Thus, $F$ has exactly one bit of entropy, what we expected.

So, to find how much entropy is present in a byte stream, you need to know how the byte stream is generated and the entropy of any inputs (in the case of PRNGs). Recall that a deterministic algorithm cannot add entropy to an input, only take it away, so the entropy of all inputs to a deterministic algorithm is the maximum entropy possible in the output.

If you're using a hardware RNG, then you need to know the probabilities associated with the data it gives you, else you cannot formally find the Shannon entropy (though you could give it a lower bound if you know the probabilities of some, but not all, events).

But note that in any case, you are dependent on the knowledge of the distribution associated with the byte stream. You can do statistical tests, like you mention, to verify that the output "looks random" (from a certain perspective). But you'll never be able to say any more than "it looks pretty uniformly distributed to me!". You'll never be able to look at a bitstream without knowing the distribution and say "there are X bits of entropy here."


Which values to store in rainbow table generation?

You can do either and the method works. Depending on which value is stored you check for existence in the table at different points in the computation. If the chains are long enough, the addition of a half step does not matter much for time, especially as the reduction function is typically very fast.

However, when you are trying to break a key with a size smaller than the hash size, it makes sense to store the former. Contrarily, if you are looking for passwords which do not have a lot of entropy and may even have different lengths, it can be more efficient to store the hash or a part of it instead.

(Note that the image you quoted is not for a rainbow table, but a simpler hash chain with the same reduction function at each step.)


Do hand-based hash functions / MACs exist?

It depends on the time you want to spend. But most likely, there is nothing with reasonable efficiency. For arithmetic operations, humans are really bad compared to computers, and the difference is at least a factor of $10.000.000$ (very very rough guess, probably even 1+ additional zeros there).

So, since you have to assume that the attacker has access to a computer and will use it, you will have to use a modern scheme and consider classical ones broken.

Anyway, for security in a modern sense, you need a modern scheme, and those require modern tools like computers to achieve any reasonable performance. Of course you can calculate SHA256 by hand... but it will probably take you hours to go through all rounds for a single hash value.

Considering your remark about letters instead of bits: Mostly that is just interpretation, but there is also format-preserving encryption (there are quite a few questions on that on cryptoSE), which operates on arbitrary sets of symbols. If you want to transfer this into a hash fucntion, see this question.

Hash functions in the classic crypto-era?

At the time when classic ciphers were created, cryptography was (as far as I can tell) almost only looking at encryption methods. The idea of hash functions - or its ideal counter part the one-way function - might have been known, but not its range of application. E.g. integrity was not much of a concern: Someone without the key couldn't possibly modify a message in a meaningful way. Other applications of hash functions might seem trivial these days, but as always: developing something new and understanding something in hindsight is entirely different.

I doubt there is a genuine classical hash function.


Encrypting documents through a proxy key

There is the obvious weakness that if Y ever gets compromized, changing the password will not help. The attacker will be able to decrypt all past and future documents. One way this might happen is if the password gets compromized, and the attacker gains access to the encrypted value of Y.

TrueCrypt volumes work in a similar way. When you create a volume, a master key is created which doesn't change throughout the lifetime of the volume, even if you change the password.


Given ciphertexts C1, C2 of different messages P1 and P2; how can we prove that both C1 and C2 were encrypted using public keys of the same pair?

Chaum-Pedersen protocol tweaked with Sigma AND composition should do.
The high level intuition: using Chaum-Pedersen protocol for DH-triple, one can prove knowledge of secret witness $\alpha$ in the following relation in (honest verifier) zero-knowledge:
$$
\mathcal{R}:=\left\{((x, y, z), \alpha)\in\mathbb{G}^3\times\mathbb{Z}_q: \quad y=g^\alpha \land z=x^\alpha\right\}
$$
where $(x,y,z)$ is the statement ("claiming that they are a DH-triple")
Recall the following ElGamal encryption scheme:

Now let $y$ be your public key and $\alpha$ your secret exponent (secret key), let $x$ be the first part of the ElGamal ciphertext above (namely $v$ in the screenshot), and naturally $z = y^\alpha = g^{\alpha\cdot\beta}$ is the shared secret and let it be the $w$ in the ElGamal encryption process.
With Chaum-Pedersen Sigmal protocol above, we can prove knowledge of a secret key that produce a ciphertext for a certain message.
Finally composing two Sigmal protocols, one for each (message, ciphertext) tuple, using AND-proof construction, the verifier could easily verify that the two ciphertexts are encrypted under the same key as the two statements shared the same $y$. $\blacksquare$


Kolesnikov & Kumaresan defined a primitive called "string select OT" which basically covers your setting but with a database of 2 items. Sender has $x^1, y^1, x^2, y^2$. Receiver has $x^*$. If $x^* = x^i$ then the receiver learns the corresponding $y^i$.

I think a generalization of their protocol would work, at the cost of $n$ 1-out-of-2 string OTs where $n$ is the number of bits in the $x$ values.

Parties do $n$ instances of string OTs on random strings $(m_0^1, m_1^1), (m_0^2, m_0^2), \ldots$ The receiver uses the bits of $x^*$ as his choice bits.
For an $n$-bit value $x$, sender defines $K_x = H( \bigoplus_i m_{x[i]}^i )$ where $H$ is a random oracle. The thing inside $H$ is the XOR of the things that the receiver would get if his choice bits were $x$. (the hash is there to kill the correlations among the different $K_x$ values)
For every $(x^i, y^i)$ in the database, sender sends gives $\textsf{Enc}(K_{x^i}, y^i)$. (assume it is an authenticated encryption, so you know when you have successfully decrypted)
Receiver can decrypt exactly one of these ciphertexts, and learn $y^i$.

  Vladimir Kolesnikov, Ranjit Kumaresan: Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. SCN 2012: 205-221

edit: Here is another approach, using ideas from one of my papers. The paper only needs this functionality for database of size 2, but I think it would generalize as well. (we refer to this subprotocol as PFE of a universal hash function).

Parties do an MPC where receiver inputs $x^*$, sender inputs randomly chosen $a$ and $b$ from a large field. Receiver learns $ax^* + b$. Think of this as evaluating a private a 2-universal hash function. It has the property that even given $ax^*+b$, any other $ax'+b$ value is uniformly distributed.
Sender sends $\textsf{Enc}( H(ax^i+b), y_i)$ for each $(x^i, y^i)$ pair in the database. Receiver can decrypt exactly one of them.

  Zhangxiang Hu, Payman Mohassel, Mike Rosulek:
  Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost. CRYPTO (2) 2015: 150-169


Differential and Linear Crypt-analysis. Number of Active S-boxes
  along-with the Differential and Linear probabilities of S-box
  contributes towards resistance against these attacks which also
  depends upon the branch number of the P Box. (Diffusion layer)

it is not only the branch number that influences on the number of active s-boxes, the cells permutation has a role, different permutations have different number of active s-box over rounds such as in skinny and midori cases.ref

  Impossible Differential. There exist one 5 round impossible
  differential in feistel cipher with bijective F function. So cipher
  with more than 10 rounds will have a good security margin against this
  attack

in term of SPN ciphers , according to this paper, the existence of impossible differential up to 6 rounds which are strongly related to the linear transformation properties.

  Boomrang Attack. This uses two differentials and security against these again depends upon number of active S-boxes along-with the Differential probability of the S-box.

a new measure analysis called boomerang connectivity table of S-box provides insights on boomerang crypt analysis which provides a fundamental understanding how the S-box  properties counter the boomerang attack. ref

  Higher Order Differential. To resist this attack, Degree of the Boolean polynomials of the S-Boxes should be higher.

using larger S-box with higher algebraic immunity provides a counter to higher order differential.

what about integral crypt analysis (division property of sbox) ?


How can I prove that it is impossible to find a cheater in shamir secret sharing?

You could use the fact that having two of three pairs does not reveal any information about the secret (polynomial). Also see the Wikipedia article on Shamir's secret sharing: it provides you with a nice graphical answer to your question.


Paillier paper: Number Theoretic Lemma doesn't seem to work

Short answer: This appears to be an error in the paper, but it's not a problem in practice.

The proof of Lemma 3 uses the following implication:

  Since $\gcd(\lambda,n)=1$, $x_2-x_1$ is necessarily a multiple of $n$. Consequently, $x_2-x_1=0\bmod n$ and $(y_2/y_1)^n=1\bmod n^2$, which leads to the unique solution $y_2/y_1=1$ over $\mathbb Z_n^\ast$.

As your example shows, the assertion $\gcd(\lambda,n)=1$ is wrong in general: $n=2\cdot 3$, hence $\lambda=(2-1)\cdot(3-1)=2$, and $\gcd(\lambda,n)=2\neq1$. Structurally, this becomes manifest in the fact that the ring $\mathbb Z/n^2$ contains nontrivial $n$th roots of unity — in your case the element $5$ — which voids the uniqueness claim.

It is not hard to prove that for $n=pq$ a product of two primes, this phenomenon occurs if and only if $p=2$ or $q=2kp+1$ for some $k\in\mathbb N$. (Modulo reordering of $p$ and $q$.)
The chance of this happening is negligible for any realistically-sized and randomly generated pair of primes $(p,q)$, hence this is not going to be an issue in practice.


Polynomial sum of negligible functions need not be negligible

Consider the negligible functions
$$\epsilon_i(n) = \begin{cases} 1 & \text{if } n \le i \\ 0 & \text{if } n > i \\ \end{cases}$$

and $q(n) = n$

It should be easy to show that each $\epsilon_i$ function is, in fact, negligible, but the sum $f(n)$ is not...


Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

Yes. The subset of $\Bbb Z_n$ of integers that are relatively prime to $n$ (otherwise said: the set of $x$ in $\Bbb Z_n$ with $\gcd(n,x)=1$ ) form a group under the multiplicative law of $\Bbb Z_n$ (multiplication modulo $n$ ).

That finite group is noted $(\Bbb Z_n^*,*)$ or just $\Bbb Z_n^*$, or $(\Bbb Z/n\Bbb Z)^\times$. It has $\varphi(n)$ elements, where $\varphi$ is the Euler totient.

That group is cyclic (otherwise said: generated by a single element) iff $n$ is in one of three forms: $4$, $p^k$, $2p^k$ (for $p$ an odd prime and $k\in\Bbb N$, including $k=0$); that is for $n$ in A033948.

Thanks to Poncho for a useful comment.


Should the field size in Shamir secret sharing scheme be larger than secret?

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel like getting into a discussion of what a field is (look it up in Wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.
If you replace 50 with 53 (which is prime), then it would work.
In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to).  Of course, it's up to you if you want to look into that; you might want to learn the basics with a prime field (which is what you're using) first.
In any case, to address your question:

So, in order to use Shamir's scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the field size, we generally divide the secret into a number of smaller secrets, and share each subsecret independently.
For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that.  When it comes time to reconstruct, we construct each of the byte values independently, and then concatenate them to form the original 16 byte secret.
Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system.  On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.
Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte).  That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...


No it's not.

As a reminer: Semantic security is equivalent to IND-CPA. Semantic security is less commonly used, because most of the time proofs are less intuitive and more difficult.

In the IND-CPA game, the attacker chooses two messages $m_0,m_1$ and sends them to the challenger. The challenger chooses a bit $b$, and sends $Enc(m_b)$ to the attacker. The attacker wins if he can guess $b$ correctly. And we consider the encryption scheme secure, if the advantage of the attacker compared to random guessing is negligible.

So, let's play the CPA game with this variant:

The attacker chooses $m_0$ and $m_1$ arbitrary (but not equal)
He gets back $Enc(m_b)$. In your scheme that would be some value $v$ and $(v+m)^e \mod n$.
Since he knows both $m_0$ and $m_1$, he can check both possibilities by calculating both $(m_0 + v)^e$ and $(m_1 + v)^e$. Comparing that with the challenge, he immediately knows $b$
The attacker wins.

If you want to have an IND-CPA RSA variant, there is RSA-OAEP. In the random oracle model and with the RSA assumption, this is proven to be IND-CCA2, which is much stronger than IND-CPA.


What operations are used in symmetric cryptography and why?

which else operations are used in cryptography and why?

This question is hopelessly broad, but I'll give the "which" a shot. Ignoring asymmetric constructions like RSA, cryptographic primitives typically stick with operations that are either a single instruction in common architectures or can be implemented cheaply with a combination of a few instructions. Thus, bit rotations, arithmetic addition, logical bitwise operations like AND, OR, and XOR, and so on, are all good candidates for operations. Table lookups are also quite common to speed up implementations.

It's not really the operations themselves that are so important, however. The way you combine them is (obviously) far more important, and hence unless you have a specific question about why a specific operation has so much use, it's not really all that relevant to ask "what operations are used". Instead, study things like how the Merkle–Damgård construction can be used to build a hash function, how a substitution-permutation network can be used to build a block cipher, how HMAC can transform a relatively weak hash function into a good MAC. If you would like more examples, I can provide them.

These are the important building-blocks of primitives, not necessarily the operations underlying them. The operations are obviously important, but don't miss the forest for the trees.

On the other hand, you have the mathematical schemes, for lack of a better term. These use mathematics to achieve some goal, and hence the "operations" in them are virtually limitless. RSA and Diffie-Hellman both use modular exponentation, though in different ways; Shamir's secret sharing scheme relies on the idea that a $n$-degree polynomial can be uniquely identified with $n+1$ points, and so uses polynomial evaluation in a finite field as well as Lagrangian interpolation; the Merkle-Hellman knapsack cryptosystem relies on the subset-sum problem; and it just goes on and on.

There are zero-knowledge proofs, secure multiparty computation schemes, cryptographic voting schemes, fully-homomorphic encryption schemes, functional encryption schemes, identity-based schemes, ... the bounds are limitless. Trying to exhaustively list the operations used here is futile.

My point is that cryptography is a vast field. There are operations aplenty, but far more interesting are the schemes themselves. The operations are just means to an end.

  What is the difference between addition modulo 2 (xor) and addition
  modulo 2 ^ register size (addition with overflow)?

XOR is not just "addition modulo 2"; it's bitwise addition modulo 2, and I dislike this definition. The point of bitwise exclusive-or is that the output of each bit is 1 if and only if the two input bits are different. Hence, it is an exclusive-or: exclusively, one of the bits may be turned on. If both are on, or both are off, the output is 0. This property makes XOR an involution, i.e. a function that is its own inverse. Bitwise-AND and bitwise-OR are not invertible.

Addition modulo 2^{register size} is just what it says on the tin: the addition can overflow or underflow.


chacha20-poly1305 padding and length encoding

The reason for the padding (and re-positioning of the AAD length) in the later draft is to make implementations easier and faster - i.e. not for a security reason.

The rationale for this change was actually documented on the CFRG mailing list by Alyssa Rowan:

  Instead of the lengths directly following their ciphertexts:

  draft-agl-tls-chacha20poly1305-04:

  AAD | len_AAD | ciphertext | len_ciphertext

  this final version of the AEAD pads the Additional Authenticated Data
  (if any) and ciphertext to a 16-byte block boundary (using between
  0-15 zero bytes) and moves the lengths to the end:

  draft-nir-cfrg-chacha20-poly1305 (the final AEAD specified here):

  AAD | padding1 | ciphertext | padding2 | len_AAD | len_ciphertext

  which is more efficient to implement (block-aligned, and the recipient
  knows the lengths are at the end, instead of having to jump backwards
  to find len_AAD). Thanks to Niels Moeller for that idea.


Determining key size in bits by knowing plaintext and ciphertext

I need to know how can I determine the key size in bits knowing the ciphertext and the encryption algorithm used?

That depends on what you mean exactly by the term encryption algorithm used.

The full description of an encryption scheme usually consists of three parts. For example if AES-128-GCM was used to encrypt, that means that the block cipher AES was used in GCM mode using a 128 bit key. If your scheme is named liked this, than you are presented with the key length directly (Note that there are different schemes as well (like stream ciphers), which won't follow this naming scheme).

If the key size is not included in the name, there is usually no way to deduce it from the ciphertext. This is due to the fact that most encryption algorithms can be used with different key sizes (128, 192 and 256 bits in the case of AES) while keeping other parameters, visible to the outside world (input and output length), the same.

  For example suppose the plaintext was "ABC" and after the encryption it became "DEF" so the key size in bits = 1 bit because each letter is shifted only by 1 to its next character? Or I am wrong?

In the case of the classic Caesar cipher that you are using here, the key is an integer value between zero and 26 (of 52, or 62, if you allow for more characters) specifying the shift. So, depending on the size of your alphabet (the number of input / output characters that will be encrypted), the key's size will be between 5 and 7 bits.


Are there cryptographic schemes that mask as unencrypted traffic?

Well there is Steganography like Richie said in the comments it is essentially the art of hiding messages. This being said it is not comparable to any encryption algorithm (like AES) security wise. Though there are tools for steganography which requiere keys so they encrypt data before they hide it but this is not the essence of steganography since steganography is only about hiding the message.

If you are looking for a way to hide your messages this would be sufficient, if you want to properly encrypt it you can do that before hiding the message.

If you're looking for only an algorithm which mutates a text to a different text i'm afraid your out of luck. a home brew of a pseudo random pad where you make the key in such a way the words change like this:

plaintext: Welcome
key: kkdbnma
cipher text: Goodbye

Though this is insecure, it might be fun to play around with but it is not to be used in real life situations!

EDIT:
as pointed out Robert NACIRI there is also the use of subliminal channels as described by this wikipedia article. As it suggests it hides messages inside normal communications, read it through for examples and a better sense of how this works. It's quite interesting.


Proving set membership in less than $\log{N}$ bandwidth

Depending on your trust assumptions about this server, you might be able to use cryptographic accumulators which provide constant-sized (non)membership proofs.

However, as far as I know, no efficient strong accumulator scheme has been developed yet. Most accumulator constructions rely on the RSA assumption where the server knows the factorization $n = pq$ of the modulus $n$ and, as a result, can compute fake membership proofs for any element $x$ by taking the accumulator $acc$ and computing a fake proof $mem = {acc}^{x^{-1} \pmod {\phi(n)}}$. The proof is verified by checking that ${mem}^x = acc$, which is true because the server faked the proof by inverting $x$.

This happens because the server can easily compute $\phi(n) = (p-1)(q-1)$ and invert $x$.

To fix this problem, a trusted setup phase is necessary that generates a modulus $n$ of unknown factorization and gives it to the server, without giving the server the factors $p$ and $q$.

Also note that pairing-based accumulators need a trusted setup phase. However, I suspect they would be faster in practice than RSA, if you want non-membership proofs!

You might find the following accumulator papers useful:

One-way accumulators: A decentralized alternative to digital signatures
Collision-free accumulators and fail-stop signature schemes without trees
Cryptographic accumulators: Definitions, constructions and applications
Universal Accumulators with Efficient Nonmembership
Proofs
Accumulators from Bilinear Pairings and
Applications to ID-based Ring Signatures and
Group Membership Revocation

The following paper proposes using a certain kind of group called a class group to construct a strong accumulator. I am not sure how it constructs (non)membership proofs though.

Secure Accumulators from Euclidean Rings without Trusted Setup


"Batched affine" short-Weierstrass elliptic-curve additions

The affine addition formula for short Weierstrass curves is usually given by
$$
\begin{align}
\lambda &= \frac{y_2 - y_1}{x_2 - x_1} \\
x_3 &= \lambda^2 - x_1 - x_2 \\
y_3 &= \lambda(x_1 - x_3) - y_1 \\
\end{align}.
$$
This gives us 1 inversion, 2 multiplications, 1 squaring, and a few field additions.
The trick here, when adding many points in parallel, is to use the so-called Montgomery trick (thus called because it was popularized in Montgomery's 1987 paper), which trades $n$ inversions by $3n$ multiplications and a single field inversion.
Here follows a simple description of the algorithm from Modern Computer Arithmetic:

So in reality you are still performing an inverse, but it is amortized among many simultaneous additions; for large enough numbers its cost becomes negligible.


Are keys generated by the user or block cipher algorithms themselves?

Key generation and key scheduling are different things. The key scheduling is part of the cipher, the key generation generally isn't.

Symmetric keys should be indistinguishable from random, so often they are the product of a secure random number generator. There are other ways as well, such as derivation from a password using a Password Based Key Derivation Function or as the result of a key agreement algorithm, possibly followed by a Key Based KDF.

DES and triple DES are a bit special as the keys are normally augmented with parity bits that are ignored in the actual cipher. So there may be routines that calculate or verify these parity bits. Those routines are however commonly not considered part of the cipher itself and modern libraries may forgo the parity calculation altogether.


Key Exchange MAC encryption order of events? Problem

You're right, it seems like there is a typo in Step 4. The MAC Slave Key should be encrypted with the MAC Master Key, as that is the information that is shared between partners. This is alluded to in the parenthetical, noting that only the partner has the Master Key to decrypt it.


Prove that (m1 ⊕ m2) = ek(m1) ⊕ ek(m2) for a 8-bit blocks i/p encryption system

Let $k$ be the 8-bit key.  Since encryption is simply done by XORin the plaintext with the key, i.e. $e_k(m) = k \oplus m$, we have:

$$e_k(m_1) \oplus e_k(m_2) = (k \oplus m_1) \oplus (k \oplus m_2).$$

Now, the thing you need to know about XOR is that it obeys the same commutative, and associative laws as normal addition, that is:

$$a \oplus b = b \oplus a$$
$$a \oplus (b \oplus c) = (a \oplus b) \oplus c$$

and it also obeys the cancellative laws:

$$a \oplus a = \bar 0$$
$$a \oplus \bar 0 = a$$

where $\bar 0$ denotes the string of all zero bits.

Using these algebraic laws, you should be able to show that the two $k$'s on the right hand side of the equation above will cancel out, leaving only $m_1 \oplus m_2$.

Similarly, you should be able to show that, if $k \oplus m = m$, then $k = \bar 0$.  The easiest way is probably to observe that, if $a = b$, than $a \oplus c = b \oplus c$.  Thus, you can XOR both sides of the equation $k \oplus m = m$ with $m$, and then apply the cancellative law.


why Niederreiter cryptosystem is not a candidate in NIST PQC competition?

Classic McEliece is using the Niederreiter T-OWF:

The KEM is built conservatively from a PKE designed for OW-CPA security, namely Niederreiter’s  dual  version  of  McEliece’s  PKE  using  binary  Goppa  codes.

https://classic.mceliece.org/nist/mceliece-20201010.pdf


Is a secure deterministic MAC always a PRF?

Your intuition is not right. The fact that no forger can obtain new valid message/tag pairs doesn't say anything about the "shape" of the MAC. For instance, if $\Pi$ is a secure MAC, then the MAC obtained by appending a bunch of zeros at the end of the tag is secure as well:

  If a forger $\mathcal{A}$ is able to create a new and valid message/tag pair $(m,t)$ for our modified MAC (the one obtained by appending the zeros to a secure MAC), then $(m,t')$ would be a new and valid message/pair for $\Pi$, where $t = t'||0^n$ (you would need to be more precise with the games being played here, but the idea is that any msg/tag pair for one MAC corresponds to one msg/tag pair for the other)

But of course this is not a pseudorandom function.

I think your intuition is that a secure MAC can not reveal anything about the underlying message, but this is not right. The security of a MAC relies on the hardness of generating new messages/tag pairs, not in the difficulty of learning anything about the underlying message. In fact, a MAC can reveal the whole message! can you imagine how?


How can I split a message in parts of similar size or smaller?

If the requirement is being able to reconstruct a message of $1280=160\cdot 8$ bits from $3$ parts that are among a set of $2^6$ type-able characters (say $10$ digits, $26$ uppercase letters, $26$ lowercase letters, and $2$ other characters, as in Base64), then no cryptography is required. Simply:

split the $1280$ bits of the message into $3$ nearly equaly-sized segments, here of $427$, $427$ and $426$ bits;
append to each segment something allowing to order the $3$ segments and making them a multiple of $6$ bits, e.g. here 00000,00001, 000010; now all messages are $432=72\cdot6$ bits, the two right bits identify the segment number;
encode each segment as $72$ type-able characters, each encoding $6$ bits.

Decoding, identifying and pasting together the segments is easy and left as an exercise to the reader.

If there is the additional requirement that knowledge of $2$ of the $3$ encoded segments should give no useful information about the message, then we need some cryptography. One simple method, optimized to reduce message expansion, is:

generate a random 128-bit $K$;
encipher the message with key $K$ (say using AES in CTR mode with implicit null IV);
split the enciphered message in $427$, $427$ and $426$ bits data segments as above;
XOR the first $128$ bits of each of the segments, and $K$, forming $K'$;
splits $K'$ into $3$ segments of $42$, $43$, and $43$ bits, append these to the respective data segments, and append the terminations 00000,0001, 00010, forming $3$ segment of $474=79\cdot6$ bits, that can be identified by their rightmost 2 bits;
encode each segment as $79$ characters each encoding $6$ bits.

Decoding is easy:

decode each segment of $79$ characters into $3$ segments of $474$ bits;
identify each segment by its right two bits;
remove the terminations, rebuilt $K'$, remove these;
XOR the first $128$ bits of each of the segments, and $K'$, forming $K$;
rebuilt the enciphered message;
decipher it using $K$.

If any of the encoded segments is missing, $K$ can't be formed again.

Notice that we must expand the message with random data somehow, or loose semantic security.


Why do cryptographers need loads of true random numbers?

Mostly, you do not actually need a lot of true randomness, as you observed. However there are at least some niche cases where you might want a fast TRNG.

Stateless implementations cannot use a typical CSPRNG. Something like a hardware token without writable storage, maybe. The intersection with applications that require a lot of speed is pretty small.
Long term key generation. People tend to want true random numbers when generating long term keys. That is not usually a frequent event, but perhaps something like a federated key store would need to do it often enough.
Latency. Even if you do not need gigabytes of entropy every second, getting e.g. 256 bits quickly can be important. Although again it is probably rare to need it and not be able to use a cache.

There are probably also use cases where the random numbers are used for non-cryptographic algorithms, but need to be both strong and non-deterministic. Maybe in gambling.


Hash into elliptic curves for private set intersection

However in the case of a private set intersection we can use a secret key $s$, so if I am correct the discrete logarithm of $h(m) *s$ would not be known :

That is correct; it is not known; however that is not sufficient; the relationship between $h(m_1) * s$ and $h(m_2) * s$ would be known (if you know $m_1, m_2$), and that breaks security (at least, within this protocol).
In this protocol, Bob computes (in step 3) $h(m_{1}) * s_A * s_B * G$ and $h(m_{2}) * s_B * G$, and sends them (in step 4) to Alice (and then Bob has no further interaction with Alice).
If Alice has a guess $m'_2$ of Bob's value, what she can do is compute $(h(m'_2) * h(m_1)^{-1}) * (h(m_{1}) * s_A * s_B * G)$ and $s_A * (h(m_{2}) * s_B * G)$; if these are the same, then her guess $m'_2$ is the same as Bob's $m_2$.  Alice can perform this computation with any number of $m'_2$ values, without any further interaction with Bob; allowing her to recover a guessable Bob's secret value after a single exchange.
This works because Alice is able to derive what her exchanged value would have been, had she started with a different secret to begin with.


Where did they get numbers for RSA factoring challenge?

RSA-896 solution costs $75,000

Actually, that was the cash prize that RSA offered for a factorization; this cash prize has been since withdrawn.

  But where did they get this number? Does anybody in the world know the factoring?

To quote RSA:

  The generation took place on a Compaq laptop PC with no network connection of any kind. The process proceeded as follows:

  First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port.

  The random bytes were used as the seed values for the B_GenerateKeyPair function, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion was exported, in DER format to a disk file.

  The moduli were extracted from the DER files and converted to decimal for posting on the Web page.

  The laptop's hard drive was destroyed.

So, if they are to be believed (and people generally do), no one currently knows the factorizations (at least, of the values that have yet to be publicly factored).


Attacking a variation of the Vigenere with very long key length

The important part about the length is how many letters appear on those 17 characters:
YVBCXGJRYHHRCJIUL
WEDNESDAYTHURSDAY
WEDNESDAYSATURDAY

We have the plaintext of 12 of the 17 characters. This should probably let us recover 12 character of the key, and then guess the remaining characters based on context (key is probably made of words, not randomly).


Using SHA1 to obfuscate published resource IDs

(should I) use something else (than SHA-1)?

Yes. That seems to be a good application of purposely slow hashes intended for password hashing, like Argon2id, or it's ancestor scrypt, or (if all else are unobtainium in the context) SHA-2 followed by bcrypt (don't even google PBKDF2-HMAC-SHA-1, which is obsolete).
These are like SHA-1, less cryptographic break of it's resistance to collision, plus an output size parameter, a plethora of extra inputs for key as HMAC or/and other salt/associated data should that be needed. And most importantly parameters to tune the execution speed; with the whole thing crafted in a way such that adversaries using GPUs or ASICs for brute force search of valid string won't gain so much advantage over using a CPU, as legitimate users do.
This will let you increase security significantly at equal size and number of IDs, or/and safely reduce size of IDs. Just tune the parallelism parameter to the minimum number of physical threads on all platforms using the system (perhaps less 1 or 2 to keep the thing user-responsive, but with a minimum of 1; use 1 if in doubt); memorySizeKB to the lowest free RAM available on all platforms (for all threads, less a fair safety cushion, including for launching the stated number of threads/processes); then up iterations to what's tolerable on all platforms.


FIPS 140-2 and FIPS 186-2 (PDF) are not standards that describe RNGs.

FIPS 140-2 refers the task of standardizing RNGs to SP800-90 (PDF) which specifies software-based pseudo random number generators, to which your module seems compliant.

FIPS 186-2 only talks about RNGs in one place, in Appendix 3, where it says that using the RNG from appendix C of ANSI X9.17 is appropriate (it no longer is as of today) and it also says that using other FIPS approved is appropriate. As it stands it looks like the RNG can be considered appropriate because FIPS 200 (PDF) says, that you should follow SP800-53 (PDF) which in turn says that SP 800-90 should be followed, which specifies the RNG in question and thereby the RNG is "FIPS-approved".

Note though that you can't claim FIPS 186-2 compliance just because you use a compliant RNG because FIPS 186-2 specifies the RSA, DSA and ECDSA signature algorithms which you'd have to implement and provide properly in order to claim FIPS 186-2 compliance.

The relevant quote from FIPS 186-2 Appendix 3 (PDF):

  Any implementation of the DSA requires the ability to generate random
  or pseudorandom integers. Such numbers are used to derive a user's
  private key, x, and a user's per message secret number, k. These
  randomly or pseudorandomly generated integers are selected to be
  between 0 and the 160-bit prime  q  (as  specified  in  the
  standard).   They  shall  be  generated  by  the  techniques  given
  in  this appendix, or using other FIPS approved security methods.

  One FIPS approved pseudorandom integer generator is supplied in
  Appendix C of ANSI X9.17, "Financial Institution Key Management
  (Wholesale)".


Messages exchanged between Bob Alice are encrypted safe?

Technically, the message is signed by Alice using her private key and encrypted using Bob's public key. So only Bob may decrypt it using his private key and he can check the authority using Alice's public key.

Both should check each other key validity using an external procedure before using such encryption/signing, e.g. meet face to face in a bar and verify keys fingerprints.


One disadvantage of DSA as conventionally implemented is that the key can be compromised if signatures are created on machines with poor random number generators.

In the wake of the Debian openssl fiasco this meant that any DSA key that had been used in an openssh client on an affected machine was potentially compromised. With RSA keys only keys generated on machines with the bad random number generator were affected (and were dealt with by a blacklist).


Is there a way to encrypt an integer within an arbitrary range?

What you are asking is a straight application of Format Preserving Encryption, which builds ciphers which input and output are in a constrained format (generically: common to input and output, hence preserved). The FPE field has many articles with proven techniques; and proposed standards, including BPS and SP800-38G Draft.

Note: the method tentatively used in the question is not Cycle-Walking, and I do not see that it can be made to work if the cryptogram is kept of the form aes_ofb_encrypt(data); problem is, if the encryption algorithm made more than one try, the decryption algorithm will first make a decryption attempt that does not match anything that the encryption side made, and will occasionally conclude it reached the original plaintext, when it did not.

Here is a minimal solution (for integers of arbitrary size), using a simple variant of CTR (or OFB) mode.

Let $[A,B]$ be the interval (assumed public), and $k\in\{128,192,256\}$ the bit width of the AES key. Let $W=1+B-A$ be the (positive) number of integers the interval. Let $n=\Big\lceil{\log_2(W)+2k\over128}\Big\rceil$ be the number of 128-bit blocks to encode $W-1$ in binary plus $2k$ extra bits.

We'll define $X\bmod N$ as the unique integer $Y$ with $0\le Y<N$ and $X-Y$ multiple of $N$. We'll assimilate integers and bitstrings using big-endian convention.

From the $IV$, let both encryption and decryption generate a bitstring $S$ of $128n$ bits by enciphering $(IV+j)\bmod2^{128}$ for $j$ growing from $0$ to $n-1$, using the AES block cipher (equivalently: by enciphering $n$ blocks of zeroes in AES-CTR mode; using OFB mode would also work though not equivalently).

Given the plaintext $P$, let the encryption procedure output ciphertext$$C=((S-P)\bmod W)+A$$and given $C$, let the decryption procedure output$$P=((S-C)\bmod W)+A$$
Trivially, ciphertext is in the desired range, and plaintext is recovered by the decryption procedure. $S$ is indistinguishable from uniform on  $\{0,\dots,2^{128n}-1\}$, thus $S\bmod W$ is nearly uniform on $\{0,\dots,W-1\}$, with a very slight bias towards values below $2^{128n}\bmod W$, but so low that the adversary gains negligible advantage.


What you describe is exactly using AES-CTR to encrypt a 32-bit or 64-bit message.  So, yes.


The short answer is: technically, no. The weaknesses of MD5 are not an issue here. However MD5 is seriously inappropriate, for it is the wrong king of security primitive; also its reputation is tarnished.

If a collision attack was to be feared, then using MD5 would be a disaster, for it is now hopelessly broken w.r.t. to collision resistance; but that does not seem to be a serious threat in the stated usage. At worse, it seem possible to exhibit different (master password, nickname) pairs resulting in the same account password, but I fail to see that it leads to a practical attack.

The main technical drawback of using MD5 in the stated usage is, paradoxically, MD5's main quality: it is fast. That makes password cracking much easier than for a purposely slow Password-Based Key Derivation Function like PBKDF2 or Scrypt, and slightly easier than if using a hash stronger than MD5, like one of the SHA-2. However being fast is not considered an MD5 weaknesses; using a fast hash is a weakness of the proposed usage.

Also, from a Public Relation standpoint, using MD5 is a bad idea, much like using a tire known to explode at high speed is a bad idea for a manufacturer of low speed cars.

Update: Unless the master password is imposed on the user (which makes the scheme much less useful), a controllably slow Key Derivation Function is required, and as an aside should be followed by a better method to generate an acceptable password (as pointed in that other answer). I recommend Scrypt, because it uses controllably much RAM and (possibly) CPU cores, hence raising the cost of a determined attack for a given penalty to the user (a small parameterizable delay, and using the computer's resources during that time). See this table from the paper defining Scrypt:
:
Note: A letter is random among 26 lowercases; a character is random among 95 ASCII symbols; text entropy per NIST SP800-63-1.


Can I use a key-derivation-function as the hash function H in SRP?

Yes, you can and use a slow hashing function when constructing the verifier.  I would recommend using PBKDF2, as it is designed for this purpose.

In fact, Wikipedia says:

  $v$ is the host's password verifier, $v = g^x$, $x = H(s,p)$. Using of functions like PBKDF2 instead of $H$ for password hashing is highly recommended.

Thus, you could use $x=\text{PBKDF2}(s,p)$.  Alternatively, you could pre-hash the password with PBKDF2, then use the result as your $p$.


First property says-
If you consider a 6-bit Inpput Difference(Difference means XOR in case of DES).i.e  6-bit binary number which is the xor of two inputs(obviously both 6 bits).When you enter both of these inputs to Sbox and get two outputs each of 4 bits and xor the outputs what you get is called Output Difference.

Total 64 inputs are possible hence 32 pairs having a same difference.

So this property says for any  non-zero 6-bit input difference there can be maximum 8 possible different 4 bit output difference and not more than that.

Hope i am clear


Why DDH is easy if a pairing function exists?

You don't 'remove the e', instead, you use the mathematical properties of it.

e satistifies the identities:

$$e(a^x, b) = e(a, b)^x$$

$$e(a, b^y) = e(a, b)^y$$

for any $a, b, x, y$

We also assume that the pairing is nontrivial (that is, $e(g,g) \ne 1$); typically, we further assume that $g$ generates a prime order group, this implies that $e(g,g)$ generates a group of the same order.

So, we have $e(g, g^c) = e(g, g)^c$ (second identity).

We also have $e(g^a, g^b) = e(g, g^b)^a = e(g, g)^{ab}$ (first and second identities).

So, if we have $e(g, g)^c = e(g, g)^{ab}$, because we know that the group generated by $e(g, g)$ and $g$ are isomorphic (even if we cannot compute that isomorphism in the $e(g,g)$ to $g$ direction; that's because all prime order groups of the same prime order are isomorphic), we then have $g^c = g^{ab}$


Why is the discrete log problem easy when the exponent comes from a binomial distribution?

Here's the deal.  The discrete log problem is feasible in the special case where the exponent is known to come from a small range of possibilities (e.g., the exponent is not too large).
Suppose we are given $y=g^m$, and we want to find $m$.  Suppose moreover we know that $m$ is small: $0 \le m < 2^{30}$, say.  Then it turns out it is easy to recover $m$, without too much computation time.

One very simple approach is to simply try all possible values for $m$: we compute $g^0$, $g^1$, $g^2$, \dots, $g^{2^{30}-1}$ and see which one of them matches $y$.  This will always find $m$, and it takes about $2^{30}$ computations.  It's feasible, but not super-fast: a few hours of computation, maybe.

A smarter approach is to use a square-root algorithm.  It turns out there are ways to solve this problem with about $2^{15}$ computations.  (Here $2^{15} = \sqrt{2^{30}}$, which is why this is known as a square-root method.  If we knew $0 \le m < M$, then these methods would require about $\sqrt{M}$ computations.)  This is eminently feasible, and very fast: perhaps a few minutes of computation.
There are several square-root methods that achieve this running time, including the baby-step giant-step algorithm (sometimes also known as Shanks' method) or Pollard's kangaroo algorithm (sometimes also known as Pollard's lambda method).

For more on efficient discrete log algorithms when the exponent is known to be chosen from a small range of possibilities, see Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset.
What does this have to do with your question?  Well, suppose we know that the exponent $m$ was drawn from a Binomial$(2^{30},1/2)$ distribution.  Then we know that $0 \le m \le 2^{30}$, so we $m$ comes from a small range of possibilities, and we can recover $m$ using the methods above.  Thus, it's not that there is anything particularly special about the binomial distribution, except that the binomial distribution is known to be bounded, and if this bound is small enough, then that lets us apply the methods above.

This situation often comes up in electronic voting.  Suppose there are $N$ different voters.  Let me sketch an approach for secure electronic voting using homomorphic cryptography.
We're going to have each voter encrypt their vote and published the resulting ciphertext somewhere for all to see.
Each voter's ballot will be encrypted as follows: for some particular candidate (say, Smith), we encrypt $m_i$ using a suitable public-key encryption scheme, where $m_i=0$ if the $i$th voter did not vote for Smith and $m_i=1$ if the $i$th voter did vote for Smith.  A voter's encrypted ballot is the concatenation of all of these ciphertexts, one per candidate, but for now let's focus on the part for Smith.  Each of the $N$ voters does this and publishes the resulting ciphertexts.
We choose a suitable homomorphic public-key encryption algorithm such that $E(m_1) \times E(m_2) = E(m_1 + m_2)$.  One standard way to achieve this is by encrypting $g^{m_i}$ using El Gamal encryption, so $E(m_i) = (g^{r_i}, h^{r_i} g^{m_i})$, where $r_i$ is random and chosen by voter $i$.  Each voter publishes their encrypted vote; thus, for voter $i$, $E(m_i)$ is published.
Since the encryption scheme is homomorphic, everyone is able to compute an encryption of $m_1+\dots+m_N$, using the relation $E(m_1+\cdots +m_N) = E(m_1) \times \cdots \times E(m_N)$.  Notice that $m_1+\dots+m_N$ is a tally of the total number of voters who have voted for candidate Smith, which is what we want to recover; and we have a public copy of an encryption of this.
Let $m=m_1+\dots+m_N$, so we have $E(m)$ and we want to recover $m$ to complete the tabulation of the votes.  During tabulation, the authorities (who have a copy of the private key, shared in threshold form) will use threshold El Gamal decryption to decrypt $E(m)$, which yields the value $g^m$.  Finally the authorities need to recover $m$.  Fortunately, they can do this by taking the discrete log of $g^m$.  This is feasible since we know that $m$ is in the range $0 \le m \le N$, and the number $N$ of voters can't be too large (e.g., we won't have more than a billion voters), so the above methods can be applied to compute this discrete log in this particular case.  I hope that makes sense.


Your code should work.

However you (implicitely?) assume the certificate uses PSS padding for the RSA signature. While this is possible, it is extremely rare in practice, you should try validation using PKCS#1 v1.5 signature padding instead.

Converted my last comment to an answer because it apparently solved the problem.


If a user has a copy of both the encrypted and decrypted data, he is in a position to perform at least a known-plaintext attack. If users can submit arbitrary plaintexts for encryption, they can conduct a chosen-plaintext attack, which is stronger. In a chosen-plaintext attack, the attacker can submit any number of plaintexts and can retrieve the corresponding ciphertext.

All reasonable encryption algorithms are resistant to chosen-plaintext attacks, and AES is considered a reasonable encryption algorithm. Someone in possession of some (plaintext, ciphertext) pairs cannot encrypt or decrypt other messages (except sometimes messages derived from the known messages if a bad mode is used). In particular, no matter how many known plaintexts and ciphertexts the attacker is, he has no method to obtain the key that is better than brute force (trying all possible $2^{128}$ keys).

Do note that deleting the private secret does not delete the master secret. The master secret can still be recovered from backup copies of the private secret that weren't deleted, from other users' private secret, or from extant copies of the master secret.


Encryption algorithms encrypt bits. All digital media (text, pictures, videos, etc) is stored as bits at the lowest level, therefore, they can all be encrypted.


Are hash functions "intentionally" designed to be efficient?

It seems your question is about design / choice criteria for hash functions, so let's go through all of them (or at least the more important ones).

Basic security. If your hash function fails to provide the basic security guarantees, e.g. 2nd and first pre-image resistance and collision resistance, there's no chance it's ever going to be used.
Advanced security. This is also a "must-have" for hash functions these days and includes things like "acts like a PRF" or "can be modeled by a random oracle".
Speed. If I have the choice between two hash functions that are equally secure for my purposes, I'm always gonna pick the faster one, unless there are other good reasons to pick another one.
Endorsements. As everywhere, if you have a good "marketing department" your product is gonna be widely used. This also holds true for hash functions which benefit massively from endorsements such as "SHA-3 finalist", "SHA-3" or endorsement by NIST, BSI, ...
Elegance. Many good hash function designs try to be simple but effective to ease analysis and give confidence that no "hidden problems" can be found because it's all "so simple".

To go a bit further into the speed side, you want your hash function to have a nice synergy with your hardware. E.g. Keccak has been designed to be fast once the gates for the the $\chi$ step will be integrated in the hardware (this is why hash competition have VHDL design requirement).


Why is $Mac_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$ not a secure MAC?

We want to forge the tag for $m = m_1 || m_2$. The tag we need to produce is:

$$\operatorname{Mac}_k(m_1||m_2)=⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$$

We'll query the oracle with the message $m_1^\prime || m_2^\prime$, which needs to be different from $m_1||m_2$ to count as forgery. Consider $m_1^\prime || m_2^\prime = (m_1 \oplus \overline{m_2}) || m_2$, which is different from $m_1||m_2$ iff $\overline{m_2} \neq 0$.

This message has the tag:

$$\begin{align}
  \operatorname{Mac_k(m_1^\prime||m_2^\prime)}
  &=⟨F_k(m_1^\prime),F_k(m_1^\prime \oplus \overline{m_2^\prime})⟩ \\
  &=⟨F_k(m_1 \oplus \overline{m_2}),F_k((m_1 \oplus \overline{m_2})\oplus \overline{m_2})⟩ \\
  &=⟨F_k(m_1 \oplus \overline{m_2}),F_k(m_1)⟩
\end{align}$$

swapping the two outputs produces the tag for $m=m_1||m_2$.

Thus we can produce forgeries using only a single query to the MAC oracle.


What is the difficulty of DLP in GF(P^Q) with a subgroup with a prime order of L

First there are the "generic" discrete logarithm algorithms like Shanks's "baby step, giant step" and Pollard's $\rho$, which run in $O(\sqrt{L})$ and are thus of exponential complexity (in the size of $L$). Those algorithms work in virtually any group.

In the special case of the multiplicative groups of finite fields, we have subexponential algorithms (i.e, algorithms which are "in between" polynomial and exponential). The index calculus algorithm has many variants whose complexity varies slightly depending on the relative sizes of $p$ and $q$ (see the Wikipedia page and its references), but the details are not very important unless you want to specialise in discrete log algorithms (in which case, read the references mentioned above). What's important for cryptography is that due to such algorithms, cryptosystems based on the discrete log in finite fields must use larger keys than those based on the discrete log in elliptic curves for the same level of security.

Also, the "quasi-polynomial" algorithm of Gaudry et al. works for small $p$ (basically, when $p \le q$), and such cases should therefore be avoided, but they were rarely used in the first place anyway.


Yes, generally the salt is prefixed to the ciphertext.
In principle you always generate a new key for each salt, so you might not need the IV. I would however use the output of PBKDF2 to create a randomized IV and key just to be sure (e.g. using SHA-512 and then use the leftmost 32 for the key and the next 16 bytes for the IV).
It is also possible to use HKDF on the output of PBKDF2 to split off both the data key and IV from the generated intermediate key (that's more neat, but also harder to implement).

Notes:

It would be a good idea to use an authenticated mode such as GCM. In that case the IV should be 12 bytes.
dkLen is specified to be in bits, not bytes - at least in the standard. Key sizes generally are.
A salt of 16 bytes is generally plenty, but 32 bytes is OK too (it should still fit in a single block of even SHA-256, so it will likely not influence the work factor created by the hash function and iteration count).


Security of semantically secure ciphers when the attacker knows the relation between plaintexts

Look at the definition of semantic security. It is for this exact reason that auxiliary information is modeled in the definition. This ensures that nothing is revealed even when the attacker knows partial information.


Decrypting data on client side for use inside program

If obfuscation id enough security, and you only want to protect the privacy of your data against meager adversaries and you have no requirements about authentication then your solution seems ok.
Also it isn't very crypto related.
Though there is a field of cryptographic obfuscation that is not practical to use.


Is Argon2id safe from the discovered Argon2i issues?

Covers Argon2id the known attacks?
Although there is no research into this, I would say that Argon2id is probably not vulnerable to the attack shown by Alwen and Blocki. Maybe an attack on the first part (the Argon2i part) could be practically applicable, but the advantage for the attack quality would be ruined by the second part (the Argon2d part), because the second part is the more memory-hard one.
Is Argon2id still side-channel resistant?
Reasonably or at least halfway. If you successfully perform a cache-timing attack on the second part (the Argon2d part), you will receive certain patterns, but they only refer to equal outputs of the first part (the Argon2i part), not to passwords.

Both attacks are complex and it is not entirely clear whether they are feasible today.

As far as I know, cache-timing attacks have not yet been executed against password hashing methods in the wild (for example against Scrypt). However, it has been shown that this is basically possible and it is quite feasible that such attacks will be carried out in the future.
Schemes based on the "Bit Reversal Graph" like Argon2i and Catena-Dragonfly seemed to be the solution - they were just less memory-hard.

Although there were voices that suggested that, the authors of Argon2 did not originally include the possibility of combining Argon2i and Argon2d (a hybrid structure), presumably to avoid making the usage more complicated. Lyra2 and other schemes of the password hashing competition relied on the hybrid structure from the beginning, mainly as a compromise between resistance against cach-timing attacks and higher memory-hardness.

It was only after the end of the password hashing competition that it became apparent that methods that are resistant to cache timing attacks are more vulnerable in other ways.

The attack of Alwen and Blocki is based on several conditions such as no parallelism (p=0) and assumptions about (probably realistic) hardware available in the future. But still a weakness is shown, which could possibly be extended even further.
I don't know of any official statement about this, but I suppose that in view of the attacks on Argon2i, the authors of Argon2 are now tending to prefer the hybrid structure.

Password hashing is an area that is much less explored than, for example, block cipher. It is therefore possible that new cryptoanalyses will be published and further changes may be necessary.


It's not harder.

Solve the DL problem to get $x$ in $Q=x.P$.
$Q = \sum_{i=1}^{n} x_i.P = (\sum_{i=1}^{n} x_i).P= x.P$

=> any set of $x_i$ that sums to $x$ (modulo the group order) is a solution to ECFP.


Why is there only one keypair in FrodoKEM?

Since there is only one keypair, doesn't that mean anyone can compute the shared secret with the public key?

No, because the secret ss1 is randomly chosen each time from a space large enough that there will never be a collision.


ABE Schemes - Access Structures & Performance

Let's assume that we're talking about monotonic access structures (without negated attributes in the policy).

A Threshold policy was introduced in Sahai, Amit, and Brent Waters. "Fuzzy identity-based encryption." Advances in Cryptology–EUROCRYPT 2005. Springer Berlin Heidelberg, 2005. 457-473. (link)

It means that a user secret key and the ciphertext are both associated with (possibly) different attribute sets. Decryption would only work if the overlap between the two sets is at least as large as the globally defined threshold (during setup). Here we don't distinguish between Key-policy ABE and Ciphertext-policy ABE.

An $(n,n)$-Threshold access structure is the same as AND gates. The later approaches usually use Shamir's Secret Sharing (SSS) with a variable threshold value $t$ as a $(t,n)$-scheme. If we require all shares to be present, then this essentially means that a single AND gates with $n$ attributes was used. Now, the authors chose to call it $(n,n)$-Threshold, because the attributes can be multi-valued (wildcards). This goes into the realm of Hidden Vector Encryption and non-monotonic access structures, even there it's still usually called AND gate.

The Tree approach was first described in Goyal, Vipul, et al. "Attribute-based encryption for fine-grained access control of encrypted data." Proceedings of the 13th ACM conference on Computer and communications security. Acm, 2006. (link)

It is a way of sharing a secret element across the attributes of a policy (KP-ABE or CP-ABE), which can then be reconstructed with Lagrange interpolation. See my answer here for more information. The construction of Goyal et al. permits not only AND and OR gates, but arbitrary threshold gates with SSS for every node of the tree. It is also fairly easy to build up the access tree from a textual representation such as a boolean formula.

Of course, there are other constructions that don't support arbitrary trees. For example Müller, Katzenbeisser and Eckert. "Distributed attribute-based encryption." Information Security and Cryptology–ICISC 2008. Springer Berlin Heidelberg, 2008. 20-36. (link) supports policies only written in a Disjunctive Normal Form (DNF).

A Linear Secret Sharing Scheme (LSSS) works on a matrix, where the rows are labelled with attributes of the policy, to produce shares from a secret element. This should be familiar as the outcome is the same as for the Tree access structure. In fact, when you implement a scheme, most of the time you can exchange an LSSS approach for a Tree approach, but that doesn't mean that it's secure anymore, because the security games and used assumptions may depend on a specific approach and may not work for the other.

If you're looking to convert a boolean formula to an LSSS matrix, then this is getting a little tricky, because it is not immediately apparent how this can be done. You can check with Lewko, Allison, and Brent Waters. "Decentralizing attribute-based encryption." Advances in Cryptology–EUROCRYPT 2011. Springer Berlin Heidelberg, 2011. 568-588. (link) to create an LSSS matrix from a boolean formulas, which use only AND and OR gates. Then Liu, Cao and Wong. "Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees" (link) present a way to use general boolean formulas (with threshold gates).

This was only a small number of access structures. Other notable mentions are Monotone Span Programs (highly related to LSSS), Branching Programs and Circuits (used in Lattice-based ABE constructions).


Searchable encryption vs Homomorphic encryption

Searchable encryption is a form of encryption where you can search for ciphertexts whose decryption satisfying some condition without decrypting those ciphertexts and looking at the decryption. The end result is typically a collection of ciphertexts.

Sometimes a secret key is needed to create a "search token" for a given query.

Searchable encryption for limited types of search is often quite efficient, but it tends to leak information.

Fully homomorphic encryption (FHE) is a form of encryption where you can do (a limited form of) computations on the decryptions of ciphertexts without decrypting those ciphertexts and looking at the decryption. The end result is an encryption of the result of those computations.

You can use FHE to do searchable encryption in various ways. This typically results in a very flexible form of searchable encryption that does not leak much information, but also quite inefficient (since FHE is currently rather slow).


Is it possible to create "non overlapping" RNGs?

Take a block cipher with a random key and for one generator encrypt the even numbers then with the other generator encrypt the odd numbers.  Your output blocks will be pseudo-random and distinct.  For more than two generators just partition the inputs accordingly.