RSA - Calculating $d$ given $\varphi (N)$ and $N$

Problem summary: in textbook RSA, it is given $N$, $\phi(N)$, and a ciphertext $c$. It is wanted the plaintext message $m$ and a private exponent $d$.

If $e$ or $m$ was random, that would be infeasible. But usually, $e$ is small thus guessable, and $m$ is highly redundant/recognizable. Thus we can try to compute
$$\begin{align}
d_e&=e^{-1}\bmod\phi(N)\\
m_e&=c^{d_e}\bmod N
\end{align}$$
for various small values of $e$ coprime with $\phi(N)$, and see which $m_e$ makes sense. Computing an $m_e$ has moderate cost, comparable to a normal decryption.

I'd first try $e=F_i=2^{(2^i)}+1$ for $i\in[0,4]$ (the Fermat primes, with $F_4=65537$ and $F_0=3$ very common). Then we can try (other) small odd integer $e>1$, including the popular $43$. I've also seen $e=2^{F_i}+1$ ($i\le3$), apparently due to a coding error.

If we find that a candidate $e$ is not coprime with $\phi(n)$, we can increase it by $2$ until it does, because some key generators do just that.


How to prove I know an x without revealing x or f(x)?

There is a technique called set membership proof. I am not an expert in this area, but it seems closely related. See the excerpts below:

  Given a set $\Phi=\{\varphi_1,\ldots,\varphi_n\}$ and a commitment $C,$ a typical approach to
  the set membership problem is to use a zero-knowledge proof of the form:

“$C$ is a commitment to the element $\varphi_1$ OR $\ldots$ OR it is a commitment to $\varphi_n$.”

  Even though there exist efficient algebraic $\Sigma$ (Sigma) protocols for handling a single such OR clause, such a proof still has length which is proportional to $n$.
  In many practical situations, the set $\Phi$ is often specified in advance by the verifying party. In other words, $\Phi$ can be considered a common input to both Prover and Verifier, and thus we might ask whether it is possible to prove a commitment is a commitment to an element of $\phi$ without having to explicitly list $\Phi$ in the proof.

The paper Camenisch et al with the above passage is available here, so start by looking at algebraic $\Sigma$ protocols if your $n$ is small, or to their techniques if it is large.


Is $f(x) = g(x) ⊕ g(\bar{x})$ a one-way function where $g(x)$ is a OWF?

Expanding on @Mikero's comment above: First, lets assume that a one-way function $h : \{0,1\}^n \to \{0,1\}^n$ exists.

Then assume towards contradiction that $f(x) = g(x) \oplus g(\bar{x})$ is a one-way function if $g$ is a one-way function. Then in particular $f'(x) = h(x) \oplus h(\bar{x})$ must be a one-way function. And further it follows that
\begin{align}
f''(x) =\;& f'(x) \oplus f'(\bar{x})\\ =\;& (h(x) \oplus h(\bar{x})) \oplus (h(\bar{x}) \oplus h(x))\\ =\;& (h(x) \oplus h(x)) \oplus (h(\bar{x}) \oplus h(\bar{x}))\\ =\;& 0^n
\end{align}

would be a one-way function, which it is clearly not as it is a constant function.


Figuring out key in hill cipher (chosen-plaintext attack)

Sure.  Assuming that you're using the encoding $A = 0$, $B = 1$, etc., just choose your plaintext messages to be the one-block strings:

$$
BA \dots A \\
AB \dots A \\
\vdots \\
AA \dots B
$$

The encryptions of these strings will then directly give you the columns of your key matrix.


I refer to you to a nice explanation of the basic attack on the "native" ElGamal scheme: How does chosen ciphertext attack on Elgamal work?

The difference between the native and this hashed scheme you outlined above is that the hashed elgamal version allows to encrypt a m-bit string message for any m since you use XOR, as long as the hashing function you use can output m bits. In the native ElGamal scheme, you have to map m into a group element, which may or may not be OK depending on which group you use. See Boneh's paper: section 4.1.
For example, it is not straightforward when using Ed25519 with the special encoding, but solutions exists such as the elligator mappings.


A function that doesn't have an inverse still has an inverse image or preimage.  I.e., if we have $f : P \to C$, and we can efficiently compute the set $f^{-1}(c) = \{p \in P\; |\; f(p) = c\}$, then that tells us information about what are the possible plaintexts $p$ for a ciphertext $c$.  It doesn't tell you which one of the alternatives is the "true" one, but in real life you very often have other, independent information about what the plaintext is likely to say.  If you put that independent information together with the preimage of the ciphertext, you may well end up inferring the plaintext.

Or an even dumber attack, you can just enumerate your independently- generated guesses at the content of the plaintext, from more likely to less likely, apply the function to each them, and see if the result matches the ciphertext.  Password cracking works precisely like this—the dictionaries and other tricks of the trade (masks, mutations, etc.) can be understood as hypotheses about which passwords real-world users are likely to pick, and the stolen outputs of the password hashes—which are functions without inverses—are used to test these hypotheses.  It's wildly successful.

So I would not look at it as a yes/no question, but as a quantitative one: how much does the attacker's knowledge of the function and ciphertext help them achieve their goal, relative to whatever independent knowledge they have?


Is SHA-1 still practically secure under specific scenarios?

I would recommend phasing out SHA-1 in any scenario where collision-resistance of a hash is required, for there is a wide consensus that an attack with $2^{69}$ complexity would work, it would already be feasible by a resourceful entity, and attacks only get better.

I'm still confident that SHA-1 is preimage and second-preimage resistant for all practical purposes in the foreseeable future, when its full output is used. Nevertheless, I would prefer SHA-256 or RIPEMD-160 when they are possible options.

I'm still confident that HMAC with SHA-1 is secure in any scenario where HMAC's key is assumed secret, for all practical purposes in the foreseeable future; this is because an improved security argument for HMAC remains valid with weak assumptions on the underlying (round function of the) hash. I could recommend it in a MAC application where using a tarnished name is not an issue, and speed matters.

Update: A collision for SHA-1 was published in February 2017 (4 years after this answer was written). It took an effort comparable to $2^{63}$ hashes (less than the $2^{69}$ consensual by 2013, but more than the $2^{61}$ of the best claimed theoretical approach, which turned out to have a few rough edges). The phasing out of the first paragraph has become a must. The second and third paragraph of the answer remain valid.


Why are twofish or other algorithms not NIST approved, are they still safe?

