How to explain just how secure AES is in layman terms?

Some audiences react positively to this line of arguments:

Mathematical attack are unlikely: the AES block cipher as a mathematical construction has been scrutinized for 15 years by many bright brains, yet what they published leaves trying all the keys as the best attack within a small factor (less than 4 for the weakest AES-128), assuming random and secret keys. Anyone with a better attack would gain high social status by revealing it. And there is positive mathematical proof that attacks against mode of operations (AES-CTR..) are impossible without attack on the block cipher. We can conclude that it is unlikely that there exists a good mathematical attack; and even more unlikely that a particular attacker knows about it.
Brute force attacks are impossible with our current knowledge: there simply are too much keys to look among. Using all the money (easily, hundreds million USD) and energy that was ever used for bitcoin mining, we could perhaps break a 95-bit key. Breaking a 128-bit key requires $2^{33}$ times more effort; that's well over the ratio of cost of manufacturing all the cars now on earth, to the marginal cost of manufacturing one.
Remaining attacks are those on usage or implementation: the key can leak from its holder, or be poorly chosen, or be derived from a weak password, or be poorly derived from a fair passphrase; the key can leak thru compromise of the machine on which it is stored or used, or side channels including timing; there might be implementation goofs, including in random generator, and mode of operation. These are very real threats, and practitioners know that humans are bad at keeping secrets (they often let it leak or/and vanish), programmers often goof or make poor choices (especially when it comes to transformation of password/passphrase to key), and it is extremely hard to be highly confident that an implementation is fully immune against attacks by an adversary that is physically close to the machine, or had physical or logical access to it (including software, design of the hardware).

An honest, knowledgeable and prudent practitioner can tell that hardware AES implementations (including those with AES-NI) are verifiably immune from timing attacks, which is the only known side channel that can be exploited from a large distance, assuming the implementation is not intentionally rigged; thus s/he's confident that save for a compromise of the key, the machine or its software, a machine using such hardware AES implementation is safe from any kind of attack from distant adversaries.

Note: I have found that admitting flatly that attacks on usage and implementation are possible, and happen, helps convince that mathematical and brute force attacks do not, and that a particular implementation is safe enough.


ECB vs. CBC, I've seen the pictures, but what's the actual strength difference?

There is no good way to calculate a strength difference between ECB and CBC. ECB is broken as a generic cipher - it is not indistinguishable under chosen plaintext attack - as repeating blocks will confer information to an attacker. That particular piece of information doesn't let itself be quantified compared to the amount of bits within the key. It's even completely separate from the key size by definition (AES-256-ECB will be as broken as AES-128-ECB).

CBC with a static IV is vulnerable for the first blocks that could be identical. CBC with a predictable IV is vulnerable as well. However CBC - when used correctly - is secure for confidentiality of data at rest.

The key stays protected by the block cipher itself. If that's "cracking the cipher" then any mode is OK. However, the key only exists to protect the confidentiality of the plaintext. And if that is compromised the security of the system is compromised. So the security of the cipher is inconsequential.

Side note: replay attacks can happen in transport security. They can happen even if the ciphertext is authenticated. Replay attacks have little to do with ECB or CBC mode as neither is a good fit - on its own - for transport mode security. ECB mode is simply susceptible to repetition of plaintext blocks; that's different from replay attacks.


Encrypted cerficiate signature for server certificate and intermediate certificate in packet capture

The intermediate certificate is signed by its issuer(a root CA or another intermediate CA), using the private key of the issuer's certificate.

The server certificate is signed by the intermediate CA at the lowest level of the certificate chain.

  when configuring the certificate chaining in the server, the imported intermediate CA already has the certificate signature encrypted?

Yes, when you want a certificate for your domain, you ask for it from an intermediate CA. After the CA verifies that you're the actual owner of the domain, they give you a certificate signed by the CA's private key. Then you can configure to use it on your server.

The intermediate certificates are simply available to the public, they are sent by the server generally for clients that don't have them installed.


Why do we add error in the definition of LWE?

In that case, how we would be able to obtain $s$ from $(a,b=(\langle a,s\rangle))$?

The operation $\langle a,s\rangle$ is a matrix multiplication, that is, completely linear, and hence Gaussian elimination allows us to recover $s$ efficiently.


How to make the interactive Schnorr identification protocol become non-interactive

The most common way to change an interactive Schnorr protocol into a non-interactive one is to rely on a random oracle. This is the so-called "Fiat-Shamir heuristic".

Notice that a transcript in your case would look like $(r, e, y)$, where $e$ is the challenge the verifier sends to the prover.
Now, you want to get rid of any interaction with the verifier to get that random challenge $e$, so what you need to do is to find a way to get rid of that interactive challenge. And there, you could have a random oracle giving you the challenge instead of the verifier.

In practice, this is done using a cryptographic hash function $H$ and so your transcript becomes $(r, H(r), y)$ or, as on Wikipedia: $(r, H(g,y,r), y)$. (It is important to include the public parameters in your Fiat-Shamir, to avoid problems such as weak Fiat-Shamir heuristics.)

Now, you can still verify that it works just like the interactive case, excepted we don't need to ask Victor, the verifier, to provide us with a random challenge anymore, since both the prover and the verifier can compute the challenge out of the rest of the data in a non-interactive way.


Trying to finalize my understanding about password storing

Each of these algorithms has a similar process:

$K_{i+1} = R(K_i)$

Where $K_0$ is set to some concatenation of the plaintext password and optionally a salt value, and $R$ is the algorithm specific "round function". The number of iterations is also adjustable by the application.

As you said, the input of the next round comes from the output of the previous round, which forces the work to be done in serial. A program that uses this need not block, it could be done in a separate thread.

The algorithms differ in their choice for $R$. It seems that BCrypt uses a function based on Blowfish, while SCrypt $R$ relies on a large lookup table. They all have the same purpose, to make checking a large number of hashes as resource hungry as possible, while trying to minimize user inconvenience caused by a small delay in checking a single password.


Completely insecure.

If you just replace the encryption with XOR with the key, then the first ciphertext block is just $c_1=m_1 \oplus k$. The second block would be $c_2=m_2 \oplus c_1 \oplus k = m_2 \oplus m_1$.

The second block is actually not encrypted at all. And that goes on, the first, third, fifth and so on block is just an XOR with the key, the second, fourth, sixth and so on doesn't depend on the key at all.


Factoring $n$ in RSA knowing $e$ and $d$

Ok, lets see if we can go through one line of reasoning, and see if that makes sense.

If we have the sequence:

$$g^{k/2^t} \bmod N, g^{k/2^{t-1}} \bmod N, …, g^{k/2} \bmod N, g^k \bmod N$$

We know that the last entry evaluates to 1, and we are looking at the probability (for random $g$) that the entry immediately before the first 1 is a nontrivial squareroot of 1.

Now, we can consider the sequences modulo $p$ and $q$, namely

$$g^{k/2^t} \bmod p, g^{k/2^{t-1}} \bmod p, …, g^{k/2} \bmod p, g^k \bmod p$$

$$g^{k/2^t} \bmod q, g^{k/2^{t-1}} \bmod q, …, g^{k/2} \bmod q, g^k \bmod q$$

Now, we might not be able to compute these values before we know the factorization, but that's OK, we're just considering them.

Both sequences end in 1, and consist of a (possibly empty) sequence of non-1 values, followed by all 1 values.  In addition, $g^{k/2^i} \bmod N$ is a nontrivial squareroot of 1 if $g^{k/2^i} \bmod p$ is 1 and g^{k/2^i} \bmod q$ is the last non-1 value (or versa-vica).  In other words, we'll have a nontrivial squareroot if the two sequences turn into a 1 value at different positions in their sequences.

So, the question is: what is the probability bounds on that?

Now, if $g$ is a random (equiprobable) value in $\mathbb{Z}_N^*$, then $g \bmod p$ and $g \bmod q$ are equiprobable and independently distributed values in $\mathbb{Z}_p^*$ and $\mathbb{Z}_q^*$; hence both sequences are selected from random starting values.

