When cryptographers create algorithms, they usually provide some argument that the algorithm is secure. They need to start the argument with some set of assumptions. For example, the in public-key cryptography, they may begin with the assumption that factoring large numbers is hard.

Many algorithms use use a block cipher as a building block. The arguments that these algorithms are secure need to make some (mathematical) assumption about the block cipher in question in order to get started. Normally, the assumption goes something like this: "If the encryption key is chosen at random, then an attacker who does not know the key cannot distinguish between the block cipher and a truly random permutation, even using a chosen-plaintext attack." (This is an informal statement of the pseudo-random permutation [PRP] assumption.)

But the PRP assumption isn't always applicable. Sometimes block ciphers are used in ways where the key is either not random or not secret (we'll see an example in a bit). In these cases, we need to make some other assumption about the block cipher's security properties.

What is the ideal cipher model?
This is where the ideal cipher model comes into play. In the ideal cipher model, we just pretend the block cipher is a random permutation for every key. Furthermore, we treat these permutations as independent. We assume that if an attacker wants to know what happens when a block is encrypted under a given key, he has to go to the work of computing it himself. He can't infer anything about the output by encrypting other blocks, or the same block under a different key.  (Exception: Given a fixed key, no two inputs will produce the same output. So the attacker can rule out that possibility, but that's it.)

Example: the Davies-Meyer Compression function. Some hash functions, such as MD5, SHA-1, and SHA-2, are examples of Merkle-Damgard constructions. Let's say we'd like to find an argument that Merkle-Damgard constructions are collision-resistant. They look like this (IV is a constant, and Hash is the output):

The function $f$ above is a compression function. Now, it's possible to show that if $f$ is secure, then so is the hash function. But we can go a bit deeper using the ideal cipher model. For MD5, SHA-1, and SHA-2, $f$ is built out of a block cipher $E$ using a so-called Davies-Meyer construction (each of these three hash functions uses a different block cipher):

$f(\mathrm{M}, H) = E_{M}(H) \oplus H,$

where $M$ is the message block and $H$ is other input (the chaining value). So $M$ is being used as the key, but if someone is trying to find a collision for MD5, then each message block $M$ is under his control. It is neither random nor secret. So we can't use the PRP assumption.

But we can model $E$ as an ideal cipher. Using this assumption, we can show, for example, that no one could find a collision for MD5 or SHA2 without doing an insane amount of work (or getting really, really, lucky).

But wait! We can find collisions for MD5! So what went wrong? Well, the ideal cipher model is just a heuristic. Block ciphers must be describable using simple algorithms --- we can't generate and store random tables listing every output under every key, these tables would be huge. This makes it inevitable that there's some mathematical relationship between different outputs and different keys.

When is it appropriate to use the ideal cipher model? Because the ideal cipher model is a heuristic way of modeling block ciphers, rather than an assumption that could plausibly be true in a technical sense, it should be avoided whenever possible. But sometimes, notably in hash functions that don't have a random secret key, it's our only option.

How do I tell when a block cipher can reasonably be modeled using the ideal cipher model? It's better to ask if the block cipher is being used in a way that requires the ideal cipher model (as opposed to a PRP assumption). Next, look at how the block cipher is being used. In MD5 and SHA1, SHA2, for example, the block cipher is buried inside of the compression function, and the attacker doesn't have complete control over the inputs to this function. Since the attacker is a couple steps removed from the actual block cipher, using the ideal cipher model becomes a bit more reasonable because it may be harder for the attacker to exploit the block cipher's weaknesses. Ultimately, the best test is the test of time.

That being said, certain common ways of constructing block ciphers have been proven to result in constructions that are indifferentiable from an ideal cipher... but these proofs make heuristic assumptions about the internals of the block cipher. So although these proofs are interesting from an academic perspective, it's not clear how much they contribute to trusting a real-world block cipher in the ideal cipher model.


Recommended authenticated stream cipher for minimum overhead?

There aren't any known attacks on the PRFness of HMAC-SHA256 better than brute force.

(So you can truncate that MAC to length L where $\:\:\frac1{2^L}+\epsilon\:\:$ is an acceptable risk of forgery.)

To reduce the impact of a forgery without making the ciphertext any longer, one should use a
format-preserving encryption (FPE) scheme that is secure against one query to the encryption

oracle and one query to the decryption oracle, which are not necessarily made in that order. $\;\;\;$

Choose either $\; [b_{client} = 0 \: \text{ and } \: b_{server} = 1] \:$ or $ \: [b_{client} = 1 \: \text{ and } \: b_{server} = 0] \;$.

Let $\;\; \operatorname{pL} \: : \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \: \to \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \;\;$ be an injective function that can be inverted

efficiently enough. $\;\;\;\;$ For the sentence two after this one to be possible, you will also need that

for all $m$, $\: m\leq \operatorname{pL}(m) \:\:$. $\;\;\;\;$ Let $\;\; \operatorname{rL} \: : \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \: \to \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \;\;$ be a function that

can be computed efficiently enough. $\;\;\;\;$ Let $\;\; \operatorname{pad}_{\hspace{.01 in}m}\hspace{-0.01 in} \: : \: \{0,\hspace{-0.03 in}1\}^m \hspace{-0.01 in} \times \{0,\hspace{-0.03 in}1\}^{\operatorname{rL}(m)} \: \to \: \{0,\hspace{-0.03 in}1\}^{\operatorname{pL}(m)}$

be a sequence of injective functions that can be computed efficiently enough and satisfies

$[message$ can be efficiently computed from $\:\operatorname{pad}_{\operatorname{length}(message)}\hspace{-0.02 in}(message,\hspace{-0.02 in}randomness)]$.

$\operatorname{unpad}_{\operatorname{length}(message)}\hspace{-0.02 in}(\operatorname{pad}(message,\hspace{-0.02 in}randomness)) \: = \: message$

For all other values of $x$, $\;\; \operatorname{unpad}(x) \: = \hspace{.08 in} \perp \;\;\;$.

$\operatorname{Enc}(key,party,packetnumber,plaintext,randomness)$
$=$
$\operatorname{FPEencrypt}(\operatorname{HMAC}(key,b_{party}||\hspace{.02 in}packetnumber),\operatorname{pad}(plaintext,randomness))$

$\operatorname{Dec}(key,party,packetnumber,ciphertext)$
$=$
$\operatorname{unpad}(\operatorname{FPEdecrypt}(\operatorname{HMAC}(key,(1-b_{party})||\hspace{.02 in}packetnumber),ciphertext))$

As long as each party only encrypts and decrypts once each for each $packetnumber$, a feasible adversary will have probability $\:\: \frac1{2^{\operatorname{pL}(m)-(m+\operatorname{rL}(m))}}+\epsilon\:\:$ of violating integrity for each submitted ciphertext

of length $\operatorname{pL}(m) \:$ (and a ciphertext whose length is not in $\:\operatorname{range}(\operatorname{pL})\;$ will always decrypt to $\perp$).

  Furthermore, if the parameters are such that that probability is noticeable, then the decryptions

  of ciphertexts with length $\operatorname{pL}(m)$ that violate integrity will be computationally indistinguishable

  from independent samples from the following distributions for each such ciphertext:

  if the indicated $party$ did not output a ciphertext for that $packetnumber$, then uniform on $\{0,\hspace{-0.03 in}1\}^m$

  else, the plaintext used by $party$ for that $packetnum$ with probability $\frac{2^{\operatorname{rL}(m)}-1}{2^{m+\operatorname{rL}(m)}-1}$,

  and each other member of $\{0,\hspace{-0.03 in}1\}^m$ with probability $\; \frac{2^{\operatorname{rL}(m)}}{2^{m+\operatorname{rL}(m)}-1} \:\:$.


How to encrypt the number one using RSA?

The algorithm you quote is usually called textbook RSA and is not used in practice for numerous security reasons (the problem you pointed out, is just one of them).

In practice, you have to pad (or armor) your message. This should be done using the RSA-OAEP (also called PKCS#1 v2.0) scheme. It transforms your message (1) into a pseudorandom block (not 1) which is then processed by the RSA encryption.


Have I made any glaring mistakes in my use of Yao's garbled circuits?

Unfortunately, the answer to your question is yes. You have made glaring mistakes. In particular, Yao's garbled circuits are suited for two-party computation only, and here you wish to carry out a multiparty computation. One huge problem that arises with your entire approach is that if the server colludes with one of the voters, then they can learn the inputs of all of the parties. (I haven't looked at all the fine details of the way you propose working, since this inherent problem arises at the onset.)

There is a protocol that generalizes Yao garbled circuits to the multiparty setting; it is called BMR. However, it is less mature and harder to implement.

If you wish to do a simple voting protocol with people voting just for and against, and you wish to just know how many voted in favor, then using an additively homomorphic encryption scheme like Paillier is the way to go. However, like everything in cryptography, it is very hard to get this right if you try to design it yourself. You should look at papers on voting protocols and then choose one of them to implement.

Alternatively, if it's for a school project, then think of a two-party application that is interesting and use garbled circuits.


Does there exist a mode of operation that forces mac-then-decrypt?

There is a type of AEAD construction, exemplified for example by the CAESAR candidate AEZ, which splits up into two components:

An enciphering scheme: "an object that is like a conventional blockcipher except that the plaintext’s length is arbitrary and variable, and, additionally, there’s a tweak" (p. 1).
An encode-then-encipher mode that enciphers the concatenation of a plaintext with a fixed number of zeroes (or some other alternatives).  On decryption, the authenticity check verifies that these final bits deciphered to zero.

The key thing is that in the enciphering scheme, a change to any bit of the ciphertext (or plaintext respectively) has a 50% chance of affecting every bit of the plaintext (or ciphertext respectively).  So attempts to modify a ciphertext will yield garbled plaintexts, and those garbled plaintexts will be safe to reveal.


Verify that a point belongs to secp256r1

An Elliptic curve defined over the finite Field $\mathbb F_p$ means that all of the coordinates are elements of $\mathbb F_p$, i.e. in affine coordinates, let $P=(x,y)$ be a point then $x,y \in \mathbb F_p$. Actually, all of the arithmetic is done over $\mathbb F_p$
In the encoding
04 11 95 23 03 f0 f1 f1 45 67 14 98 e4 39 80 ce 25 39 02 6e 72 34 fe 02 38 8a ea cc fb 3a 3d 4d dc d9 6d 3c fe 8b 55 bf ea c3 3a a1 59 13 54 b3 91 79 45 b7 3b 49 d9 0e 96 2a de 79 d3 49 dc 79 ca
The first byte defines the compression and 04 means there is no compression. So, after removing the 04, the first half belongs to $x$ and the second half belongs to $y$ coordinate of the point.
You forgot to take $\bmod p$.
With testing equality of both sides
#Sagemath
x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

print(y^2 % p)
print( (x^3 + a * x + b) % p )
#or test with assert
assert(y^2 % p == (x^3 + a * x + b) % p)

outputs
107039974491263683037557989129009082794410266580376414531485756411379666775575
107039974491263683037557989129009082794410266580376414531485756411379666775575