The reason NIST chose one algorithm out of the five AES finalists, even though all of them were pretty well-respected (and some were, at the time, considered likely to be more secure then Rijndael) is because NIST is a standards body, and the whole point of the AES project was to find a standard algorithm. The issue with approving lots of algorithms is that you can easily end up with multiple standards-compliant implementations that can't talk to each other because they don't implement the same algorithm. AES is supported everywhere, and is reasonably fast on all platforms (plus, the fact that it's so common makes stuff like AES-NI practical).

These days, it seems to be common to have several algorithms in order to provide a fallback if a flaw is found in one (for instance, that's the point of SHA-3), but that's not the normal way standards agencies work, and even with SHA-3 NIST picked one algorithm. It's not thought of as "good enough to make the list;" the rule is "the algorithm that best meets our goals for this standard."

As for why Rijndael was chosen -- it was a good balance of security, software performance, hardware performance, and ease of implementation (or so it was thought at the time; it's actually kinda tricky to securely implement). Twofish and Serpent were believed more secure at the time, but other things like performance meant they weren't good for all uses. Since the point was creating one standard, they weren't chosen.


The main reason is historical (and a bit sad).

ECDSA can be seen as a repurposed authentication mechanism. The private key owner wants to prove knowledge of the private key $x$ that matches a given public key $Q = xG$, but without revealing that private key. Thus, this is organized as a three-step protocol:

The prover makes a commitment on a newly generated random value $k$; the commitment is the point $kG$ (value $r$ is basically the X coordinate of that point).
The verifier issues a challenge (let's call it $e$).
The prover responds to the challenge with a value $s$, which is such that the verifier can check that the prover knew a value derived from $k$ and $x$, but without actually revealing $x$.

This authentication scheme is then turned into a signature scheme by making the signer play the protocol against himself: the challenge is computed deterministically from the commitment, making the physical presence of the verifier unnecessary. The signer can play the protocol by himself, and the transcript of the protocol (the pair $(r,s)$) can be verified non-interactively afterwards.

Now, in the 1980s, there was a nice protocol fitting that mechanism, known as Schnorr signatures. In a Schnorr signature, the challenge $e$ is computed as a hash value over the signed message and the commitment, and the response is computed as $s = k - xe$ (some variants make it $s = k + xe$). However, Schnorr had filed a patent on that algorithm. When the US federal government looked for an algorithm to standardize for all US federal organizations, they wanted to avoid patents as much as possible (otherwise, they would have used RSA, which was also patented). Thus, they looked for a more-or-less Schnorr-like protocol that would be nonetheless different enough so as not to infringe on the patent. They thus lifted the ElGamal signature scheme, which was not patented (at that time! Certicom filed patents afterwards, for ElGamal adapted to elliptic curves). It was ElGamal that introduced the modular inversion of $k$, which is cumbersome to implement. The result of the adaptation of ElGamal into a US standard was called DSA. ECDSA was later defined as DSA applied on elliptic curves.

Thus, you can say that the specific formula of DSA and ECDSA, with the $k^{-1}$, was chosen for patent avoidance reasons, not for any cryptographic advantage. Indeed, that formula sucks: it makes implementation more complicated, it prevents some security proofs, and it makes the signatures somewhat malleable (if $(r,s)$ is a valid ECDSA signature, then $(r,-s)$ is also a valid ECDSA signature on the same message with the same key), a property which has induced some occasional trouble (namely, transaction replay attacks in Bitcoin).


If a probabilistic encryption algorithm is used, how does decryption return the correct message?

In a probabilistic encryption scheme, for every plaintext there is more than one possible ciphertext.

Here's an example—with lots of details not related to your question omitted, so don't take these scissors and try running with this at home!

The recipient knows the secret ~256-bit number $r$ of times that a base point $B$ must be added to itself to yield a public point $R = B + B + \cdots + B = [r]B$ on some standard elliptic curve, say Curve25519.  (There's a shortcut to computing $[r]B$ so you only have to do a few thousand arithmetic operations and not a mindbogglingly unimaginable number.)

To conceal a message $m$ using the public point $R$, the sender:

picks a secret ~256-bit number $s$ uniformly at random;
adds $B$ to itself $s$ times to obtain $S = [s]B$;
adds $R$ to itself $s$ times to obtain $[s]R$;
computes $k = H([s]R)$, a secret key;
computes $c = \operatorname{crypto\_secretbox\_xsalsa20poly1305}(k, 0, m)$, the authenticated ciphertext under the symmetric key $k$ and nonce 0; and
transmits $(S, c)$ to the recipient.

The recipient, on receipt of $(S, c)$, then:

computes $[r]S = [r\cdot s]B = [s\cdot r]B = [s]R$;
computes $k = H([r]S) = H([s]R)$, the same secret key as the sender derived;
computes $m = \operatorname{crypto\_secretbox\_xsalsa20poly1305\_open}(k, 0, c)$, or rejects if forged.

There are roughly $2^{256}$ possible sender secrets $s$ that could be used to encrypt the message, and they all work for any message $m$, so in this cryptosystem, for any message $m$ there are about $2^{256}$ distinct ciphertexts that have $m$ as the corresponding plaintext.

This is not simply an artificial example.  To meet the standard notion of security for public-key encryption, indistinguishability under adaptive chosen-ciphertext attack, there must be many ciphertexts for any given plaintext, randomly chosen by the sender.  Otherwise, an adversary without knowledge of the private decryption key can easily tell whether a challenge ciphertext conceals one of two (or three, or $n$) possible plaintexts by encrypting the candidate plaintexts and comparing the resulting ciphertexts to the challenge.  This implies that the minimum number of distinct ciphertexts for each plaintext must be around $2^{192}$ to give confidence in security against multi-target attacks.

There are also probabilistic symmetric ciphers, like AES-CBC with randomly chosen IVs affixed to the ciphertext, or crypto_secretbox_xsalsa20poly1305 with randomly chosen nonces affixed to the ciphertext.  In this case, the randomization serves to prevent the same message content at different times from leading to the same ciphertext and enabling an adversary to recognize repeated messages.

Randomization per se is not always necessary in the symmetric setting: it is sufficient to deterministically keep state for crypto_secretbox_xsalsa20poly1305 and transmit each successive message with a count of the number of messages sent so far, for instance.  But in some cases like AES-CBC it is obligatory—though of course you could use a secret pseudorandom function of the message sequence number, such as $\operatorname{AES}_k(\mathit{seqno})$, to choose the AES-CBC IV.


What is the length of the SHA-1 message digest and how is RSASSA-PSS used for verification?

Currently iIam configuring SHA1 hash function which takes default length as 128 bit. Is it OK to configure with this, since I see in most of the SHA1 uses 160 bit? So what is the most common length used for SHA1 Hash?

Assuming that you mean output size: the output size of SHA-1 is 160 bits (20 bytes) and cannot be configured. In some cases protocols however use only the leftmost bits of the hash.

Although using only the leftmost bits is generally considered secure SHA-1 already has a security strength of about 80 bits (half of 160 bits output size) - about the bare minimum. Removing bits from the output size will also decrease the security, so that is not recommended.

Sometimes protection against pre-images is not an issue and cutting down the SHA-1 size is not a problem (HMAC-SHA1 for instance could use fewer bits).

  I read in many places that RsaSsaPss is used for verification of signature? I assume Message Digest or Hashed Value or Signature -> all these terms refers to output Hashed value of SHA1.

Only Message Digest or Hashed Value refer to the output of the hash value. The signature is generated using a combination of the hash function, the padding function (e.g. PSS) and of course the RSA modular exponentiation. More details in PKCS#1 v2.1 or v2.2.

  How to use Rsa Ssa Pss function to verify the signature? should i pass the Message Digest value and expect that the plain text should match with initial input given to SHA1 function?

Depending on the implementation you need either to pass the data and the signature into the signature verification function or you need to pass the hash function or hash value and the signature to the signature verification function.

The signature implementation must have been configured for the right algorithm and initialized for verification with the correct public key, of course.

For signature generation / verification it is generally required to use a secure hash function such as SHA-2.

Beware that the MGF1 function that is used for PSS may also use a hash function. You may have to configure that one separately - it should default to SHA-1 - which in the case of MGF1 would be secure.


I will give the hint:

It is a simple Mathematics rule, given $cp, e$, and $n$ we have this relation:

$(k \cdot p)^e \equiv cp \bmod n$, then we can write this modular relation as;

$k^e \cdot p^e = cp + l\cdot n$, for some $l \in \mathbb{Z}$

$p$ divides $n$ that we already know, and from the equality, $p$ also divides the $np$

Rest left to the op.


Can we use non-adaptive zero-knowledge proof in group signatures

This question is hard to answer in general, without specifying a concrete group signature scheme and a security model in which you want the group signature scheme to be secure.

However, we may observe some things: first you will need a non-interactive proof/argument system as signatures are non-interactive by definition. Second, you will most likely be required to include the common reference string (CRS) of the proof/argument system in the group public key. Third, you will probably (in any reasonably strong model I can currently think of) have to simulate proofs (resp. signatures) after handing the group signing key over to the adversary. In these cases you will definitely require adaptive zero-knowledge proofs/arguments, i.e., ones that allow the adversary to choose the targeted statements after seeing the CRS.

Nevertheless, it can not be excluded that one can define a (weaker, maybe also non-adaptive) security model as well as a construction in this security model which does not have this requirement. The question is whether such a model would still provide the security guarantees one would hope for.


What criteria make the theta step of Keccak's round function reversible?

I went through it, and while this isn't a complete answer, which should shed some light (and note: when I'm talking about $x$, $y$ and $z$, I'm referring to the ranges those indicies can take on; not any specific index)

First rule: if $x$ is even, then $\theta$ is invertible.  The proof of that is actually fairly elegant; however it's also rather irrelevant to Keccak (because even if you were going to tweak Keccak, the $\chi$ step requires $x$ to be odd).

Now, from here on down, we'll assume $x$ is odd.

Here is how it works; there is a function $L(y)$ that maps the range of $y$ into a set of integers; $\theta$ with the parameters $(x, y, z)$ is invertible iff $z$ is not a multiple of any of the integers within the set $L(y)$

$L(y)$ also has the property that $L(a) \cup L(b) \subset L(ab)$

Here is the list of $L(y)$ for $y<38$:

$L(2^n) = \emptyset$

That is, if $y$ is a power of 2, $\theta$ is always invertible

$L(3n) = \{ 1 \}$

What that means is that, since all values of $z$ are multiples of 1, then $\theta$ is never invertible if $y$ is a multiple of 3.

$L(5) = \{ 15 \}$

In the Keccak case, the actual value of $z = 64$ is not a multiple of 15, and hence $\theta$ is invertible.

$L(7) = \{ 7 \}$

$L(10) = \{ 15 \}$

$L(11) = \{ 341 \}$

$L(13) = \{ 819 \}$

$L(14) = \{ 7 \}$

$L(17) = \{ 85 \}$

$L(19) = \{ 9709 \}$

$L(20) = \{ 15 \}$

$L(22) = \{ 341 \}$

$L(23) = \{ 2047 \}$

$L(25) = \{ 15 \}$

$L(26) = \{ 819 \}$

$L(28) = \{ 7 \}$

$L(29) = \{ 475107 \}$

$L(31) = \{ 31 \}$

$L(34) = \{ 85 \}$

$L(35) = \{ 7, 15 \}$

$L(37) = \{ 3233097 \}$

Now, there are certain obvious regularities with above listed $L$ function values; for example, if $y$ is prime other than 2, then every $L(y)$ listed consists of a single element which is a divisor of $2^{y-1}-1$; and in every case listed, we have $L(ab) = L(a) \cup L(b)$; however I cannot prove either of those observations hold in general.


how do i implement zero knowledge proof?

Theoretically speaking it's rather easy.

You simply have the key owner (the prover) perform a proof that they have the private exponent for at least one of the public keys on the list. This is a standard OR-proof which composes multiple (Sigma) Zero-Knowledge proofs. As you're using standard elliptic curve crypto the public keys will be of the form $P_i=[x_i]G$ for a private key $x_i$ and the public key $P_i$ and some curve-defined generator $G$, this allows you do use a standard Schnorr-proof.

Prover (knowing $x_i, P_1,\ldots, P_N$):

Randomly choose $r\stackrel{\$}{\gets}\mathbb Z_q$ that is an integer in $[0,q)$.
Compute $a_i=[r]G$
Choose random $c_1,\ldots,c_{i-1},c_{i+1},\ldots,c_N\stackrel{\$}{\gets}\{0,1\}^h$ for $h$ being the output length in bits of your favourite hash function, e.g. SHA-256.
Randomly choose $z_1,\ldots,z_{i-1},z_{i+1},\ldots,z_N\stackrel{\$}{\gets}\mathbb Z_q$ and set $a_j=[z_j]G-[c_j]P_j$ for all $j\neq i$.
Compute your favourite hash function $c=H(a_1\|\ldots\|a_N)$ or alternatively receive a random $h$-bit string from an interactive verifier after sending them the $a_1,\ldots,a_N$ or if you have some context $m$ to the proof, append it at the end of the hash input.
Compute $c_i=c\oplus c_1\oplus\ldots\oplus c_{i-1}\oplus c_{i+1}\oplus\ldots\oplus c_N$
Compute $z_i=r+x_i\cdot c_i\bmod q$
Output (c_1,\ldots,c_N,z_1,\ldots,z_N) as the proof along with $m$ if any. For the interactive case outputting the $z$s suffices.

Verifier (knowing $P_1,\ldots,P_N$ and receiving $(c_1,\ldots,c_N,z_1,\ldots,z_N)$ as well as the optional $m$):

In the interactive case: Output a random string $c$ of length $h$-bit after getting the $a$s, then receive the proof.
Compute all the $a$s: $a_i=[z_i]G-[c_i]P$
In the interactive case: Check that $c_1\oplus\ldots\oplus c_N=c$ and that the $a$s computed in step 2 match those received before step 1.
In the non-interactive case: Check that $c_1\oplus\ldots\oplus c_N=H(a_1\|\ldots\|a_N)$ or with the context appended as specified.
If no check failed so far, accept the proof, otherwise reject it.

Of course the issue with the above protocol is that the proof scales linearly with the number of public keys on the board, but you'd need more sophisticated approaches to solve that (e.g. Ring Signatures).


Would the Intel SHA extensions help in creating SHA1 collisions?

If you break the attack into two phases, like in the SHAttered paper, it may help the first phase. The researchers say that they used a CPU cluster for the first phase; the more expensive second phase used a GPU cluster.

  ...from an attacker’s point of view, it may
  seem best to implement the attack on a CPU in order to be able to claim a better attack
  complexity. However, a GPU being far more powerful, it is actually much more efficient
  to run it on the latter: the attack of [18] takes only a bit more than four days to run on
  a single GTX 970, which is much less than the estimated 150 days it would take using a
  single quad-core CPU.

The trade-off is that GPUs may be more difficult to program, but on the plus side, they are more cost-effective.


I'm Chief Scientist at Security Innovation, which acquired NTRU, and one of the co-authors of NTRUSign.

The difference between NTRUEncrypt and NTRUSign is in how they use the lattice. All the NTRU algorithms are based on solving the Close Vector Problem in a particular form of lattice known as an "ideal lattice".

For NTRUEncrypt, the encryption method is basically:

Select a random point in the lattice
Add the message to that point as a small perturbation.

Decryption is then a matter of mapping back to the lattice point and recovering the message by subtracting the lattice point from the ciphertext. This only works because the message is chosen to have a particular form that means that the mapping back to the lattice point will always work. Well, almost always -- you may have read about decryption failures in NTRU. These occur when the mapping back to the lattice point doesn't work, but we can control their probability. But hold this thought.

For NTRUSign, the signing method is:

Hash the message to a random point in space
Find a lattice point close to that hash point and publish it as the signature

Verification is:

Hash the message to the same point in space
Verify that the signature point is a lattice point and is close to the message.

So this is the difference between decryption and signing. Decryption only works on messages with a very specific kind of structure, the structure that's produced by encryption. For decryption, those messages come out of encryption, so it's not a problem. But for signing, the "messages" (actually hashes) come out of a hash function, and creating a hash function that has the right structure but doesn't allow just anyone to sign is very hard. The obvious hash function to use is one that maps a message randomly to the integer vector space containing the lattice, and for this hash function decryption wouldn't work at all.


how does OpenSSH use bcrypt to set IV's?

If I am reading the code right, it does indeed use the key as the IV, here are the relevant functions:

sshkey_parse_private2 from sshkey.c is the function that performs the KDF and decrypts the private key blob. The KDF takes the
The first decryption function called within sshkey_parse_private2 is cipher_init, as follows:

r = cipher_init(&ciphercontext, cipher, key, keylen, key + keylen, ivlen, 0)) != 0)

The format of that function from cipher.c:

cipher_init(struct sshcipher_ctx **ccp, const struct sshcipher *cipher, const u_char *key, u_int keylen, const u_char *iv, u_int ivlen, int do_encrypt)

That means the IV passed to cipher_init is simply key + keylen

Additionally, the round count for bcrypt is 16


Is there a situation where RSA cannot be replaced with ECC + symmetric algorithms? If no, why do we still use it?

Summary: ECC+symmetric algorithms can do almost anything RSA+symmetric algorithms commonly do (plus forward secrecy where RSA struggles). But RSA is often preferred, sometime rightly so, in particular due to it's superior performance for the public-key side.

At common security levels, the public-key RSA operation (used for signature verification, and on the encryption side of public-key encryption) remains significantly more compute-efficient than anything ECC-based has to offer. That's an advantage in some applications, including:

For the signature of a digital certificate: it can be verified many millions times in its active lifetime, when it is generated only once; the cost of its signature can be neglected entirely, while the power or/and time saving by the users of the certificate becomes sizable. That is part of why CAs typically use RSA public/private key pairs.
For data (including code) signature verification by underpowered devices (IoT).
For asymmetric encryption by underpowered devices (IoT), complemented by symmetric crypto for large ciphertext.

To illustrate: with $e=3$, on a CPU with 32×32→64-bit multiplication, a straightforward RSA signature verification with $n$-bit public modulus uses about $4(n/32)^2$ multiplications (e.g. <17k multiplications for $n=2048$), while ECC-based crypto in field $\Bbb Z_p$ with $n$-bit $p$ requires about $k\,n(n/32)^2$ multiplications for some integer $k$ typically 12 or more (e.g. 200k multiplications for $n=256$). In practice, even when using RSA with $e=65537$ (like 8 times slower than $e=3$) perhaps due to diktat by authorities, RSA typically keeps a sizable advantage because it is easier to optimize.

Also, RSA signature with message recovery is sometime what minimizes the size overhead of signing. E.g. for a 350-octet payload to be conveyed signed, the signed message is

384-octet with RSA-3072 per ISO/IEC 9796-2 scheme 3 and SHA-256
398-octet with ECPVS (ANS X9.92-1) and SHA-256
414-octet with ECDSA/EdDSA and SHA-256

Thus when size is a hard limit, RSA signature with message recovery might be the only option. Admittedly, that applies only for a narrow interval of size: the gain is a fraction of the hash size thus becomes proportionally negligible with larger payloads, and ECC wins for smaller ones (because RSA cryptograms have the size of the public modulus). It happens that the interval where RSA wins is close to the maximum practical capacity of a 2D-code (e.g. QR-code).

That answer points another rather specialized use case of RSA where it shines: deterministic, size-preserving public-key encryption.

That answer points yet other practical reasons why RSA remains widely used.


There are many limits on key size. As far as I know 56 bit in USA and 40 bits in India without license.

In general, this is incorrect, at least for the US. However, when exporting cryptography you should be aware of export regulations for countries. It does generally matter how the cryptography is made available and to who. This site however doesn't give any legal advice.

In case of https connection who decides the encryption strength the server or client.

The client sends out the cipher suites, but the server gets to choose. Generally the server will support a small subset of ciphers for TLS 1.2. For TLS 1.3 the set of cipher suites was deliberately made smaller in the protocol specification.

How can I force a less than 32-bit encryption on server and clientside.

Generally you cannot get any cipher suite with so little security. Basically it would equate to no security at all, so you'd just be fooling yourself.

If the data is read then it's not a problem but want to prevent man in the middle attacks.

This means you need to authenticate the handshake and provide message integrity. "Unfortunately" if the key agreement and authentication is strong, then the encryption will be strong as well.
The only way to have weak encryption and strong authentication is therefore to deliberately weaken the encryption component.


How can one securely generate an asymmetric key pair from a short passphrase?

The best you can hope for is the following:

You derive the password into a "big enough" (e.g. 128 bits) secret key $K$ with a Key Derivation Function like PBKDF2. There are some details to be aware of (see below).
You use the secret key $K$ as seed for a Pseudorandom Number Generator. The PRNG is deterministic (same seed implies same output sequence) and produces random bits.
You use the PRNG in the key pair generation algorithm for whatever asymmetric algorithm you want to use. This step is cheap and simple for discrete-logarithm based algorithms like DSA, ElGamal, Diffie-Hellman, and their elliptic-curve variants, provided that the group parameters are known in advance (e.g. it is hardcoded in all relevant pieces of software that you are doing ECDSA / ECDH with the standard P-256 elliptic curve defined by NIST). For RSA, this is less cheap and simple, because the key generation process entails generating random integers until primes are reached. This is still doable.

Since this procedure is deterministic (for a given source password), you can run it again every time you need the private key.

Now the trouble with passwords is that they are from the relatively small and non-uniform space of "things which fit in the mind of an average user". They are vulnerable to exhaustive search, which, for passwords, is traditionally named dictionary attack. There are three generic ways to cope with that problem:

Do not let the attacker learn any piece of data which allows him to verify a password guess. In the usual context of storing password hashes in a server for user authentication, this means that you do not want attackers to be able to read the database; this is why Unix-like systems have switched to shadow passwords about 15 years ago. You still want to store hashed passwords, and use the two other protections, because illicit read-only access does happen in the real world.
Use a configurably slow key derivation function. This makes dictionary attacks proportionally slower -- but also normal usage slower, by the same factor. This is why KDF such as PBKDF2 or bcrypt include an iteration count. You want to raise that count up to the highest value which is still tolerable for your users.
Use a salt to prevent attack parallelism. Parallelism is about attacking N passwords (not necessarily simultaneously) for less than N times the cost of attacking one (precomputed tables are a kind of parallelism). The salt is a public piece of data which acts as a variation to the KDF; this is equivalent to saying that there are many distinct KDF, and the salt says which one you use.

In your scenario, you do not have the first protection: the resulting public key is, by nature, public, and thus can serve for offline dictionary attacks. The attacker just has to try possible passwords until he finds the same public key. That's intrinsic to what you want to achieve.

The third protection (the salt) could also prove difficult. The salt needs not be secret, but it still must have some level of integrity. Wherever the salt is stored, the user who wants to recompute his private key must be reasonably assured that he is using the right salt (otherwise he will compute the wrong private key). Depending on the usage scenario, it may or may not be easy to have such a storage space. A partial solution is to use the user name as salt (presumably, the user will be able to remember his own name); as salts go, user names are less than ideal, because:

two users on two distinct server installations (using the same software) may have the same name;
when a user changes his password, he does not change his name;

and this breaks the "unicity" property that the salt tries to achieve. Still, the user name as salt is much better than no salt at all (better yet, use the user's email address as salt: users remember their own address, and email addresses are, by nature, unique worldwide). If you do not use any salt at all, then two distinct users on the same system, who happen to choose the same password, will end up with the same key pair, and simply listing the public keys will show it immediately.

Note: deriving the private key from the password means that when the user changes his password, he also changes his private key. Chances are that this is a problem. This is one of the reasons why you could prefer an indirect system, where a totally normal key pair is stored somewhere, symmetrically encrypted with a password-derived key. Thus, when the password is changed, you just decrypt the key with the old password, and encrypt again with the new password. But this requires an available storage area. This model is directly supported by, e.g., GnuPG.


How do I multiply two points on an elliptic curve?

There is no point multiplication operation on secure elliptic curves*, there is only scalar multiplication apart from the point addition of the group.
Scalar multiplication
Scalar multiplication with a scalar $t$ is adding a point $P$ it self $t$-times
$$ [t]P : = \underbrace{P + P + \cdots + P}_{t-times}$$ and it is well defined operation since the group is operation is the addditon of the points. Scalar multiplication is a natural writing of the adding $t$-times.
If you want to execute a Diffie-Hellman here it is;
Elliptic Curve Diffie-Hellman Key Exchange (ECDH)
ECDH is executed with the parties' public keys. Let say Alice has secret key $a$ and public key $A = [a]G$ and Bob has secret key $b$ with public key $B = [b]G$ with the base point $G$ defined by the standards.
Then both parties can agree on the key as;

Alice: get Bob's public key $B$ and multiply it with secret key $a$; $S = [a]B=[ab]G $
Bob: get Alice's public key $A$ and multiply it with secret key $b$; $[b]A=[ab]G = S$

So both arrived at the same point $S$, now they can use the $x$-corrdinate point $S$ with a Key Derivation Function (KDF) like HKDf to derive a symmetric key.
Ephemeral
Originally, Diffie-Hellman is defined as ephemeral, that is for each key generation, Alice and Bob generates new uniform random points by selecting a uniformly random $a$ and $b$ per run of the protocol. This provides forward secrecy if you delete the keys after decryption.
If you don't generate new uniform random keys, it is called the static DHKE. Therefore you will see around static-static, ephemeral-static, static-ephemeral, and ephemeral-ephemeral usages of the DHKE on around. Hopefully, the static case is no longer available in TLS 1.3.
MITM attack
DHKE is vulnerable to a man-in-the-middle attack especially the ephemeral case since the public points are changing all the time. A signature must be used to prevent this attack.

* As noted by CodeinChaos in the comments we can define a multiplication on curves with $[a]G \cdot [b]G = [ab]G$. This, clearly, have commutativity, associativity, identity, and distribution law. The inverse depends on the order of the $G$. This multiplication, however, is exactly the Computational Diffie-Hellman (CDH) problem. If you solve the Discrete Log (DL) problem on the curve then you can solve the CHD, the reverse is not known in the general case.
Since we required that the DL (or CDH) must be infeasible for security, this multiplication operation is not a feasible operation on the secure curves.


HMAC tag to verify the key (verification in the reverse direction)

It looks fine; whether you use the secret $S_0, S_1$ as the HMAC key, or whether you use the random value $r$ as the HMAC key; if $t' = t$, it implies that either $S_0 = S_1$, or we found a collision in the underlying hash function.

I would personally suggest you use $S_0, S_1$ as the key.  With HMAC, it doesn't really matter; however if we extend this to other Message Authenticate Codes, it does.  For example, if we were to use this idea to CMAC, well, if we're given the values $CMAC_r(S_0)$ and $r$, we can compute two plausible values of $S_0$ if it's at most 16 bytes long.  Using the secret values $S_0, S_1$ as the key prevents this; instead, you'll be relying on the security properties of the MAC.

One last note: this scheme also has a problem if $S_0, S_1$ has low entropy (that is, they appear in a dictionary that the attacker might have); in that case, an attacker can go through his dictionary, and check for matches.  If this is a concern, you'll see some type of password authenticated key exchange; they handle this case better (but they are also rather more complicated to implement)


How exactly does certificate based authentication work?

I'm answering this based on the TLS v1.2 certificate based client authentication feature. Other protocols may vary in the details.

  Can anybody tell me what is being sent from the user's side for
  getting authentication from the server?

The overhead to a normal handshake consists only of the user's certificate (+ intermediate certificates eventually, really uncommon) and the signature over some previsouly exchanged data.

  Generally, how and what is sent from the user so that the server can
  identify the user?

During the course of a standard TLS handshake a bunch of data is exchanged. This includes the server's certificate, random nonces of both parties and cipher suite negotiation data.
If the server requests a client certificate (which will also include a list of the valid CAs it's going to accept), the client will sign the whole transcript up to this point and will send the signature and the certificate to the server. The inclusion of the nonces prevent re-use of the signature, the inclusion of the server's certificate prevents out-of-context use of the signature and the cipher suite signature prevents downgrade attacks.

  How is certificate based authentication able to replace password based
  authentication, and how exactly does it work?

The server receives the signature and the certificate. It can then verify the correctness of the signature using the public key embedded in the certificate. If the signature is valid, the server knows that the client has the private key belonging to the certificate. As the server can choose the trustworthy CAs himself (including himself), he can trust the CA to have bound the correct public key to the correct person. So he knows that only the person ownging the certificate could have signed this handshake and thereby the client is the person owning the certificate.

This directly authenticates the handshake to the server and there's no need to subsequently send a password for the sake of authentication.


What is the meaning of IND-CCA secure under standard model?

Your questions can be split in two:

  What is the meaning of IND-CCA secure? What have an adversary access
  in a challenger-adversary game?

This basically means that the scheme achieves the indistinguishability notion, even if an attacker has access to a decryption oracle. See
Easy explanation of "IND-" security notions? for more detail on this.

  What is the standard model?

This simply means that no additional assumptions are made for proving the security of the scheme. You see, a lot of crypto proofs require additional assumptions. For example, one of the most used is the Random Oracle Model, which assumes the existence of an ideal hash function that guarantees uniformly-random outputs. Proofs in the standard model are therefore considered more desirable.


Is it valid to call this table an S-Box?

Not really; at least, not with the meaning we usually give to "S-box".

The "S" in "S-box" stands for Substitution; we take the data, and replace it with a value from the S-box (using the data as an index into the S-box).  The classical (if not the original) example is the S-boxes within AES; at certain points within the cipher, we take each 8 bit value $V$ from the block, and replace it with $SBox[V]$.

We don't do anything like that in MD5; instead, the "S" constants stand for "Shift".  They don't replace anything; instead, they modify how much shifting (rotating in more common parlance) we do per round.


Is Common Name encoded in the certificate?

The "Common Name" is part of a X.500 name; here, the one called "SubjectDN", which designates the owner of the public key which is contained in the certificate. That name is part of the certificate, in the part which is covered by the signature; as such, it is exactly as trustworthy as any other element in the certificate.


Your solution is not correct. You have to show that $\mathbf{\text{negl}_2}$ satisfies the definition of negligible functions and what you "showed" actually is that given any sufficiently large polynomial $p'(n)$, it holds that  $\mathbf{\text{negl}_2} < \frac{p(n)}{p'(n)}$.

I see two easy ways of solving that exercise:

Try to prove it by contradiction supposing that $\mathbf{\text{negl}_2}$ is not negligible and then finding a polynomial whose inverse is asymptotically smaller than $\mathbf{\text{negl}_1}$.
Try to prove it directly: from any given polynomial $p'(n)$, you know that $p(n)p'(n)$ is a polynomial, therefore,  $\mathbf{\text{negl}_1}$ must be smaller than $1 / (p(n)p'(n))$ for all $n$ bigger than some $n_0$...


If we have a signature scheme with deterministic verifier and a non-interactive protocol which is [co-non-malleable as an argument of knowledge] and statistically witness-indistinguishable, then we can get a fully non-interactive version of what you want by letting "mutate" be

"run that protocol's prover on", and letting "verify" be "run that protocol's verifier on".

If the protocol is only in the CRS model but has the property that

statistical witness-indistinguishability holds for all possible outputs of the CRS generator, then assuming the existence of a compatible private key would be enough leave the CRS model

by letting the "CRS" be part of the public key, since the signer would store enough about the generator's randomness to let one verify that the "CRS" is a possible output of the generator.  Section 8.3 gives such a protocol.  Given a statistically hiding commitment scheme,

this paper's proof of Theorem 4 lets "assuming the existence of a compatible private key"

be replaced with "letting the signing phase be interactive".


From the product of two permutation matrices raised to the same power, is it easy to find the power?

The product of two permutation matrices is itself a permutation matrix. So there's nothing special about its "factors" being public.  You should consider a single public permutation matrix $A$ and finding $r$ from $A^r$.

  Edit: oops, this was based on a misinterpretation of the question.

And there's nothing particularly special about it being a matrix. If $A$ is a permutation matrix corresponding to permutation $\pi$, then $A^r$ is the permutation matrix corresponding to $\pi$ composed with itself $r$ times. Let's call this permutation $\pi^{(r)}$.

So the question boils down to to the "discrete log" problem in a permutation group: given $\pi$ and $\pi^{(r)}$, find $r$. This problem is easy.

First, observe that if $\pi$ is a simple cycle on $n$ items then $\pi^{(r)} = \pi^{(r \bmod n)}$. Since $n$ must be small in this problem, you can easily just "brute force" to determine $r$ mod $n$.
Second, any permutation can be uniquely decomposed into disjoint cycles. The operation $\pi^{(r)}$ acts independently on all the cycles of $\pi$. So if $\pi$ is composed of cycles of length $k_1, k_2, \ldots$ then we can use the above trick on each cycle and learn $r \bmod k_1, r \bmod k_2$ and so on. Then you can use the CRT to solve for $r \bmod \textrm{lcm}(k_1,k_2,\ldots)$. And indeed, the order of $\pi$ will also be $L=\textrm{lcm}(k_1,k_2,\ldots)$ in the sense that $\pi^{(L)}$ is the identity permutation.

So you can efficiently identify $r$ as uniquely as is possible (mod $L$).


How is El Gamal different from Diffie Hellman Key Exchange

The difference is purely conceptual. That is, when Diffie-Hellman published their paper, they equated between public-key encryption and trapdoor functions. Thus, they did not think that they had constructed a public-key encryption scheme, and this invention came only a year later with RSA. In fact, Diffie and Hellman even explicitly talk about publishing one part of the key...

The contribution of ElGamal was to formalize this as an encryption scheme, and free us of the conceptual block that public-key encryption requires a trapdoor function. By the way, conceptual contributions are very important, so this does not belittle it in any way. In addition, note that El Gamal was very clear about this in his paper. A quote from the paper:
"Section II shows a way to implement the public key distribution scheme introduced by Diffie and Hellman to encrypt and decrypt messages."


Review of AES encryption concept for an open source project

You're pretty much on the right track, I've got a few comments/suggestions though:

  store the plain sha1 of the unencrypted image with the encrypted image

I'm assuming the sha1 hash is to ensure the integrity of the data being encrypted?  If that's the case, you should have a read through this answer.

Assuming you're limited to non-authenticated modes (I don't see GCM, EAX or otherwise) as options in CryptoJS, then you'd probably do best to encrypt-then-MAC:

InitialKey = PBKDF2(dkLen=32, count=100000, salt=salt, password=password) — where dkLen is the native block size of the underlying hash algorithm, in this case, sha256 = 32 bytes.  Note: 1000 rounds of PBKDF2 is considered weak in 2013, if you must use PBKDF2 (as opposed to something stronger like Scrypt), then aim for as many rounds as is tolerable by the user
SecondaryKey = PBKDF2(dkLen=64, count=1, salt=salt, password=InitialKey) — Note; just one round here.  If you're wondering about this two-step PBKDF2 process, check out this excellent answer by D.W.
AES_key = SecondaryKey:0-32
HMAC_key = SecondaryKey:32-64
HMAC = HMAC_SHA256((cipherText || iv || salt), HMAC_key) — where || denotes concatenation
cipherText = cipherText || HMAC

I'd be inclined to use CTR mode (and no padding) instead of CBC, but that's just a preference - CBC is perfectly fine.  Also, as @owlstead pointed out, you need to consider the implications of a user updating their password, and having to decrypt/re-encrypt all of their images, but that's beyond the scope of my answer.


Is it just as difficult to find a desired output in a hash digest, for MSB vs LSB?

As the other answers point out, output bits of a good hash function are uniformly distributed, so your substring has equal chance to appear in any part of the hash digest.

However, in the case of Bitcoin, the address is not a random string. Not only it starts with a predefined number (1 or 3), but the string is the result of the Base58-conversion, which may (I did not check) produce biased outputs. The addresses may even be of different lengths.


What characters are valid in PGP encrypted and signed messages?

OpenPGP as defined by RFC 4880 knows two different encodings.

Binary encoding

Obviously, there is no reasonable limitation to an (ASCII) character subset in binary encoding.

Radix 64

Radix 64 is also often called ASCII armored. In the end, it is a base64 encoding with a checksum. The content may consist of [a-zA-Z0-9+/=].

ASCII-armored OpenPGP messages also include a header, which may contain arbitrary UTF-8 strings.

An example message in ASCII-armor (modified from the one in the RFC):

-----BEGIN PGP MESSAGE-----
Version: OpenPrivacy 0.99
Comment: An example for an UTF-8 string with arbitrary characters

yDgBO22WxBHv7O8X7O/jygAEzol56iUKiXmV+XmpCtmpqQUKiQrFqclFqUDBovzS
vBSFjNSiVHsuAA==
=njUN
-----END PGP MESSAGE-----


Simulation Based Proof: How the Corrupted Party's Input is Given To Simulator

The simulator obtains "client $B$'s input" in the same way the simulator obtains $\:\{\hspace{-0.03 in}0,\hspace{-0.04 in}0\hspace{-0.03 in}\}\;$.

Even in the real world, the server computes its response without using any secrets, that response is the only message $B$ receives, and (from your description) no other party gives any output. $\:$ Thus, it doesn't matter what input the simulator sends to the trusted third party.


Follow up to the answer (to some degree).
Using a hash function in this way is somewhat equivalent to fast forwarding a pseudorandom number generator.
A linear congruential generator (LCG) can be skipped ahead [link], in fact many PRNG's can be skipped/jumped ahead [link].
The problem with fast-forwarding any hash/prng, is that if you know the cycle period (which you do with most PRNGs),
by fastforwarding the period-1, you effectively move back 1 state.
Thus if we found a way to say move forward quickly with a SHA256, the first person to correctly estimate its cycle period would also have the ability to move backward as well.
The only fix for this is to have a system with a huge number of varied cycles.  E.g. having 256 bits worth of different cycles lengths, which each cycle being 64-256 bits in cycle length, fitting in 512 bits of state.
No known way of doing this, but should one be found, you've solved multiple comp-sci and cryptology problems, and made efficient signing of messages trivial.
tl;dr - if you can go forward and calculate its cycle length, you can go backward.


Public key cryptography instead of passwords for web authentication

The WebAuthn standard sounds similar to what you are describing.


Encrypted counter as IV in CBC mode encryption using same key

Just to be sure we're on the same page, I interpret your question as defining encryption of a string $P_1 P_2 \cdots P_\ell$ with a counter $\mathsf{ctr}$, key $K$, and an $n$-bit blockcipher $E$ as follows:
$$ \mathcal{E}_K(\mathsf{ctr}, P_1P_2\cdots P_\ell) = C_0 C_1 C_2 \cdots C_\ell$$
where $C_0 = E_K(\mathsf{ctr})$, $C_{i+1} = E_K(C_i \oplus P_{i+1})$, and each $P_i$ is an $n$-bit string. (So I'm assuming plaintexts have already been padded as necessary.) I'm assuming the values that will be used for $\mathsf{ctr}$ are determined ahead of time. If this is incorrect, attacks become possible.

The scheme above is secure in the sense of real-or-random security under chosen-plaintext attacks (this is a somewhat stronger condition than semantic security). That is, an adversary cannot distinguish between $\mathcal{E}_K$ and an oracle that given an nonce and an $nm$-bit plaintext returns $(m+1)n$ random bits. This is true as long as $E$ is secure (in the sense of being a pseudo-random permutation), $K$ is random, and the total length of all the ciphertexts encrypted under a given key is much less than $2^{n/2}$ bits (the birthday bound).

Proof sketech. A standard game-hopping security proof might proceed like this:

Change the scheme to use a random permutation $\pi$ in place of $E_K$ (this is reasonable if $E$ is secure and $K$ is random).
Change $\pi$ to a random function $\rho$ (this is reasonable as long as long as the number of queries to $\pi$ is much less than $2^{n/2}$; see the PRP-PRF switching lemma).

As long as no input to $\rho$ is ever repeated, all its outputs are uniformly random and independent. Therefore using the encryption scheme over $\rho$ is indistinguishable from an oracle that outputs random strings, as long as this condition holds. So we need to bound the probability that an input to $\rho$ is repeated.

From here the proof proceeds like the standard CBC security proof, with the caveat that instead of looking for collisions just among the $\rho$ inputs we've already seen, we also need to worry about one of the inputs being equal to a counter value we'll need in the future. (This is where the assumption that counter values are pre-determined comes into play.) Since barring a repeated input, each $C_i$ and therefore each $C_i \oplus P_{i+1}$ is a uniform random value independent of previous queries, the probability that a given $C_i \oplus P_{i+1}$ is equal to a counter value is at most $q / 2^n$, where $q$ is the number of queries the adversary will make (and hence the number of counter values we require).

Using a union bound, the probability that such a collision will ever occur is at most $q^2 M /2^n$, where $Mn$ is the length of the longest plaintext. This probability is negligible as long as $(qM) \ll 2^{n/2}$. And note that $qMn$ is an upper bound for the total number of bits encrypted.

So. The encryption scheme $\mathcal{E}$ is not significantly less secure than CBC with a random IV. The larger question of whether the protocol as a whole is secure as a much more difficult question, and one that I can't answer without knowing more about it (and probably couldn't answer even if I did). But you are authenticating the counter, right? :)


How does authentication work differently between asymmetric and symmetric cryptography?

A start would be the Wikipedia article about Authenticated Encryption, and the GCM mode is an AE-mode for block ciphers.

Additionally to the key, IV and cypher text you need the authentication tag, which is generated during the encryption process.

Decryption reconstructs the tag and compares it two the original. If they do not match, the decrypted text is invalid.


Why is CAMELLIA suddenly so widely used?

The reason why you see that is because Camellia is the highest-preference cipher in NSS (Chrome and Firefox).  Servers that support Camellia and use the client-preferred cipher suite will use Camellia.

NSS's rationale for this ordering is:

  National ciphers such as Camellia are listed before international
  ciphers such as AES and RC4 to allow servers that prefer Camellia
  to be able to negotiate Camellia without having to disable AES
  and RC4, which are needed for interoperability with clients that
  don't yet implement Camellia.

See also: Bug 430875


How do we compare performance of two encryption algorithms?

I'll collect the comments and build an answer from that.
First,

  [..] you just perform the operation, say, a thousand times for
  keys with similar security properties and record the time for each.
  Note that the speed is rather implementation dependent, so you're
  measuring the implementations of the algorithm rather than just the
  algorithm.

of course life and code development would be too simple with this, so

  [Y]ou also need to consider [..] the quality
  of the implementations. If you coded them yourself, do you know about
  the implementation tricks for both algorithms that a quality
  implementation would use? Comparing naive implementations might not
  tell you very much.

and still of course security developement has its own special issues which need to be respected before comparing speed:

  In addition to the above, it is not just the optimization level of the
  implementation that matters, but e.g. resistance to side channel
  attacks, so in some cases an implementation could even be faster than
  a good implementation.

So the logical conclusion is ...

  If you want to compare RSA and Paillier encryption algorithms, then
  you shouldn't compare two implementations of those algorithms, you
  should compare the computational complexity of the algorithms.

with this helpful comment on how to do so:

  In this case, one thing to consider is the different length of the
  modulus and numbers involved (In Paillier, calculations are done with
  numbers twice as long, if the same $n$ is used, due to $\bmod n^2$).

Credits to Maarten, poncho, otus, user2768 and tylo for this joint effort of an answer.


Is this really more secure than using bcrypt with a complexity of 11
  or 12 ?

It depends. Obviously if you consider everything on their servers compromised this isn't more secure than using a higher workload for the password hashing scheme (PHS). If you assume they can guard their pepper better than their password database then the passwords are irrecoverable from the dump.

  The password "chain" is secure as its weakest part, so is there any
  point adding the extra 2 parts in ?

A chain isn't really the correct analogy here. Assume an attacker can brute-force infinitely many bcrypt hashes but can't get the pepper. There's no way such an attacker could recover the passwords because he can't obtain the hashes required to brute-force them.

A better analogy would be an onion. You can't get to the core (the password) without going through all the layers (pepper, bcrypt, SHA-512).

  I understand that the Global "pepper" means that a DB dump protects
  the hashes until that pepper is found, and then each hash is still
  salted per user, but how much would that slow down people reversing
  the passwords in the event of a DB leak over simply bcrypting them ?

The pepper is a 256-bit AES key. If an attacker doesn't get hands on this one there's no way they can recover the hashes and thus potentially the passwords. However as soon as you have exfiltrated the key, the additional AES encryption has just about 0 influence on the run-time required for brute-forcing a key. So you win in case you can protect the key and you lose nothing if you can't do that.


Is it secure to encrypt a 1 GB data file with AES-CTR by ECIES?

I do not believe there would be any issues, as long as:

The problem you are attempting to solve is that you want to encrypt a file so that the client can decrypt it, but no one else can
The client has a public/private key pair
The encryptor has the client's public key and you somehow know that it's the client's public key
The encryptor has access to randomness (as the security of ECIES depends on it)
You add some integrity transform (along with the AES-CTR), to make sure that no one can modify the encrypted message without being detected.  If you need a suggestion about which integrity transform to use, perhaps HMAC-SHA256 would work; alternatively, you could replace AES-CTR with (say) AES-GCM.

You appear to be concerned about the size of the file being encrypted; the public key portions could care less about how long the message is (it does the same thing regardless), and the AES-CTR portion can easily handle a terabyte without an issue.

You may want to consider breaking the file up into smaller pieces and encrypt and send each piece separately, but that is for purely practical reasons (e.g. if one of the smaller pieces get corrupted, the receiver can ask for that specific piece to be resent, and not the entire 1Tb file); however the cryptographical security would not depend on that.


Why are hashes padded only at the end of the block?

Is it somehow connected with sequentially reading in files /data of unknown length?

Yes, indeed. It is part of a requirement to perform online message processing, or, in other words, the ability to stream the data without knowing how much data to expect.

  Would it make a difference if you always knew the length of the message to be hashed?

Well, yes, in that case you could indicate the message length in advance. Some modes of operation, such as CCM, a authenticated mode for packet encryption, rely on this kind of information. But for hash algorithms it is not required to know the message length in advance and still be secure.

Nothing prevents you to create a protocol to include the message length in advance. If you build it on top of SHA-1 or SHA-2 then this should prevent message length attacks (if implemented correctly). You'd include the message length twice that way, and would lose compatibility with software that just expect the hash.

SHA-3 is already protected against length extension attacks. Length extension attacks may not be applicable to all algorithms or situations. Length extension attacks are mainly an issue for keyed hashes. HMAC is a keyed hash which has deliberately been designed to protect against length extension attacks.


Does AES-GCM without security tag turn into regular CTR Mode?

I'll keep to the final question as security evaluating the entire scheme would be off topic:

  If we use the implemented AES-GCM mode but without security tag (TAG_SIZE 0 bit) does this make the cipher behave like regular CTR mode as to the attacker can no longer start guessing passwords and knowing whether he has guessed the correct one and thereby losing this potential oracle?

Yes, GCM would then just get you CTR mode, but with a specific way of calculating the initial counter: $n << 32 + 2$ where $n$ is the encoded nonce, shifted left 32 bits (multiplied with $2^{32}$), and then added the value 2 in the zeroed, least significant bits. The proof is in the implementation.

Notes:

The implementation I pointed at uses a (GCM default) nonce of 12 bytes; if you do not do that then calculating the initial counter will get more complex.
Not all libraries will allow a tag size of zero as that obviously falls outside the acceptable range for the size of the authentication tag $t$.

Off topic, some remarks on using GCM in your protocol:

As others have commented, creating (or in this case hacking) your own protocol is probably not the safest thing to do; there are already schemes out there that will do this for you. And just using CTR instead of GCM should be preferred if you go with this scheme.

Beware that the decryption will always succeed, but that parsing / handling the plaintext may still result in an oracle. E.g. if you encode a number and send it then decoding could possibly fail, resulting in an oracle.


collision resistance with added permutation

If the permutation is a shared secret, I don't see how that's different from normal HMAC; in the sense that you can't find a collision unless you know the key, the amount of permutations would be too many to calculate; but HMAC has those same cryptographic properties, even for a less-than-ideal hashing algorithm.
Update:
Here I explain the details of the number of possible permutations of the input bits (fun fact: this calculation actually comes into play when designing block ciphers). The issue is, while the number of ways you could permute the bits is extraordinarily high, the number of possible states will be upper-bounded at $2^n$ for $n$ bits. For an $m P n$ case (you select $n$ bits from set of bits $M$) you will be bounded by the number of possible $M$, as well as the possible $N$, making $2^n$ still your upper limit.
You cannot exceed the security provided by a normal $2^n$ bit hash, you can only match it with more permutation. Since any decent hashing algorithm already does this (and more), you end up with no change in your level of security. We're comparing internal states with input/output possibilities, and the input/output possibilities will always cap your security level. For this reason, I fail to see how it is different from a normal cryptographic hash.


Keep in mind that Adiantum was designed for one particular use case: block-based disk encryption.

In other contexts, especially in a web browser context, storing an IV and an authentication tag along with the ciphertext is not a problem. So you can stick to traditional AEADs, that will be faster than Adiantum in addition to being easier to use securely.


Are there any key exchange schemes that only require entropy on one side?

No.

A deterministic device initially holding no secret information can no establish any secret information thru public channels.

The argument is elementary: that device can be fully simulated by an adversary, which can thus determine any information that device may contain.


Secret Sharing: Is this simplification secure?

Is the above suggestion secure?

Sure; for any group that doesn't have a subset that's a group in $\Gamma$, they don't have enough information to reconstruct the shared secret.

Your approach is indeed a subset of Benaloh's, where you constrain the circuit to be a layer of AND gates, followed by a single OR gate.

  2.What's the advantage of the more general approach as presented by Stinson?

The size of the shares; your scheme requires a share size for an individual that is proportional to the number of groups it's a member of.  For example, if the access structure is "any of 1000 members of group A, plus any of 1000 members of group B, plus any of 1000 members of group C", then everyone's shares will be 1,000,000 times the size of the shared secret; with Benaloh's method, each share need not be any larger than the shared secret.

Of course, if the access structure is "any 500 of the 1000 member groups", you're far better off with Shamir's method, rather than either of these two...


This is a trickier question than you might think.

The first thing to note is that your scheme doesn't respect record boundaries. TLS 1.2 seems to have been rewritten to use a random IV for CBC mode encryption for each record (to avoid certain attacks). It is therefore likely that the idea of TLS 1.2 is to respect record boundaries.

The document "AES Galois Counter Mode (GCM) Cipher Suites for TLS" - RFC  5288 - mentions "An Interface and Algorithms for Authenticated Encryption" - RFC 5116. This document specifies the use of a 4 byte salt and 8 byte random. That means that the nonce is 12 bytes total, consisting of the persistent part of 4 bytes and 8 bytes random. The GCM specification strongly recommends a 12 byte (96 bit) nonce/IV. This specification in turn is based on GCM ESP, RFC 4106, which specifies the use of GCM for IPsec. So in general the use of GCM in TLS 1.2 seems to follow previously established standards.

The specification of a per record random (explicit) part is of course in line with the cipher suites that use CBC based encryption. In this case however the IV only has to be 8 bytes instead of 16, which saves some 8 bytes as overhead. That's still 8 bytes more than your proposed scheme - which, again, doesn't respect record boundaries - but it's better than CBC.

Notes:

If you would change to a fully implicit nonce you should still keep to 12 bytes to keep within the GCM specifications. If you would specify 16 bytes IV then the GCM specification requires an additional GMAC. There seems to be no way of specifying a 16 byte counter to be used; the 4 least significant (rightmost) bytes are set by the algorithm itself.
Related, in your scheme it is impossible to use a GCM API that only allows 12 byte nonces (i.e. without the counter included in the IV). You would need some way of keeping track of the counter and a method of instantiating GCM with that full 16 byte counter.
In your scheme it would be impossible to parallelize encryption/authentication and decryption/verification unless you had a way to pre-compute the record payload.

In conclusion, although your scheme could work (it's more efficient and isn't likely to be insecure), it doesn't respect record boundaries and it would put additional requirements on the GCM library. Finally, it would not follow pre-established standards for the use of GCM in a transport protocol.

In TLS 1.3 (under construction at the time of writing) it seems that the record number may be used instead of the explicit random, which would require less overhead in the record header and less calls to the random generator.

Note that Figure 2 in RFC 5116 "An Interface and Algorithms for Authenticated Encryption" includes the counter in the nonce specification. I've made a report for an ERRATA on this as the GCM specification and the ESP documents both treat the nonce as a 12 byte value (so without the counter).


Why don't most encryption algorithms use perfect secrecy?

Perfect secrecy can only achievable if the $\text{key size} \geq  \text{message size}$ and the key is never re-used.
It is not suitable for modern usage, where a lot of messages are sent/received and that is impractical since one has to send the key beforehand in a secure channel and this is not encryption. You must trust the carrier or you have to carry the keys yourself. Instead, we go the other way, use shorter keys with good analyzes algorithms. Exchange the key with DHKE protocol ( where mostly elliptic curve version is used), and use AES-GCM, AES-GCM-SIV, or ChaCha20-Poly1305.
Reuse of the key has catastrophic results that confidentiality is broken. What will you do when the keystream is depleted? Would you wait for the new key, or you would re-use some part of the keystream? Both have critical results. You will not communicate when needed or OTP will fail, see Crib-Dragging. Instead, one can use DHKE to create a new key, even for every encryption, and even can achieve forward secrecy.

Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?

The encryption should be easily computed so that the legal party doesn't use so much power to encrypt. This doesn't mean that it is breakable since the adversary can compute with lots of resources. If the algorithm, block or stream cipher, use correctly given key then, then one can adjust the key size so that brute force out of reach of anybody, even for the quantum computers.
The encryption can be randomized and indeed in modern cryptography, we prefer this, forget the otherwise, it is insecure. See semantic security and indistinguishability. For example, we prefer at least Ind-CPA security. CBC and CTR mode can achieve this, however, ECB cannot. Actually we want more, the standard of IND-CCA2/NM-CCA2- ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack. The examples are AES-GCM, AES-CCM, and ChaCha20 which are an Authenticated Encryption with Associated Data (AEAD) and provides Confidentiality, Integrity and Authentication.
The decryption must be unique since there is no way for the receiver to determine the correct message among the possible answers.
The password is not the correct term. We use the encryption key or in a short key when it is clear in the context. The password is only applicable if the key is generated by using a Password Based Key Derivation Function like PBKDF2 or Argon2id.

Why aren't many popular algorithms like AES like this?

Mostly answered, AES is a fast and secure keyed permutation. Yes, for each key, AES chooses a permutation from all possible permutations. We expect that it chooses this in a way that its selection is indistinguishable.

There are also Q/A and answer here that talks about achieving perfect secrecy with AES with some very nice answers;

Can one claim that AES is a perfect cipher?
Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?
Key length and message length in AES and perfect secrecy if plaintext length <= key length


If $P=NP$, then any one-way function can be inverted.  Any one-way function can be inverted using non-deterministic polynomial time.  Therefore, the assumption that $P\ne NP$ is necessary (but maybe not sufficient).


What happens if I choose $e=3$? Can I retrieve the message by simply calculating $\sqrt[3]{c}$?

Yes, if the plaintext message is smaller than $\sqrt[3]{N}$, then yes, a simple computation of $\sqrt[3]{C}$ will recover the original message.

  Why can't I do that with bigger $e$'s?

Actually, you could... as long as the plaintext message is smaller than $\sqrt[e]{N}$.  However, if you actually consider that for, say, $e=65537$, well, that value turns out (for any sane value of $N$) to be less than 2; hence that could be used only if the plaintext message was either 0 or 1 (and if that's the case, well, the problem would be pretty easy anyways).

  Is it possible to retrieve $d$, $p$ or $q$?

No, it's not.  If it were, well, that'd give an easy way to factor the modulus (!), even if we were using RSA properly.  All the attacker would need to do is take the modulus, and pretend that he was using textbook RSA and $e=3$; he would generate messages his own of his own choosing, encrypt those messages (using plaintext RSA and an $e=3$), and use the technique to recover $d$, $p$ or $q$.  Any of the three is enough to factor the modulus.


What is most secure way for one party to encrypt 4 bytes in less than 40 bytes, which will be publicly available?

The obvious answer is to use a one time pad.  If you are truly using a unique random 4 byte key for each 4 byte block then it is provably secure.

The user has an entropy seed from which an infinite number of keys of any size can be deterministically derived.

The real problem is this "derived" randomness and how random it truly is.  I'm not aware of any infinite source of it.
With Salsa/ChaCha you could generate up 2^64 512 bit keys, each key being able to encrypt 16 different 4-byte blocks.  So I suppose infinite enough.
Users would need to seed it with a 320 bit key.  They need to change their their key after 2^68 (if my maths isn't wrong) encryptions. Using a setup similar to XChaCha allows you to extend this to 2^132.
In summary, if you have a cryptographically secure source of randomness you can just XOR.


Complexity class of an idealised version of Bitcoin's proof-of-work (hashcash)?

Bitcoin's proof-of-work problem is solved in constant time, since there is no asymptotics. Complexity classes are irrelevant here.


Validating JWT works with small changes to public key, why?

The certificate is much more than a public key, changing the public key will of course prevent verification but most of what you did doesn't change that.
Your certificate above also has the following information:
Common Name: INNOPAY
Organization: INNOPAY BV
Organization Unit: Fun Department
Locality: Amsterdam
Country: NL
Valid From: July 24, 2019
Valid To: July 23, 2021
Serial Number: 3838059474068972016 (0x354386c1bab421f0)

changing that may make the certificate invalid and invalidate any signatures on it. but Token verification should be unchanged.


Collision-resistance of $H\Bigl(\bigl(H(m_1\mathbin\| 1)\oplus H(m_2\mathbin\|2)\oplus\dots\oplus H(m_n\mathbin\|n)\bigr)\mathbin\|n\Bigr)$?

What can we say about the collision-resistance of $\tilde H$ as a function of $b$ ?

That it is effectively nonexistent; it is easy to generate collisions (and second preimages).

You can generate a second preimage by selecting two blocks $m'_i, m''_i$ to correspond to each original block $m_i$; you compute $H(m'_i \mathbin\| i), H(m''_i \mathbin\| i)$, and then use linear algebra (e.g. Gaussian Elimination) to see which combination of $m'_i, m''_i$ all xor the same as the original sequence of $m_i$; that combination hashes to the same value.  As long as the original message is at least $b$ blocks long (that is, $n \ge b$), such a combination exists with good probability.

Once you can create second preimages, you can generate collisions by picking a message and generating a second preimage for it.


Why is SHA2 used for file verification if it's susceptible to length extension attacks?

The use of a hash function for verifying integrity of a file is not impacted by length extension attacks. The setup is the following:

You have a file $m$.
There is a "guaranteed" source for $h(m)$, with $h$ being a hash function. (For instance, you can get $h(m)$ from an HTTPS Web site with verified provenance.)
You recompute $h(m)$ and look for a match.

To make an undetected alteration of the file, the attacker would have to find a message $m'$ distinct from $m$, and such that $h(m) = h(m')$. This would constitute a second-preimage attack. No such attack is currently known on any of the SHA-* functions. The "length extension attack" does not seem to help for second-preimage attacks.

It is interesting to note that the "length extension attack" does not contradict any of the classical properties expected from secure hash functions (i.e. resistance to collisions, preimages and second-preimages).


If you are looking to implement private ECC operations using BMR, then you need to convert these operations first into a Boolean circuit. This will be extremely expensive and not the way to go. Rather, you need a direct protocol for this. Note that there are secure protocols for ECDSA, if this is what you are looking for.


Your assumption "(assuming finding remainder and division takes place in constant time)" is not fulfilled here. We are dealing with big numbers and division complexity is some function M(b) where M is the complexity of your multiplication algorithm, e.g., Schönhage-Strassen with O(b log b log log b). Schoolbook division is of order b².

Note that for cryptographic purposes n is really huge; even a polynomial time algorithm in n (exponential in b) is not feasible here.

EDIT: A note on complexity computation: Only leading terms in a sum are relevant, lower order terms are always negligible. When you complexity is already exponential, you can neglect polynomial factors. Therefore the complexity of division is just mentioned to make clear that your assumptions did not hold in the first place, it turns out to be negligible in the course of the argument.

NOTE: This all assumes a classical computer as model of computation. With a quantum computer, you can factorize an integer in polynomial time using Shor's algorithm. Current published Quantum Computers have 14 QBits and can factorise the integer 15 (fifteen). Apply Moore's law and some leeway for non-published Quantum Computers and you have an estimate when this kind of cryptography will be broken.


OK
I had asked this unanswered question earlier and now, I think I have an answer (sort of), not really but I think I know where to look for it. We assign each type of card combination a score such that a winning card combination always has a higher score and a tie always have equal score.The two players then play Yao's millionaire's problem to decide who is winner. With mapping known, a player who reveals the secret exponentiations (or cards) and the secret data used to provide his/her input to the problem, one can easily verify that they have shown scores honestly. Which means that the problem is in NP and thus the player should be able to construct zero knowledge proof showing that the score really reflects his card rank without revealing either the cards or the score according to a 1987 paper.That way two players can check who won without actually revealing his/her cards


But this notation is defined (informally) in the first paper.

The notation $O(\nu(n))$ is used for any
function, $f(n)$, that vanishes faster than the inverse
of any polynomial, that is for every polynomial, $\mathrm{poly}
(n)$, and $n$ large enough, $f(n) \leq 1/\mathrm{poly}(n)$

Therefore, what it means is no probabilistic polynomial time (PPT) algorithm $A$ can guess the next bit at inverse polynomially decreasing error rate.
Given any PPT algorithm $A$ this error probability decays super-polynomially, for example at a rate $\exp(-\log^2 n)$ which goes to zero faster than any polynomial.
Claim: $\exp(-\log^2 n)$ is less than $n^{-c}$ for any constant $c$ for $n$ large enough.
Proof: Look at the reciprocal. $$\exp(\log^2 n) > n^c$$ if and only if
$$\log^2 n > c \log n$$ which will clearly happen as soon as $$\frac{\log^2 n}{\log n}>c$$ i.e., as soon as $\log n>c$.
Note that $\exp(\log^{1+\epsilon} n)$ is superpolynomial for all $\epsilon>0.$
Edit: The superpolynomial convergence is essentially what is referred to as negligibility.


Does Terra Quantum AG break AES and Hash Algorithms?

The onus is on the company to prove their claims, especially when they are extreme. There is also no financial motivation to not prove their claims. I can understand if they say that they want to keep their new "unbreakable algorithm" secret until they patent it, but what reason in the world would there be to not present a break? This is especially the case since it's not something that can be utilized now. Unless, that is, they claim that they can break AES using today's quantum machines in which case I really have to hold back from writing expletives.
In short, this has all of the smell of snake oil with all the motivations of a company trying to get a lot of press and attention, and doing damage while they are at it. It's unfortunate that people don't think that they can make money while keeping their basic ethics.
Of course, one could argue that how can I make this judgment without having seen the details. I guess I'm old enough to not care to be wrong with a 1 in a $2^{40}$ chance. (I just made up that probability but without publishing how I got to it, I guess that no one can challenge me.)


Why Elliptic curve cryptography are not popular in practice

It is true that elliptic curves allow the same security with smaller key sizes. However, the size is not the only important aspect. Familiarity of algorithm, ease of implementation, performance, how many independent implementations exist, etc. affect how widely algorithm is implemented.

For Elliptic Curves, like many other technologies one factor slowing down the adoption has been patents. EC2m was previously considered "patent mine field" and there are also some patents on ECP techniques.

Elliptic Curves are still fairly new, and for security levels usually deployed, it is very common that in practice performance of RSA, DSA or DH exceeds ECC of similar security strength.

For larger security levels (around 192-bit or 256-bit security strength, i.e. 384-bit - 521-bit ECC curves), the required DSA/DH primes or RSA modulus grow so large that ECC usually wins in performance.

So, in my experience the reasons for smaller adoption are: difference in complexity, smaller speed on usual key lengths, patent risks, and the fact that there are less implementations than of, say RSA.

I have seen Elliptic Curves getting some attention and deployments and it seems to be growing. The drivers for that (which help with ECC adoption) seem to NIST's transition to higher key lengths (see SP 800-131A) and NSA Suite B. There are very few applications where the difference in key length is significant differentiator.


PKCS#11: Which CKK_types are supported by CKM_PKCS5_PBKD2?

I am not familiar with that specific Solaris library (is that a software token?).

However, what I can say is that PKCS#11 does not set any minimum requirement for the algorithms that a certain implementation should offer. CKK_IDEA could be supported, but only if the implementer chooses to. For instance, up to a few years ago, IDEA was patented and it was often not included in libraries and devices for legal reasons.

Besides, that is there any good reason not to use CKK_AES? That is the best choice in most cases.


Prove the Security of Schnorr's Signature Scheme

Pointcheval and Stern [PS00] proved that the Schnorr signature is existentially unforgeable under chosen-message attacks (EU-CMA) in the random oracle model assuming that the discrete-logarithm problem$^1$ (DLP)  is hard.

On a high level, the reduction (from DLP to the EU-CMA-security of Schnorr signature) works as follows. The reduction algorithm $\mathcal{B}$ embeds its DLP challenge $g^\alpha$ into the public key (i.e., sets $y=g^\alpha$) and then  uses the oracle-replay attack to obtain, from the forger $\mathcal{F}$, two different forgeries that share the signing randomness ($r=g^k$). This enables $\mathcal{B}$ to solve for $\alpha$.

For simplicity, let's first focus on a weaker model called the existential forgery under no-message attacks (EU-NMA) and a strong forger that is always successful. We show that a strong forger $\mathcal{F}$ that breaks the Schnorr signature in the EU-NMA model making at most $q$ queries to the random oracle $H$ (i.e., a $(1,q)$-adversary) can be used to break the DLP with probability $1/q$.

This requires two rounds of simulation:

Round 1. $\mathcal{B}$ runs $\mathcal{F}$ on $(G,g,g^\alpha)$; the random oracle $H$ is simulated in the standard manner (i.e., lazy sampling plus a table to ensure consistency). At the end of this round $\mathcal{F}$ returns a forgery $(M_0^*,(s_0^*,e_0^*))$ where $e_0^*=H(M_0^*\|r_0^*)$. For simplicity, it is assumed that $\mathcal{F}$ made the random oracle query $H(M_0^*\|r_0^*)$.
Rounds 2. Now $\mathcal{B}$ rewinds $\mathcal{F}$ to the point where it made the random oracle query  $H(M_0^*\|r_0^*)$ in Round 1 (the "critical" point) and re-runs $\mathcal{F}$ but answering the fresh random oracle queries independent of the previous round.$^2$ This constitutes the oracle-replay attack. At the end of Round 2, $\mathcal{F}$ returns a forgery $(M_1^*,(s_1^*,e_1^*))$ where $e_1^*=H(M_1^*\|r_1^*)$.

There is a non-negligible probability (at least $1/q$, but this has to be argued rigorously) that in Round 2 too $\mathcal{F}$ forges at the critical point (i.e., $M_1^*=M_0^*$ and $r_1^*=r_0^*$) but that the responses to the random oracle query $H(M_0^*\|r_0^*)$ were different (i.e., $e_1^*\neq e_0^*$). The intuitive reason is that $\mathcal{F}$ has to forge on some query, and in the worst case it chooses this point randomly. If this is indeed the case, then
  $$s_0^*=k_0^*-\alpha e_0^* \text{ and } s_1^*=k_0^*-\alpha e_1^*,$$
(as $r_1^*=r_0^*$, but $e_1^*\neq e_0^*$) and $\mathcal{B}$ can solve for $\alpha$
 $$\alpha=\frac{s_1^*-s_0^*}{e_0^*-e_1^*}.$$

The above argument can be strengthened to accommodate a general $(\epsilon,q)$-adversary in the EU-CMA model. To simulate the signing oracle (for the EU-CMA model) the reduction only has to program the random oracle appropriately.$^3$. Bounding the success probability of the reduction for the  general adversary (that is successful with a non-negligible probability $\epsilon$) is quite technical and uses the so-called forking lemma. To be precise, it is shown in [PS00] that an $(\epsilon,q)$-forger $\mathcal{F}$ that breaks the Schnorr signature in the EU-CMA model can be used to break the DLP with probability $O(\epsilon^2/q)$.$^4$

Footnotes.

$^1$The DLP on a cyclic group $(G,g,q)$ requires finding $\alpha\in\mathbb{Z}_q$ given $g^\alpha\in G$.

$^2$That is, the queries up to the critical point are answered consistently, but the fresh queries after the critical point are answered independently of Round 1.

$^3$To generate a signature for a message $M$, select $e,k\in_R\mathbb{Z}_q$, set $r=(g^\alpha)^e\cdot g^k$, and program the random oracle to set $H(M\|r)=e$. Return $(M,(e,k))$ as the signature. It is not difficult to see that the message is valid, and from the right distribution.

$^4$It was later shown in a series of works [PV05,GBL08,Seu12] that the loss is tightness of $\epsilon/q$ is inherent (conditioned on the assumption that the so-called one-more discrete-logarithm is hard).

References.

[PS00] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.

[PV05] Pascal Paillier and Damien Vergnaud. Discrete-Log-Based Signatures May Not Be Equivalent to Discrete-Log. ASIACRYPT 2005.

[GBL08] Sanjam Garg, Raghav Bhaskar, and Satyanarayana V. Lokam. Improved Bounds on Security Reductions for Discrete-Log Based Signatures. CRYPTO 2008.

[Seu12] Yannich Seurin. On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model. EUROCRYPT 2012.


There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A:

  Using methods 1 and 2 [yielding provable (1) and probable (2) random primes],
  $p$ and $q$ with lengths of 1024 or 1536 bits may be generated;
  $p$ and $q$ with lengths of 512 bits shall not be generated using these methods.
  Instead, $p$ and $q$ with lengths of 512 bits shall be generated using the
  conditions based on auxiliary primes.

Even though FIPS 186-4 requires (in the second part of this quote) that $p-1$, $q-1$, $p+1$, $q+1$ have at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, many regard this as an unnecessary complication.

The rationale about requiring that $p-1$ (and $q-1$) has at least one large factor is to insure resistance against Pollard's p-1 factoring. The standard rationale that such precautions become pointless past a certain size is that we have factoring algorithms (including GNFS and ECM) with a much better asymptotic run time; that becomes rigorous (thus true) if we add: for any fixed odds of success [Pretty much the same applies to requiring that $p+1$ (and $q+1$) has at least one large factor, which would be in order to guard against Williams' p+1 factoring; and when we do not need to guard against Pollard's p-1, we do not need to guard against Williams' p+1, thus I disregard the later].

Determining quantitatively when we can dispense of precautions against Pollard's p-1 is not trivial!

There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM].


Where do $\lambda_i$'s come from?

Consider a polynomial of degree 4, $p(x) = p_4 x^4 + p_3 x^3 + \cdots + p_0$. We can write polynomial evaluation as a linear operation on the coefficients:

$$
\begin{bmatrix}
p(1) \\ p(2) \\ p(3) \\ p(4) \\ p(5)
\end{bmatrix}
=
\begin{bmatrix}
1^0 & 1^1 & 1^2 & 1^3 & 1^4 \\
2^0 & 2^1 & 2^2 & 2^3 & 2^4 \\
3^0 & 3^1 & 3^2 & 3^3 & 3^4 \\
4^0 & 4^1 & 4^2 & 4^3 & 4^4 \\
5^0 & 5^1 & 5^2 & 5^3 & 5^4
\end{bmatrix}
\begin{bmatrix}
p_0 \\ p_1 \\ p_2 \\ p_3 \\ p_4
\end{bmatrix}
$$

The matrix in the middle is a Vandermonde matrix and hence it has full rank.

Now this also means that the rows of the Vandermonde matrix form a basis. So another vector like $[1~0~0~0~0]$ can be written as a linear combination of those rows, say:

$$
\begin{bmatrix}1 & 0 & 0 & 0 & 0\end{bmatrix}
=
\begin{bmatrix}\lambda_1 & \lambda_2 & \lambda_3 & \lambda_4 & \lambda_5\end{bmatrix}
\begin{bmatrix}
1^0 & 1^1 & 1^2 & 1^3 & 1^4 \\
2^0 & 2^1 & 2^2 & 2^3 & 2^4 \\
3^0 & 3^1 & 3^2 & 3^3 & 3^4 \\
4^0 & 4^1 & 4^2 & 4^3 & 4^4 \\
5^0 & 5^1 & 5^2 & 5^3 & 5^4
\end{bmatrix}
$$

Multiply on the right by the vector of coefficients and you can see that

$$
p(0) = p_0 = \sum_i \lambda_i p(i)
$$

More generally, if you have $d+2$ distinct points $x_0, x_1, \ldots, x_{d+1}$, then there exist coefficients $\lambda_1, \ldots, \lambda_{d+1}$ with the following property: For any degree-$d$ polynomial $p$, you can write $p(x_0) = \sum_{i=1}^{d+1} \lambda_i p(x_i)$. The $\lambda_i$ coefficients are the coefficients of the "Vandermonde vector" of $x_0$ when written in the basis of the Vandermonde matrix on $x_1, \ldots, x_{d+1}$, which is indeed a nonsingular matrix.

What is "specific structure" ?

It says right there in the next sentence (p14 of this):

  In addition, $h(x)$ generated in this way is not a “random polynomial” but has a specific structure.  For example, $h(x)$ is typically not irreducible (since it can be expressed as the product of $f_a(x)$ and $f_b(x)$), and this may leak information.

If I were to rephrase what they say: Given degree-$t$ Shamir sharings of $a$ and $b$, everyone can locally (i.e., without communication) multiply their shares. The result is a degree-$2t$ sharing. But there are two problems:

If this wire is used in subsequent multiplication gates, we need the value to be shared on a degree-$t$ polynomial.
The wire might not used in subsequent multiplication gates. Consider the case where it is an output wire, then the only thing we do in that case is open all the shares (to reveal the output). Now it is true that the degree of the polynomial doesn't really matter. But the distribution of the polynomial matters because the entire polynomial is revealed when the shares are announced.

Here the polynomial is known to be a product of two deg-$t$ polynomials. So if the polynomial is revealed, its factors are also revealed, and it could become obvious that $a$ is the constant term of one factor and $b$ is the constant term of the other factor. In other words, the protocol would leak $a$ and $b$ whereas we only wanted the product $ab$ to be revealed as output.

I'll note that the second "problem" can also be resolved by adding a random $2t$-sharing of 0 (instead of doing an interactive degree-reduction step). But in either case, the "raw" result of locally multiplying shares is not suitable for direct use. The protocol must include some mechanism to "sanitize" it.


Desirability of chaining an LCG in an authentication scheme

Would it be too slow to make for a good authentication mode?

No, it would be too insecure for a good authentication mode.

In particular, given any message $M$ that's at least two blocks long, it's trivial to find a second message $M' \ne M$ that has the same tag (no matter what the key is); and hence one could be substituted for the other without detection.


How to recover small messages from textbook RSA?

Disclaimer: I did not come up originally with this attack, but rather it was first described in "Why Textbook ElGamal and RSA Encryption
Are Insecure" by Boneh, Joux and Nguyen (PDF).

This answer will give a summary of the attack, similar to what is documented in Introduction to Modern Cryptography by Katz and Lindell.

First for the actual attack:
Let $c=m^e\bmod N$ be given as well as $(N,e)$ and let $m<2^l$ for some $l\in\mathbb N$. Then there exists $m=r\cdot s$ with $r,s<2^{\alpha\cdot l}$ for some $1/2<\alpha<1$ with decent probability:

Set $T:=2^{\alpha\cdot l}$.
For all $r$ from $1$ to $T$ compute and store $x_i=r^e\bmod N$.
Sort the pairs $(r,x_i)$ by the second component.
For all $s$ from $1$ to $T$ check (e.g. using binary search) whether $c\cdot s^{-e}\bmod N=x_i$ for some $i$, if so return $r\cdot s \bmod N$ as the message $m$.

(If $s^{-e}$ cannot be computed, then $s$ shares a non-trivial common divisor with $N$, and so one can trivially factor $N$ by calculating $\gcd(s,N)$.)

Now for the run-time of this algorithm:
One needs about $2^{\alpha\cdot l}$ modular exponentiations for step 2, $\mathcal O(l\cdot 2^{\alpha\cdot l})$ for step three and about $\mathcal O(l\cdot 2^{\alpha\cdot l})$ for step four. So overall one does get away with "little more" than $2^{\alpha\cdot l}$ steps. Given that there's at least some chance (a few percent) that $\alpha=1/2$ will work, this would result in an attack with about $2^{l/2}$ run-time.

Note that steps 1 to 3 above don't depend on the ciphertext $c$, so they can be done in advance, and the resulting table reused for several ciphertext.

As for why this attack works, note that we effectively brute-force factor the message by exploiting the homomorphic property of RSA and that $c=m^e=(rs)^e=r^es^e\bmod N$.


The capacity $c$, together with the rate $r$, is the state of the algorithm between the applications of the sponge.

It is of course affected by the message (there is no other input after all) but not directly: the input first has to go through the sponge function, $f$, after it is XOR'red with the rate, $r$. Similarly, only the rate $r$ is output during the squeezing. So the previous capacity $c$ is similarly protected by a sponge. Note that there is always an $f$ between the input and output (of course).

The capacity and the rate are first initialized to zero.


How do you distribute secret shares without knowing who to first distribute them to?

As long as you know the reconstruction threshold a priori, I see no reason you can't generate a bunch of shares before knowing who you will distribute them to. Once you know who you are going to distribute them to, just send one share to each person.

On the other hand, if you don't know the reconstruction threshold, you wouldn't be able to construct, I don't see how you can do it. It would seem like an ill-posed problem at that point.


without doing your homework for you: did you check the open-source implementations of ISO 8583? is the answer somewhere in there?

DL-ISO-8583, in C
jPOS ISO-8583 Framework, in Java
j8583, also Java
PHP ISO-8583 Parser

Retrieved from wikipedia (strangely, the Spanish page, a good tip for finding more external references is changing the language tab)