And, half of the values of $g$ are quadratic residues modulo $p$ and half are quadratic nonresidues modulo $p$.  For a quadratic nonresidue, the mod-p sequence will become a one at step $t_p$ (where $p-1 = 2^{t_p} z_p$ for odd $z_p$; for a quadratic residue, it will be come one at an earlier step.  Hence, the maximum probability for any particular step will be 0.5.

The same logic holds for $q$.

Now, $g \bmod p$ and $g \bmod q$ are independent variables, and so the maximum coincidental probability will occur if both chains have two stages with probability 0.5 each; in that case, the probability that they are difficult will be $1 - (0.5 \cdot 0.5 + 0.5 \cdot 0.5) = 0.5$

This argument could be tightened up a bit; however it should be enough to give you some insight...


RSA decrypt message with low public exponent (n = 187, e = 3 and C = 185)

For small $N$, textbook RSA decryption is possible without factoring $N$ using the cycling method, (sometime called cycling attack; see this for a reference):

initialize $M\gets C$
set $D\gets M^e\bmod N$ (otherwise said, encrypt $M$)
if $D\ne C$, then set $M\gets D$ and loop to the previous step
output $M$ and exit.

Since encryption is a reversible mapping of the finite integer set $[0,N)$, the algorithm must cycle and stop. Obviously, when it does, we have $C=M^e\bmod N$, thus the algorithm has deciphered $C$.

Note: this is unrelated to small $e$. It works well for small $N$, but for other $N$ or multiple messages to decipher, it is more efficient to factor $N$.


Can key hardening compensate lack of entropy?

Yes. That's the entire idea of key stretching, you can get away with a password that offers less strength against attacks. You add more operations to a brute force/dictionary attack to protect the keys. The disadvantage is that you need to do the same number of operations during key derivation.

Passwords commonly don't have 64 bits or 80 bits of entropy though. Say that the alphabet is 64 characters (6 bits) then you'd need a fully random password of 11 characters. For 80 bits you'd already need 14 characters. Those are easy to generate of course, but it may be tricky to remember them. And if you have to revert to a password manager, you might as well use a password that requires a few more keystrokes.

Note that shorter doesn't necessarily mean less strength. A password of 12 zero digits is not very strong. And although the idea behind "correct horse battery staple" is great, the strength of the passphrase is of course not the same as 28 fully random characters.

J.D. indicates that, indeed, different operations are performed for a single round. The amount of operations however will stay the same, so the increase should be in the same ball park. You could possibly assign a weight to each round of AES vs each round of the key strengthening routine to get a better estimate about the increase of strength.


How do you implement a cipher as one lookup table?

For a fixed key, a (block) cipher is a reversible transformation of a plaintext set to ciphertext set. Usually (and in the slide) these sets are identical, and consist of all the exactly $n$-bit strings. This set has $2^n$ elements, and is often noted $\{0,1\}^n$.
Note: in this notation $\{0,1\}$ designates the set with the two elements $0$ and $1$, and as usual raising a set to the $n$ means we are considering the set of all $n$-tuples with each element in the base set.

One possible implementation of a that transformation is a table $T$ of the cipher's output for each of its input. This table has one entry for each input, thus $2^n$ entries. Each entry is an $n$-bit string, thus uses $n$ bits. The table thus uses $2^n\cdot n$ bits.

To use the cipher defined by way of the table, one converts the $n$-bit input to an integer $j$ with $0\le j<2^n$, fetches the table at index $j$ that is $T[j]$, obtains an $n$-bit value, and that's the cipher's output.

Addition per comment: if the adversary possesses a box (of whatever color) implementing that transformation, we must assume the $n$-bit inputs and outputs, and their correspondence, are observed when the box is used. That might not be a total disaster if the adversary can't economically reproduce the box, and/or enumerating all input/outputs is impossible (e.g. requires too much time/energy, or exhausts a usage counter).


How to solve the Diffie-Hellman problem if $g$ is unknown?

In general, there are a huge number of possible values for $g^{ab}$, depending on what $g$ is.

However, in this case, whoever set up this problem took care to radically reduce the number of possibilities.

Here's how you would attack this problem:

Step 1: factor $N$
Step 2: for each prime power factor $q^k$ of $N$, we need to determine the set of values of $g^{ab} \bmod q^k$.  Two special cases where this is easy:

If $g^a = 0 \pmod q$, then obviously $(g^a)^b = g^{ab} = 0 \pmod {q^k}$, and so we have one solution to this subproblem.
If $g^a = 1 \pmod{q^k}$, then $(g^a)^b = g^{ab} = 1 \bmod {q^k}$, and so we have one solution to this subproblem.

In practice, these special cases don't come up that often, in this case, it does.

Step 3: once we have the set of possible solutions to each of the subproblems, we can use the Chinese Remainder Theorem to join them together to come up with the set of solutions to the original problem.

Now, normally, each subproblem comes up with a large number of potential solutions, and so the combinatorics of step 3 comes up with a truly huge number of solutions.

However, in this case, it turns out to be only two solutions to the overall problem (and, as luck would have it, you really don't need the CRT to join those solutions in step 3; there's a simpler way to compute them).


I need help determining the best encryption options based on System.Security.Cryptography in .NET

without introducing another library

Well, this isn't exactly an ideal situation, but there's still hope. After having browsed the list of available tools there are still some things that can be done, but of course the solution will be less robust and less modern than if one could rely on external libraries.

  Which one would be better to use?

This still depends. If you absolutely cannot tolerate ciphertext expansion under any circumstances whatsoever and if you absolutely cannot tolerate using external libraries under any circumstances whatsoever then yes, CBC-mode is your best choice. If you cannot tolerate ciphertext expansion, you want to look into using EME or XTS mode as a fallback, but for the rest of this section I'll assume that ciphertext expansion is acceptable.

Your best choice if you absolutely cannot tolerate using external libraries under any circumstances whatsoever is to use AES-CTR + HMAC-SHA256. You already found the Enum for CTR-Mode, this leads the question to HMAC-SHA256. The optimal way here is to take the entire ciphertext with all associated data (such as routing information and / or salts), run it through HMAC and append (or otherwise pair it with) the resulting authentication tag. Then on decryption reject any incoming messsage that either lacks a tag or has an invalid tag. The key should be derived as described below, but should definitely be independent of the AES key and the CTR IV.

  Use of Use of PBKDF2 is outdated, and it was suggested to use Argon,
  but here is what I'm using. Not sure of what to replace this with
  within the constraints of .NET out of the box

That's the problem. There is nothing. This is the only situation where falling back to PBKDF2 is acceptable. There are two things to still get somewhat good security out of PBKDF2 and you really want to do both:

Use a non-fixed iteration count. The one really nice thing about PBKDF2 is that its runtime is perfectly linear in its iteration count, so ideally you want to dynamically measure how many iterations per second you can do on your target system and then linearly extrapolate how many you actually want to do. Usually with this you want to target 100ms on something like a server, but the more CPU-time you can spare the better.
Aggregate-Derive-Expand. As pointed out as a "side-note" in the answer on CodeReview.SE the current PBKDF2 parameters lead three separate "chains" of derivation which are easily parallelized by an attacker. Ideally (and this is possible here), one concentrates the keying material into a single string ("aggregate") using eg a straight SHA256 hash (this may get more complicated for more complex keying material structures and properties), then one runs this through the expensive key-derivation function so this function gets called exactly once and thus can be as expensive as possible ("derive"). Finally one gets what TLS calls a "master secret". From this one derives the actual secrets needed like e.g. the AES key, the HMAC key and potentially the CTR IV ("expand"). Ideally one would do this using HKDF, but in this case PBKDF2 with a single iteration also does the trick as would do "label-driven-expansion" where you put the master secret into the key input of an HMAC instance and a label for the key (such as the string "AES key") into the message input.


Why does CTR mode XOR the plaintext into the output of the block cipher rather than XORing the plaintext into the input of the block cipher?

There are some serious problems with this design that would preclude it from being standardized, so it probably does not have a name.
The 2 visibly main flaws are as follows:

If the plaintext follows a pattern similar to the block counter, the
block cipher inputs may repeat, exposing information about the
plaintext (exact same issue as reuse of nonce, but could happen
multiple times per message, example given at end)
Plaintexts with a length not equal to a multiple of the block size
would need the length included with the ciphertext in order to
decrypt, as the full block output is required to decrypt, or they
require padding of the last block.

The structure of CTR has several desirable properties that your example does not.
It allows encryption without padding or additional length data to decrypt. It allows
precomputation of the cipherstream prior to the plaintext being available, which
can mean huge speed improvements if there is enough memory available and message
plaintext is available at irregular intervals. CTR can also be processed in a highly
parallel manner, and requiring the plaintext as an input could slow that down if it
is not available immediately.

Here is an example of a duplicate block:

"THIS IS A TEST SIMPLY TO EXPLORE WHAT WILL HAPPEN IF WE ENCRYPT THIS IS A TEST WITHOUT A SECURE MODE"

Block 0 plaintext = "THIS IS A TEST S", block 4 plaintext = "THIS IS A TEST W"

In this example, the input to the block cipher will be the same for block 0 and 4 for this message, regardless of the nonce, as "W" becomes "S" when xor'd with the block counter for block 4. Lots of data types have similar types of repeating information with only small changes, such as image files and executable programs. This is almost as bad as ECB for potential plaintext recovery.


What encryption mode should I use to protect CAN bus communication?

Theory aside, there's basically no way to have security on the CAN bus.
The Controller Area Network, or CAN bus, is a differential bus that is robust enough for critical communications but simple enough to be used with micro-controllers. CAN bus employs a message-based protocol over four wires, power, ground, CAN-, and CAN+, where the message from a device with the lowest ID becomes dominant on the bus.  In the language of the CAN specification, the “dominate” bit is “0” and “recessive” bit is “1” based on the fact the signal lines are drive to their high and low states by transistors in the dominate state and that resistors passively pull the signal lines to each other in a passive fashion in the recessive state. Relating to physical security of this bus, if you "short" two lines, it will cease to function.
CAN data frame starts with an arbitration field that contains the ID of the node. If two nodes have a message at the same time, both nodes will start transmission concurrently, and the node with the higher ID number in binary will stop transmitting when it sets the bus to be recessive, which is a “1”, but detects that the bus is in a dominate state, which is a “0”. At this point, a collision has happened and the node has lost arbitration. This is also the physical reason that it is impossible to physically protect the CAN bus from a malicious device on the bus, because setting the bus to “0” that forces the bus into the dominate state is an attack on availability, such as a DoS attack. The best that the system can do in this case is to detect the fault and shut down.

Security for CAN bus through authentication protocols for CAN bus proves difficult because authentication codes are not tied to message IDs, which makes them impossible to trace, and do not generally seem appropriate for implementations on simple microcontrollers. Although authentication is required and is an important problem, you will have to focus only on encryption of the data in the CAN frame because of its importance from the hardware implementation perspective.
You cannot use a counter because you cannot guarantee delivery of a packet.  You are pretty much stuck with ECB mode for encryption.


Needing to encrypt plain sight information

The answer in the comments from dchest is probably the most standard. Encrypt the page with a single, random key. Then encrypt that key for each user using the shared secret that you hold with that user.

It is unclear whether this meets your needs as it is unclear exactly what your needs are.

With that in mind, a fairly advanced way you could get the functionality you require is with Ciphertext-Policy Attribute Based Encryption. It is very complex and would require a lot to describe in this answer (and I don't even know if it meets your needs as they seem to not be fully defined at this point).


How does PUF hardware help in software activation?

You're right about hardware activation devices for desktop applications.  Dangling dongles outa your printer port is quite legacy.  New applications tend to use some form of on-line activation system. You see this in games  and Windows.

But it is becoming more common in the embedded world, where it can act as product key, hardware ID, or activation number.  Consider the most fundamental behaviour of a PUF. It allows a  challenge–response protocol to generate a non clone-able set of values, each usually (but not necessarily)  one bit wide, with some degree of repeat ability.  Using fuzzy extraction, secure sketches, error correction and compression, a single number can be produced with very good reliability.  The PUF (oscillator based) with multiple challenge-response pairs would live within an FPGA like so:-

And that's it: a set of bits.  Use the set as you will.  It could very well simply be the (uncloneable) device ID.  PUFKY is a design for a random 128 bit cryptographic key extracted from ring oscillators.  Intel have   Stratix FPGAs/SoCs that incorporate on-board SRAM PUFs for protection against counterfeiting, cloning or reverse engineering. It can also be the key for cryptographic communications from the chip. You can see where the PUF fits into the Stratix:-

Circling back to software activation, a PUF is the evolved in-built "dongle" of yesteryear protecting modern software.  It's just that the 'software' these days can be intellectual property like IP cores, gate/block configurations, digital signal processing algorithms etc. and communications data within and around embedded devices.


Order of OTs and commitments in Yao's Protocol for malicious adversaries

In the simulation, the output of the corrupted party is needed by the ideal adversary/simulator BEFORE the commitments and circuits are sent. Otherwise, the simulator is unable to generate values that will be indistinguishable from those in a real execution. In order to obtain this output, the simulator must send the corrupted party's input to the trusted third party (ideal functionality) and then get back the output. Since the corrupted party's input is extracted by the simulator in the OT phase, the OTs must be run first.


Why does Merkle-Damgård hashing involve putting the padding at the end instead of at the start?

I can only provide a programming sense to this;
One may not know the size of the message beforehand (streaming), when finished, the length-padding can be executed nicely at the end. Otherwise, the system must store all of the messages to calculate the size, this will be very bad for constrained environments.


Sliding windows implementation (Exponentiation by squaring)

Serious cryptography software today does not use sliding windows for exponentiation by secrets precisely because it leaks the secrets through array indexing.  You might find it older versions of OpenSSL, libgcrypt, etc.  In modern software, your best bet is probably libgmp (mpz_powm, not mpz_powm_sec) or other generic bignum libraries optimized for speed, not for security.


Universal hash functions with homomorphic XOR property

I believe that the internal GHASH function from GCM would meet that criteria (if you trim off the length word, and require universality only with equal length inputs [1]); it can be defined as:

$$\operatorname{GHASH}_k( M_n, M_{n-1}, …, M_0 ) = \sum k^i M_i$$

With the input $M_n, M_{n-1}, ..., M_0$ being the input message divided into 128 bit blocks, $k$ being the universal hash key, and the arithmetic (both the additions and the multiplications) done over the field $\operatorname{GF}(2^{128})$

It meets the criteria:

It is universal (for equal length messages); for random $k$ and any two distinct equal length messages $M, M'$, we have $\operatorname{GHASH}_k(M) = \operatorname{GHASH}_k(M')$ with probability $\le |M| / 2^{128}$
It meets your homomophic requirement; this is because addition in $\operatorname{GF}(2^{128})$ is exclusive-or, and we have $k^i M_i \oplus k^i M'_i = k^i( M_i \oplus M'_i)$
It is quite efficient (especially with AES-NI instructions); I can't say that it's the most efficient possible...