Therefore it is a valid point on the curve.
Using Curves on SageMath
There is another way, and maybe easier on the SageMath. This method uses the Elliptic Curve construction and defining point on the curve.
#secp256r1
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

K = GF(p)
E = EllipticCurve(K,[a,b])

x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")

P = E(x,y) ### try to set the point with the coordinates.

If the $P$ is not a point on the curve, you will get many errors
Further notes
In the next steps, you may want to add/double points. Elliptic curve uses special formulas for point addition. You may found them here, or use directly Sagemath, you can just use addition for point additions P+Q and 5*P  for scalar multiplication where it is usually written as $[5]P = P + P + P + P +P$


Can you explain what the AES paper means by "sharing active S-boxes"?

We talk about cryptanalytic tools here. A differential trail  describes how a certain difference evolutes throughout the cipher, which helps to find out a key in a standard differential cryptanalysis. Each trail activates certain non-linear operations (S-boxes), which contribute to its probability (a difference goes through a nonlinear operation probabilistically).

The biclique key search method works with a pair of such trails in a small part of the cipher. For the method to work, these trails must activate non-interleaving groups of S-boxes, otherwise more sophisticated conditions come into play.


Is prime order group used in ECDSA unique?

This question has two faces;

The number of rational points of the used curve is prime like secp256r1, i.e. $\#C(K) = p$ where $K$ is the field where curve $C$ is defined;
In the group theory, let $G$ be a finite group and $H$ be a subgroup of $G$.
Then the order of $H$ must divide the order of $G$. This the Lagrange's Theorem in group theory. More formally;

Lagrange's theorem - If $H$ is a subgroup of a group $G$, then ${\displaystyle \left|G\right|=\left[G:H\right]\cdot \left|H\right|.}$

Below a corollary to the Lagrange theorem;

If the order of the group is prime then there are no subgroups other than the trivial subgroups.

Therefore, an order $p$ group has no subgroups other than the trivial subgroups which are the identity group and the group itself.

The number of the rational points of the used curve is not a prime,  $\#C(K) = n$;
This really depends on the group. The Lagrange theorem doesn't guarantee the existence of the subgroups if an integer divides the order of the group.
Consider the Curve25519 which has a prime order subgroup $n$ and the co-factor is $h=8$ ( $h = \#E(\mathbb{F}_p)/n$) then we have the subgroup of order $2,4,8,n,2n,4n,8n$, i.e. we have all possible subgroups.
You can find a group that has two prime subgroups of order $p$ the if there are no other subgroups the curve group will be isomorphic to $\mathbb{Z}_p \oplus \mathbb{Z}_p$. Is this possible in Elliptic Curves?
I haven't seen an example in secure elliptic curves. The reason is simple; we want a large prime subgroup order that is close to the curve order in order to effectively use the curve. If there are two different subgroups of order $p$ then the curve order will be $\geq p^2$. This means you are wasting your computations.

More into theory (4.1 is in the second edition of Washington's Book);

Theorem 4.1: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_n}
> \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some
integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with
$n_1|n_2$.

If the $E(\mathbb{F_q})$ falls into the first case implies that the subgroup order $r$ must divide $r|n$. But the subgroups of $\mathbb{Z})_n$ are unique. Therefore there cannot be two subgroups that have the same order.
The second case is more interesting [1] [2] [3] since it is a direct product of groups. Since $n_1\mid n_2$ there is a subgroup of $H$ of  $\mathbb{Z_{n_2}}$ such that it is isomorphic to $\mathbb{Z_{n_1}}$. Now we have two subgroups of the same order $\Bbb Z_{n_1} \oplus \{0 \}$ and $\{0\} \oplus H$.
As said before we don't prefer curves that can have two different subgroups of order large prime.


Error-correction occurs within lattices in roughly two forms:

Binary error-correction is sometimes used within lattice-based protocols, although not all of the time. There are certain issues with doing this, namely that the errors in LWE-based encryption are not naturally of small hamming weight, while binary error-correction corrects errors of small hamming weight. Some analysis used a certain independence heuristic which ended up being invalid, leading to improper settings of parameters/attacks on NIST PQC candidates.

Error-correction with "lattice codes", or more properly codes for the Additive White Gaussian Noise (AWGN) channel. These are often called "sphere packings", and are used to correct the LWE error $e$ in an LWE sample $(A, As + e)$, which is of small $\ell_p$ norm (generally for $p = \infty$).

Lattice cryptography very often uses this second type of code. Basic examples are in Regev-style encryption, where one encrypts $m\in\{0,1\}$ via $(A, As + e + (q/2)m)$.
Here, one can view $(q/2)m$ as the value of $m$ being encoded under the lattice code corresponding to $(q/2)\mathbb{Z}^n$.
There are other more complex lattice codes used --- the Micciancio-Piekert "gadget matrix" $G$ can be seen as using the lattice $\bigoplus_i\Lambda_q(g^t)$, where $g = (1,2,\dots,2^{k-1})$. Van Poppelen's masters thesis looked into the potential benefits of using (direct sums of) the Leech lattice $\Lambda_{24}$.
There are more things you can do with lattice codes, but I hope the above is useful in understanding the "error correction" that most commonly occurs within lattice cryptography.


What is Rolling Code in cryptographic terms?

A Rolling Code is a method to generate short authenticated messages $M_i$, where $i$ is incremental modulo $n$ (thus rolling after $n$ messages), usually with the additional property that when the receiver has last accepted message $M_i$, it will only accept messages $M_{(i+j)\bmod n}$ for $1\le j\le m$, for some $m\ll n$ (perhaps $m=n/2$). This blocks attacks where a passive eavesdropper replays a message she intercepted, if the legitimate receiver has received that message or a later one, and until at least $n$ codes have been generated. Loss of less than $m$ consecutive messages is tolerated without undue message rejection.

A simple form of $M_i$ could be the concatenation of counter $i$ on $k$ bits (with $n=2^k$), and of a MAC of $i$ using a secret key shared by sender and receiver, obtained using HMAC.
Another option could be that $M_i$ is $i$ as a 128-bit block enciphered using one AES-128; $n$ is $2^{128}$ thus roll over never occurs in practice, and messages are authenticated by using a much smaller $m$, say $2^{48}$.

In the context of a door opener using one-way communication and no shared time reference, this gives useful but imperfect protection. An attack against the protocol (rather than the authenticating cryptography) remains possible by an active adversary:

User wants to open door, activates transmitter, which generates $M_i$.
Adversary intercepts $M_i$, and jams it (perhaps, by sending a strong signal during some fraction of the frame carrying the message, which can be reconstructed; that can be a header, or any fraction of a message shorter than its CRC if the message is protected by CRC).
Since the door does not open, user retries, re-activates transmitter, which generates $M_{i+1}$.
Adversary similarly intercepts and jams $M_{i+1}$.
Adversary immediately send $M_i$; the door opens, legitimate user is happy.
Later, adversary send $M_{i+1}$, door opens, adversary is happy.


Is it safe to say that a XOR with an unknown input provides a random output?

I am wondering if you have an input $x_{1}$ and you XOR it with an unknown random second input $x_{2}$, is it safe to say that the resulting $x_{1}\oplus x_{2}$ will be random ?

Yes, this is literally what proofs of the security of one-time pads come down to.  Informally it comes down to the following observations:

If $x_2$ is random, then it means that each of its bits is 0 or 1 with equal probability and independent of all other bits in $x_2$;
If $x_2$ has those properties, then $x_1 \oplus x_2$ also must.

And this really comes down that after the XOR, for each bit in $x_1$ you get with equal probability, either the original bit from $x_1$ or the flipped bit, and that you XOR all of the bits independently of all other ones.


How to design a balanced LFSR with period 1023 and linear span 55?

The polynomial factorisation of $X^{2^L-1}+1$ into irreducible factors gives you all the polynomials $g_i(X)$ that can be used as LFSR polynomials in generating any sequence of period $2^L-1.$ Say your goal is to generate a sequence of this period with linear complexity $c.$ Assume

$$(X^{2^L-1}+1)=\prod_{i=1}^v g_i(X),$$
there will be no repeated factors. Not all factors will be primitive of course.

Then for each $g_i(X)|(X^{2^L-1}+1),$ find the linear complexity of the periodic sequence it generates, say it is $L_i.$ You can use Berlekamp Massey for this.

If you can find a subset $J\subset \{1,2,\ldots,v\}$ with $\sum_{i\in J}L_i=c,$ then the corresponding polynomials $$g_i(X),\quad i\in J$$ will generate the sequence you need, for some initial conditions. Some of these polynomials will generate a sequence of length dividing $2^L-1$ of course.

More generally, given polynomials $f_i$ and letting $\Omega(f_i)$ be the set of sequences they generate, then
$$
\Omega(f_1)+\cdots+\Omega(f_v)=\Omega(lcm(f_1,\ldots,f_v)),
$$
and this has been known since the 1950s, published by Zierler in 1959, in Siam Journal of Discrete Maths.

Another good and accessible but somewhat dated reference is the book by Rueppel, The Analysis and Design of Stream Ciphers.

Appendix:

Magma online calculator gives the following factors for $X^{1023}+1$ (truncated)

  X + 1, X^2 + X + 1, X^5 + X^2 + 1, 1>, other degree 5 factors,
  X^10 + X^3 + X^2 + X + 1, other degree 10 factors

so what you found experimentally is not surprising.

Edit: As I alluded to, and this holds for any characteristic, but I will state it for binary, given any sequence $s(t)$ over $F_2$ with period dividing $2^L-1$ (and thus for period equal to $2^L-1$) there is an appropriate trace expansion for that sequence of the form
$$
s(t)=\sum_{i \in J} tr^{L_i}_1(\theta_i \alpha^{i t})
$$
and each of those trace sequences are some cyclic shift of some maximal length sequence (equivalently some cyclic shift of the output of some primitive LFSR) with length $L_i | L,$ where $L_i$ is the number of elements in the cyclotomic coset of $i$ modulo $2^L-1.$ So if a sequence with the parameters you want exists (w.r.t. linear complexity) it can be constructed this way.


Why is g is less than p in Diffie-Hellman?

It's an element of the field of all integers modulo $p$, and these are represented by the numbers $0,\ldots, p-1$. And $g$ will be one of them.


Is there an effective way for public key generation in homomorphic encryption schemes?

I must confess to not fully understanding your question but hopefully this will assist.

To generate a public key in Elgamal, you need a group (e.g., subgroup $\mathbb{G}_q$ of $\mathbb{Z}_p$ for large primes $p,q$) and a generator ($g$ where $\mathrm{order}(g)=q$).

A secret key is chosen from $x \in_r \mathbb{Z}_q$ and the public key is computed as $y=g^x$.

If you want to generate a public key $y$ without caring about $x$, you can use any element of $\mathbb{G}_q$.
If you want to ensure that no one knows $x$ for a given $y$, you could compute $y_i=\mathcal{H}(g)+i$ for $i=\{0,1,2,\ldots\}$ until you find a $y_i \in \mathbb{G}_q$.