[1]: You cannot get both the homomorphic properties and the universality (across messages of different lengths) to hold simultaneously.  The homomorphic property requires that $h_k(0) = 0$ and that $h_k(00) = 0$, hence we have two different messages $0$ and $00$ which hash to the same value with high probability (actually, 1), thus $h_k$ is not a universal hash family.


This is first half of the calculation presented on the Wiki page.

Notice that every bit of the result is actually a XOR of just five bits:

Now we slightly modify the algorithm you wrote to create five numbers by rotating the original number to the left and only then XOR them together:

As you can see the result is exactly the same.


Is a stream cipher similar to One-Time Pad using hash secure?

If you are imagining something like 256+ bits of key -> SHA-256 -> one block keystream that you XOR with the plaintext, that is indeed almost the same as one-time pad. However, there is no advantage to doing that, considering you might as well have used the original key directly as a one-time pad.

If, instead you use a password-based hash, a dictionary attack or similar can be successful, and unless the password has more entropy than the output size of the hash, the attacker can at least rule out some possible messages, meaning it lacks perfect secrecy.

Even in the first case, where your key is high entropy, the fact that you run it through a hash function will affect the possible outputs and their frequencies, so a computationally unbounded adversary would gain some information about the contents of the message – some options may be impossible and some may be more probable.

In practice, using a (password-)hash to produce a keystream amounts to a stream cipher, and assuming your key/password has enough entropy and you do not reuse the same key/password for other messages, it is very likely secure. From a confidentiality point of view, that is: stream ciphers (and OTP) are malleable so you want authentication if the integrity of the message matters.

(Insert obligatory recommendation to use standard ciphers in practice.)


Weakness in using only one RSA key pair for two-way communication?

The question and comments seem to be asking the following:  If an implementation of RSA is used in the following way, is it still secure?  An RSA modulus $N = pq$ and exponent $e$ are generated, and (N,e) is given to Party $A$ and $(p,q,e)$ is given to Party $B$.  Then, the parties encrypt their communication where Party $A$ encrypts using the modulus and exponent, while party $B$ encrypts using the private primes and the exponent.

To really answer the question, we'd have to define what encryption padding method is being used (OAEP, PKCSv1.5, etc) and what notion of "secure" we want.  We'd also have to define what it means to encrypt with the secret key instead of the public key.  But as long as the encryption methods with either key are generating the same ciphertext (more precisely, the same distribution over ciphertexts), then whatever reasonable security notion we want will be achieved in this setting under the same hardness assumptions.  This is because the adversary is seeing ciphertexts that are all indistinguishable for ciphertexts generated in the usual way, so the basic security achieved will transfer over easily in provable way.


What is the mathematical property stating that it is hard to find a collision in the AES algorithm?

As mentioned in several of the other answers, AES is a family of permutations indexed by the key. Hence there cannot exist any collision of the form $AES_k(x) = AES_k(x')$ for $x\neq x'$.

On the other hand, if we look at the function $f_x: k \rightarrow AES_k(x)$ we should ideally have a random function. Finding a non-random property of this function would be a major step in cryptanalysis of AES. So, with this reasoning the standard reasoning for random functions applies. For AES this means we have a function that maps 256 (192, or 128) bit strings to 128 bit strings. By the birthday paradox we know that an adversary that evaluates $f_x$ $q$ times has a success probability of $\mathcal{O}(\frac{q^2}{2^{128}})$ and that is also the best one can do without a huge improvement in the cryptanalysis of AES. However, this means one can find collisions of that function in about $2^{64}$ AES evaluations. This is already doable: the bitcoin network currently does about $2^{70}$ SHA2 computations per day!  And AES is faster than SHA2.


In practice, how many algorithms depend on the totient function?

I know that the security comes from the fact that the totient $\phi(n)$ is difficult to compute

Actually, we don't know that.  We know that if we can recover $\phi(n)$, we can decrypt an RSA encrypted message (given the public key), but we don't know how to go the other way; given a way to decrypt RSA encrypted message (given the ciphertext and the public key), how we might recover $\phi(n)$.  Decrypting RSA messages might be easier than recovering $\phi(n)$.

However, to address your question "what public key algorithms assume that recovering $\phi(n)$ is hard", well, recovering $\phi(n)$ is equivalent to factoring $n$ (in the sense that if you can solve one of them, you can immediately solve the other".  Hence, what you're looking for are public encryption methods that assume that factorization is difficult; I believe that list would be RSA, Rabin and Paillier (which is a public key encryption scheme with some additional homomorphic properties that can be useful at time).


Random Number Generation with a Entropy pool versus Seed

What I want to know is what are the benefits of using an entropy pool over a single byte seed value?

There are no benefits of an entropy pool. It's a  necessity.  If anything, it's a strong  indicator of a poor true random number generator (TRNG) and hints at the construction actually being a de facto pseudo random number generator (PRNG), which I believe /dev/random to be.

The golden rule of any TRNG is that H(in) >= H(out) where H is entropy. The following diagram illustrates the Linux random number generator's entropy pool.

As the input events are totally irregular and of indeterminate frequency, H(in) cannot be calculated.  You can easily wait >60 seconds for a single random output byte to become available.  You mention that the Linux implementation is well documented.  Not for this point.  There is no quantitative assessment of input entropy that I can find in the literature.  The best is the report at the bottom, but that still accepts the developers' assessment of 1 bit of entropy/event.  It might well be far lower but as stated, irregular events cannot be given a rate.  No one has undertaken an accurate entropy measure of the jiffy events themselves. δ3s are not valid units of entropy.  Ergo the golden rule is not proven.

Thus the entropy pool acts as an accumulator and low pass filter to smooth the jiffies.  You will have had to implement this for yourself in your Javascript port.  Re iteratively hashing the pool is very much akin to the re permutations of a sponge construct during the squeeze phase, and thus another parallel with a PRNG.

TRNG are all about real entropy and it's accummulation.  Any port of /dev/random will have to address the capture of entropy from a machine, and as Javascript is more highly abstracted than the kernel, it will be harder. But a pool will be unavoidable.  You cannot easily re seed a generator's state byte by byte and bit by bit as irregular entropy events are detected.  Whether you implement a direct copy of /dev/random or some NIST CSPRNG, you'll need the pool to cheat. It's got nothing to do with the number of concurrent applications. You're confusing the entropy pool with a connection pool.

This question may be a trifle stale, but the answer is still relevant today for anyone developing a true random number generator.

Ref. François Goichon, Cédric Lauradoux, Guillaume Salagnac, Thibaut Vuillemin. Entropy transfers in the Linux Random Number Generator. [Research Report] RR-8060, 2012, pp.26.


Is it safe to reuse a symmetric key when using asymmetric encryption?

The use of the AES key many times is not a problem. However, there is a fundamental flaw with your solution. The server has no way of validating that it received the client's authentic public key. In particular, a man-in-the-middle can capture the client's public key, can forward its own public key to the server, and can then decrypt all traffic sent by each party (since it will be able to decrypt the AES key). Also, the client cannot know that it is talking to the authentic server at any stage.

Apart from that, you lose a lot of properties that people like to have in such protocols, like forward security.

In general, it's not a good idea to make up your own protocols (no matter how simple). My recommendation is to just use TLS v1.2 with a forward-secure cipher suite. The best to use are TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256, or TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256. However, you still have to solve the problem of somehow enabling the parties to identify each other, and to be sure that the correct public key is used. This is handled by using certificates.


Is "reused one time pad" safe to encrypt a message like "random number + mod"?

Here's my understanding of the encryption process you're talking about:

You take a random number $r$, and compute $t = r \bmod n$
You concatinate the two numbers $r$ and $t$, and express the concatination as a bitstring $u$
You then xor that bitstring $u$ with a secret bitstring $s$

You do the same for two different random numbers $r$ and $r'$, using the same values for $n$ and $s$.

If that is correct, then here is one way that someone with the two encrypted strings can recover a short list of possible $r, r'$ values:

Consider all possible $r$ values (in your example, $r$ was a 6 digit number, so that would be trivial; I don't know how long you would make $r$ in the real case)
For each such $r$, compute the corresponding $t = r \bmod n$, and combine them to form the bitstring $u$.
Exclusive-or $u$ with the first ciphertext to create the corresponding bitstring $s$.
Validate that guess on $s$ by attempting to decrypt the second ciphertext with it; recovering the corresponding $r'$, $t'$ values.  If $t' = r' \bmod n$, then add $r, r'$ to the list of plausible values.

In the simple example you gave (and depending somewhat on how you encode the numbers as bitstrings), that would give you a list of approximately 100 $r, r'$ values, one of which are the correct one.  It would be possible to list this to only the correct value given 1 or 2 more ciphertexts.

One time pad (where you use the secret bitstring $s$ only once) is safe because, while can reconstruct the possible values of $s$ (based on what the original message might be), you have no way to verify any possible $s$ value.  By reusing $s$, you provide such a way, and thus lose the security guarantees that you have when you use $s$ only once.

It is likely possible to design a more efficient attack method; however that method would likely depend on the details of how you encode an integer as a bitstring


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

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

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

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

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

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


If you ask about the protocol itself, as a theoretical construct, then it is safe. In theory it indeed provides all the feature that it promises.

And now for the "but..." part. When you use a protocol to communicate, you are actually using one implementation of the protocol. The implementation tries to do exactly what the protocol says. However you can never be sure that there are no bugs in the source code.

What i am trying to say is that OTR is definitely not all show. Theoretically it provides everything that it promises, and practically the libotr library (which i think adium uses) is a good implementation of the protocol with active development and security audits (i believe). So it definitely is better than no encryption at all and if you suspect snooping you should definitely use it.

Lastly if you want even more security dont rely only on otr.You must learn how to use crypto properly, use other protocols for anonymisation, obfuscate you traffic etc.


What is the name of an attack where the compromise of one key compromises the whole system?

The whole system depends on the security of one private key (..that gets..) compromised.
  Give a suitable name for such an attack.

I would call this class of attacks: Master key compromise.

Examples of such attacks (as asked in comment) include

The master key is revealed to an attacker by physically stealing a backup copy, bribery or duress (obligatory XKCD) of a holder of the master key. Mitigations use safes, and/or k-out-of-m secret sharing.
The adversary extracts the master key from a device holding it (the most obvious example of that is when the master key is in every device, which is not unseen). Mitigations include using security-certified device at least for master keys (HSMs, SAMs, Smart Cards). Method of extraction include

directly reading the memory/medium that stores the key,
examining memory where the device using the key copies it, perhaps temporarily (e.g. with a debugger, a JTAG port, exploitation of a buffer overflow vulnerability somewhere in the code..)
timing attack, (differential) power analysis and similar side-channel attacks (including fault attacks)

Cryptanalytic attack or/and brute force attack, where a secret key (including private) is inferred from public material, like ciphertext, plaintext made available to an adversary, public key. Mitigation include using larger security parameters for master keys.


Strength of $H(k\|H(m))$ as a MAC algorithm

Should be comparable in strength to $H(m||k)$. The weakness is that a collision in the inner hash breaks the MAC. Using strong hashes the strength in bits is $\min(2^{n_O},2^{{n_I}/2})$ where $n_O$ is the output size of the outer hash and $n_I$ the output size of the inner hash.

But since cryptoanalysis usually breaks collision resistance long before it breaks keyed modes like HMAC, it's riskier than the security loss against generic attacks indicates.


Private Information Retrieval and Writing at the same time possible?

Here's a single-server one: https://link.springer.com/content/pdf/10.1007%2F978-3-642-13708-2_26.pdf

Obviously the data would need to be encrypted, otherwise it will be obvious what was changed, and the PIR-write protocol needs to somehow re-randomize the ciphertexts that were not modified.


See page 17 of the thesis you linked to. There he mentions affine coordinates and homogenization. For your points, $Z=1$. So just set $Z=1$ in your functions above.

  To find the poles, we must remember that as a rational
  function, $Y = Y/1$. Homogenizing, we have $f(X, Y, Z) = Y/Z$. Then to find the poles
  of $f$, we must analyze $Z$ as a polynomial. For all affine points on $E$, $Z = 1$, so $Z = 0$
  only at $\mathcal O$.

Here's more about projective coordinates.

Keep in mind that in general, the sum of two points in projective coordinates having $Z=1$ is not a point with $Z=1$. In this case, the author already did the sums $P_3 + S$ and $P_1 - S$ in affine coordinates.


Running Argon2 (or any other key-stretching KDF) twice to generate two different keys (or other outputs) from the same password is not a good idea, since it makes key derivation twice as slow while not making the password any harder to crack by brute force.  Or, in other words, it makes the password twice as fast to crack compared to just running the KDF once with twice as many iterations.

Hashing the key with a secure cryptographic hash, such as SHA-256, and storing the hash alongside the encrypted data is a perfectly good and secure way to implement a key check value.  You don't even need to store the entire hash; just, say, the first 32 or 64 bits of the hash should be plenty to catch any accidentally mistyped passwords.

Alternatively, you could use the Argon2 output as the input to a fast non-password-based KDF such as HKDF-Expand and use it to derive both the encryption key and a separate check value.  This is a general solution that will work whenever you want to derive multiple quasi-independent keys (or check values etc.) from the same password.  In particular, this method provides a stronger guarantee of independence than your suggestion of hashing the key: not only can the key not be calculated from the check value, but (assuming the the underlying hash function is not very badly broken) the check value also cannot be calculated from the key.


How to select a 'tweak' used in FE1 mode format preserving encryption?

The tweak is a service that the encryption method provides for you.  What it allows you to do is provide context separation for various encryptions using the same key.

Here's the problem that it is trying to help with: suppose you use the same key to encrypt a number of items; for example, suppose you're encrypting all the items in one column of a database with this key.

This leads to an issue: if the data record corresponding to Alice has a 5 in this field, and the one corresponding to Bob also has a 5 in this field, then both records would have the same encrypted value.  Someone looking at the encrypted records won't be able to tell what that common value is, however they know they're the same.  And, if Bob knows what his value is, then he knows what Alice's value is.

One obvious way to handle it is to just use a different key for each record.  That'd work, but that's a lot of keys to handle and store.

The tweak provides an alternative way to handle it; it changes the mapping between plaintext and ciphertext; however (unlike the key) we don't assume that the attacker doesn't know what it is.  In our database example, we might make the tweak the user's name ("Alice" and "Bob"); then, even if Alice's and Bob's encrypted record happen to have the same encrypted value, no one can deduce anything from that (because the mappings from the ciphertext to the plaintext is independent; they might map to the same value, and they might not).

What does this mean for you?  Well, that depends on what you're using FE1 for.  If you are literally encrypting one value with the key, well, you really don't need it - you can set it to a fixed value (say, the empty string).  However, if you are encrypting multiple values with the same key, you might be able to take advantage of it.

One final note: why is this tweak especially important for Format Preserving Encryption?  Well, with standard encryption modes, we add a randomization factor (IVs) during encryption (so that, even if you encrypt the same value twice, we'll pick different IVs), and so the encrypted text would look different.  However, this randomization necessarily makes the ciphertext larger than the plaintext.  With Format Preserving Encryption, we don't have that option; hence we need another way to address this.


How exploitable are cache timing attacks?

An important article from last month on ZDNet shows that cache timing attacks can be very exploitable.

Researchers at Vrije University in Amsterdam announced a new side-channel attack on Intel CPUs called NetCAT.  From the article on ZDNet:

  Named NetCAT, this is a vulnerability in all Intel chips that support
  the Data-Direct I/O Technology (Intel DDIO) and Remote Direct Memory
  Access (RDMA) features.

  When these two features are enabled, academics have shown that they
  can launch an attack on remote, networked computers, and infer certain
  types of data that is being processed inside the CPU's cache.

To emphasize: the attacker does not need physical access to the device.

  VUSec academics have shown that sending carefully crafted network
  packets to a DDIO-capable CPU allows an attacker to keep an eye on
  what else is being processed in the CPU.

In short, NetCAT allows keylogging, and the attacker can even predict the words that will be typed from an SSH session.


Factoring the modulus, by definition, does not uses the public exponent, just the modulus. In fact, it is easy to see that the public exponent has no impact whatsoever on security until it is actually used, e.g. something is decrypted or signed.

For the security of the algorithm (not just the key), it is not known whether a short public exponent induces extra weaknesses. Some people have feared it so, but in fact, for all we know, the shortest possible public exponent ($e = 3$) is as good as any other.

With some details:

All other things being equal, a short public exponent implies better performance of public-key operations (message encryption, signature verification), so that's a good idea.
Some widely deployed implementations of RSA cannot use public exponents which do not fit in 32 bits, so you need, for interoperability, to keep your public exponent short.
A short private exponent may induce trouble. If you want to force the private exponent to be short (and that's a bad idea) then you must allow the public exponent to be big (about as big as the modulus). So this is an argument for a short public exponent: it prevents the private key generation system from doing something tempting (for performance) but stupid (for security).
There is a widespread tradition of using $e = 65537$ and not $e = 3$, because of an old myth about a possible attack which does not actually apply to properly used RSA (see this for some details).

As has been pointed out, two 101-digit primes imply, in bits, a 670-bit or so modulus. It so happens that the current World record for a RSA modulus factorization is for a 768-bit integer -- and it took a lot more than one week (depending on how you look at it, it took between two and four years; and it included some heavy thinking by really smart people). So your bet is quite safe, provided that you did not botch the prime generation. In particular, sentences like this:

  I also tried to make them to be as distinct as possible.

make me fear the worst. The good way to generate the two primes is to generate both of them randomly with, as most as is feasible, uniform generation. A lot of well-intentioned "fixes" like the one you may allude to above can easily turn, in fact, into big weaknesses. You should refrain from that. Randomness is enough.

(Similarly, I hope you used a proper cryptographically strong source of randomness. And, more generally, just use some existing software like OpenSSL: this will be vastly easier and safer.)


How many random bits are required to create one RSA key?

For creating an RSA key pair you need an undefined number of random bytes from the source. The reason for this is that finding primes is indeterministic and hence it may be required that multiple random large numbers are required. In the end this also depends on the details of the key pair generator used.

However, it is possible to use a well seeded DRBG / PRNG for the key pair generation process. A PRNG is a deterministic or pseudo random number generator; it depends on the entropy of the seeds to generate a computationally random stream of bytes. That is: only the seed is truly random, but to an attacker the output of the PRNG is indistinguishable from random.

If a secure PRNG is used then using 256 bits of seed is all you need; for constrained systems you could even bring this down to 128 bits (at the cost of a lower security margin, of course). So if your system has issues generating large amounts of randomness you could seed your own PRNG and inject it into the RSA key pair generator - if that's possible for your runtime.

OAEP is a padding scheme independent on the key pair generation. That is: the calculations performed for key pair generation do not rely on the calculations performed by OAEP. OAEP may be performed on any secure RSA key pair, as many times as required. As per specification it uses hLen random bytes per usage, which means 32 bytes when SHA-256 is used and 64 bytes for SHA-512.


Relative merits of AES ECB and CBC modes for securing data at rest

While I'll try to answer your question at a theoretical level below, I'd like to first stress the following:  It's a bad sign if, in the course of writing software, one is making such low-level decisions about encryption methods.  Encryption security is extremely brittle, with seemingly insignificant details causing complete failure.

With that said, the question brings up some interesting issues with encryption security versus efficiency.

As the other answer notes, ECB reveals when the same block has been enciphered twice and CBC does not (as long as the IV is unique or random).  If you are, for some reason, absolutely sure the same block will never be enciphered, then ECB is in theory fine.  (One technique might be to encipher the blocks in "batches" using a wide-input blockcipher, so that now a ciphertext will repeat only if an entire "batch" repeats.)  But in my opinion this is an unnecessary risk.

Will you ever change blocks of the data once it is written?  This need is one of the distinguishing requirements when dealing with "data at rest" (as opposed to e.g. data being sent over an SSL connection).  ECB, while insecure, will allow you to efficiently change the data in place while CBC will not.  But be aware that the security your are achieving in either case is not ideal.

In general, and especially if local updates are needed, a better technique is to employ a "tweakable block cipher" with the disk location as the tweak.  This will hide repeats amongst different blocks if one uses the block's index (disk location, etc) as the "tweak."  Moreover, it will allow for efficient updates.  This can be combined with the "batching" technique above to provide a level of security that seems pretty strong:  A repeat will only be noticed by an adversary who can watch you change the data, and only when you write the same batch of numbers to the same location twice.  Otherwise the data will be kept private in a strong sense.

It might be help to look at the IEEE 1619 standards documents and associated references for information about tweakable blockciphers and the wide-input batching technique.  The theory outlined there is a long way from a "secure" implementation, and again it seems you probably want to use an existing implementation of this stuff rather than roll own.


First, you're taking the question backwards. Inertia is the default position. You shouldn't be looking for reasons not to switch, but for reasons to switch. If there are no strong reasons to switch, nobody will switch.

Security is not a reason. Between SHA-2 and SHA3, there is no reason to believe that one is more secure than the other. It isn't like when switching from MD5 to SHA-1 or from SHA-1 to SHA-2, where in each case the older function has structural weaknesses that did lead to attacks, and had a smaller output size that was starting to raise concerns over brute-force attacks. SHA-2 and SHA3 have the same sizes and no known structual weaknesses.

Performance is not a reason for most applications. Indeed, performance is a reason not to switch. SHA3 is slower than SHA-2 on a general-purpose processor. It was one of the slowest finalists of the SHA3 competition across various processors. This is not a big reason not to switch, because hashes are pretty much never a bottleneck, but it's certainly not an incentive to switch.

SHA3 does have a performance benefit, which is that it's cheap to implement in specialized hardware. It's very fast on a dedicated circuit. This is especially important for low-power devices: SHA3 costs fewer Joules per byte than SHA-2 (or any other SHA3 finalist) when implemented in hardware. So IoT may drive the adoption of SHA3. However, hardware design takes time, and hardware designers are conservative (you can't fix bugs in hardware), so this won't happen any time soon. Furthermore, a hardware implementation of SHA3 uses more gates than SHA-2, so it costs more to build a SHA3 device, even if it costs less to use afterwards, therefore there isn't a clear cost incentive to switch even when a low power requirement is critical.

SHA3 also has a versatility benefit. The same core primitive (the Keccak sponge) can not only be used as a hash, but also as a MAC (KMAC, at lower cost than HMAC), as a key derivation function (SHAKE with a partially-secret input, at a lower cost than constructions such as HKDF), etc. It's not that SHA3 can do things that nobody else can do, but it can do things that otherwise require more complex combinations of primitives. That's an incentive to switch, but only in circumstances where 1. you need those extra things and 2. it is a problem to combine more code. Again, IoT (which wants low-cost, low-power devices) may look towards SHA3, but only once protocols that use more than SHA3's hash functionality are defined and start being deployed.

Coming back to security, a benefit of SHA3 is that it's very different from SHA-2. Indeed this is one of the main reasons it was chosen over other SHA3 proposals: since its construction is different, if a new class of attacks breaks SHA-2, it's unlikely to apply to SHA3, and vice versa. The security benefit would not be in switching to SHA3, but in deploying software and protocols that support both, so that if a weakness is found in SHA-2, the world can quickly and cheaply transition to SHA3.


Generating a cryptographically secure, many-time use, symmetric encryption key

Short story: Ultimately, your question comes down to a question of the quality of the Windows RNG. Your approach is fine if your RNG is good, but you're trusting the largely opaque Windows RNG to give you a perfect 32 bytes of entropy. I would recommend generating more bytes and then using a hash or KDF to compress it to 32 bytes.

Slightly longer story: All good random keys are generated from the same principle: An $n$ bit key is generated from a source providing $m$ bits of output with $n$ bits of entropy. If the source is high quality entropy output, then at best $n = m$ and the direct output can be used as a key. Otherwise, you would use something like a hash or a KDF to compress the $m$ bits of entropy to an $n$ bit key. Pick a good entropy source, and the random bytes it outputs will be a good key.

In your case, you are using the recommended cryptographic RNG provided by your host OS. This seems like a reasonably secure RNG source, but in general we like to be cautious about these things since there are many practical things that can go wrong. Since Microsoft doesn't publish the details, by default we tend to have more skepticism about it. A series of low entropy bytes might be output, the RNG might be badly constructed and a compromise of our key might lead to a compromise of the system's RNG state and thus future or past keys, and other such problems. To mitigate these failures, generally good practice is to pass RNG output through a hash or KDF before turning it into a key (even if $n = m$).

The Windows CryptGenRandom API is another portal into the Windows RNG, and I would think would work very similarly to the .NET call you referenced. Note that it has been at least in part reverse-engineered and had a few attacks against it, although I don't think low entropy itself is one of them.


Block cipher information leakage using same key

The reason for the 'birthday bound' in block ciphers are collisions that may occur after an expected $2^{n/2}$ blocks (or lack there-of); cases where the inputs to the block cipher is exactly the same (and hence the output is as well).

How might someone, with a large amount of ciphertext, find such collisions in the mode in question?  Having found such a collision, how might they use it to deduce information about the plaintext?


How to represent the point-at-infinity(Elliptic Curves) in code?

I suppose it is a short Weierstrass curve. There are several possibilities:

Projective coordinates: a point $P = (x,y)$ is stored with three coordinates, $X$, $Y$ and $Z$ that satisfy $x=X/Z$ and $y=Y/Z$. We note $P=(X:Y:Z)$. That means a point can have more than one representation (it is the same as fractions, $\frac 3 4$ is the same as $\frac{15}{20}$). The curve equation $y^2 = x^3 + Ax + B$ becomes $Y^2Z = X^3 + AXZ^2 + BZ^3$ and the point at infinity is the point that have $Z=0$, then you can check that $\infty = (0:1:0)$ (or more generally, $(0:\lambda:0)$ for any nonzero $\lambda$).
Jacobian projective coordinates, same as above but with $x=X/Z^2$ and $y=Y/Z^3$ and the infinity point is $(1:1:0)$ or more generally $(\lambda^2 : \lambda^3 : 0)$ for any nonzero $\lambda$.
If you keep only affine coordinates, you can add a boolean is_infinity in you class.

Anyway, depending of how you will implement addition formulas on the curve, you must know that most of them won't work flawlessly with all the points, unless you use complete unified formula (see here for Weierstrass curves).

On a side note, you can take a look at Edwards curves where the infinity point has an affine representation (the Edwards form of Curve25519 or Curve448 are used for the cryptographic primitive signature EdDSA).


How much can I assume hashes to be different for different contents?

All contents whose size is = the hash size will have different hashes (so that if hash(file1) ≠ hash(file2) then hash(hash(file1)) ≠ hash(hash(file2)))?

No, but finding such a value should be impossible for a secure hash.

  All contents smaller that m bits/bytes will have different hashes?

That depends on the value of m. If m = 1 (bit or byte) then it will be true for any secure hash. If m is very large we get back into the situation that there must be identical hashes because of the pigeonhole principle.

  All contents that differ by less than m bits/bytes will have different hashes?

No, because of the pigeonhole principle again. No, but finding a pair of messages that collide should be impossible for a secure hash.

  All contents that differ by less than m consecutive bits/bytes will have different values?

See above.

  Inserting less than m bits/bytes within a content will change its hash?

See above.

  Inserting less than m bits/bytes at the end/beginning of a content will change its hash?

See above.

  Anything else?

Basically it all comes down on the basic properties of secure hash values.

  If there are such assumptions that are true, do they survive the hash being truncated?

In general truncating a secure hash of course limits the security, but it should only harm security by 1 bit for each 2 bits removed (for collision attacks - possibly more for other attacks, but those would have a higher security in to deal with in the first place).

  I guess answers to these questions are very dependent with the chosen hash functions. I’m very interested by answers about hashes of the SHA2 and SHA3 families, but answers about other hash functions (even MD5 and SHA1) are welcome as well.

The answers above are for generic secure hash functions. MD5 / SHA-1 are obviously not considered secure anymore.

Detailing each and every security property of each and every secure hash and testing if it is vulnerable to attacks is way too broad for any answer.


No it is not a good idea as a password cannot be directly used as a key. You would need a PBKDF (password based key derivation function) with a salt and work factor to create a reasonably secure key out of a password. But that leaves us with a problem: you are trying to create exactly such a function - password hashes and PBKDF's are largely synonymous.

If you do not derive a key correctly then the decryption may leak information by which you can retrieve your password even without going through the iterations. If padding oracles apply during decryption in your scheme then the resulting implementation would be very weak, to name just one issue.

The salt does not require confidentiality in PBKDF schemes, so encrypting it should not disallow any attack.


Is allowing both digitalSignature and keyEncipherment certificate usages a bad practice?

The guidance is more about keeping the certificates used for different operations seperate. Not keeping the certificates used for different ways of achieving the same operation seperate.

In the case of different TLS key exchange, the overall operation is still the same, i.e. Generating and exchanging a session key. While technically one method generates a key then sends it, with the other involves signatures they have the same overall lifecycle and consequence if the key linked to the certificate is disclosed.

The general guidance applies more to situations where the operation is different. E.g. With email signing there are two operations, encrypting the email (to prevent it being intercepted) and signing it (to prevent it being forged). As per this answer there are situations where you'd want to disclose the encryption key but not the signing key.

This doesn't apply to the different key exchange algorithms in TLS so the certificate usage is more of a technicality.

Of course if you then used the same certificate to sign something then that would be a terrible security practice.


Generally you should be fine with having a minimum size of 128 bits and a maximum size of 256 bits for parameters such as salts. Although you should halve the security parameter because of the birthday problem, I think most cryptographers would still choose 256 bits salts as maximum.

It is unlikely that the birthday problem can be used to enhance the security beyond the, say 192 bit security it offers after about $2^{64}$ files. So you would have a very large margin with 256 bits. Salts are sometimes even set to 64 bits - for instance in the OpenSSL command line for encryption - but like anything of 64 bits, that may be on the low side by now.

WRT the security of the construction rather than the salt size

Beware that advertising a security strength of 256 bits for password based encryption is rather insincere. Passwords commonly have a security strength far below 64 bits. Even a strong key strengthening function such as scrypt will not add significant strength to this.

Such issues may be partially resolved by using public key encryption where the public key is used for encryption and the private decryption key may be kept in an less accessible location until it is used. That private key may need to be wrapped as well, possibly with a scheme such as specified in the question. OpenPGP is an (old) format that could be described this way.


Multivariate Cryptography: Security of the affine transform T

Almost a year since I posted this question, back then I was starting the study of the field. Now I can answer myself:

The security of both affine transforms $(T,S)$ relies on the IP2 assumption defined in the Isomorphism of Polynomials. Plus, if the private polynomial $\mathcal{F}$ is known there are other implications, like finding $T$ or $S$ would reveal the other affine transform.

This is, any multivariate scheme where $F,S$ or $F,T$ is known gives us the ability to break it. When $F$ is not known, as usually, we could obtain $T\cdot S$ as a matrix if both are linear transform instead of affine, and the linear part of $F$ is the identity matrix. From here nothing else can extracted, from the moment, in my study.

Regarding IP1, it can be broken when $F$ is known, or when $F$ is unknown by quering an oracle $n$ times with the canonical vectors $\overrightarrow{e_i}$.

Besides other techniques to strip out $T,S$ exist, i.e: when the characteristic is not $2$ and both transforms are linear.

There is more work not published in literature that I've discovered, i.e: the special structure of matrices $S$ that make the private polynomial invariant in a way that we can revover $T$, and more techniques that the audience must await for.


Beavers Triple Vs BGW Multiplication on MPC

Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations.

But there are other advantages as well. Define a "linear representation" $[x]$ to be any way of representing/distributing a value $x$ among parties such that the following properties hold:

The adversary's view of $[x]$ is independent of $x$.
Given $[x]$ and $[y]$, it is possible to compute $[x+y]$ via local computations only.
Given $[x]$ and $c$, it is possible to compute $[cx]$ via local computations only.
There is a protocol that opens $[x]$ to reveal $x$, even in the presence of an adversary (can be formulated for any adversarial model).

For example, Shamir secret shares are one possible linear representation, secure against semi-honest adversaries.

If you assume a setup phase in which parties obtain many Beaver triples $[x],[y],[xy]$ on random inputs, as well as many random $[r]$, then you can do MPC in a very straight-forward way.

This recipe for making an MPC protocol is appealing because you just have to define an appropriate linear representation and plug in. This is what SPDZ, MiniMAC, BDOZ, etc., do (plus other optimizations of course).

In particular, these protocols use a linear representation that is secure against a dishonest majority. If you use computational assumptions during the offline phase, then you can in fact generate such Beaver triples. If you just stick to the VSS paradigm then you cannot get security against dishonest majority.

For a good presentation of this MPC paradigm (abstract linear representations + pre-processed Beaver triples), I recommend the video lectures of Claudio Orlandi & Ivan Damgaard from the 2015 Bar-Ilan winter school.


Is there a reference that prove that the AES Key Schedule generate random looking round keys?

Actually, that's remarkably easy to show.  The AES key scheduling logic is invertible:

For AES-128, you can start at any round, take a specific setting for that round key, and invert it to come up with the unique AES key that generates that round key
For AES-192, you can start at any round, take a specific setting for that round key (and 64 bits from the previous or next round), and invert it to come up with the unique AES key that generates those round key bits
For AES-256, you can start at any round, take a specific setting for that round key (and the 128 bits from the previous or next round), and invert it to come up with the unique AES key that generates those round key bits

Because that is a 1:1 mapping because the master key, and the 128/192/256 round key bits, then if the master key is selected uniformly, so must the round key bits be.


How can i check if a public key match with a private key

One method works with any signature scheme and any program including OpenSSL: make a signature of a file with the private key, and check signature and file against the public key.

If the check is OK, then private and public key match (or the signature scheme is broken).

If there is some failure, then private and public key do not match (or the program is misused, incomptible with the key formats, or broken).

Example with openssl, showing Verified OK for matched private/public keys tstpri.pem/tstpub.pem; Verification Failure for unmatched keys altpri.pem/tstpub.pem.

# generate an secp256k1 private key
openssl ecparam -genkey -noout -name secp256k1 -out tstpri.pem
# extract the public key
openssl ec -in tstpri.pem -pubout -out tstpub.pem >/dev/null
# generate an alternate secp256k1 private key
openssl ecparam -genkey -noout -name secp256k1 -out altpri.pem

# create a file fil (any content will do)
echo foo >fil

# sign fil with private key
openssl dgst -sha256 -sign tstpri.pem -out tst.sig fil
# verify the signature with matching public key
openssl dgst -sha256 -verify tstpub.pem -signature tst.sig fil
Verified OK

# sign fil with alternate private key
openssl dgst -sha256 -sign altpri.pem -out tst.sig fil
# verify the signature with non-matching public key
openssl dgst -sha256 -verify tstpub.pem -signature tst.sig fil
Verification Failure


The fields are shades of grey encoded:

The legend right above the Figure description.


Difference between RFC-5869 (HKDF) and SP800-108 (Nist's HMAC-based KDF spec)?

RFC-5869 is about the "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)", while NIST SP-800-108 gives "Recommendation for Key Derivation
Using Pseudorandom Functions". The main difference between Extract-and-Expand KDFs and KDFs based on PRFs are the requirements on the input keying material.

A PRF requires a uniform random key, which implies that the key must have a high entropy. So, in case of the NIST SP-800-108 versions of HMAC based KDFs it is assumed that you provide a random key at the beginning.

The HKDF scheme from RFC-5869 (and also NIST SP-800-56c) was originally proposed by Hugo Krawczyk in [1] as extract-then-expand KDF. As the name suggests, the function works in two steps. First, a key for key-derivation is extracted from the input keying material and a salt. The next step is essentially what SP-800-108 defines: use an HMAC (i.e. PRF based) KDF to derive further keys. The difference between SP-800-108 and RFC-5869 is the randomness extraction. With an extract-then-expand KDF you can use for example a shared secret to derive cryptographic keys and you must not provide a random key as input.

[1]. Hugo Krawczyk, "Cryptographic Extraction and Key Derivation:
The HKDF Scheme", 2010, https://eprint.iacr.org/2010/264


Is there any examples of information-theoretic secure MPC for dishonest majority against malicious adversary?

What you are asking for is not possible, not even if you ask for passive security. Here is a sketch of a proof.
Suppose for sake of contradiction you have an $n$-party MPC protocol $\Pi$ for $f(x_1, \ldots, x_n) = x_1 \land x_n$, where the $x_i$'s are bits. This protocol is secure against a computationally unbounded adversary who can passively corrupt $\ge n/2$ parties.
You can take this $n$-party protocol $\Pi$ and construct a related 2-party protocol $\Pi^*$. Player 1 in $\Pi^*$ plays the role of parties 1 through $n/2$ in $\Pi$, and Player 2 in $\Pi^*$ plays the role of parties $n/2+1$ through $n$ in $\Pi$. So $\Pi^*$ is a 2 party protocol that takes input $x_1$ for Party 1 and $x_n$ for Party 2 and computes $x_1 \land x_n$.
The 2-party protocol $\Pi^*$ is secure against 1 corrupt party. Corrupting 1 party in $\Pi^*$ is like simultaneously corrupting $n/2$ parties in $\Pi$, and by our assumption $\Pi$ is secure in that scenario.
So now we have a 2-party protocol $\Pi^*$ for securely computing the AND of two bits, which is secure against a passive, computationally unbounded adversary (who corrupts 1 party). But this is known to be impossible. If you're asking about perfect security, it was proven in:

Kushilevitz: Privacy and Communication Complexity

The proof was later generalized to statistical security in:

Maji, Prabhakaran, Rosulek: Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation, section 4


What are the differences between collision attack and birthday attack?

Collision attacks are attacks where success is obtained when two values obtained by some process are identical. The term is often used in the context of hashes, since collision-resistance is one of their desirable property.

Birthday attacks are collision attacks that work by the effect of chance, with the colliding values obtained by some roughly random process (as in the birthday problem).

Marc Stevens's Single-block collision for MD5 (2012) is an example of collision attack that is not a birthday attack.


Unbalanced numeric Feistel network implementation

Does the implementation follow accurately the described network generalization?

No. The Feistel network analyzed in the paper assumes independent round functions, but the code does not give that.
The issue is where the code reads random.seed(input + key + round). The corresponding pseudocode either has the same issue, or is at at least ambiguous with
$$\text{return }\mathit{hash}(\mathit{data}+\mathit{key}+\mathit{round})$$
when perhaps it means
$$\text{return }\mathit{hash}(\widehat{\mathit{data}}\mathbin\|\widehat{\mathit{key}}\mathbin\|\widehat{\mathit{round}})$$
where $\widehat x$ is a representation of integer $x$ per (say) big-endian binary, over a fixed-width bitstring chosen large enough for the maximum possible value.
If we use the same hash at each round, it is desirable that the input of $\mathit{hash}$ is unique for any triple $(\mathit{data},\mathit{key},\mathit{round})$. We can do this with just numbers, as
$$\text{return }\mathit{hash}(\mathit{data}+(\mathit{key}\cdot\mathit{nbrounds}+\mathit{round})\cdot\mathit{second})$$
Problem with the current proposition is: there is very little difference in the round functions for the different rounds. For a fixed $\mathit{key}$, if we note $F$ the function $x\mapsto\mathit{hash}(\mathit{key}+x)$, then the Feistel round function $F_i$ at round $i$ is $x\mapsto F_i(x)=F(i+x)$, which is very far from independent functions.
This is a good context for slide attack when $\mathit{first}=\mathit{second}$ and these are small (that is, $2^\mathit{first}$ is enumerable). At least a related-key attack works: no mater how many rounds, we can query two black boxes that implement the cipher and tell if they have their keys offset by one or not. And because the round function's result is added, which is associative with the $i+x$ operation at the input of $F$, I think it extends to a distinguishing attack in the single random key setup; perhaps even a way to tabulate the $F$ function and recover the functional equivalent of the key in sizably less than $4^\mathit{first}$ queries.

Is there any way of reversing the modulus addition ⊞ on the encryption function other than by using modulus subtraction ⊟ on the decryption function?

I see nothing simpler that works.

What would be the security implications of dynamically computing $\mathit{first}$ and $\mathit{second}$ as the $\mathit{first}\cdot\mathit{second}$ finite field is strictly equal to the input $\mathit{data}$?

As is, with $\mathit{data}$ the input block, that's not functional. This would mean the maximum value of the ciphertext is $\mathit{data}$. Thus, by induction, either the cipher is identity (which it won't be in all likelyhood), or it is not injective thus is not decipherable.
Therefore, we can't do without at least another input, which is the $\mathit{top}$ of the range $[0,\mathit{top})$ for $\mathit{data}$. And then we have a serious problem when $\mathit{top}$ is prime.
In Format Preserving Encryption (the academic name of what the question studies), one standard solution to this is cycle walking, which essentially increases $\mathit{top}$ a little until finding $\mathit{top'}=\mathit{first}\cdot\mathit{second}$ with $\min(\mathit{first},\mathit{second})$ above some reasonableness thresold, then fixes encryption by encrypting again when the ciphertext is in range $[\mathit{top},\mathit{top'})$. That's compensated at decryption by decrypting again when the decrypted plaintext is in range $[\mathit{top},\mathit{top'})$.

I have not touched side channel attacks, which are heavily language-dependent anyway.


The (CCA-related) problem of this padding scheme is that it lacks a failure condition, i.e. a ciphertext which a decryption oracle will refuse to decrypt.

Now first for the chosen ciphertext attack which exploits RSA's homomorphic property. Assume you want to decrypt a ciphertext $c$ that is the encryption of $m$ which is encrypted properly according to the above procedure. Assume further you have a decryption oracle which won't decrypt $c$ itself.

First you chose a random integer $1<k<N$ yourself. Next you compute $c'=k^e\cdot c \bmod N$. You send $c'$ (which clearly isn't $c$) to the decryption oracle and get $m'$ in return. You compute $(r||m)=m'\cdot k^{-1} \bmod N$ and unpad the result as in the original decryption procedure.

As was noted by poncho in the comments of this answer, my above attack assumes, that the decryption oracle will give you the full message back and not just the lower $l(n)$ bits.

To fix this we'll apply an attack I like to call "hard-core predicate attack". It bases on the fact (as can be found in Katz' and Lindell's Introduction to modern Cryptography) that the least significant bit of a RSA encrypted message is a hard-core predicate. In the book the authors outline an attack to recover a full RSA message, given only an oracle that tells them whether the message corresponding to the queried ciphertext is even. Using this method we can recover the full blinded message $m'$ using polynomially many decryption queries and afterwards proceed with the above attack. For simplicity of the description I'll assume the decryption oracle only yields the least significant bit.

First, we determine whether the current least significant bit of $m$ is $0$.
If yes, then we know the least significant bit and multiply the ciphertext with $2^{-e}\bmod N$ (which shifts the message to the right by one bit) and continue from the start.
If no, then we know the least significant bit and multiply the ciphertext with $2^{-e}\bmod N$, the second least significant bit is then the negated XOR of the least significant bit of the new ciphertext and the second least significant bit of the modulus.


Why Stream Ciphers can be slower in software than Block Ciphers

Almost everything depends on the hardware platform the algorithm is implemented for and specifics of the implementation.
So really one cannot say "algorithm x is faster than y" without referring to the specific hardware platform.
For example, this page https://bearssl.org/speed.html contains a couple of benchmarks. Taking amd64 as the platform, if we have no AES-NI acceleration, Chacha20 beats AES-128-CTR. However, if we do have AES-NI, the situation reverses and AES-128-CTR is a couple of times faster than Chacha20.

If you want to test various algorithm implementations on your machine, you can play e.g. with openssl benchmarking tool

openssl speed -evp aes-128-ctr
openssl speed -evp chacha20-poly1305


Description of signatures with message recovery (as in ISO/IEC 9796-2 and EMV Signatures)

Informally, a signature scheme with message recovery is one where some or all of the message is embedded in the signature. That can reduce the size of the signed message, sometime by a proportion approaching 2, e.g. for RSA public-key certificates.
Common practice: Signature scheme with appendix

Space saver: Signature scheme with total message recovery

Best of both worlds: Signature scheme with partial message recovery

$$\begin{array}{ll}
\mathsf{Gen},\mathsf{Sign},\mathsf{Ver}&\text{Key generation, signature, verification algorithms.}\\
\operatorname{Pub}, \operatorname{Priv}&\text{Public and private keys (bitsrings).}\\
M_r&\text{‘Recoverable’ message.}\\
M'_r&\text{‘Recovered’ message, equal to }M_r\text{ on successful verification.}\\
M_n&\text{‘Non-recoverable’ message, equivalently ‘clear’ or ‘visible’.}\\
S&\text{Signature.}\\
\end{array}$$
A signature scheme with total message recovery [some sources make total implicit, e.g. the HAC section 11.2.3] can be formally defined as three functions [easily computable, with a compact and public definition]:

a key generation function

with inputs

some parameters (in particular for key size)
a random bitstring,

with output a public/private key pair $(K_\text{pub},K_\text{priv})$,

a signature function $\mathcal S$

with inputs

same parameters
$K_\text{priv}$ obtained from the output of the key generation function
any message $M$ in some large subset $\mathbb M$ of the set of bitstrings $\{0,1\}^*$
an (optional) random bitstring [that is used in ISO/IEC 9796-2 scheme 2]

with output a bitstring designated as the signed message $S=\mathcal S_{K_\text{priv}}(M)$,

a verification function $\mathcal V$

with inputs

same parameters
$K_\text{pub}$ obtained from the output of the key generation function
any bitstring $S\in\{0,1\}^*$

with output a pair $(b,M)=\mathcal V_{K_\text{pub}}(S)$ with

$b$ a boolean, either $\text{false}$ [bad signature] or $\text{true}$ [good signature]
a bitstring $M$

such that for all parameters and random seed(s), $\forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M))=(\text{true},M)$.
A signature scheme with total message recovery is defined to be existentially secure [or equivalently: secure in a chosen-messages setup] if a computationally bounded adversary, given $K_\text{pub}$ and access to an oracle producing $S_{K_\text{priv}}(M)$ when given any $M\in\mathbb M$, can not with sizable odds exhibit $S\in\{0,1\}^*$ with $V_{K_\text{pub}}(S)=(\text{true},M)$, and such that the oracle was not queried with $M$.
Notice that in a signature scheme with total message recovery, $M$ is an output of the message verification function; when it is an input in a signature scheme with appendix. Recovering $M$ from the signed message $S$ requires evaluating $\mathcal V_{K_\text{pub}}(S)$, and in particular knowledge of $K_\text{pub}$.

For $k$-bit security, the size of signature and message must obey $|M|\le|S|-k$ (for odds of success of a trivial adversary not querying the oracle and trying $S$ at random are at least $2^{|M|-|S|}$, assuming $|S|$ is fixed for a given $|M|$ and all messages of size $|M|$ can be signed).
Some schemes also offer partial message recovery : signature generation breaks the message $M$ into $M_r$ and $M_n$ in a public, scheme-defined manner, with $|M|=|M_r|+|M_n|$; it is assumed that $M_n$ [the non-recoverable part] is made an additional input of the signature verification function (as in signature with appendix); while $M_r$ [the recoverable part] replaces $M$ in the output of the verification function, which becomes $(b,M_r)$.
The correctness requirement becomes that for all parameters and random seed(s), $\forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M),M_n)=(\text{true},M_r)$, where $M_r$ and $M_n$ are extracted from $M$ in a prescribed manner, and can be recombined into $M$.
The security requirement becomes that a computationally bounded adversary, given $K_\text{pub}$ and access to an oracle producing $S_{K_\text{priv}}(M)$ when given any $M\in\mathbb M$, can not with sizable odds exhibit $M_n$ and $S\in\{0,1\}^*$ with $V_{K_\text{pub}}(S,M_n)=(\text{true},M_r)$, and such that the oracle was not queried with $M$ obtained by recombining $M_r$ and $M_n$.
Typically, $|S|$ is fixed for a given public key, but independent of $|M|$; and $|M_n|=0$ for $|M|$ below some threshold. For $k$-bit security, $|M_r|\le|S|-k$ must hold, or equivalently $|M_n|\ge|M|-|S|+k$