For Benaloh (or Paillier), the first point is the same, the second is more complicated if you want to additionally ensure that no one knows the factorization of $n=pq$ (however there are techniques to do this).

Finally, I do not see any applications of encrypting without requiring decryption. If you simply want to obfuscate a value, there are more efficient primitives you can use. If you don't need decryption (per se) but do want to do things like plaintext equality tests, these require a decryption key!


An arithmetic circuit for the indicator function?

Any degree $d$ polynomial (over a field) has at most $d$ roots (unless it is identically zero). As the indicator function has $q-1$ roots, one gets that it must have degre $\geq q-1$.
There are generalizations of this to multivariate polynomials (the best known is Schwartz-Zippel). You could potentially try to generalize to non-fields, but one quickly runs into odd behavior --- say over $\mathbb{Z}/6\mathbb{Z}$ the linear function $f(x) = 3x$ has $\geq 1$ root. This is because it is "identically zero in a CRT component" though, but I do not know of the proper generalization to avoid issues such as this.


Is there any hash function for which a preimage of a fixed element is always known?

Take any standard hash function family $\{h_s(\cdot)\}_s$, a point $c$ and a list of inputs $(x_s)_s$ and define $h'_s : x \mapsto h_s(x)$ if $x\neq x_s$, and $c$ otherwise. As you said, it does not contradict collision resistance or preimage resistance - in other words, you can prove that if $(h_s)_s$ is a family of (say) collision-resistant hash functions, then so is $(h'_s)_s$. If you have a collision on Merkle-Damgård applied to $(h'_s)_s$ without $IV$, then you are done. The existence of any collision-resistant hash function implies the existence of a hash with the properties you want, via this trivial method.


Zero knowledge proof for a discrete logarithm

This problem was studied in [BCK], and interestingly they showed that constructing a Schnorr-like zero-knowledge proof system (ZKP) in a group of unknown order with non-trivial soundness error is not possible in the plain model (i.e., without CRS). Their result is much more general and talks about homomorphisms in groups of unknown order.

However, if one considers the CRS model, then [BBF] recently showed that ZKP is possible in the generic group model under the "adaptive root" assumption. Boneh talks briefly about this work here.

[BBF]: Boneh, Bünz and Fisch, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Crypto 2019

[BCK]: Bangerter, Camenisch and Krenn, Efficiency Limitations for Σ-Protocols for Group Homomorphisms, TCC 2010


AES Encryption With PBKDF2 KDF in pycrypto

As a quick aside, something newer like Argon2, the 2015 password hashing competition winner, is better than PBKDF2. Using a Key Derivation Function (KDF) and the same key to encrypt many messages (for example) isn't particularly secure. There are also methods of exchanging keys like Diffie-Hellman Key Exchange, although they may not be applicable in certain use-cases.

From re-reading your question, it seems you think a KDF is a function that allows you to keep a shared secret key and generate (with random salt) the same derived key.  In which case the salt would have no effect whatsoever.
Note that PBKDF2 is built from a hash function.  In the case of pycrypto it is using HMAC-SHA512.  As such, the salt needs to be the same in order for the derived key to be the same.
When you are generating a new salt, you are generating a different hashed key.  That is exactly why salt is used. Actually, for deriving Multiple Keys can be risky with PBDKF2, once your password is found the two keys are gone. You can use PBKDF2 to generate a key and then use KDF.
The purpose of the salt is to prevent against pre-computed attacks on the hash (eg. Rainbow-table).  See more here.
Sending the salt over the network strengthens the KDF. As a simple example (I am the attacker):
Without a salt
I download a file with a list of all hashes for likely n character passwords.  I watch traffic and match many transmitted digests with my downloaded file.  I required internet, significant storage space, and network hacking skills.
With a salt
I cannot download (or generate) a file with all likely passwords as every password has too many possible hashes.  I watch traffic, and must generate a new hash file for every salt I see.

As you can see (hopefully), the salt makes it far more difficult to pre-compute anything before you see the salt.


Research Question (Part 2): new symmetric key cryptosystem

Again, given this new (verified) information, does this system offer any theoretically interesting properties that could warrant publication?

Again, no.  You could put together a paper and submit it to eprint (or maybe arxiv, I'm not familiar with their acceptance policies), but beyond that, I can't think of any journal or conference that'd be interested.

As for your "verified" information:

  Perfect secrecy: for $x \in P, y \in C$, $p(x|y) = p(x)$

It is a homework exercise to show that if you have this property, then you must have at least as many keys as possible plaintexts.  So, to encrypt a megabyte plaintext, you must have a megabyte key.  So, do you have megabyte keys?  Or, do you have a low ceiling on the size of the plaintext you can encrypt?

  If Alice and Bob share $l$ messages using the same public object $T$, then if Eve obtains a plaintext/ciphertext pair she may decrypt all such messages

So, the public object $T$ is effectively a nonce; that is, a given $T$ value can be used to encrypt only a single message.

  with large number $l$ of distinct $(T_i, C_i)$ pairs so that $(T_i, C_i) \not = (T_j, C_j), i \not=j$, then, if Eve has a lot of compute, she may brute force construct an approximating key $K_a$, that would, with probability proportional to the size of $l$, give useful information about any new $C$

So, if the attacker gets a number of ciphertexts, they can get information about plaintexts encrypted with the same key.  This falls rather short of the "perfect secrecy" you claimed in the previous bullet points.

The only comeback would appear to be "by a lot, you mean more computation than is feasible.  However, if you make that argument, you have to assume that there are no optimizations beyond the attack you have sketched out; that means that you are making an assumption (and so you are not really any better than, say, AES or ChaCha…)

  worst case encryption and decryption times grow linearly with key size. In most cases encryption/decryption time grows at rate of log of key length.

I'm not sure what to make of this.  By 'key length', we typically mean 'length of the key in bits'.  To use $n$ bits of the key as part of the encryption or decryption time, that takes at least $O(n)$ time (if nothing else, to read the key bits).  If encryption/decryption time grows (in most cases) logrhythmically with key length, that means in most cases you don't access the majority of the key bits (because you don't have the time).  This property would make key searching attacks far more efficient (as the attacker wouldn't have to guess most of the key).

Is that what you really meant?


Are the GPS coordinates a good source of entropy?

Probiably not.  If a hacker where to locate the device physicaly then the search space would be greatly decreased.  Even knowing the city (ip can give you that) might be enough.
Other similar sources with a higher entropy could be changes in lat and long, but those are most likely small.
You would most likely get better entropy using the accelerometer/gyrometer/magnomiter instead (if avaliable, I am assuming this is for a phone).
If you wanted lots of entropy, you could ask the user to give their phone a nice toss while poling gyro and acceleration.


Obfuscate an "I'll reveal if you do" function

If there is _______________ obfuscation scheme for such $\hspace{.03 in}f$s then there is a scheme

that does what you describe, where _______________ is either "a differing-inputs"

or "an extractability", depending on how you define "doesn't know Alice's secret".

Note that if there is no a-priori bound on the length of $x$, then the $\hspace{.03 in}f$s will have to be Turing machines with unbounded input length rather than just circuits. $\:$ In order to obfuscate such programs with the latter paper's candidate construction, one needs (publicly verifiable) SNARKs instead of just SNARGs.

However, if there is an a-priori bound on the length of $x$ or the commitment scheme's

verification function is sufficiently parallelizable (for example, if it follows a Merkle tree),

then one can replace the FHE scheme with a leveled FHE scheme.

On the other hand, this paper gives an argument against

the plausibility of the types of obfuscation that I linked to.

I see a lot of papers mentioning that standard assumptions suffice for the existence of a pseudorandom generator with linear stretch in NC1, although I cannot actually find any good candidate for that. $\:$ If there is one, then by chaining it to make the stretch sufficiently large and applying Naor's construction to the resulting PRG, one gets a commitment scheme whose verification function is in NC1. $\:$ Observe that

the $\hspace{.03 in}f$s are computable by just ANDing the output of the verification function with each bit of $y$.

Thus, if there is a pseudo-random generator with linear stretch in NC1 and a

_______________ obfuscation scheme for NC1, then there is a scheme whose

commitment is slightly interactive but otherwise does what you describe.


The conversion to binary is not part of the DES standard. So you'll have to define that part of the protocol yourself. The cipher itself needs to be used with a mode of operation, as fgrieu indicated.

There are basically two families of modes of operation: streaming modes of operation and block modes of operation.

In block modes sych as ECB or CBC you have to split the plaintext into separate, sequential blocks, usually after padding the plaintext.

In streaming modes such as CFB and OFB the bytes may be encrypted byte for byte.

Of course the API (the programming interface) of high end implementations of ciphers or modes may hide such implementation details.


The diagram shows the gist of the algorithm, but not everything in it.

The bulk of the encryption in GCM uses AES in CTR mode. "CTR mode" means that "successive" values of a counter are encrypted with the block function (the AES properly said) in order to yield a key-dependent pseudorandom stream which is combined (bitwise XOR) with the data to encrypt or decrypt. Each counter value thus has the size of a full block, which is 128 bits. Note that there is no requirement for the notion of "successive values" to match any given arithmetic model, in order to achieve security; we only need that the "successive values" are distinct. Of course, for encryption and decryption to work, sender and recipient must agree on the initial value and how to "increment" it in order to obtain the successive values, and that is defined in GCM.

The specification for GCM is NIST SP800-38D. In that document, we see the following:

While the counter value has the size of a block (16 bytes), only the last (rightmost) 4 bytes are modified to step into the "next value". The last 4 bytes are interpreted as a 32-bit integer (with big-endian convention), which is incremented. Note that the value conceptually "wraps around" (if the last 4 bytes have value FF FF FF FF, the increment yields 00 00 00 00, and the first 12 bytes of the block are kept untouched).
If the IV for GCM has size exactly 12 bytes, then the value "counter 0" in the Wikipedia schema is the concatenation of the IV, and 00 00 00 01. The value "counter 1" will be identical, except that the last byte will be 02 instead of 01. Note that the AES-encrypted value "counter 0" is used as post-processing for the authentication tag; the first counter value used to encrypt actual data is "counter 1".
If the IV for GCM has any other size, then it is first processed with GHASH, in order to yield a full 16-byte initial value for "counter 0". Note that, in that case, the GHASH output is also used for the last 4 bytes, so the starting value for the 32-bit integer is not necessarily 1 (and the "wrapping around" behaviour may actually happen, if we start close enough to FF FF FF FF).

In GCM, the AES block function is used for exactly three things:

To encrypt an all-zero block, to yield the h value (used in GHASH, for the authentication tag).
To encrypt the value "counter 0", used to mask the authentication tag.
To encrypt values "counter 1", "counter 2"... to produce the pseudorandom stream that is combined (with XOR) with the plaintext or ciphertext.

The details of GCM have been made such that, if the IV has length exactly 12 bytes, then all these values are guaranteed to be distinct to each other; the security of GCM depends on it. An important consequence is that if you use the AES/GCM key for anything else, then all security guarantees evaporate like dew in the morning sun.

It shall be noted that the use of the last four bytes as wrapping counter is not a universal convention. That is, it is defined that way in GCM and all GCM implementation follow it (otherwise they would not interoperate). However, other schemes that use CTR mode may have different conventions. In EAX and CCM, the full 16-byte block is considered to be the encoding of a complete 128-bit integer.

Computers are not limited to what can fit in a register, in exactly the same way that you have only ten fingers, but can still perform operations on numbers that contain several digits. On a 32-bit computer, you would use four 32-bit registers to hold the complete 128-bit value. See for instance how it is done in BearSSL implementation; the gist of the increment operation is as follows:

            cc0 ++;
            carry = (~(cc0 | -cc0)) >> 31;
            cc1 += carry;
            carry &= (~(cc1 | -cc1)) >> 31;
            cc2 += carry;
            carry &= (~(cc2 | -cc2)) >> 31;
            cc3 += carry;

The four 32-bit words are cc0, cc1, cc2 and cc3 (of type uint32_t, i.e. exactly 32 bits each). These weird expressions compute the carry propagation with branchless, constant-time code; a simpler (but not constant-time) implementation would look like this:

            cc0 ++;
            if (cc0 == 0) {
                cc1 ++;
                if (cc1 == 0) {
                    cc2 ++;
                    if (cc2 == 0) {
                        cc3 ++;
                    }
                }
            }

To be clear, I repeat that the code snippets above handle the EAX/CCM case, where the counter is incremented as a 128-bit value, not the GCM case, where only the last 4 bytes are incremented arithmetically.


What is wrong with encryption-based / hash-based commitment schemes?

The second construction is trivially not hiding. It is easy to verify a guess $m'$ just by recomputing $H(m')$ and comparing the result with the commitment.

The first construction is a bit trickier. If it is a CPA secure encryption scheme, then it is certainly hiding. However it may not be binding.

It is easy to construct secure encryption schemes, where different keys decrypt the same ciphertext to two different messages. In fact most symmetric encryption schemes without authentication definitely fall into this category. As do public key encryption schemes such as ElGamal encryption.


Why is Paillier Cryptosystem called probabilistic?

As user curious said in a other answer probabilistic means that the encryption of the same plaintext under the same key gives as output a different ciphertext.

This is a more general property and it is known as a basic security property: it is usually refered to as semantically secure or indistinguishability (roughly: an attacker cannot guess which one of two plaintext he provided has been encrypted). It was firstly defined and introduced by Goldwasser and Micali in their seminal paper "Probabilistic Encryption" on 1984. This property is usually achieved introducing a random token into the encryption algorithm.
A very simple way to transform any deterministic encryption algorithm into a probabilistic one is to pad the plaintext with a random string before to encrypt it and do unpad it after the decryption. Under symmetric encryption it can be easily achieved using a random IV (or counter) for a secure block operation mode (as CBC or CTR).

More precisely about Pallier cryptoscheme, the encryption algorithm uses a random $r$ element per encryption.

Encryption

Let $m$ be a message to be encrypted where $m\in \mathbb Z_{n}$;
Select random $r$ where $r\in \mathbb Z^{*}_{n}$;
Compute ciphertext as: $c=g^m \cdot r^n \bmod n^2 $.


Why do some key derivation functions (like PBKDF2) use a salt?

PBKDF2, like most password-based key derivation functions, has a salt input because that is often useful. Two examples:

When using PBKDF2 as a key derivation function, the salt allows to re-use the same master key for multiple derived keys, e.g. a confidentiality key and integrity keys, with a different salt per use. In the same vein, PBKDF2 could be used to generate per-site passwords from a master password and the site name as salt.
When using PBKDF2 for storage of access-control password tokens, salt will make brute-force attack impossible to carry before the salt is known, defeating rainbow tables. That's noted in the question.


An instance of the (approximate) Shortest Vector Problem is simply a basis of some lattice. The desired output is any (approximately) shortest nonzero vector of that lattice. To solve this problem in the worst case, an algorithm must produce the desired output given any basis of any arbitrary lattice. (Other lattice problems have similar instances, usually including a basis and sometimes other information, like an arbitrary target point in the case of the Closest Vector Problem.)


How to confirm my implementation is constant time? I'm in scala using bouncy castle from Java.

This code is not constant time, for no platform is specified. Computing platforms that run in constant time or cycles are the exception. I don't know any device with internet and video currently for sale that does. That's actually contributing to make attacks harder!

For cryptographic security, what matters is Data-Dependent Timing Variation: execution time that varies depending on the data manipulated¹. The question's code most likely exhibits some DDTV, since it apparently uses Java's BigInteger type, which is not designed to avoid DDTV, and doesn't even come close. Bouncy Castle is riddled with DDTVs where it uses BigInteger, more or less sizable depending on version and platforms, at least in it's generic RSA decryption code (the only part I have studied in depth). The BC developers approach that issue by lowering DDTV when that's easy, and trying to hide it with some degree of noise when that's not. That's probably the best they can in the framework of a portable Java crypto library.

Except starting from scratch using techniques geared for constant-time down to the bare hardware for all the crypto primitives (like done for crypto accelerators in high security devices, and in BearSSL), I see little hope to reach zero DDTV, which is the most satisfying option form a security standpoint, and is practiced.

For lack of that, the only option is try making DDTVs low enough that they do not open to attack, and try to assess that. It's complicated.

In the following I'll discuss just a few down-to-earth incremental countermeasures that can be added on top of existing libraries, and may help. I'm sure neither that its necessary, nor sufficient, nor even certainly without security drawback.

One general-purpose countermeasure, effective in theory (even perfectly so) is to start a timer at the beginning of the calculation, set to elapse after it ends considering a worst-case scenario (perhaps, the experimental maximum time plus a few times the experimental standard deviation $\sigma$), and at the end of the calculation wait precisely until the timer elapses before releasing the result. But that's a portability nightmare; adversaries (or poor control of the platform) can increase the computation time (e.g. by adding workload) or slow the CPU so that it exceeds the timer; or maybe adversaries will manage to get a measure of CPU time not accounting for waiting that the timer elapses.

Another countermeasure adds a random delay. It needs to have fine granularity. A simple method draws a uniformly random integer and wait that number of cycles (or if not possible, dummy loops²), with the maximum integer calibrated for an average of a few $\sigma'$ ³ for lack of a more rationally determined value⁴. While it is possible for an attacker to mitigate such delays by correlating different experiments, or repeating the same and averaging or keeping the minimum measured time⁵, they are useful by adding uncertainty in the adversary's inputs, which tends to make a successful attack require more measurements, thus more time.

Problem with the above delays (final or randomly added) is that they are not or marginally useful against side channels other than pure timing (differential power analysis, electromagnetic and audio variants, hardware features like caches..).

A general class of countermeasure targeting a wider spectrum of side-channel attacks is blinding. The general principle is to mix-in a random value that changes how the computation is made (hence its timing and other side-channel leakage, in a manner unrelated to secret data), but not its final outcome, thanks to mathematic properties.

One blinding countermeasure applicable to computations modulo $n$, for example that of $s=(k+e\cdot\text{Priv})\bmod n$, is to

add $r_i\cdot n$ for random(s) $r_i$ (say in range $[0,2^{64})$ ) to some or all inputs (here $k$, $e$, $\text{Priv}$ ) of the formula
perform the computation modulo $u\,n$ instead of $n$, for some $u$ (say in a range $[2^{63},2^{64})$, fixed or dynamically chosen at random),
finally reduce modulo $n$.

Another countermeasure in that spirit, with a chance to make timing differences in elliptic curve scalar multiplication less exploitable, while only increasing the execution time moderately (like 30%), is to indirectly generate $k$ and compute $R=k\times G$ (where $\times$ is point multiplication on the elliptic curve):

Choose some parameter $m\approx2^{32}\sqrt n$ and precompute $G_m=m\times G$ ($m$ can be fixed and public including a power of two, or a secret randomly chosen at a time when performance does not matter much).
Generate random $k_a$ and $k_b$ in $[0,m')$ with $m'\approx m$, perhaps fixed $m'=2^{\left\lceil\log_2(m)\right\rceil}$
Compute $R=(k_a\times G_m)+(k_b\times G)$ where $+$ is point addition on the elliptic curve.
Use $k_a\cdot m+k_b$ instead of $k$ in the computation of $s=(k+e\cdot\text{Priv})\bmod n$. The choice of the equivalent $k$ is not quite perfectly uniformly random, but it remains fine for the purpose of Schnorr signatures. The reduction modulo $n$ can be differed to the final computation of $s$. The test $k=0$  can be replaced by a check of $R=\infty$ (in practice that will only occur if there is some bug or fault, e.g. in the RNG, and the best course of action is to zeroize/burninate the private key, if that causes no huge loss).

Conclusions:

Forget about constant time on most modern computing platforms.
Zero DDTV is desirable and achievable, commonly in hardware, and even in software, but forget about it when using Java's standard BigInteger class.
Starting from this code, the most reachable short-term objective is mitigating DDTVs to bring them below the level where they are demonstrably exploitable by known means in practical conditions.
How, and how to assess it, are vast subjects, barely touched in this answer.

¹ We really only care for data that is secret, but in this code fragment a lot is.

² With the issue that they could get optimized out by a smarter compiler, or JITC of the target platform.

³ Contrary to the previous $\sigma$, this $\sigma'$ needs to account mostly for DDTVs, not for platform-related variability.

⁴ Computing how much is necessary would require some model of the actual DDTVs, and an hypothesis on the time available for the attacker.

⁵ Which (from an attacker's perspective) is a more robust strategy than averaging if measurements are plagued by spurious activity adding to the timings. A distribution of the random delays that seldom is minimum, including near Gaussian as resulting from multiple equal delays spread along the calculation to thwart resynchronization, will give a harder time than a uniform delay to an attacker that must rely on this strategy.

Orphan note: It conceivably could help to replace random sources used in random delays and blinding by a CSPRNG, keyed by a long-term random symmetric key and the input of the computation (here, the message to sign). That will make timing deterministic, thwarting any attempts to remove the random delays (explicit, or induced by blinding) using multiple measurements with the same input. But that might not be a good idea: it's typically a better attack strategy to correlate timing measurements with as many varying inputs as possible, rather than repeating fewer measurements to make them more precise; the timing is deterministic only inasmuch as the adversary can't force the re-seeding of the fixed long-term random symmetric key; and being deterministic can well turn a disaster if the adversary manages to extract that key, or if the input of the computation is secret, or if the adversary is trying to synchronize a fault-injection attack.


The meaning of formal and semi-formal in cryptography

You may want to check the answers to this question. As the question (and answers) point out, it is not rare to find people use "formal proof" to refer to proofs generated using computer-aided means.

However, as some comments to your question also point out, a "formal" proof of something strictly means a mathematical proof showing that all the claimed (security) properties are met. This can be done using computer-aided tools, but not necessarily. The term provable cryptography refers to a major area in cryptography which deals with the main techniques to create such proofs (not necessarily -and not usually- computer-aided tools). See, for instance, this entry in the Wikipedia for some further insight and references.

About "semi-formal" proofs: I guess that it refers to proofs that do not go down to the full detail, and just set out the overall approach and leave some (or all) parts as sketches. This means that while they may overlook some things, such "semi-formal" proofs point towards the right direction to build a formal proof.


Proof of knowledge outside of Zero Knowledge

If you don't have any zero knowledge requirement, then a proof of knowledge is achieved by just having the prover send the "witness" in the plain to the verifier. Thus, no, a proof of knowledge that has no privacy requirement is not interesting.

Note that it can be interesting to have a witness indistinguishable proof of knowledge, or a witness hiding proof of knowledge. These are not full blown zero knowledge but have meaningful privacy requirements.

The best place to read about witness indistinguishability and witness hiding is in Oded Goldreich's book on the Foundations of Cryptography (Volume 1). (Note the errata on strong witness hiding.) You can also look at Uri Feige's PhD Thesis, which is extremely clear and easy to read (but less general than the treatment in the Foundations of Cryptography).

The reason why one would want these not "full blown" zero knowledge notions is that it is possible to achieve them more efficiently in some sense. In addition, they can be used as important stepping stones to full zero knowledge.


Do we always use Sophie-Germain primes $1\bmod 4$?

This seems to put a huge restriction on density of Sophie-Germain prime if they are $3 \bmod 4$.

I'm not sure how you come to that conclusion; whether $2p+1$ is a factor of $2^p-1$ would not have any immediately obvious consequence to $2p+1$ being prime.

  For this reason do all systems use Sophie-Germain primes with $1 \bmod 4$ for discrete logarithm?

Actually, Sophie-Germain primes of the form $3 \bmod 4$ would appear to be more prevalent; for example, the primes listed here are all of the form $3 \bmod 4$.  One reason is that it makes the value $g=2$ be a quadratic residue, that is, its use during the DH operation doesn't leak the lsbit of the private exponent, and that's appreciated by some people.


Recommended way to Implement One Time Password?

I do not fully understand the scheme you are describing, especially the interactions between your apps A and B. I'll try to describe a sensible HSM usage for a  OTP based authentication.

I think you have a little misconception about how a typical OTP is usually handled. There is no need to store an OTP ever, it is always calculated upon use. The typical scenario is, that the user (his OTP calculating app) and the server both store a shared secret. From that secret and some additional information (like a timestamp if you use TOTP, or a counter if you use HOTP) the one time password is calculated using the HMAC algorithm.

This HMAC calculation can be done in software (if you use a normal app on your phone, like FreeOTP) or in hardware (like a PKCS#11 token) on both sides. The server side in your case, could use your HSM which stores the user's secrets to do the HMAC calculation. For a real massive multi user setting, you will probably have to create the shared secrets on the HSM dynamically from a master secret to overcome storage restrictions.

The specific procedure how you calculate your 6 digit (or whichever length you need) OTP ist outlined in the RFCs for HOTP and TOTP.


The sender encrypts the data with a symmetric key. After that, he encrypts (using RSA algorithm) this symmetric key with the public asymmetric key of the receiver.

That's one possible implementation of a hybrid cryptosystem for encryption/decryption. It is also quite common to derive the symmetric key using the asymmetric key pair. This is performed for instance by IES for Diffie-Hellman based cryptography but also by RSA-KEM.

How does the sender know the public asymmetric key of the receiver?

Diffie Hellman.

No, Diffie-Hellman is used to derive symmetric keys. It cannot be used to distribute public keys.

How does the sender know the public asymmetric key of the receiver?

Digital certificate PKI, by querying a CA.

An implementation of a PKI could certainly work.
But PKI doesn't necessarily mean that there are CA's (e.g. see how PGP operates).
And if they do exist - for instance in PKI-X used in e.g. browsers - then they generally are only needed to sign certificate requests and verify that certificates are not revoked. During operation the CA certificates can simply be send using a certificate chain. Quering a CA is not required at the time of verification.


A key-generator outputs an encrypted string that only changes the second half - what weaknesses could that expose?

The reason what you called "real licenses" look like ssh-rsa keys is probably just the encoding format for some of them. ssh-rsa keys are base64 encoded, and that might be the only reason. The decode content can really differ based on the license checking algorithm.

You'd probably be better off disclosing your license verification algorithm, and letting people comment on its security/strength which will enable you to improve it in case any issues are found. The fact that the licenses start with the same prefix, on its own, doesn't indicate much about the security of your license verification.
You should also be clear about the assumptions you're making about a potential cracker, and what can they do. That would help assess whether the licensing scheme is secure under those assumptions.


Why use symmetric encryption with Public Key?

I think you're looking for Hybrid cryptosystems.

As you correctly noted it's not only unsafe to encrypt large data with a asymmetric system it's also very slow compared to symmetric systems. That's why we usually use both of these systems together (hence hybrid) to "fill each other's gaps".

We share a symmetric key using asymmetric cryptography. The advantage is that we only have to share the symmetric key once at the beginning of a session and all succeeding messages will be encrypted using the symmetric key. The asymmetric system provides safe key-sharing and the symmetric system guarantees fast encryption / decryption.

  B. Also, if you do have secret symmetric (e.g. AES) keys, you might not want to share them with others, if they have high importance to you.

That's true, but we always create new keys for each communication channel, we don't use a single symmetric key for all communication.


What do the magic numbers 0x5c and 0x36 in the opad/ipad calc in HMAC do?

Those "magic numbers" are related to the security proof behind the HMAC construction.

In their Crypto'96 paper, Bellare, Canetti and Krawczyk first prove that $\mathrm{NMAC}_{(k_1, k_2)}(x) = F_{k_2}(F_{k_1}(x))$ forms a secure MAC ("message authentication code") provided $F_k(\cdot)$ is an iterated and keyed compression function enjoying some good security properties and $k_1$ and $k_2$ are statistically independent keys. NMAC could be instantiated by common iterated hash functions, such as SHA-256, but one should be able to replace the IV by the key, which is not possible with standard implementations.

To avoid this practical problem, the authors have defined another mechanism, named HMAC. Given a single key $k$ as well as an iterated hash function $H(\cdot)$ built out of a compression function $f(\cdot)$, they first derive two keys $k_1 = f(k \oplus \mathtt{opad})$ and $k_2 = f(k \oplus \mathtt{ipad})$ out of $k$ and define $\mathrm{HMAC}_k(x) = \mathrm{NMAC}_{(k_1, k_2)}(x)$. Thus, the constants $\mathtt{ipad}$ and $\mathtt{opad}$ are just meant to be different, such that the inputs $k \oplus \mathtt{opad}$ and $k \oplus \mathtt{ipad}$ to the compression function are different. Their values have been arbitrarily chosen by the HMAC designers, and any pair $(\mathtt{opad}, \mathtt{ipad})$ could have been selected, as long as $\mathtt{opad} \neq \mathtt{ipad}$.


Hash function such that fx(hash(s1),hash(s2)) = hash(concat(s1,s2))

I'll consider only a non-adversarial model for the requirement of a low collision probability; that is, we are considering naturally-occurring strings only (which implies they are of bounded size; I'll limit it to $2^{64}-1$ bits, over 2305 Petabyte). However I'll consider that we need to reliably detect strings that differ only in a small consecutive segment. Caveat: in the following, hash is thus not used in its default meaning in cryptography.

My (new) proposed $h(s)$ is $256$-bit ($32$ bytes), among which the first $64$ bits are the number of bits in $s$ (truncated to the lower $64$ bits); and the $192$ last bits are a $192$-bit Cyclic Redundancy Check (CRC) of $s$, that is as the coefficients of $s(x)\bmod p(x)$, where $s(x)$ is the binary polynomial with coefficients the bits of $s$, and $p(x)$ is a fixed $192$-bit primitive polynomial. Conversions from bitstring to integer or polynomial, and back, are big-endian (the last bit corresponds to the least significant bit of integer or constant term of polynomial).

We define $g(h_1,h_2)$ as follows:

from $h_1$ and $h_2$ we get the integers $l_1$ and $l_2$ as the first $64$ bits, and build the first $64$ bits of $g(h_1,h_2)$ as $l_1+l_2$;
from $h_1$ and $h_2$ we get the polynomials $m_1(x)$ and  $m_2(x)$ which coefficients are the last $192$ bits, and build the last $192$ bits of $g(h_1,h_2)$ as the coefficients of
$$m_1(x)\cdot x^{l_2}+m_2(x)\bmod p(x)$$

The desired $g(h(s_1),h(s_2))=h(s_1\|s_2)$ holds, and its computation is fast, independently of the length of the original strings, noticing that $x^{l_2}\bmod p(x)$ is quickly computed by pre-computing $q_j(x)=x^{2^j}\bmod p(x)$ for $0\le j<64$, and multiplying modulo $p(x)$ those $q_j(x)$ corresponding to the bits set in $l_2$.

The hash of any bitstring $s$ of at most $192$ bits is its length $l$ (in binary over $64$ bits), followed by $192-l$ 0 bits, followed by $s$. For longer bitstrings, we can either use the definition, or use $g(h(s_1),h(s_2))=h(s_1\|s_2)$; both allow computing the hash of an arbitrary bitstring in time roughly proportional to its length.

A practical implementation of $h$ on a modern $64$-bit CPU can use a table of $2048$ pre-computed $192$-bit values ($8$ tables each $256$ entries each $3$ words of $64$ bits), and each additional $8$ bytes of $s$ will require only $8$ fetches of $3$-word entries, and few simple operations dominated by $24$ wordwise XOR. That's very fast.

It is trivial to make collisions, but that can not occur between bitstrings of different length, or which differ only in a small segment (of size no more than $192$ bits).

One suitable $p(x)$ is $x^{192}+x^{149}+x^{97}+x^{46}+1$, taken from Jörg Arndt's Table of weight-5 binary primitive polynomials with (roughly) equally spaced coefficients. We might however want to use a random primitive polynomial, which gives even better insurance that no collision occurs between naturally occurring strings (argument: with neither knowledge of the polynomial nor example hashes, it is computationally impossible to find distinct strings with sizable odds of hash collision).

My original (and in retrospect overly complex) proposed $h(s)$ is $256$-bit ($32$ bytes), among which the first $64$ bits are the number of bits in $s$, and the $192$ last bits are $2^s\bmod p$, where $p$ is a fixed $192$-bit prime such that $(p-1)/2$ is prime and $2^{(p-1)/2}\bmod p=p-1$.

Because $2^s\bmod p=2^{s\bmod(p-1)}\bmod p$, we can compute the hash of a string in time about proportional to its length, by first reducing $s$ modulo $p-1$.

We define $g(h_1,h_2)$ as follows:

from $h_1$ and $h_2$ we get the integers $l_1$ and $l_2$ as the first $64$ bits, and build the first $64$ bits of $g(h_1,h_2)$ as $l_1+l_2$;
from $h_1$ and $h_2$ we get the integers $m_1$ and $m_2$ as the last $192$ bits, and build the last $192$ bits of $g(h_1,h_2)$ as
$$m_1^{2^{l_2}\bmod(p-1)}\cdot m_2\bmod p$$

The desired $g(h(s_1),h(s_2))=h(s_1\|s_2)$ holds, and its computation is fast, independently of the length of the original strings.

A suitable choice of $p$ is $\lfloor325\cdot\pi\cdot2^{182}\rfloor+78356$, that is in hexadecimal ff41208fd469fe8cfdcfdb1b1a977095890fed10d7b6f8a3 (Note: $325$ was selected so that the leftmost byte of $p$ is FF, $78356$ is the lowest integer so that $p$ matches the other requirements).

Examples (with this choice of $p$)
The hash of the empty string is
0000000000000000000000000000000000000000000000000000000000000001
The hash of the one-byte string 00 is
0000000000000008000000000000000000000000000000000000000000000001
The hash of the one-byte string 4c is
0000000000000008000000000000000000000000000010000000000000000000
The hash of the one-byte string bf is
0000000000000008800000000000000000000000000000000000000000000000
The hash of the one-byte string c0 is
000000000000000800bedf702b960173023024e4e5688f6a76f012ef2849075d
The hash of the one-byte string c1 is
0000000000000008017dbee0572c02e6046049c9cad11ed4ede025de50920eba
The hash of the two-byte string c0c1 is
0000000000000010f4cf3a34057419042ee1a3d61690616770b8532f43255211

It is easy to find a collision, but it won't occur by accident, and only for strings of equal length. For example, the $24$-byte strings
000000000000000000000000000000000000000000000001 and
ff41208fd469fe8cfdcfdb1b1a977095890fed10d7b6f8a3 both hash to
00000000000000C0000000000000000000000000000000000000000000000002.

The above has the property that it is slightly difficult to come up with a string having a given random value in the right part (first preimage resistance); that's the discrete log problem. By making $p$ much larger, or using a group derived from point addition on an elliptic curve of known order, we can make that very difficult. This is nice to have, but not useful in the context of the question.

The idea in that other answer as modified per this comment also works, but is prone to collisions for messages differing by few consecutive bytes, contrary to all the methods considered in the present answer.


Does using Noise asynchronously weaken its security properties?

Online $\neq$ Synchronous
Yes, Noise can be used in a somewhat asynchronous setting.
Noise is initially meant to be an "online" protocol to establish secure channels, however "online" here does not really imply it requires a "fully synchronous network", but more like a "reliable channel" in which packets will come in the right order but not necessarily at a given time.
The appropriate handshake
In your case you said that:

They know each other's public static keys in advance

Which means indeed that the KK pattern is the most appropriate one.
Now, it seems you'd like to have A perform what is called a "0-RTT" encryption (that is encrypting a message/payload for B without having done an interactive handshake first) and this is actually covered by Noise:

Patterns where the initiator has pre-knowledge of the responder's static public key (i.e. patterns ending in K) allow zero-RTT encryption, meaning the initiator can encrypt the first handshake payload.

So, what you want to achieve is actually already possible using 0-RTT and the KK handshake and it's actually in the spec and you don't need to run the different steps differently from what the spec says.
First notice that the lines above the ... are representing the "pre-knowledge" of the parties.  They have acquired the static keys through some mean (for example by relying on a server) and then the actual protocol start:

-> e, es, ss means that A is sending to B its ephemeral key e and is performing a DH es using its ephemeral key and B's static key, and then it is performing another DH
ss using its own static key and B's static key (of which it had pre-knowledge).
After having performed these 2 DH, A can already compute the shared chaining key ck
which is just a hash of the 2 DH outputs
A can then the payload of its handshake using ck. Notice that in all Noise handshake messages, you have an implicit payload which can be zero-length or not. (And which is encrypted under certain conditions.)
Upon reception B will learn the ephemeral key of A and has pre-knowledge of its static key, so B is able to compute the same 2 DH as A using the e it received and its own static key and then using both static keys, so B gets the same value for ck and will be able to decrypt the encrypted payload.
B generate an ephemeral key, computes the DH ee between the 2 ephemeral keys and compute finally the DH se between A's static key and B's new ephemeral key and now the ck state is updated once more to its "final" state, which A will also be able to compute upon reception of <- e, ee, se. The payload to this message can directly be encrypted as well using ck.
Notice that at this point the final shared key ck has been computed as being the hash of first es hashed with ss hashed with ee hashed with se.
Subsequent messages can just be encrypted using the resulting key ck and incrementing the nonce (and ad hash) as per the spec.

We need to be careful as the spec is telling us the following:

After performing a DH between a remote public key (either static or ephemeral) and the local static key, the local party must not call ENCRYPT() unless it has also performed a DH between its local ephemeral key and the remote public key. In particular, this means that (using canonical notation):

After an "ss" token, the initiator must not send a handshake payload or transport payload unless there has also been an "es" token.

But since we had first an es token and then a ss one, we can call ENCRYPT() on our payload. :)
So IMO you do not need to do anything differently from what the spec already allows and does. This is already possible without any change by simply exploiting the optional handshake payloads.
The alternative
Now, while I'm at it, if you really have strong asynchronous requirements, you might want to take a look at what Signal's X3DH is doing with its one-time prekeys since being asynchronous is the goal of X3DH and it's based on a server setup like yours:

X3DH is designed for asynchronous settings where one user (“Bob”) is offline
but has published some information to a server. Another user (“Alice”) wants to
use that information to send encrypted data to Bob, and also establish a shared
secret key for future communication.


Is there a way to sign a message so that any subset can be verified?

We can easily see that the signature must be at least as large as the message.  Otherwise, it would be impossible to verify any arbitrary single bit.  Signing  a message with n bits must necessarily must involve a signature that can validate n unrelated 1 bit message subsets.
However, if we assume Bob and Mallory are given copies of the message, there may be opportunities where computations are done over the entire message, but not transmitting the entire message.  This could help reduce the signature size.
You may be interested in Merkle Trees.  I don't know if they are exactly what you are looking for, but they provide some interesting approaches for proving things about contiguous subsets of messages.   In a worst case scenario, you would have to send Victor effectively the entire Merkle tree.  However, for revealing small fractions of the tree, you may be able to keep a large portion of the information out of the message.  You only have to reveal the sibling leaves for every bit you send, which would not reveal the whole message, while still authenticating it as a subset.
There are a few cryptocurrency algorithms out there which leverage this for micropayments.  Alice generates a list of coins, puts them in a Merkle tree, and then gets the top of the tree signed by Victor.  She then gives this signed top to Bob, who authenticates it with Victor (online or offline).  After this point, Alice can send Bob a coin simply by revealing it, and all of the sibling internal nodes required to prove it was part of her list of coins.  These algorithms, of course, strive to be efficient.  They expose the coins in order, so they only ever have to reveal contiguous subsets, not the arbitrary ones you might need.  This keeps the message traffic down to O(n log m) for n coins transferred out of m coins minted.
Another approach would be to carefully select the message that Alice constructs to have the properties you desire, rather than being an arbitrary message.  Zero Knowledge Proofs are full of clever situations where Bob has to demonstrate information about a message while carefully controlling how much information is transmitted.
One thing you should definitely watch out for is whether there is any issue with Eve computing the message from just S and the message traffic between Bob and Victor.  The content of the message could start getting leaked.  If you know the internal node over a group of n bytes, you can brute force those n bytes, recovering a part of the message that hadn't been revealed by Bob.  But if the goal is simply to provide subsets of a verified message to Victor, that may be acceptable.


How measurement error works in PRNG operation?

Unless the measurement error is huge (e.g. you read every bit correctly with probability $p = 0.5$), it doesn't add significantly to the work required to find the key.

To give a concrete example, let us consider a measurement error where we read each bit correctly with probability $p = 0.75$ (and for simplicity, let us assume that the errors are independent of each other, and whether the correct bit was a 0 or a 1).

Then, what the attacker can do is cycle through every possible key, and generate the first 1000 bits of the PRNG with that key, and check if at least 600 of those bits agree with the first 1000 bits of the noisy sample he was given.  With extremely high probability, the correct key will generate a sample with that many bits set, and no incorrect key will.

This procedure still takes $O(2^{|K_s|})$ time, and so all you've done is increase the time required by a constant factor.


What you describe is called proxy mining, and it exists. You basically start your "own" pool, and let your master divide the work.

It's mostly done to have less load on the pool though, it has no computational advantage over having all slaves join the pool.


Cipher recommendation for known-plaintext attack

AES-128 in CTR mode would be more than sufficient. There is no efficient known-plaintext attack publicly known for it. Many others would also do the job.

However, the secrecy of the key depends primarily on the key itself. It should be sufficiently large and sufficiently random, so that it can't be brute-forced.


What is the actual result of a Logjam's DH attack?

Simple description of Logjam
Logjam is a two-step process. First, you take a group and apply a precomputation to it. Most people use one of a few different groups, so breaking a single group effectively breaks every single key exchange done by anyone using that group. If a group is "broken", then any key exchange done with Diffie-Hellman using that group can be broken quite easily,* revealing the shared secret. This is the second step to the process, using values derived from the precomputation to quickly determine the shared secret.
Logjam does not attack any one user's individual key and it does not rely on any information specific to any single key exchange event. In fact, the initial precomputation step of the attack could be performed for a group even if no one has ever used that group before. All it means is that when anyone does use that group, the derived shared key could be passively recovered by an eavesdropping party.
Slightly more accurate description
A simplified view of Diffie-Hellman is that it involves Alice and Bob agreeing on a generator $g$, and a prime modulus $p$. All operations are done modulo $p$, making it a finite cyclic group. Alice generates a secret integer $x$ and sends the result of $g^x$ to Bob. Bob generates a secret integer $y$ and sends the result of $g^y$ to Alice. Now Alice calculates $(g^y)^x$ and Bob calculates $(g^x)^y$. It just happens to be that $(g^y)^x = (g^x)^y = g^{xy}$, so now $g^{xy}$ is the shared secret. DH gets its security from the fact that Eve has access to $g$, $p$, $g^x$, and $g^y$, but is unable to calculate the value of $g^{xy}$. Seems all rosy, right?
Recall that all of the above operations are done modulo $p$. Unfortunately, it turns out that a one-time computationally-intensive calculation done on $p$ allows an attacker to derive information that allows them to calculate $g^{xy}$ from only $g^x$ and $g^y$, despite never having direct access to either $x$ or $y$. They can re-use the information derived from the analysis for any exchange done modulo that same prime $p$.
Full description
https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf
Mitigations
There are three ways to mitigate this attack:

Use a custom modulus - You can generate your own DH modulus instead of an existing group. This would force an attacker to perform an extremely complicated precomputation step tailored specifically to your system, making it impractical to attack. After all, $10,000,000 to break a third of the Internet's key exchange is nothing to a powerful adversary, but it's probably too much to spend on a single target. This is an option if you don't want reduced performance from a larger modulus.

Use a large modulus - You can use an existing but large (2048-bit or greater) group. While the precomputation attacks are still possible and breaking the group would allow mass recovery of shared secrets, the size of the modulus would make it impossible to attack with any modern technology. This is a risky option if technology significantly improves in the near future.

Use elliptic curve cryptography - Finally, you can switch away from finite-field Diffie-Hellman and instead use elliptic curve Diffie-Hellman. ECDH, in addition to being faster and more secure even at smaller key sizes, is not vulnerable to precomputation attacks. It performs calculations as points on a curve, rather than modulo a large prime number (your potentially exploitable group).

* It still requires some serious computing power, don't get me wrong, but it's nothing compared to the initial precomputation step. A powerful ASIC cluster could break each key exchange using the broken group in real time.


Searching for the hash on Google sometimes instantly gives the plaintext. However, that only works for some common hash values.

Other than that, there is no more efficient way than brute force. Even so, you can optimize the brute force algorithm to make it faster. Hashcat can run the attack on GPU's, making it possible to perform many hash calculations in parallel.


Diffie-Hellman key exchange protocol with finite field GF(2^5)

Three words Finite Field Arithmetic. The elements of the Finite Field (Galois field) can be represented by a polynomial, like in this case. We prefer it since it gave us good computing properties.

$GF(2^5)$ is a binary field extension with the base field 2, the binary field. To construct this field we need an irreducible binary polynomial [*] of degree  5[‡]. In your case it is $f(x)=x^5+x^2+1$. The field can be constructed by $GF(2)[x]/x^5+x^2+1$. An irreducable binary poynomial with degree 5 need not be unique, there is only 6 possibilities for constructing $GF(2^5)$ [#].

$f(x)=1+x^2+x^5$,
$f(x)=1+x+x^2+x^3+x^5$,
$f(x)=1+x^3+x^5$,
$f(x)=1+x+x^3+x^4+x^5$,
$f(x)=1+x^2+x^3+x^4+x^5$, and
$f(x)=1+x+x^2+x^4+x^5$

For the binary field extension and we prefer the ones with small degree monomials and with fewer monomials. So, $f(x)=1+x^2+x^5$  is a good choice.

The addition is polynomial addition with the coefficients are reduced to base field. Multiplication is a bit tricky, we need modulo reduction with the irreducible polynomial. In your case, whenever you see $x^5$ replace it with $x^2+1$. In this website, you can see the table for addition and multiplication. For small cases, generating the table and hardcoding it in a table can be helpful, however, be aware of the cache attacks.

One way is multiplying all at once then reduce
\begin{align}
(x^2 + 1)^6 &= x^{12} + 6 x^{10} + 15 x^8 + 20 x^6 + 15 x^4 + 6 x^2 + 1 \\
            &= x^{12} + x^8 + 15 x^4 + 1 \\
     \vdots &= \vdots\\
\end{align}

This is not the preferred method since it can scale too much, especially for large finite fields. The better method is the multiply-and-reduce paradigm as below.

\begin{align}
(x^2 + 1)^6 &= ((x^2 + 1)^2)^2 (x^2 + 1)^2  &&,\text{expand one level } \\
            &= (x^4 + \color{red}{2} x^2 + 1)^2 (x^4 + \color{red}{2} x^2 + 1) && , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= (x^4 + 1)^2 (x^4 + 1) &&,\text{work on left} \\
            &= (x^8 + \color{red}{2}x + 1) (x^4 + 1)  && , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= (x^8 + 1) (x^4 + 1)  && , \text{use } x^5 = x^2+1\\
            &= ((x^5)x^3 + 1) (x^4 + 1) \\
            &= ((x^2+1)x^3 + 1) (x^4 + 1) \\
            &= (x^5 + x^3 + 1 ) (x^4 + 1)&& , \text{use } x^5 = x^2+1\\
            &= (x^2+ \color{red}{1} + x^3 + \color{red}{1} ) (x^4 + 1)&& , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= (x^3 + x^2 ) (x^4 + 1) &&, \text{multiply}\\
            &= x^7 + x^6 + x^3 + x^2  &&,\text{use } x^5 = x^2+1\\
            &= (x^2+1)x^2 + (x^2+1)x + x^3 + x^2 &&,\text{expand } \\
            &= x^4 + \color{red}{2} x^3 + \color{red}{2} x^2 + x &&,\text{use }\color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= x^4+ x &&
\end{align}

And, for the other equation, you can see their equality by; $$(x^3+x)^5=x^5(x^2+1)^5=(x^2+1)(x^2+1)^5=(x^2+1)^6$$

We, actually, use bit vector to process the binary polynomials:

$ (x^2+1)= [00101]$, we can represent with 5 bits since the finite field $GF(2^5)$.

Whenever we see, 1 out of size 5 we reduce it.

$ (x^5)= [1|00000] = [00101]$, the reduction is shift and x-or. We can say, replace the 1 with position 5 with $[0|00101]$ and x-or. Similarly, we can write formulas for
$x^6 = (x^5)x = [01001]$ and
$x^7 = (x^5)x^2 = [10100]$, and so on. In your case 6 should be enough if you multiply one by one.

\begin{align}
[00101]^6 &= [00101]\cdot [00101]\cdot [00101]^4 \\
          &= [10001]\cdot [00101]\cdot [00101]^3 \\
          &= [10|10001]\cdot [00101]^3 \tag{use $x^6$}\\
          &= [11000] \cdot [00101] \cdot [00101]^2\\
          &= [11|11000] \cdot [00101]^2\\
   \vdots &= \vdots
\end{align}

[*] A polynomial is said to be irreducible if it cannot be factored into nontrivial polynomials over the same field. (Wolfram defn.)

[#] The list is taken from Wolfram, too.

[‡] There is a sequence on the number of binary polynomials on the degree; OEIS A059912


Can you explain what is whitelisting in TLS False Start

Is it a list of allowed ciphers stored at the client side?

This list is defined by the application or more likely the implementation. Basically what you do with "False Start" is that you run a normal TLS handshake and if all of the conditions you found are met, you also immediately start sending encrypted application data - before you have finished the authentication with the server, ie awaited his Finished and ChangeCipherSpec. Because you wait for the third message run before making your decision, this means the cipher suite has already been negotiated and thus you can apply your white-listing strategy.

  How is this different from the client's ciphersuite list?

Indeed, these two lists may be identitical but the RFC explicitely states that you want strong security with the picked cipher suite if you want to use "False Start". Now consider what this requirement means: You cannot possibly connect to servers which only support cipher suites you consider "potentially weak", the RFC mentions RSA key-transport as an example for that. So if you'd make these lists equal, yoo wouldn't be able to connect to those servers which is usually undesirable.

For your last question, consider this quote from the RFC:

  Instead, the security goal is to ensure that if anyone at all can
  decrypt the application data sent in a False Start, it must be the
  legitimate peer.

Basically you want to make sure that if you are under attack and you used "False Start", an attacker can't learn anything about the application data, which is why you want to be "extra-confident" in the cipher-suite.


It is the encryption using the key $Y_i$ of the constructed message.

The message consists of key $K_i$ XOR'ed (bit for bit) with the previous key $Y_i$, followed by ${nonce}_1$.

  where $K_i$ is the
     potential session key if the handshake is successful, '${nonce}_1$' is
     pseudo randomly generated nonce specific to one authentication
     session. Both $K_i$ and ${nonce}_1$ is 128 bit each. Total message size is
     256 bit.


Direct sum of Binary numbers In Mixcolumns

You misunderstand $(02) \cdot 10000100$; it is not integer multiplication (resulting in a 9 bit integer); instead, it is multiplication in $GF(2^8)$ (which results in an element in $GF(2^8)$, which can be represented in 8 bits).

AES uses a polynomial representation of $GF(2^8)$, using the polynomial $x^8 + x^4 + x^3 + x + 1$; what this means is that multiplication of two elements can be performed by multiplying the two values (however, disabling all internal carries); and then reducing the product modulo $11b$ (again, without doing any carries).

When we multiply by 2, this can be simplified to "shift all the bits left by 1, and then if the original bit 7 was a one, xor in the value 0x1b, and take the lower 8 bits of the result".

Given that, multiplying by 3 (which is also used as in the Mixcolumns operation) is easy, as $3 \times x = (2 \times x) \oplus (1 \times x)$, and we know how to evaluate both $2 \times x$ and $1 \times x$


Which algorithm would be ideal for ephermal key generation followed by DH key exchange?

Using ECDHE as an example, the steps are like this,

The client sends supported named curved list.
The server chooses a curve and generate key-pair, and sent back curve type and public key.
The client uses the server curve type to generate key-pair, and send back curve type and public key.

Now, both client and server can generate same secret(i.e. pre-master secret in SSL)


How can I get issuerNameHash and issuerKeyHash from PEM or DER certificates?

Expanding on what Maarten shows, openssl asn1parse can display the details, AND can also extract encoded parts of the certificate (or other ASN.1 structure):
>openssl asn1parse -i <cry87661.crt
    0:d=0  hl=4 l= 845 cons: SEQUENCE
    4:d=1  hl=4 l= 565 cons:  SEQUENCE
    8:d=2  hl=2 l=   3 cons:   cont [ 0 ]
   10:d=3  hl=2 l=   1 prim:    INTEGER           :02
   13:d=2  hl=2 l=   1 prim:   INTEGER           :01
   16:d=2  hl=2 l=  13 cons:   SEQUENCE
   18:d=3  hl=2 l=   9 prim:    OBJECT            :sha256WithRSAEncryption
   29:d=3  hl=2 l=   0 prim:    NULL
   31:d=2  hl=2 l=  71 cons:   SEQUENCE
   33:d=3  hl=2 l=  20 cons:    SET
   35:d=4  hl=2 l=  18 cons:     SEQUENCE
   37:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
   42:d=5  hl=2 l=  11 prim:      UTF8STRING        :Root CA RSA
   55:d=3  hl=2 l=  12 cons:    SET
   57:d=4  hl=2 l=  10 cons:     SEQUENCE
   59:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
   64:d=5  hl=2 l=   3 prim:      UTF8STRING        :OCA
   69:d=3  hl=2 l=  11 cons:    SET
   71:d=4  hl=2 l=   9 cons:     SEQUENCE
   73:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
   78:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :NL
   82:d=3  hl=2 l=  20 cons:    SET
   84:d=4  hl=2 l=  18 cons:     SEQUENCE
   86:d=5  hl=2 l=  10 prim:      OBJECT            :domainComponent
   98:d=5  hl=2 l=   4 prim:      IA5STRING         :OCTT
  104:d=2  hl=2 l=  32 cons:   SEQUENCE
  106:d=3  hl=2 l=  13 prim:    UTCTIME           :200212181027Z
  121:d=3  hl=2 l=  15 prim:    GENERALIZEDTIME   :20600202181027Z
  138:d=2  hl=2 l=  71 cons:   SEQUENCE
  140:d=3  hl=2 l=  20 cons:    SET
  142:d=4  hl=2 l=  18 cons:     SEQUENCE
  144:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
  149:d=5  hl=2 l=  11 prim:      UTF8STRING        :Root CA RSA
  162:d=3  hl=2 l=  12 cons:    SET
  164:d=4  hl=2 l=  10 cons:     SEQUENCE
  166:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
  171:d=5  hl=2 l=   3 prim:      UTF8STRING        :OCA
  176:d=3  hl=2 l=  11 cons:    SET
  178:d=4  hl=2 l=   9 cons:     SEQUENCE
  180:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
  185:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :NL
  189:d=3  hl=2 l=  20 cons:    SET
  191:d=4  hl=2 l=  18 cons:     SEQUENCE
  193:d=5  hl=2 l=  10 prim:      OBJECT            :domainComponent
  205:d=5  hl=2 l=   4 prim:      IA5STRING         :OCTT
  211:d=2  hl=4 l= 290 cons:   SEQUENCE
  215:d=3  hl=2 l=  13 cons:    SEQUENCE
  217:d=4  hl=2 l=   9 prim:     OBJECT            :rsaEncryption
  228:d=4  hl=2 l=   0 prim:     NULL
  230:d=3  hl=4 l= 271 prim:    BIT STRING
  505:d=2  hl=2 l=  66 cons:   cont [ 3 ]
  507:d=3  hl=2 l=  64 cons:    SEQUENCE
  509:d=4  hl=2 l=  15 cons:     SEQUENCE
  511:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Basic Constraints
  516:d=5  hl=2 l=   1 prim:      BOOLEAN           :255
  519:d=5  hl=2 l=   5 prim:      OCTET STRING      [HEX DUMP]:30030101FF
  526:d=4  hl=2 l=  14 cons:     SEQUENCE
  528:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Key Usage
  533:d=5  hl=2 l=   1 prim:      BOOLEAN           :255
  536:d=5  hl=2 l=   4 prim:      OCTET STRING      [HEX DUMP]:03020106
  542:d=4  hl=2 l=  29 cons:     SEQUENCE
  544:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Subject Key Identifier
  549:d=5  hl=2 l=  22 prim:      OCTET STRING      [HEX DUMP]:0414D4AA2B2544332349A2A8AF4B4C0EE7AE475683A2
  573:d=1  hl=2 l=  13 cons:  SEQUENCE
  575:d=2  hl=2 l=   9 prim:   OBJECT            :sha256WithRSAEncryption
  586:d=2  hl=2 l=   0 prim:   NULL
  588:d=1  hl=4 l= 257 prim:  BIT STRING

The SEQUENCE beginning at 31 is the Issuer name (and the one beginning 138 is the Subject name, which is the same as the Issuer in this cert because this cert is a selfsigned cert for a root CA) and the BIT STRING at 138 is the subjectPublicKey field within the subjectPublicKeyInfo substructure, which only for a selfsigned cert is the same as the issuer key, so:
>openssl asn1parse -i <cry87661.crt -strparse 31 -out cry87661.name
[snipped]
>openssl asn1parse -i <cry87661.crt -strparse 230 -out cry87661.keyx
[snipped]
>dir cry87661*
21/01/20  19:11             1,224 cry87661.crt
21/01/20  19:27               270 cry87661.keyx
21/01/20  19:13                73 cry87661.name

but these don't match your values:
>openssl sha256 <cry87661.name
(stdin)= e60bd843bf2279339127ca19ab6967081dd6f95e745dc8b8632fa56031debe5b

>openssl sha256 <cry87661.keyx
(stdin)= 89ea6977e786fcbaeb4f04e4ccdbfaa6a6088e8ba8f7404033ac1b3a62bc36a1


IPsec authentication and encryption lgorithms

Your question is kind of broad, but I think it's still more or less answerable.  Let me just address your sub-questions one by one:

  I am looking for the implementation of IPsec security algorithms for both authentication and Encryption. Is there any open source implementation available for the same?

Yes, plenty.  If you specified which platform and/or language you're using, we could point you to some suitable ones, but just off the top of my head, the OpenSSL library is fairly extensive and portable.

  And if someone supposed to implement these algorithms, then what background knowledge is required for someone new in the cryptography world?

It depends a lot on just which kinds of algorithms you want to (re)implement.  Generally, high-level "derived" algorithms like HMAC or basic cipher modes like CBC, which simply build on top of existing crypto primitives, are relatively easy and safe to implement, whereas low-level "primitive" algorithms like block ciphers or hash functions are difficult to reimplement efficiently and securely.

In any case, the standard advice with crypto is that, if you don't have to implement something yourself, don't.  Unless you're only doing it as a learning exercise, that is, and never intend to actually use your code for anything security-critical.

In any case, if you do end up implementing some crypto code yourself (especially, God forbid, if it's low-level), the very next thing you should do is read up on possible attacks against your code, and see if you can break it.  If not, show it to someone who knows more about crypto than you, and see if they can break it.  Repeat until your code gets broken, or you run out of experts to consult. :-)

  Please recommend some links and documents that can help in understanding these algorithms for the implementation.

What you really need, to begin with, is a good introduction to cryptography and data security.  I'm not really the best person to give specific recommendations here, but some books I've seen recommended by other include the Introduction to Modern Cryptography by Katz & Lindell, the Handbook of Applied Cryptography by Menezes, Oorschot & Vanstone, or, if those seem too intimidating in their scope, perhaps Cryptography: A Very Short Introduction by Piper & Murphy.

For learning about specific crypto algorithms, Wikipedia is often a very good starting point, and will typically have links to further material.  If the algorithm is standardized, reading the relevant RFC / NIST SP / other standard is also often helpful.  Many algorithms also have their own semi-official web pages maintained by their developers; for example, if you wanted to learn about HMAC, you could do a lot worse than starting at Mihir Bellare's HMAC page.  And, of course, there's plenty of useful information right here on Crypto.SE, if you just search for it.

  Also suggest some open source implementations of following algorithms: HMAC-MD5, HMAC-SHA1, DES-CBC, Triple-DES-CBC and AES, and the open source projects that have used it.

Those are all very common algorithms, and any half-decent crypto library (such as the OpenSSL library mentioned above) should support them.

  Apart of the one I have listed above which are others algorithms that can be used for IPsec?

I'm not really familiar with IPsec myself, and the Wikipedia page just refers to RFC 4835, which seems to be the authoritative reference.  It's a pretty short and readable document, so I suggest you just read through it.  In particular, sections 3.1.1 and 3.2 list the encryption and authentication algorithms that IPsec implementations MUST, SHOULD and/or MAY support:

    Requirement    Encryption Algorithm (notes)
    -----------    --------------------------
    MUST           NULL [RFC2410] (1)
    MUST           AES-CBC with 128-bit keys [RFC3602]
    MUST-          TripleDES-CBC [RFC2451]
    SHOULD         AES-CTR [RFC3686]
    SHOULD NOT     DES-CBC [RFC2405] (2)

    Requirement    Authentication Algorithm (notes)
    -----------    -----------------------------
    MUST           HMAC-SHA1-96 [RFC2404] (3)
    SHOULD+        AES-XCBC-MAC-96 [RFC3566]
    MAY            NULL (1)
    MAY            HMAC-MD5-96 [RFC2403] (4)

  What are the differences between authentication algorithms (HMAC-MD5 and HMAC-SHA1) and similarly what are differences between encryption algorithms (DES, 3DES, AES)?

In brief:

MD5 is an old hash function that is considered broken for many purposes, although there are so far no known effective attacks on it when used specifically in the HMAC construction.  SHA-1 is also considered somewhat weak these days, although not nearly as weak as MD5, and the NIST now recommends phasing it out (although HMAC is, again, considered an exception).

The hash functions currently recommended by NIST (and mostly by industry consensus) are the SHA-2 family of hashes, which are considered more secure than SHA-1.  There's also an upcoming SHA-3 standard, which has not yet been finalized, but should be due any day now; it's not designated as a replacement to SHA-2, which is still considered secure, but as an alternative to it.

In any case, given the choice between MD5 and SHA-1, you should definitely go with SHA-1.  But it would be better yet if SHA-2 were an option.
DES is an old block cipher from the 1970s, and should no longer be used; its main weakness is simply its short key length, which makes it vulnerable to brute force attacks on modern computers.

3DES, a.k.a. Triple DES, is an encryption scheme built on top of the DES cipher, which effectively doubles its key length, but also triples the time needed to encrypt and decrypt messages.  It's still considered secure, although it's not as efficient as more modern ciphers.

AES is the modern replacement for DES, and the block cipher currently recommended by NIST.  It has several improvements over DES, including significantly longer key length, twice as long block size (which matters for some application involving large amounts of data) and, frequently, higher speed.  In general, if you have no specific reason to use something else, AES is the cipher you should be using these days: it's fast, it's secure, it's widespread and, above all, it's standard.  To slightly misquote an old catchphrase, nobody ever got fired for using AES.


Low level explanation of how a message is sent via RSA

How it is done in practice is that no one uses RSA to encrypt messages. They use RSA to encrypt (and sign) an encryption key, and then encrypt the message with the encryption key. They send the encrypted key and the encrypted message to the other party. The other party uses their RSA private key to decrypt the key, then uses that key to decrypt the message. Furthermore, in practice, they also add padding to the key before encrypting it with RSA.

That said, RSA can indeed encrypt any message that is smaller than the modulus N. So, if your byte stream in the question is smaller than the modulus, you can encrypt it with RSA. If the byte stream were larger than N, you could theoretically break it up into smaller messages and encrypt them individually. The problem with this is RSA is deterministic; so you'd have to add some random padding to make it non-deterministic. Typically people just don't bother with RSA for bulk encryption, however.


Is there a contingency plan in the event of a catastrophic attack on AES?

I'm not aware of any official NIST policy on the matter, so I can only make educated guesses.

I guess new algorithms have sprung up and are already in place. ChaCha20 is used in TLS 1.2 and 1.3. For hash functions, neither SHA-2 nor SHA-3 are depending on AES in any way. The sponge function in Keccak (SHA-3) can also be used as a symmetric cipher (Ketje, Keyak and Kravatte) and - with a bit of tweaking - as MAC (KMAC). So rather than to move backwards I think NIST would simply standardize on existing ciphers together with more modern ciphers based on Keccak.

Although I see merit in the answer of AleksanderRas, I personally don't think that one of the original AES candidates would be chosen as new AES (or FES, for fixed encryption standard). The world has moved on; there are likely more secure and certainly faster block ciphers around. For instance, I could see that Bruce Schneier and the Skein team would choose Threefish over Twofish. Possibly Serpent would make a chance if Rijndael is broken, as runner up with a high security margin. It does seem to have much in common with AES though, so maybe a break could also influence the security of Serpent, even if it does have a high number of rounds.

This brings us to an important final point: possibly a broken AES could simply be fixed by upping the number of rounds. In that case: the king is dead, long live the king. The hardware is there after all, and quite often the number of rounds can be configured. This would make the most sense in the short term and would allow NIST some breathing space to think of a replacement.


Different ways for modular exponentiation $A^E$ with negative A's

For any integer $A$ we have the congruence $A \equiv A + kn \text{ mod } n$ for all integers k. This means a generic algorithm to get $A$ (where $A < 0$) into the range $[0, n)$ would be something like:

function(A):
    while(A < 0):
        A = A + n
    return A

Doing A = A % n will work in some languages as well (e.g. python) but not all languages (e.g. C).