The first standard message scheme with message recovery was ISO/IEC 9796:1991 [later renamed ISO/IEC 9796-1, but never approved under this name]. It did not use a hash, because standard hashes where then a novelty. It featured only total message recovery, and had the constraint $|M|\le|S|/2$ (within a few bits). It was broken in a chosen-messages setup [first within 1 bit; then fully but with many messages; then with another attack that obtains the signature of $k$ extra messages from that of $k+2$ chosen other messages for most practical arguments]; and was withdrawn in 2000.
The second standard message scheme was ISO/IEC 9796-2:1997, now known as scheme 1 of ISO/IEC 9796-2. It improves on ISO/IEC 9796:1991 by using a hash, which allows a more compact signed message, and partial message recovery. Scheme 1 of ISO/IEC 9796-2 was broken in a chosen-messages setup [the best known attack is that in the paper (alternate link) noted in the question], but remains secure in practice when the adversary is restricted to obtaining signature of messages not specifically constructed to enable an attack. ISO/IEC 9796-2:2002 enforced a minimum hash width of $h=160$ as a mitigating measure, added schemes 2 and 3 intended to fix security for good, defined the so-called alternative signature production and opening functions that practice demanded, and included as normative the previously informative non-alternative signature production and opening functions. Amendment 1:2008 to ISO/IEC 9796-2:2002 added an ASN.1 module. ISO/IEC 9796-2:2010 makes only purely editorial changes AFAIK, beyond consolidating that amendment.
In ISO/IEC 9796-2, the message $M$ to be signed is subdivided as $M=M_r\|M_n$. The recoverable part $M_r$ is at the beginning of the message, of some maximum size determined by the parameters; it is transmitted embedded into the signature $S$, which has size fixed by public key parameters. The non-recoverable part $M_n$ is empty for short $M$ [and always a byte-string even when $M$ is not, thus $|M_r|\equiv|M|\pmod 8$]; $M_n$ is often transmitted unmodified along the signed message, but could be implicit in whole or in part (e.g. a version number). When $M_n$ is empty [resp. non-empty], the scheme operates in total [resp. partial] recovery mode.
Scheme 1 of ISO/IEC 9796-2 is deterministic. For signature, a message representative is formed by concatenating prescribed padding, $M_r$, the hash of the whole message $M$, and other prescribed padding; the underlying [RSA-like] private-key function is then applied to obtain the signature, which is about the size of the public modulus. For verification of the signature and message recovery, after preliminary checks, the underlying public-key function is applied; the padding in that result is checked; the recovered $M_r$ is extracted from that result; and the hash extracted from that result is compared to the hash of the message reconstructed from the recovered $M_r$ and, for partial message recovery, the non-recovered $M_n$ obtained by other means.
I refer to EMV 4.3, Book 2, Annex A2.1, for a detailed exposition of ISO/IEC 9796-2 scheme 1, restricted to $n\equiv m\equiv 0\pmod 8$, SHA-1 (thus $h=160$), implicit hash identifier, $m\gt n+176$ [that is partial message recovery], and the so-called alternative signature production and opening functions RSASP1 and RSAVP1 in PKCS#1. This parameterization is common in Smart Cards, and directly supported [including with total message recovery] by Java Card 2.2.x/Classic.
Scheme 2 of ISO/IEC 9796-2 is randomized [and correspondingly has the signed message larger than scheme 1 in many use cases], with a security argument resembling that of RSASSA-PSS of PKCS#1, applicable including in a chosen-messages setup. Scheme 3 is a special case of scheme 2 with the random bitstring reduced to empty. The split of message into recoverable and non-recoverable portions is such that scheme 3 can be used as functional equivalent to scheme 1 with restored security in a chosen-messages setup [although I know no formal security argument].
Assuming an $n$-bit public modulus, when sending an $m$-bit message and its signature, the signed message of ISO/IEC 9796-2 schemes 1 or 3 has about $\min(n,m+h+16)$ bits where $h$ is the width of a hash [SHA-1 is popular, giving $h=160$]. This allows a significant [at least when considering proportion] size saving for messages with $m$ commensurate to $n$, such as public-key certificates [compare to $m+n$ bits using the schemes in PKCS#1]. For example: with $n=1984$, $h=160$, $m=2000$ [250 bytes], the signed message may use $2176$ bits [272 bytes, rather than 498 bytes with PKCS#1]: $1984$ bits [248 bytes] for the RSA cryptogram, conveying $1808$ useful bits [226 bytes] forming the recoverable part of the message; and $192$ bits [24 bytes] forming the non-recoverable part of the message.
ISO/IEC 9796-2 has a maze of features and parameters: three schemes; many hashes; optional hash identifier [intended to allow interoperability in contexts where the signer decides which hash is used, without requiring guesswork on the verifier side]; modulus of size not multiple of 8; messages of size not multiple of 8 when the hash allows; total or partial message recovery; either RSA or Rabin signature scheme [an analog with even public exponent]; and two slightly different options of RSA signature production and opening functions: those not designated as alternative sign as $x\mapsto \min(x^d\bmod N, N-(x^d\bmod N))$ which saves one bit over the alternative: PKCS#1's RSASP1. EMV originally referred to ISO/IEC 9796-2:1997, but only uses partial message recovery, the alternative functions not alluded to in this standard, and now refers to ISO/IEC 9796-2:2010 without stating the scheme, functions, or other options. The European Digital Tachograph [annex 1B, appendix 11] does just as EMV when it refers to ISO/IEC 9796-2 in a signature context for certificates, but also refers to ISO/IEC 9796-2 in its authentication and key agreement scheme where it uses scheme 1 with total message recovery [thus different padding than EMV] and the non-alternative signature production and opening functions of that standard [because that enables re-encryption of the signature using a different private key with the same modulus size as the signature key, regardless of which modulus is smaller].
ISO/IEC 9796:1991, ISO/IEC 9796-2, and EMSR3 of P1363a (similar to ISO/IEC 9796-2) use RSA or Rabin as the underlying public-key cryposystem. There's also ISO/IEC 9796-3, the similar EMSR1, and EMSR2, that use the Discrete Logarithm (possibly over an Elliptic Curve group).

Regarding the note in ISO/IEC 9796-2:2010 quoted in that comment to the question:

For practical purposes, an application may wish to structure the message $M$ to ensure that data it wants to be explicitly stored or transmitted (e.g., address information) is allocated to the non-recoverable message part $M_n$

That's intended to draw attention to the fact that only the non-recoverable part of the signed message [if any] is intelligible before verification of the signature. As a consequence, information that needs to be readily available before or absent signature verification is better placed in that non-recoverable part of the message, rather than in the recoverable part.
As a real-life illustration: contrary to the recommendation in this note, in the aforementioned European Digital Tachograph specification, the message in a certificate [defined by Annex 1B, appendix 11, 3.3.1 CSM_017] has the identification [designated CAR] of the public key of the authority that produced that certificate placed near the beginning, thus in the recoverable part of the message, thus unintelligible before signature verification, which can be a problem to decide which public key is appropriate to verify that certificate, absent context. To avoid this, a copy of CAR, designated X.CAR, was appended at the end of the signed certificate [defined in 3.3.2 CSM_018], allowing not reading the certification authority's certificate if it is already known and its public key cached, and giving a chance to know what allegedly generated a certificate even if it fails to verify. That complication increases the certificate size by 8 bytes, and creates confusion about if an hypothetical certificate with its X.CAR not matching CAR is deemed valid, and what/who is deemed to have generated it; that could have been avoided if CAR had been at the end of the certificate data, thus in the non-recoverable portion.


Question about modular arithmetic (division)

The answer depends on how $n$ is chosen.

If $n$ is coprime with each of the $y_j$ (including if $n$ is prime and all the $y_j$ are in range $[1..n[$), and $x_1\bmod n$ is uniformly random on $[0..n[$ (including if $x_1$ is uniformly random on that interval, or on a much larger interval), then demonstrably, Bob can not determine what $y_i$ Alice has picked by examination of $X\;=\;x_1*y_i\bmod n$. Proof sketch: the application $F_i:x_1\to X$ is a permutation of $[0..n[$; therefore $X$ is uniformly random on $[0..n[$, regardless of $y_i$; thus $X$ can't leak information about $y_i$.

However, if $n$ is the product of all the $y_i$ and these are distinct moderate primes, then Bob can find with fair odds which $y_i$ was chosen: $X$ is divisible by that $y_i$, and only those few (perhaps no) other $y_j$ that divide $X$.

There are gradations between theses two extremes.


Shamir Secret Sharing - Threshold decryption implementation

The index $i$ is running through the $n$ possible participants (1=Alice, 2=Bob, 3=Charlie, 4=Dave, and 5=Eve). Now to be able to easily refer to the $t$ out of $n$ persons — required by the threshold scheme — the index $i_j$ is used: $i_1$ is the first of the $t$ people taking part to the decryption, $i_2$ is the second, ..., $i_t$ is the $t$-th. (If Alice, Bob, and Charlie decrypt, this will be $i_1=1$, $i_2=2$, and $i_3=3$; if Alice, Dave, and Eve decrypt one will have $i_1=1$, $i_2=4$, and $i_3=5$.)

Now there is obviously a typo in you book as $\mu_2=\mu_1^{-1}\pmod p$ and not $\mu_1{-1}\pmod p$.

Additionally, I believe the computation of $c_{i_j}$ given in your book is incorrect: instead $\displaystyle\prod {i_k\over i_k -i_j}$ you should read the public values $\displaystyle\prod {x_{i_k}\over x_{i_k} -x_{i_j}}$ where the values $x_l$ are the public elements defining the polynomial $f$ of the secret sharing scheme.

Hence, read the source instead. The implementation given in the paper is also more efficient as it does not require any inversion mod $p$.

(For the last bit of your question, I assume you were referring to a product not a sum. And yes, you can mod $q$ whenever you want, but it's probably more efficient to keep things as small as possible.)