This is a case for public-key cryptography (in the form of digital signatures, or a key exchange algorithm).

In the simplest case, the program (Alice) would know (embedded in the source or in a configuration file) a public key, and the user (Bob) would have the corresponding private key.

Bob would then send the message which should be authenticated, and sign it using the private key. The program (as well as anyone who has the public key) can then verify that the message really came from you.

This authenticated message should include a timestamp and/or nonce, and the program should make sure not to accept the same timestamp/nonce twice (this will prevent a replay attack).

If you want something where the user actually uses a password, have a look at the secure remote password protocol (SRP). In this case, the server stores a password verifyer instead of the password itself, and the exchanged messages are a Diffie-Hellman-like key exchange, which don't give any clue about the password. You also get a shared secret between Bob and Alice, though I'm not sure how secure this is against man-in-the-middle attacks when Alice can't be authenticated due to missing secret.


Elliptic curves with pairings at 128-bit security in libpbc?

The security of pairing-based cryptography relies on the security of the elliptic curve (which is linked to the size of underlying finite field, or "base field") and of the finite extension field being used.

The "Dlog security" column in the linked page is the size of the finite extension field. Its security used to be comparable to the corresponding RSA security; 1024 bits would provide only 80 bits of security. However, The "Dlog security" of the extension fields used in pairings has changed with some recent research, which makes things even more complicated. See Updating key size estimations for pairings, which estimates, for example, that a BN curve with a base field of 451 bits and "Dlog security" of 5532 bits would provide 128 bits of security)

The "Base field size" is related to the elliptic curve security; in this case security is usually half of the field size (to be precise: half the size of the prime-order subgroup). The "type A" curve there would provide 256 bits of security; but since the corresponding Dlog security is only 80 bits, the overall security is only 80.

Considering that, none of the listed benchmarked curves in the page you linked to provide 128-bit security. However, libpbc does support generating curves with arbitrary sizes for some pairing types, so it is possible to generate a pairing with 128-bit security.


How to use CRT to compute 4 square roots while decryption in Rabin Cryptosystem

As first step to compute the four square roots of $c \pmod N$ one can compute the two square roots $\mod p$ and the two square roots $\mod q$ and then using the Chinese Reminder Theorem combine them to the four square roots $\mod N$ where $N = p \cdot q$.

Let's start computing the square root of ciphertext $c \mod p$.
Usually $p \equiv q \equiv 3 \pmod 4$.
So $m_p = c^{\frac{1}{4}(p+1)} \pmod p$.

Proof: $m_p^2 = c^{2\cdot\frac{1}{4}(p+1)}= c{\frac{1}{2}(p+1)} = c \cdot c^{\frac{p-1}{2}} = c \left( \frac{c}{p}\right) = c \pmod p$, because $c^{\frac{p-1}{2}} = \left( \frac{c}{p}\right) = 1 \pmod p$, where $\left( \frac{c}{p}\right)$ is the Legendre Symbol of $c \mod p$ and $c$ is a square (so the symbol is equal to 1).

Similarly: $m_q = c^{\frac{1}{4}(q+1)} \pmod q$.

Now you have the two square roots modulo the two primes numbers $(m_p, m_q, -m_p = p-m_p, -m_q=q-m_q)$.

Consider now the system:
$$\left\{ \begin{eqnarray}
m = m_p \pmod p \\
m = m_q \pmod q
\end{eqnarray}
\right. $$
Using the extended Euclide algorithm you know that:
$p\cdot y_p + q\cdot y_q = 1$ because $\gcd(p,q)=1$.
So multiplying by $m$:
$m\cdot p\cdot y_p + m\cdot q\cdot y_q = m$.

look at the equality $\mod p$:
$$m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m \pmod p$$
but you know that $m = m_p \pmod p$ and $m = m_q \pmod q$so:
$$m_q\cdot p\cdot y_p + m_p \cdot q\cdot y_q = m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m\pmod p$$.

Combining the two possibilities for the square root $\mod p$ with the two possbilities $\mod q$ you'll find the four results you listed.


On the probability of a collision in RFO-rCTR

The key idea here is the blocks within the same message do not collide—message $1$ will have no possible block collisions, message $2$ can collide with the message $1$'s $s(n)$ blocks, message $i$ can collide with message $i-1$'s $s(n)$ blocks or message $i-2$'s $s(n)$ blocks, etc.

In other words, the number of possibly colliding block combinations is given by
$$
\sum_{i=1}^{e(n)} (i - 1)s(n)\,,
$$
which simplifies to $s(n) {e(n) \choose 2}$. We turn this into a probability $$ \frac{s(n){e(n) \choose 2}}{2^{l(n)}} \le \frac{s(n)e(n)^2}{2^{l(n)}}\,.$$


$\;\;\;$ Sure. $\:$ The simplest way is to OTP-encrypt the

$\;\;\;$ output of an almost xor-universal hash family.
$\;\;\;$ That could be used for encrypt-then-MAC, where

$\;\;\;$ the MAC is applied to an ordered pair that indicates

$\;\;\;$ [the message number or how far into the pad to start] and the OTP ciphertext.

$\;\;\;$ (Presumably, the pairing function would be $\;\;\; \langle x,\hspace{-0.03 in}y\hspace{-0.03 in}\rangle \: \mapsto \; $prefixfree$(x)\hspace{.04 in}||\hspace{.04 in}y \:\:\:\:$.)
$\;\;\;$ Yes.
$\;\;\;$ The tightest way I'm aware of to get provable universality while still hopefully being

$\;\;\;$ second-preimage resistant is the trivial construction that just concatenates an output

$\;\;\;$ from a universal hash family with the output from a standard cryptographic hash function.


For the GCM mode polynomial, it's likely that they simply looked it up in a table.  Low-weight irreducible polynomials over ${\rm GF}(2)$ are useful enough that people have spent time compiling lists of them; the one I linked to above (Seroussi 1998) is fairly often cited, and indeed contains the GCM polynomial.

Of course, this just changes the question to how such lists are compiled in the first place.  As the paper linked above notes, the basic procedure is to simply generate successive low-weight polynomials and test them for irreducibility.

The specific test that Seroussi used to generate the linked table was apparently based on Victor Shoup's NTL library, which nowadays can be found here; the GF2XFactoring module in that library provides an IterIrredTest() function that implements "an iterative deterministic irreducibility test, based on DDF."  Conveniently, there are also BuildIrred() and BuildSparseIrred() functions for finding "canonical" irreducible polynomials of a given degree over ${\rm GF}(2)$.

For more details on how irreducibility testing actually works, you might want to take a look at e.g. this answer on math.SE and these slides linked from it (Brent & Zimmermann 2008).  In particular, according to the slides, it would seem that for most practical purposes (i.e. for polynomials of degree less than 100 million or so), a perfectly good way to test if a polynomial $p(x)$ of degree $d$ is irreducible over ${\rm GF}(2)$ is to simply use repeated squaring and modular reduction to test whether $$x^{2^d} \equiv x \pmod{p(x)}.$$

(Ps. There's apparently also a Wikipedia article on factorization of polynomials over finite fields that you might find useful.)


When solving for $x$ in the equation $g^x \equiv h \text{ mod } p$ the idea behind Pohlig Hellman is to solve discrete logs  on group elements with smaller orders and then recombine those results to obtain $x$. For each prime factor $q^e$ of $p-1$ you do the following:

Find an element with order $q^e$. You can do this via $g' = g^{\frac{n}{q^e}} \text{ mod } p$.
Compute $h' = h^{\frac{n}{q^e}} \text{ mod } p$.
Now, via e.g. brute force find $x'$ such that ${g'}^{x'} \equiv h' \text{ mod } p$. Note that since the group order of the group is $q^e$ this should be fairly quick as long as $p-1$ is smooth.

Using your example we obtain:

For $q^e = 2^4$:
$$g_1 = 278, h_1 = 148, x_1 = 12$$
For $q^e = 3^1$:
$$g_2 = 208, h_2 = 128, x_2 = 2$$
For $q^e = 7^1$:
$$g_3 = 79, h_3 = 53, x_3 = 5$$

We now need to use the Chinese remainder theorem to recombine all our $x_i$ to solve for $x$ using the follow congruences:

$$x \equiv 12 \text{ mod } 2^4$$
$$x \equiv 2 \text{ mod } 3$$
$$x \equiv 5 \text{ mod } 7$$

This yields $x = 236$. We can verify this is correct by observing that $15^{236} \equiv 131 \text{ mod } 337$.


What is the entropy per Diceware word if a random symbol is inserted into a random position in the word?

If you add a truly random character into a truly random position of a word (uniformly chosen), you get "entropy of position" + "entropy of character" as addition to the entropy of the word. (Not exactly, it's a bit less). The entropy of character is the size of the possible characters. 64 possible characters would be $log2(64) = 6$ bits of entropy. Entropy of position are the numbers of possible positions where the character can be placed. With a word with a length of 4 characters you can get 5 positions. (length of the word plus 1. "foo" has 4 pssibilities: "?foo", "f?oo", "fo?o" and "foo?".)

Example: You got the word "hello". Now you want to add one character of a possiblity of $26+26+10 = 62$ characters (small and big letters and numbers) into the word. Possible outcome: "h9ello", "helalo", "heXllo", ...
Entropy of "hello": Let say 0, because it is a constant value in this example. Entropy of character: $log2(62) = 5.95$ bits. Entropy of position: $log2(4+1) = 2.32$ bits. Whole entropy: 8.27 bits.
Problem: That's not entirely true, because you lose a bit entropy to a specific effect. Look at the example "hello": You could add an "e" after, but also before the e in the word. It's not possible to distingush this two possibilities ("heello" and "heello"), they are the same. That's one possibility less than we have calculated. You can do this for every letter of the word. Words like "hhhhh" are even worse, because every time the random character is a "h" you can't tell where in the word it was added.


Ok, so the question is how is AES implemented within SPDZ. I'm going to explain the big picture and then whoever is interested in details should check out the original paper here or the code here.

Let's start with the setup: running the AES algorithm requires a 128-bit key $k$ and a 128-bit message $m$. In the generic SPDZ setting $k$ and $m$ are going to be additive shared across the $n$ parties: $k=\bigoplus_{i=1}^n k_i, m=\bigoplus_{i=1}^n m_i$. Namely no one knows the key or the message but they can reconstruct $k$ and $m$ if all parties broadcast their shares.

In your case $P_1$ sends random shares of $m_2, m_3$ to $P_2$ and $P_3$ and fixes $m_1 = m \oplus m_2 \oplus m_3$. Then $P_1$ can set its $k$ share as $k_1 = 0$ since the other parties $P_2, P_3$ can reconstruct the key using $k_2$ and $k_3$.

Next question that comes in mind is in which field must the shares live in. Since the cleartext computation of AES is performed on blocks of size $8$ the authors choose to have $k$ and $m$ split into $\frac{128}{8}$ blocks of $8$ bits. Now parse each share $k_i,m_i$ as $16$ blocks of $8$ bits each where each block lives in $\mathbb{F}_{2^{40}}$.

It's good to keep in mind that on secret data $[x]$:

Linear operations: $z = [x] \oplus [y]$ or $z = [x] \cdot y$ are for free - just local additions or multiplications by scalars.
Multiplications: $[z] = [x] \cdot [y]$ require special pre-processing data as Beaver triples and involves some data sent around between the parties.

Assume there is an embedding $f$ which converts $x \in \mathbb{F}_{2^8}$ to the same element $x$ but in a different field: $\mathbb{F}_{2^{40}}$. Similar for $f^{-1} : \mathbb{F}_{2^{40}} \mapsto \mathbb{F}_{2^8}$. If we have an embedded key and a message: $[f(k)], [f(m)]$ the AES algorithm in MPC looks like this:

ShiftRows, MixColumns, AddRoundKey come for free since they involve additions or multiplications by public scalars - check wiki.
SubBytes where we do $\mathsf{SBox}(x)$ involves first extracting the embedded bits from $\mathbb{F}_{2^{40}}$ by applying $[y] = f^{-1}([x])$, perform $[y^{2^k}]$ by bit-decomposing and shifting bits and then apply the embedding again on $f([y^{2^k}])$ to be able to multiply the squares in $\mathbb{F}_{2^{40}}$.

More details on: given a shared input $[x]$ how can we compute a share of $[\mathsf{Sbox}(x)]$? One can expand the Sbox in polynomial form and compute $[x] \mapsto [x^{254}]$ using Section 4.2 in the paper. To perform $[x] \mapsto [x^2]$ we can bit-decompose $[x]$ and then just move secret bits around to obtain the squaring $[x^2]$ - think how squaring happens in a characteristic two field.

All nice and neat: we can perform squarings (almost) for free by doing a bit-decomposition. Now the troublesome part comes when we need to multiply squarings according to section 4.2 such as $[x^2] \cdot [x^4]$. This is where the embedding $f$ comes into play to allow us to multiply $\mathbb{F}_{2^8}$ elements inside a bigger field $\mathbb{F}_{2^{40}}$.

You might ask: What's the magic that tells us how to construct an embedding $f$? Well, basically just a bit-decomposition and some bit shuffling.

I have skipped some details but I hope you get the gist: embed data to multiply stuff in a larger field, invert the embedding to obtain cheap squarings (or any bit-wise manipulation easier). The implementation uses the approach I told you here with some extra optimizations for switching back and forth between embeddings.


Algorithm design to verify an assertion on encrypted values

There are two natural solutions to your problem.

The first one would be to rely on an additively homomorphic encryption scheme. In such a scheme, given encryptions of two numbers $a$ and $b$, anyone can, given only the public key, homomorphically compute an encryption of their sum, $a+b$ (usually modulo some value $M$, which can be set large enough so that no overflow occurs, given bounds on the values $a,b$).

If the values $(a,b)$ are small enough, this can be instantiated using the ElGamal encryption scheme, with messages in the exponent (decryption then requires computing a discrete log). If the inputs might be large, a good alternative is to use the Paillier encryption scheme, which does not have this small input requirement.

With such a cryptosystem, the protocol you want is straightforward: simply send only encryptions of $a$ and $b$ to the third party, and let him compute the encryption of $a+b=c$ by himself - that way, he is automatically convinced that the third ciphertext indeed encrypts $a+b$.

If you cannot really choose which encryption scheme you want to use, or want to rely on a different encryption scheme for other reasons, an alternative to the above is to use zero-knowledge proofs. After sending the three ciphertexts to the third party, you can perform with this party a zero-knowledge proof that the third ciphertext encrypts the sum of the first two ciphertexts - this will not leak any information about the content of the ciphertexts, appart from the fact that the statement is true. Zero-knowledge proofs for such linear statements are known for most standard public-key encryption scheme (they can in theory be designed for arbitrary encryption schemes, even e.g. AES, but would be a quite inefficient for encryption schemes without algebraic structures), using e.g. standard Sigma-protocols (which you can make non-interactive in the random oracle model if you don't want to require interactions with the third party).


Standard format to store text in LSB steganography?

There is no standard. But since the goal of steganography is undetectability, it is not usual to hide data into consecutive pixels. Steganography hiding data into all the pixels is broken.

Some algorithms use a function that detects areas of the image where the insertion produces less distortion along with a PRNG.

See, for example:
https://hal.archives-ouvertes.fr/hal-00541353/document


Is there any proof for ECDSA signature algorithm?

As pointed out by @SEJPM, you can read more about security proofs for DSA/ECDSA family on this thread.
As for whether there exists an interactive protocol corresponding to DSA/ECDSA à la Schnorr identification/Schnorr signature, not that I am aware of. I would add that this is unlikely for two reasons:

The (unfortunate) reason for coming up with DSA/ECDSA was to bypass the patent on Schnorr signatures. Therefore its design was supposed be different enough from Schnorr.
If there were some kind of a sigma protocol then it is very likely that this would lead to a security proof (at least in the random-oracle model) as there exist standard methods to construct signatures from identification. Since we don't know a proof, one could say that there probably isn't an interactive protocol either (but this argument is very hand-wavy).


Is there a general way to crack this graph cipher?

As stated by @tylo, this cipher can be cracked by simply finding the greatest common divisor for your numbers.

Continuing from your example: if i am encrypting the message HELLO using the key 605, while following along the graph (or what is essentially a matrix) with the intention to spell out my message, i only actually need the calculations for the first two letters to find the key:

H: 805030 * 605 = 487043150
E: 505040 * 605 = 305549200

Taking these numbers one can trivially find gcd(487043150, 305549200)—gcd being the greatest common divisor—e.g. by using a tool like WolframAlpha, which finds the gcd to be 6050 (6050 rather than 605 due to both of the numbers multiplied with the key ending in a zero, thus for this purpose having an unnecessary extra power of magnitude. Removing these zeros would give 605 directly).


Could this be a valid variation of the Schnorr protocol?

As noted by Perseids in a comment to this answer, the formula $s = r + c + x$ would allow an adversary (who has completed the protocol once in the role as verifier with $P$ and already got one valid triplet $t_1,c_1,s_1$) to compute responses to any arbitrary challenge, simply using the formulas $t_2 = t_1$, $s_2 = s1 + c_2 - c_1$.

Your other alternative $s = rc + x$ would however work, given a few additional restrictions:

$c \neq 0$. Since we are working in a prime order subgroup, this implies the existence of a multiplicative inverse $c^{-1}$ modulo the group order $q$. This is not a significant restriction to the original protocol, since $c = 0$ would entail the response $s = r + 0x = r$, which would not prove possession of $x$ and hence be pointless. With the alternative formula, however, $c = 0$ would entail $s = x + 0r = x$, which would leak the private key.
$t$ and $y$ belong to the same prime order subgroup as $g$. This is implicit from the protocol specification, but it might be stressed that $V$ is able to verify that this is indeed the case, by checking that $p, q$ are prime numbers such that $q|p-1$, and that $g^q = t^q = y^q = 1 \bmod p$.
We define $r = log_g(t) \bmod p$ and $x = log_g(y) \bmod p$. The attacker is not required to know the exact value $r$ and $x$ for the following math to work out.

We also need a security claim, in order to define exactly what it is we assume about the original protocol and want to prove with respect to the alternative one. The most appropriate claim would be that an adversary $A$, who does not know $x$ and does not have real-time oracle access to the authentic prover $P$, has only a negligible chance of successfully playing out the protocol with a honest verifier $V$.

It might be noted that an adversary $A$ with real-time oracle access to the authentic prover $P$, would be trivially able to successfully play out the protocol with any honest verifier $V$. Hence, in order not to prove something we already know, we have to assume this is not the case.

Suppose an adversary $A$ is able to impersonate $P$ and provide false proofs of $x$ using the alternative formula. Since $sc^{-1} = (rc + x)c^{-1} = r + xc^{-1}$, such an adversary would also be able to provide false proofs of $x$ using the original formula. Since the latter is impossible, so is the former.

A proof might be outlined as follows:

Let $A$ be an adversary who is able to successfully play out the protocol based on the alternative formula $s = rc + x$, given the restrictions listed above. Let $V$ be a (honest) verifier who expects the $s$ value to comply with the original formula, subject to the same restrictions (in particular that $c \neq 0$). Let $A'$ denote $A$ taking the role of a prover of the $x$ using the original formula.

Now, all we need to do is to add a few steps where $A'$ plays out the protocol steps with $A$ (i.e. himself):

$V$ asks $A'$ to commit
$A'$ asks $A$ to commit and gets a value $t$, such that $t^q = 1 \bmod p$, which $A'$ forwards to $V$.
$V$ replies with a challenge $c$ chosen at random from $\mathbb Z_q^*$
After receiving $c$, $A'$ sends $c^{-1}$ to $A$, gets a value $s$ and sends the response $s' = cs$ to $V$.
Finally, $V$ accepts if $g^{s'} = ty^c \bmod p$.

If $V$ doesn't accept $s'$ as a proof of $x$ given challenge $c$ in step 4, neither would a verifier who expected a response using the alternative formula accept the response $s$ to the challenge $c^{-1}$ as a proof of $x$.

So what does this prove with respect to the security claim? Firstly, assume that the original protocol meets the security claim, but the alternative protocol doesn't. If the alternative protocol doesn't meet the security claim, it means that the adversary $A$ has a non-negligible probability of successfully playing out the above protocol, but since we have just proved that this would mean that $A'$ also would have the same probability of successfully playing out the protocol, this would contradict our original assumption (that the original protocol meets the security claim), and hence it is not possible that the alternative protocol doesn't.


Simple explanation of weak one way function

The part that I find confusing is: $1-1/Q(n)$, does this mean that we can invert all except a polynomial part which we cannot invert?

This is relaxation from Strong OWF, in which, any polynomial time algorithm will succeed in inverting $f$ on random input with negligible probability.

In weak OWF,  any polynomial time algorithm will fail to invert $f$ on random input with non-negligible probability.

  What does this mean in practice?

There is a theorem state as;

Theorem: If there is a weak OWF, then there is a strong OWF. In particular, given a weak OWF $f:\{0,1\}^* \to \{0,1\}^*$, a there is a fixed  $m\in \mathbb{N}$  polynomial time input length $n \in \mathbb{N}$ such that $f'$

$$f'(x_1,\ldots,x_m) = (f(x_1),\cdots ,f(x_m))$$

is a strong OWF. In particular this holds for  $m=2\,n\,q(n)$.

For a proof see

Therefore, in practice, we know at least one way to construct a strong OWF from weak OWFs.


Security (CPA?,CCA?) in Authenticated identity-based encryption

The eprint version has the following to say (adapted for your notation):

  Authenticated-decrypt: [...]
  Check that $s = H_3(\gamma, Msg)$. If not, reject the ciphertext, otherwise output then plaintext $Msg$.

In the attackers case, the decryption oracle would try to check if $s = H_3(\gamma', Msg)$ with $\gamma'=\gamma \oplus H_{2}(a,s) \oplus H_{2}(t,s) \oplus H_2(a, s) = \gamma \oplus H_{2}(t,s)$. This leads to a wrong hash and the oracle rejects the decryption before giving any useful information to the attacker.


Post-Quantum cryptography usability in IoT devices

Can I use Quantum encryption/decryption algorithms in IoT devices such as RaspberryPi, Arduino etc, or should the hardware infrastructure obey in quantum logic?

The question needs to be reformulated as:

  Can I use Post-Quantum encryption/decryption algorithms in IoT devices (..) ?

Yes. They can use such encryption/decryption/key exchange algorithms, designed for security against attacks by quantum computers. Such algorithms are an active research topic, with current candidates currently in a public selection process by NIST. They run on classical computers, and perform the same tacks as today's algorithms. The main functional difference is hopefully increased resistance to cryptanalysis.

Post-Quantum Cryptography tends to be more resource-intensive than the current generation of cryptography: slower computations, larger keys and messages, especially if we compare current parametrization of current algorithms to PKC with their proposed parametrization. But all RaspberryPi and I guess all except the most low-end Arduinos are adequate for many of the Post-Quantum algorithms under consideration.

The skeptical will say: why bother now?

Post-Quantum cryptography does not solve the actual security problems that pleague IoT: sometime abysmally poor security architecture, poor software quality, backdoors, implementation mistakes, side-channel and fault-injection attacks.
Post-Quantum cryptography algorithms are new (with few, not very practical exceptions). And the history of cryptography suggests that it sometime takes years of public exposure to uncover theoretical problems, and that implementation never get entirely safe to side-channel and fault-injection attacks if the attacker is invasive enough.
With parameters in the upper range of current crypto (AES-256 for block ciphers, SHA-512 for hashes, RSA-4096 or ECC cryptography on a large safe curve), current-generation crypto is safe from both classical and quantum computers in the foreseeable future: classical computers currently surpass quantum computers on nearly all tasks (with a few claimed exceptions in simulation of physical phenomena), and there are reasons to believe that cryptanalysis, because it requires exact results on large quantities, is among the problems that require the most difficult advances in quantum computers.

Addition: Quantum Key Distribution (which has next to nothing to do with PKC) is not feasible with the hardware available on current computers and network gear. It does not solve the problem of initial key distribution, nor of recovering from a complete state compromise, and has a poor security track record (see this). It is pointless in an IoT context in the foreseable future.

Advances in quantum technologies impact practical uses of crytography in other ways than Quantum cryptanalysis, QKD and PKC:

They enable increasingly fast, dense, and power-efficient devices, both using crypto and trying to break it. Except for password hashing, the net long term effect is more security against offline attacks.
But sensors based on quantum effects conceivably can be used for improved side-channel attacks extracting the secrets embedded in devices, including IoT and Smart Cards.


Pre-shared keys aren't used on the web. Using asymmetric cryptography and a public-key infrastructure has huge advantages: there's no need to exchange long-term secrets at any point, all the security relies on a few public values (the root CA public keys). Commonly-used web browsers do not support PSK ciphersuites.

Pre-shared keys are meant for embedded clients that have very limited computing power, that only talk to a very small number of servers. Symmetric cryptography is significantly cheaper than asymmetric cryptography, so it's the only way to have secure communication with devices that simply can't perform a signature or signature verification in a reasonable time, or where it would consume a too big fraction of the battery reserved, or where there isn't enough room for the extra code. If a device only communicates to a very small number of peers over its lifetime, it only needs to store those peers' keys, so PKI wouldn't be an advantage on that side. What is saved on the client side has a cost on the server side: the server needs to store all the clients' secret keys and not just one private key.

Pre-shared keys may also be used if some key exchange or key distribution takes place using a protocol other than TLS, and then the exchanged symmetric key is used for TLS. I don't think this is very common though.

Browsers do use session resumption as a performance optimization. Session resumption is effectively equivalent to having a pre-shared key, but this key was shared through a previous TLS session. On the web, the original session always used asymmetric cryptography. Session resumption means that one or both sides of the communication store some confidential data from which the next session's key can be derived. Generally the burden is on the client: the server sends the client a ticket, which is some encrypted and signed data, and the client stores both this ticket and the shared secret for the next session (premaster secret in TLS terminology). To resume a session, the client sends the ticket back to the server, and the server verifies the signature and decrypts the ticket to obtain a copy of the premaster secret.

Saving a session in this way keeps the advantages of the public-key infrastructure. As in any communication system based on hybrid cryptography, the payload is protected using symmetric keys which are ultimately obtained using key establishment methods based on asymmetric cryptography. The client does have the burden of storing the secret key securely between sessions, but this burden is made easier because the client can fail safe and erase the session data whenever it wants: erasing session data is only a small loss of performance, unlike the PSK-only scenario where it means losing the ability to communicate.

Session resumption was added to TLS 1.0 as an afterthought. In TLS 1.3, the key exchange protocol has been revamped, and session resumption is now merged with pre-shared keys. The same principles apply: a web browser would only ever use PSK as a way to resume a session that was started with asymmetric cryptography, whereas tiny embedded systems may support nothing but PSK.


Secure method for encrypting 32 byte private keys

SIV is a mode specially designed for this purpose. SIV-AES would be a good choice, but it has the same issues as AES-wrap; not many implementations. If you use a GCM you should make sure that the IV is unique (if your plaintext is ever not random you would otherwise be in problems).

As for the password based key derivation function: yes, PBKDF2 is good, with a high enough iteration count. For this kind of data though I would really make sure that the pass phrase has enough entropy. You could consider scrypt with a relatively high memory usage and possibly additional key access restrictions / authentication.


Why is a nonce used to initialize Hash_DRBG, HMAC_DRBG, and CTR_DRBG?

What am I missing here?

You could re-use the master secret over multiple invocations and just rely on different nonces.

This may come handy – for example – on embedded hardware without a proper True Random Number Generator.


In CBC mode of encryption, what happen if the IV is changed when it arrives at the receiver end?

For the first block, assuming the noise in the IV is not much, it may be possible to recover part of the plaintext. Say, only one bit of the IV is flipped. In this case, all but one bit (of the first block of) plaintext can be recovered, as the with usual notations $C=E_K(P\oplus IV \oplus e)$, $e$ is a vector of small Hamming weight. By decrypting $C$, Bob gets $P\oplus IV \oplus e$. By the perceived knowledge of $IV$ all but those bits are affected by $e$ can be recovered (but you need to know which bits of the IV are vulernable, otherwise, the plaintext is lost).
For all the subsequent blocks, it will not be possible anymore. Even if $e$ is Hamming weight $1$, assuming the cipher is strong enough, it will make the first block of ciphertext look totally random. When this is fed to the next block, it will produce completely off ciphertext blocks.


Why RSA2048 sign of Intel accelerate card is fast?

Specialized hardware is the answer. This machine uses asynchronous computation, very likely using parallel Montgomery multipliers and a local register of 4096 bits (4096 seems to be the largest key size for RSA, so we can conclude that this is the size of the register). Similar hardware can be found in Smart Card CPU's. These don't go as fast, because they are hampered by low power consumption, TDP, a relatively slow - often 8/16 bit - CPU and large transistor sizes. The solution requires OpenSSL 1.1 to utilize the asynchronous API that the Intel QuickAssist hardware offers.

Newer Intel chips have vectoring instructions that also help to speedup the multiplication and squaring required to perform fast modular exponentiation (the base of any RSA calculation). However, they don't offer a Montgomery multiplier of sufficient size to overtake fully specialized hardware (actually, the use of the vectoring constructions may quickly lead to overheating and scaling down of processor frequencies).

It's unlikely you can beat specialized hardware in software; modular exponentiation is not a cheap operation (it's only fast compared to finding large primes required for RSA key pair generation). Furthermore, you may make a very fast implementation that is not protected against side channel attacks, which is a major requirement for keeping your private key secure.

Note that the specialized hardware is not an RSA accelerator (that the software delivered with the hardware does offer). It performs the mathematical operations more quickly. It can also be used to speed up (EC)DH and (EC)DSA, for instance.


Are there example certificates available for test purposes?

I used the XCA tool. It allows creation of certificates.


In my knowlegde, XTR is a cryptosystem build over $GF(p^6)$. We however use the subfield $GF(p^2)$ to have a compact representation.
I don't know if there are other cryptosystems defined directly on Galois field extention, but using some tools are common. For that, take a look on the operative environment of Weil or Tate pairing.


ECDH anonymous key exchange to avoid PKI

I have figured out a way to use TLS with only a EC key by using DSA instead of RSA. I had not realized you could do DSA with a EC key. My mistake was trying to use RSA to sign the certificate.

Now I can generate my certificate and self-sign it only with the EC key. The peer will simply check to make sure the certificate was signed by the appropriate node ID (which is the same as the EC public key). And that the public key from the certificate is the same as the node ID.

In practice it simply boils down to using the cipher suite TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256 with a custom trust manager.

Thank you both for taking time to answer my question.


Signing/verification between Java and the OpenSSL

Your problem is not with the signature scheme, something else is wrong.

RSA is specified by the RSA cryptography standard, PKCS#1 (mirrored in various RFC's). The PKCS#1 v1.5 padding was introduced in version 1.5 but it persisted in 2.0, 2.1 and 2.2. Those did however introduce a more secure padding scheme called PSS.

Unfortunately nobody calls the signature generation schemes by their true name: RSASSA-PKCS1-v1_5. Both your C code and your Java code seem to use that signature scheme.


What is the maximum size of the plaintext message for RSA OAEP?

The input length of OAEP is directly specified in the standard:

M        message to be encrypted, an octet string of length mLen,
         where mLen <= k - 2hLen - 2

or simply mLen = k - 2 * hLen - 2 if we want to calculate the maximum message size.

Where:

k - length in octets of the RSA modulus n
hLen - output length in octets of hash function Hash
mLen - length in octets of a message M

The key size of RSA is defined as the number of bits within the unsigned modulus representation. So the key size is identical to the modulus size in bits.

So to complete the calculation we have to include k = ceil(kLenBits / 8) where kLenBits is the key size in bits. This can be rewritten as k = (kLenBits + 7) / 8 for integer-only calculations. However, since kLenBits is commonly limited to multiples by eight k = kLenBits / 8 usually suffices.

The same goes for hLen which is practically always the hash output in bits - say hLenBits divided by 8. From here on all calculations will be in octets / bytes.

To calculate the maximum payload of RSA OAEP we then substitute the nLen and hLen by their respective calculations (and <= by = because we're looking for the maximum):

mLen = k - 2 * hLen - 2

becomes

mLen = kLenBits / 8 - 2 * hLenBits / 8 - 2

If we observe this we see that the amount of overhead only depends on the hashlength: 2 * hLenBits / 8 - 2. This makes it easy to write out the possibilities for SHA-1, SHA-2 and SHA-3:

\begin{array} {|l|c|c|}
\hline
\text{HASH} & \text{OVERHEAD} & \text{RSA 1024} & \text{RSA 2048} & \text{RSA 3072} & \text{RSA 4096} \\
\hline
\operatorname{SHA-1} & 42 & 86 & 214 & 342 & 470 \\
\hline
\operatorname{SHA-224} & 58 & 70 & 198 & 326 & 454 \\
\hline
\operatorname{SHA-256} & 66 & 62 & 190 & 318 & 446 \\
\hline
\operatorname{SHA-384} & 98 & 30 & 158 & 286 & 414 \\
\hline
\operatorname{SHA-512} & 130 & \text{N/A} & 126 & 254 & 382 \\
\hline
\end{array}

note that SHA-1 has an output size of 160 (or hLen = 20 in PKCS#1). Probably better to simply include the calculation in your source code if the function to calculate the maximum input size is missing from your crypto library. Of course you want to avoid 1024 bit RSA; I've added it just for when backwards compatibility is required.

Great so now we can finally fill in the numbers as kLenBits = 2048 and hLenBits = 256:

mLen = 2048 / 8 - 2 * 256 / 8 - 2 = 256 - 64 - 2 = 190

so the message has a maximum size of 190 bytes.


Question about TLS v1.2 Ciphers on my Web Server

How is DHE, ECDHE being used with RSA?

[EC]DHE means ephemeral Diffie-Hellman, so the master key is negotiated using DH parameters generated for the session. The server will generate these parameters and sign them via RSA using the private key corresponding to the servers long-term certificate.

  How is CBC, GCM being used with SHA?

CBC and GCM are the modes that the block cipher (AES) will operate in. SHA is the hash function used in the pseudo-random function (generally HMAC) that derives keys from the master key, and in the case of CBC mode also provides message integrity.

  Which one is the better one to use?

GCM is preferred, in general prefer using an AEAD mode of operation (more info on authenticated encryption here).

  Should I used ECDSA instead of ECDHE?

ECDSA is for signing data while ECDHE is for establishing a shared secret e.g. the master key. To use ECDSA you would need a server certificate that uses an ECDSA keypair. These are not very common currently. But if you did have an ECDSA certificate you would use it in conjunction with ECDHE, e.g. ECDHE-ECDSA-AES128-GCM-SHA256.


Why is a bit biased when generated from random $v \in Z_q$ for odd q?

What Peikert is saying here is that you can generate a random bit $b$ by first picking a uniformly random number $v \in \mathbb{Z}_q$, and then setting $b = 0$ if $v \leq q/2$ and $b = 1$ if $v > q/2$.

However, when $q$ is odd there is one more number in $\mathbb{Z}_q$ that is smaller than $q/2$ than there numbers that are larger than $q/2$. I.e., the bit will be slightly biased towards zero.

Put in other words, the probability of $b=1$ will be $\frac{\lfloor q/2 \rfloor}{q}$ and the probability of $b=0$ will be $\frac{\lceil q/2 \rceil}{q} = \frac{\lfloor q/2 \rfloor + 1}{q}$.

Note: Actually, Peikert seems to be using a slightly different "rounding" method. But the same argument applies. You would have more numbers mapping $b$ to $0$ than $1$ (or the other way around).


How to measure Cycles per Byte of an Algorithm?

To perform a good check, please use a large number of iterations (i.e. a for loop) of calls to the cryptographic primitive with your specific data size. Then average these out.

To avoid compiler optimizations, be sure to print out the result after the clock has been stopped. For instance, you could XOR all the outputs together and print that out. Otherwise the compiler may determine that your call has no side effects and simply remove the entire call to SHA-3.

Note that internal operations are usually performed on 64-bit or larger registers, i.e. 8 bytes at a time. It is perfectly possible to have sub-one scores - although I admit that for SHA-3 the value of 0.9 cycle/byte does not seem likely.


Looking at hash output – is Base64 encoding in any way better than HEX encoding?

The algorithms themselves just output binary (i.e. bytes) if you read their specifications. It's the implementation in API's and applications that output the hexadecimals and/or base64.

Sometimes there are also ad hoc standards / common practice that specifies a certain output format. This is for instance the case for the output of the bcrypt password hashing algorithm. In that case it's not just the hash that is displayed but also the type of algorithm, number of iterations and if course salt.

Base64 is more efficient than hex, while hex is easier for humans to digest. The value of the bytes as well as the amount of bytes are just easier to see in hex; the amount of stored bytes is for instance simply half of the displayed hex digits. However for textual formats or indeed larger hash values base64 may be chosen for its efficiency (~33% overhead for base64 vs 100% for hex).

The command line utilities md5sum, sha1sum and their successors have always kept to outputting hex; it's to be expected that hex is therefore more likely to be output by applications that want to remain compatible.

Note that I've changed the case of the terms "Base64" and "HEX" in this answer to lowercase to be compatible with RFC 4648: The Base16, Base32, and Base64 Data Encodings which tries to standardize the encodings. It only uses the uppercase variant in the title. "Hex" is an abbreviation, not an acronym, so all uppercase does not make sense.

Personally I prefer all uppercase for hexadecimals; people recognize the upper part of letters / digits more easily, so it makes sense to use it as default (and on all my old computers the characters were also in uppercase, so they are in most debuggers).


Question about hashing passwords with PBKDF2

The example seemed to show what I needed to do as far as hashing and
  salting my passwords, but I was concerned with using a colon to create
  a split between the iterations, salt, and password.

  Wouldn't that just give clues to someone who would try to hack my
  database as to how I was hashing my passwords?

The security only has to come from the algorithm and the key used, keeping the algorithm or its parameters secret should not be necceasary. That is the principle of Kerckhoff, on of the pillars of modern cryptography.
This means in consequence, that since you are using an algorithm considered secure, it is no problem to show the public parameters to an attacker.

  Also, I am open to hearing others thoughts on which algorithm I should
  be using because there is a lot of information out there and it seems
  like there is nothing conclusive as to which one is the best.

PBKDF2 is fine, but it is not as resilient to attacks with specialised hardware as other schemes. SCrypt is the most well established such algorithm. Another scheme worth mentioning is Argon2. It is the recent winner of the academic Password hashing competition, but due tp its newness it is not as widely used (and implemented) as SCrypt.


Encryption(AES) and verification per message

Idea 1 is similar to what TLS actually does (and begs the question "why aren't you using TLS?").  Modern thought is that it'd be generally better if you first encrypt, and then perform the MAC, as in:

E := AES(M)
Send IV, Encrypted HMAC(IV | Encrypted)

But no radical problem is known with your idea (unless you send M1 and M2 at different times; if you do, you open yourself up to a chosen plaintext attack -- however, that's an issue with CBC mode, not your general idea)
On the other hand, idea 2 is known to be broken; if the messages are longer than 32 bytes, then the attacker can (for example) modify one of the first bytes in the encrypted region that holds M1; on decryption, this would modify the first 32 bytes of M1, but nothing past that.  That is, the encrypted zeros would still decrypt as zero, and so the attacker has managed to modify M1 undetected.


NTRU crypto from unseen.is; myth busting help

I'll comment only the statement referring to an AES-256 replacement with 4096-bit key:

  According to our engineers, this will take 23840 times longer to crack than aes256

Bob writing that is not able to correctly transcribe even the numbers that engineer Alice allegedly spelled: most likely, $23840$ is intended to be $2^{3840}$, which is the ratio $2^{4096}/2^{256}$ of the number of 4096-bit keys to that of 256-bit keys. For reasons that I'll detail, that ratio of number of keys is irrelevant. Bob is incompetent at crypto, or totally gullible, or dishonest (I mean or as inclusive, not xor). And if anyone left Alice with the impression that $2^{3840}$ was a meaningful number, Alice is incompetent or dishonest, and that does not spell well for the system or code Alice designed or wrote.

Thus at least one holds: The FAQ's author is dishonest; it is dangerous to trust the engineer cited by the FAQ as advisor.

AES-256 is a symmetric cipher with a huge key of 256-bit. Remember the tale of the man who asked the sultan as reward for his good services 1 grain or rice on a first square of a checkerboard, 2 on the second, 4 on the third.. and got impaled for having asked $2^{64}-1$ grains of rice, which is orders of magnitude more than the worldwide yearly rice production nowadays? Well, 256-bit instead of 64-bit is like this man asking a checkerboard with 256 squares instead of 64. 64-bit of key was considered quite safe against key enumeration in 1970, and the reasonable optimists about the power of Moore's law agree that 1 year does not quite give 1 bit when it comes to brute force, and that whatever exponential trend there has been has already started to slow. Meaning 128-bit is still safe from key enumeration for the next two decades, and 256-bit is safe from key enumeration for whatever matters to man (the later is even with quantum computers running full gear). Increasing key size to 4096-bit serves no purpose towards the threat of key enumeration, and it is pointless to consider the ratio $2^{4096}/2^{256}$ of keys for whatever security consideration or practical purpose.

Increasing the key size of a block cipher could conceivably serve some other purpose (like making side-channel attacks harder, although the opposite could also occur). But if that was the intend, the extra protection obtained (if any) would not be anywhere near $2^{3840}$, or quantifiable to 4-digit precision (if we trust $23840$).

Fact is, past a certain key size, the time (as in the quoted statement) or effort it takes to recover a key does not depend so much on the key size (at least, not as $2^\text{size}$), but on how the key is generated in the first place, and how well it is protected from later leakage. Over that limit (much less than 128-bit nowadays), a bad RNG, careless storage, a buffer overflow, another side-channel (timing, power consumed..), a fault-injection attack, younamit, are more likely threats to a key's confidentiality than key enumeration is.


Signal vs Telegram in terms of protocols?

Alright, I'll bite.

First, let me propose bounding the discussion to just the core of the protocol.

In particular, let's not get hung up on:

Social engineering attacks
How broadly the end-to-end encryption is applied (i.e. are all conversations in the app encrypted?)
The backgrounds of the inventors and reasoning for inventing the protocol
Metadata leakage (i.e. who is talking to whom, which is pretty much the same between the two protocols)

There's a surprising amount of vitriol floating around the internet on those points, NONE of which is germane to the discussion at hand.

MTProto

EDIT: the following is specific to MTProto 1.0.  MTProto 2.0 has since been released, in late 2017.  Some of the potential problems discussed below have been fixed (ex. they migrated from sha1 -> sha256), while others have not seen updates (ex. MTProto 2.0 still uses IGV).  I encourage people to read the new spec (the url is the same; the content has been updated).  I would also encourage any sufficiently-motivated, enterprising individual to write a new answer that takes into account updates to the protocols. :)

Let's quickly review the basics of MTProto 1.0:

(Full specification for those interested: spec v1 )

The protocol starts with a standard Diffie-Hellman key exchange.  Users can compare a hash of the generated key, exposed as either an image and hex code, for the two parties to exchange over an existing secure channel (preferably, in person).  There was a theoretical vulnerability where the original image wasn't large enough (and hence the key-exchange could be man-in-the-middled by someone with sufficient resources), but that's reportedly been fixed by increasing the size of the images / hex printout.  The session key ("auth_key") is derived from this original key (see the spec for particulars).

The meat of the specification hinges on the message envelope.  Briefly, it takes the payload, prepends a salt and session ID, hashes that (SHA-1), and uses that as the "msg key" (MAC).  This also gets mixed with the auth_key (SHA-1 based KDF) to produce a per-message encryption key (256 bit) and initialization vector (256 bit).  The salt, session ID, payload, and 0-15 bytes of arbitrary padding are then encrypted with AES in IGE mode.  Finally, the auth_key_id, "msg key" (MAC) and encrypted data are concatenated to produce the final message.

Whew.  Actually, the diagram from the spec makes much more sense.

MTProto makes what many cryptographers would consider odd choices.  You pointed out several in your question.

A hash algorithm that's reaching the tail-end of its life (SHA1)
An old attempt at authenticated encryption (IGE), of which the authentication part has long-since been broken, but which MTProto doesn't actually use to provide authentication.
A discouraged mode (MAC-then-encrypt)
Vulnerability to a chosen-ciphertext attack  (which may not have been a choice as such).
A non-standard padding algorithm (which is to say, "append whatever bytes catch your fancy")

Those are the sorts of decisions that give cryptographers the willies - and rightfully so.  They've all been broken in various ways.

However - I'll point out that, just like choosing good primitives doesn't necessarily guarantee a secure protocol, choosing bad primitives doesn't necessarily guarantee an insecure protocol.  Anecdotally, bad primitives have probably lead to insecure protocols more often than good primitives have lead to secure protocols, but that's beside the point.  Bad primitives can still be secure as long as you side-step the parts of them that are broken.

Let's examine that:

Would a break in SHA1 lead to a break in MTProto? (it would probably allow an attacker to forge a single chat message per collision; but we're not quite there yet as of 2016)
Does the known problem with IGE lead to a break in MTProto? (no; they're not depending on the authentication)
Is MAC-then-encrypt used improperly in MTProto? (no)
Does the IND-CCA attack invalidate the security guarantees of MTProto? (the authors admit not, at least tentatively)
Does the padding algorithm make MTProto susceptible to any attacks? (technically yes, since it's used in the IND-CCA attack, but again, it doesn't lead to known plaintext-recovery attacks)

Then why do those choices give cryptographers the willies?  First because of experience: even if two choices are not problems on the surface, they can sometimes interact in non-intuitive ways to result in real problems.  In a sense, problematic choices are anecdotally multiplicative in complexity and probability of breakage.  (By analogy, that's an inherent property of high-dimensional design spaces.)  Also, cryptographers have to think about lots of unknowns: are nation-state attackers using unpublished vulnerabilities in any of those underlying algorithms?  Those are particularly concerning since, again, they can interact badly with other design decisions.

Axolotl / Signal Protocol

The Signal Protocol (formerly known as Axolotl) is, to some degree, an orange to MTProto's apple.  It solves different problems, and is concerned with slightly different security model.

For example, Signal is primarily concerned with key derivation and updates/ratcheting (the Axolotl Ratchet, now called the Double Ratchet Algorithm; DRA for short), while MTProto is primarily concerned with the message envelope format, assuming that key exchange has already taken place via fairly generic Diffie-Hellman.

The goal of the Double Ratchet algorithm is to minimize the impact of compromised keys.  This article explains how it works better than I ever could, but the gist is this:

DRA takes the best properties of DH ratcheting (used in OTR - the "Off The Record" IM protocol) and symmetric key ratcheting (used in SCIMP, the Silent Circle Instant Messaging Protocol).

Breaking that down:

SCIMP uses a (one-way) KDF to derive a new key after every message is sent, and the previous key is promptly forgotten.  This way, if the key is ever compromised, it can only be used to decrypt future messages, not past messages.
OTR renegotiates DH keys for every round-trip of messages between parties, and thus self-heals compromised keys after a round-trip has taken place.  This limits the exposure window, but the window can extend into the past in this case, unlike with SCIMP.

DRA on the other hand, regenerates per-message keys like SCIMP, but also renegotiates the DH keys for every round-trip.

The envelope used in the Signal Protocol is unremarkable (in a good way), when compared with MTProto:

Encrypt-then-MAC (using HMAC-SHA256)
AES in CTR mode, PKCS5 padding (>= version 3, at least)

No red flags there.

A formal analysis showed that the Signal Protocol (then called TextSecure) is vulnerable to an Unknown Key-Share attack, whereby B can trick A into sending message M to C, such that A believes it has actually sent M to B.  The paper suggests a way to mitigate that attack, but I wasn't able to find any information as to whether that change has actually been applied.

Conclusion

In the envelope, Signal uses a simple Authenticated-Encryption (AE) system, whereas MTProto uses a custom wrapper that, through a series of odd choices, doesn't qualify as AE or IND-CCA.  Although there are no known plaintext-recovery attacks in MTProto (yet), those properties could well lead to theoretical (or practical) attacks.

For key derivation, Signal has a good story to tell: compromising the current key will only compromise a set of future messages (possibly zero; until the next message from the other party arrives).  However, in MTProto, compromising the authorization key (which is the closest equivalent key) allows all past and future messages to be compromised.

Personally, I (as a developer) wouldn't use MTProto except if I needed interoperability with Telegram.  The folks behind the Signal Protocol (Open Whisper Systems) have fairly universally been praised for the security of their protocol, which makes it an obvious choice.


Can I use PBKDF2 for authentication and decryption?

It's fine, as others have noted.

However, by invoking PBKDF2 twice (first to check the password, then to derive the actual key), you're essentially doubling a legitimate user's workload, whereas an attacker still only needs to run it once for each guessed password.  Thus, you're cutting the legitimate user's advantage in half, or, equivalently, wasting one bit of password entropy.

(Also, the way PBKDF2 is defined, deriving more than one hash output length of key material is basically equivalent to invoking the whole PBKDF2 function two or more times, so you won't gain much that way.  Other KDFs like scrypt may behave differently in this respect.)

Instead, I would recommend deriving a single "intermediate key" $K_I$ from the password $P$, using PBKDF2 with a suitably high iteration count, and then deriving both the password verification value $V$ and the actual encryption key $K_E$ from the intermediate key using a fast KDF (e.g. PBKDF2 with an iteration count of 1), like this:

$$\begin{aligned}
K_I &= \text{PBKDF2}(P,S,c,\max(\ell_P,\ell_V,\ell_{K_E})) \\
V \,\|\, K_E &= \text{PBKDF2}(K_I,S,1,\ell_V+\ell_{K_E})
\end{aligned}$$

where $S$ is the salt, $c$ is the iteration count, $\ell_P$ is the output length (in bytes) of the PRF used to instantiate PBKDF2, and $\ell_V$ and $\ell_{K_E}$ are the desired byte lengths of the verification token $V$ and the encryption key $K_E$ respectively, and $\|$ denotes their concatenation.

(The reason for choosing the intermediate key length as $\max(\ell_P,\ell_V,\ell_{K_E})$ is that we want the intermediate key to be at least as long as each of the final outputs $V$ and $K_E$, and there's no point in asking for output shorter than what the PRF naturally gives us; in fact, an even better choice could be $\max(\ell_V,\ell_{K_E})$ rounded up to the next multiple of $\ell_P$.)


Yes, this is exactly what a message authentication code is for.  Its job is to prevent an attacker from tampering with your message, or from forging completely bogus messages.  For a secure MAC, it should not matter what these messages contain.

(And no, a secure MAC cannot compromise your key; if it did, it would by definition not be secure, since an attacker could use the key to forge messages.)

However, you probably don't want to use classic CBC-MAC if you can avoid it, since it's not provably secure when used on arbitrary messages.  (It is secure when the messages are prefix-free, i.e. when no valid message can be a prefix of another valid message, but this can be somewhat tricky to ensure.)  It's better to use CMAC or one of the other modern cipher-based MACs (OMAC2, PMAC, etc.) instead; unlike CBC-MAC, these have security proofs that don't require any special assumptions about the messages.

Also note that a MAC does not prevent an attacker from:

blocking or delaying the delivery of valid messages,
re-sending verbatim duplicates of previously captured messages, or
tampering with any metadata (such as sender or receiver IDs) that is not included in the MAC input.

To protect against such attacks, you'll likely want to include an incremental message ID and/or a timestamp in your messages, as well as some way of identifying who sent the message and to whom.  You also need to make sure that these extra fields are actually included as part of the MAC input, so that the attacker cannot change them.

Ps. When combining encryption with a MAC, the reason why we usually encrypt the message first is actually the opposite of what you may think: it's not meant to hide the plaintext from the MAC, but to protect the encryption scheme from chosen-ciphertext attacks by ensuring that only ciphertexts with a valid MAC are ever passed to the decryption code.

(Also, not all MACs are guaranteed to be privacy-preserving, which means that, if you calculate the MAC on the plaintext and then transmit the MAC output unencrypted, an attacker might theoretically learn something about the plaintext just by observing the MAC output.  That said, most commonly used MACs — including CBC-MAC, when used properly — are privacy-preserving.  And in any case, this doesn't matter for you, since you're transmitting the whole message unencrypted anyway.)


A timestamping authority (digital notary)

If you search on "timestamp", "timestamping", and "notary" on Crypto.SE and Security.SE, you'll find lots of references.  I've collected a number of timestamping services that were mentioned in one of those places; this should provide a number of companies and online services you can check out:

http://www.proofofexistence.com/
https://www.btproof.com/
https://www.universign.eu/en/
http://www.guardtime.com/
http://securo.it/
http://www.cryptostamp.net/
http://www.itconsult.co.uk/stamper.htm
https://www.globalsign.com/timestamp-service/

I cannot vouch for or endorse any of those.

See, for instance, the following questions on this site, and the following other resources:

https://security.stackexchange.com/q/19184/971
https://security.stackexchange.com/q/43995/971
How are timestamps verified?
Signature and Timestamp for Long Term Document Archival Question
Timestamping services authorities, utilizing Linked, hybrid and other than PKI schemes
https://security.stackexchange.com/q/24458/971
https://en.wikipedia.org/wiki/Trusted_timestamping
http://tools.ietf.org/html/rfc3161
https://security.stackexchange.com/q/32493/971
https://security.stackexchange.com/q/47289/971

Happy reading!


Password hash contained '\x00' in middle, resulting in ValueError from bcrypt.hashpw

You should not be hashing it before passing to bcrypt, which is designed to do the hashing and key-stretching work itself.
It's choking on the hash result because it's expecting a redundant, mushy, ASCII (or UTF-8), not-rigorous, user-entered string.
Generally speaking, hashing things that might be untrustworthy is good to avoid various numeric vulnerabilities (e.g. the internal SHA-512 ops in Curve25519 to sanitize things) -- but, in this case, you can just trust bcrypt; it's designed to work safely and well when fed a lame, user-created password (and a proper, randomly-generated salt ).

 On further contemplation, though, I believe that the behavior of pyca/bcrypt is actually incorrect here. You are supposed to use a cryptographic hash function to convert passwords which are more than 72 bytes (576 bits) into a size that bcrypt can accept. [This is only for pigeonholing purposes; it IS still designed to safely stretch cryptographically mediocre passwords.]
Looking at the ticket on their tracker, and the changeset which they affirmed as having "fixed" it, it appears that the authors did not actually fix their implementation's oddball behavior, but instead merely updated their documentation to recommend the following workaround:

a common approach is to hash a password with a cryptographic hash (such as sha256) and then base64 encode it to prevent NULL byte problems…

This seems sloppy and bizarre to me; it will, for instance, limit such digests' output to, at most, around 408 bits (with base85 encoding), thus truncating >72-byte passwords to just 51 bytes. I would be very interested to see the opinions of more experienced cryptographers on this.
This doesn't negate the first half of this answer, but it's something to keep in mind. Obviously, even with the workaround, the scheme is still quite secure (the best cryptographic schemes are designed to survive some slip-ups in their implementations); it just doesn't seem completely correct to be applying such arbitrary truncations to the user's password, above and beyond what the author of bcrypt itself applied.

You might want to consider bouncing that 72-byte limit back to your users, if you would otherwise have to truncate longer ones by a minimum of 30% to comply with pyca's implementation quirks. (I'm sure that those who care to max out their password's entropy and are hitting that 72-byte limit would, if they looked into how the sausage is made, ultimately prefer the former.)


I think you overlooked some words in section 9:

  Key re-exchange is performed using whatever encryption was in effect
     when the exchange was started.  Encryption, compression, and MAC
     methods are not changed before a new SSH_MSG_NEWKEYS is sent after
     the key exchange (as in the initial key exchange).

Note that it is better to keep to the naming of the methods within the protocol, i.e. use key re-exchange instead of re-keying. That makes searching and conversation much easier...


What is the most important piece of information in a X.509 certificate?

As fgrieu says in his comment, the answer to this question is ambiguous; it depends on what you use the certificate for.

You can perfectly trust a certificate, without having a CA signature. A CA signature only signifies that whoever trusts the CA, will also trust your certificate.

The public key however is the way with which the owner of the certificate and key will identify their self with. Therefore, I would say that the public key is more important, because a certificate is useless without it.

  This is because basically you can't do anything without having a valid certificate, whereas if public key for some reason is missing, I still think you can digitally sign documents (since it uses private key and not the public one).

Without the public key, nobody will be able to verify your signature, so your signature might as well be random noise.

  I need to know which is the right answer. Thanks!

As I said, there is no "right" answer here; apart from that you actually need a public key to be in there.


How to calculate complexity of ElGamal cryptosystem?

Well, there are some major problems with your code.  Technically, the time estimate of your code is correct (that is, if you insert modulo operations when you update pow1 and pow2), however no one would actually use that algorithm to do ElGamal.

Lets hit some of the issues:

You use an $O(N)$ algorithm to compute $x^N$; in real usage, exponents are huge (perhaps around $2^{256}$), and an algorithm that takes $O(2^{256})$ iterations is utterly infeasible.  In practice, we use an algorithm that performs in $O(\log N)$ operations (modular multiplications), such as this one; this reduces the amount of work to something that can be implemented in practice.
On the less drastic, but still real issue: your code appears to assume that you have the private key $d$ when doing encryption; in practice, you'll start with the public key (which I believe in your code is $y$.
Also, while I'm listing nits, you also need to perform a modular reduction when you compute C1 as well.  Furthermore, you don't need to recompute C1 and C2 in the loop; you're interesting only in the final values, and so you can compute those after you have the final values of pow1 and pow2.

I'm sure there are other issues I missed.  However, the bottom line is that if you really want to compute the time complexity of ElGamal, you need to use the algorithm that we actually implement in practice.


Are there cryptographic hash functions with homomorphic properties?

My understanding is that, for the even more special case where a and b are not only of equal length but some power of two times a fixed block size, all hash tree systems (also called a Merkle tree system or a binary hash chain) meet your criteria.

  E.g. satisfying following relation h(a || b) = h(a) · h(b), where
  h(x) is hash function itself, x || y is concatenation and x · y
  is some hash-specific combination function making single hash given
  two of them.

In particular, the hash specified by the Tree Hash EXchange format (THEX) spec
uses the hash-specific combination function x · y == SHA1( 0x00 || x || y ).
whenever the underlying pieces of text a and b are the same length and are both some power of two times a fixed block size.

When c and d are exactly one block in size,
the tree hash T() used in THEX is defined something like

T(c) == SHA1( 0x01 || c ) # only for 'c' exactly 1 block long
T(d) == SHA1( 0x01 || d ) # only for 'd' exactly 1 block long
T( c || d ) == SHA1( 0x00 || T(c) || T(d) )
            == SHA1( 0x00 || SHA1( 0x01 || c ) || SHA1( 0x01 || d ) )

Typically a block has a size of 1024 bytes; Dan Williams and Emin G¨un Sirer have written a paper on picking an optimal block size.

There are apparently two common ways to avoid the easy collisions described by
" What is the purpose of using different hash functions for the leaves and internals of a hash tree? ":

some Merkle trees -- such as the THEX described above -- use one hash function for the leaves, and a different hash function for the internal nodes.
Other Merkle trees -- such as the one used by BitTorrent -- keep track of both the file length and the root SHA1 hash value, and files are considered "the same" only if both match. This allows them to use the same unmodified SHA1 hash function for both the leaves and the internal nodes. (Some people think of this as a single "tree hash value" that includes two parts, the file length and the cryptographic hash value).

Merkle trees can handle files with size that is not a power of two --
How does a "Tiger Tree Hash" handle data whose size isn't a power of two? --
but if the first file isn't a power of two times the fixed block size, concatenating 2 files doesn't give the nice relationship you wanted between the hash of the two smaller files and the hash of the bigger combined file.


Should I calculate SHA-256 hash of a raw bytes of a token or it's hex encoding?

The encoding doesn't change the output of the entropy source. They are reversible operations. You can use what encoding suits you, change to base64 for transmission and strong on the database, and change to byte is a good choice since, in general, the cryptographic hash functions are accepting bytes to process, so it might better to convert them bytes before applying SHA-256 so that you can get the benefit of the speed of the SHA-256. Base64 or Hex may need more time to hash the same data due to the increase in the length, that is $~3n/4$ in Base64, and $2n$ in Hex for $n$ bytes.
If the CSPRNG has good entropy then you even don't need the SHA-256, or at least 4096-bit token, hashing the output of the source is a good idea, however, if the source needs 4096-bit to produce good 256-bit randomness, there might be a problem there. This, however, really depends on your CSPRNG.


reduces the coefficients of a modulo 3 on NTRU

Reducing mod 3 means indeed reducing each coefficient mod 3, and again we choose the representatives symmetrically around 0, so each coefficient becomes -1,0 or 1 (instead of, which is also possible, 0,1, and 2, or some other choice).

$-7X$ becomes $-X$ because $-7 \equiv -1 \mod 3$. The starting constant 3, becomes 0, and disappears, $-10X^2$ becomes $-X^2$ (adding 9), $-11X^3$ becomes $X^3$, as $-11 \equiv 1 \mod 3$ (add 12 to the left) etc. etc.

Your final example $5X^8$ could become $2X^5$, but also (subtracting 3 again, to get a representative from $\{-1,0,1\}$) the actually used $-X^8 = (-1)X^8$.

So mod 3 is actually a bit more restrictive: replace each coefficient by its unique equivalent value in among -1,0 and 1, not just any representative that would be equivalent to it. As your quote says "It is very important that he choose the coefficients in this way" (not only for 32, also for 3).


What are the typical instance parameters of non-commutative cryptographic schemes?

The most common proposals around non-commutative cryptography have been around braid groups. Its proponents have struggled to find parameter sets that are agreed to resist security analysis. Recent proposals have included the algebraic eraser key establishment system and WalnutDSA, a signature scheme that was entered in the NIST post-quantum crytpography process, but failed to pass the first round.
I don't know if there are currently any proposed parameters for the Algebraic Eraser scheme, but this 2016 paper gives a cryptanalysis of the scheme proposed for ISO/IEC 29167-20 standardisation (the standard was not published). The Algebraic Eraser authors' response is also available.
The WalnutDSA submission can be found on the website of the NIST process (the WalnutDSA website link no longer works), as can the cryptanalysis that led to its non-progression.


We begin with the singular curve
$$
y^2 = x^3 + 17230x + 22699\,.
$$
This curve is singular, as can be immediately determined by its $0$ discriminant. Furthermore, it has a singular point $(23796, 0)$, where both partial derivatives vanish. We translate the curve to have this singular point at $(0, 0)$ by changing variables $(x, y) \mapsto (x - 23796, y - 0)$, after which we obtain the corresponding curve
$$
y^2 = x^3 + 23426x^2\,,
$$
which can be rewritten as
$$
y^2 = x^2(x + 23426)\,.
$$
This curve is a node, not a cusp. A cusp would have, after translation, the form $y^2 = x^3$, because it would have a triple root.

Having the curve in the above form, it becomes easy to solve the logarithm. Because it is a node, we know it maps to a multiplicative group. And because $23426=7020^2$ is a square modulo $23981$, we know it maps to the multiplicative group $\mathbb{F}_{23981}^\ast$, i.e., the integers modulo $23981$. The map is

$$
(x, y) \mapsto \frac{y + 7020x}{y - 7020x}\,,
$$

after which we can simply solve the discrete logarithm over the integers modulo $23981$.

Here's a short Sagemath script that does the transformation and finds the discrete logarithm:

sage: p = 23981
sage: P.<x> = GF(p)[]
sage: f = x^3 + 17230*x + 22699
sage: P = (1451, 1362)
sage: Q = (3141, 12767)
sage: # change variables to have the singularity at (0, 0)
sage: f_ = f.subs(x=x + 23796)
sage: P_ = (P[0] - 23796, P[1])
sage: Q_ = (Q[0] - 23796, Q[1])
sage: # show that the curve is of the form y^2 = x^3 + x^2
sage: print f_.factor()
(x + 23426) * x^2
sage: t = GF(p)(23426).square_root()
sage: # map both points to F_p
sage: u = (P_[1] + t*P_[0])/(P_[1] - t*P_[0]) % p
sage: v = (Q_[1] + t*Q_[0])/(Q_[1] - t*Q_[0]) % p
sage: # use Sage to solve the logarithm
sage: print discrete_log(v, u)
53

This method, and others, are best described in Section 2.10 of Washington's Elliptic Curves: Number Theory and Cryptography.


When reading the paper, it seems that there are three or so properties that make a generic authenticated encryption method:

a generic encryption method and MAC are used;
two different keys are used for both;
two pass encryption is used (generally encrypt-than-MAC).

EAX uses two well defined algorithms: AES and CMAC. So it seems the definition fails on (1). As EAX uses only 1 key it will always fail on (2) as well.

But yes, if you do not consider the special way $\mathcal{N}$ is constructed then EAX outputting just $\mathcal{C}$ could be considered a relatively generic construction when it comes to (3).

Adding it up, I personally think this should be a big NO, EAX is not a generic construction as defined in the paper; and just outputting $\mathcal{C}$ only makes a tiny difference.


Why does HOTP use such a complex truncate function?

It looks to me that the original intent was to make sure that all bits of the hash digest have an equal chance to contribute to the truncated portion.  But one of the properties of a secure hash function is to ensure that a single bit change results in a cascade that yields changing bits across the entire digest.  If you don't trust this property in the hash algorithm, you either have a very weak hash algorithm or a weak understanding of the properties that make a hash algorithm strong.

If any of the input bits to the hash differed originally, at least some of bits in the last four bytes will reflect it, with the expected reduction in collision resistance from $2^{80}$  to $2^{16}$.

So, given a good hash algorithm, it's not "more secure".  At best, it's equally secure.  In the real world, it's slightly more risky (and therefore less secure) because the added complexity offers the chance for a programmer to make an implementation mistake.


Why does NIST say that 2nd preimage resistance depends on the message length

The reference for the claim is here, titled "Second Preimages on $n$-bit Hash Functions for Much Less than $2^n$ Work" by J. Kelsey, B. Schneier.
The attack is specific to un-truncated Merkle-Damgaard hash functions. I haven't understood the mechanism of the attack, but as far as I understood, it require some unrealistically large working memory for the attack to work, and therefore it doesn't affect real-world security of SHA-1/2 hash functions.


Why can ECC key sizes be smaller than RSA keys for similar security?

Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of.

When someone uses the term "discrete log", they can mean two things:

A discrete log in the group $Z^*_p$; that is, given $p$, $g$ and $g^x \bmod p$, recover $x$
A discrete log in some other group; that is, given a group $G$, a generator $g$ and the value $g^x$, recover $x$.

Of course, the precise meaning is given by context.

In this specific case, the quote refers to the first meaning of discrete log; a log over a multiplicative group modulo a prime (and for such a group, there exist subexponential ways of solving it).

However, when we're dealing with the security of an EC group, we don't care about discrete logs modulo $Z^*_p$; instead, we care about the discrete log within the EC group (that is, the second meaning).  These EC groups (or, at least, the ones based on curves that we actually use) do not have these fast methods of solving it; in particular, the number field sieve algorithm does not appear to apply.

And, because the DLOG problem in an EC group is much harder, we can use a smaller EC curve safely.


zkSnarks - why isn't PCD more widely used?

There are two types of overhead in PCD systems:

Overhead of proof verification: Computing the pairings necessary to verify prior proofs is expensive, and adds overhead unrelated to the statement you're trying to prove.
Overhead of predicates: In the Scalable SNARKs paper, each recursion level verifies the execution of the vnTimyRAM CPU. This involves verifying the CPU execution itself, as well as authenticating that the memory accessed during this step is correct. Checking CPU execution is cheap; it requires roughly a thousand gates. Memory checking, however, is very expensive; each access requires verifying a Merkle tree path. While the authors try to mitigate via the efficient Ajtai hash function, the overhead due to this check is still the largest in the circuit.

Together, these overheads are much more expensive per cycle than other approaches for verifying RAM computations; the primary reason to use recursive SNARKs is for the lower memory consumption.


Is encryption possible without secure random numbers?

All secure cryptography requires a secrete key, it can be a symmetric shared secret or an asymmetric key pair with secret private key.
The question is how do you get a secret if there are no secure random number sources.
Note there are natural sources of random numbers which don't rely on cryptography for their security, but the question said the oracle can predict any RNG including predicting radioactive decay and cosmic rays, and the number I'm thinking of. That is an impressive oracle you have there.
If there is no initial secret, and anything we do to try to create an initial secret is detectable by the oracle then anything the legitimate user can do so can the attacker.
A secret is how we differentiate between legitimate users and attacker, the attacker is assumed to not know the secret.
With all secrets given up by the Oracle there is no difference between legitimate and attacker and no secure cryptography.


I'm not sure whether you'd prefer a good academic intro, some practical guides on implementation, or some breaking research in this area, so here are my recommendations for each:

Academic overview: Handbook of Applied Cryptography Chapter 4
Practical implementation guidelines: NIST's Federal Information Processing Standard 186 (especially Appendix B.3.2-6, pp. 53-61), provides several suitable algorithms, very readable, drafted to be easy to follow.
Recent research (including a review of the literature on the topic): Loebenberger and Nüsken compare some available random prime generation methods in "Notions of RSA integers."

As Loebenberger and Nüsken note, several different approaches to RSA key generation are scattered throughout several standards, including IEEE 1363-2000, FIPS 186-3/4, ANSI X9.44, and ISO/IEC 18033-2.

Below is an overview of some of the standards out there, though most readers will be better off stopping here and just reading one of the above three links.

  I. PKCS#1 (aka RFC 3447) (historical note)

PKCS#1--developed by RSA before submission as RFC 3447--is maybe the canonical certification defining RSA implementation, and provides absolutely no guidance on the generation of random primes.

  II. IEEE 1363-2000

I'm reluctant to say too much about 1363-2000 (aka P1363) since the IEEE standard is not free. If you have a copy, key generation for RSA is detailed in Sec. A.16.11, with references to subsections of A.15 for primality testing. Generation of provable primes, probable primes, and recursive construction of primes with an implicit proof of primality are each mentioned, the last of these citing Maurer ("Maurer, U. M. “Fast Generation of Prime Numbers and Secure Public-key Cryptographic Parameters,” Journal of Cryptology 8 (1995), pp. 123-155.") and Mihailescu (Mihailescu, P. “Fast Generation of Provable Primes Using Search in Arithmetic Progressions,” Yvo G. Desmedt, Ed., Advances in Cryptology, CRYPTO ‘94, Lecture Notes in Computer Science 839 (1994), Springer-Verlag, pp. 282-293.) from the mid-90s, as well as Shawe-Taylor (Shawe-Taylor, J. “Generating Strong Primes,” Electronics Letters 22, July 1986, pp. 875-877.), who may also warrant a read for the exhaustive study of the topic.

Most notably, the document recommends a fantastic academic primer to this subject, Chapter 4 of Menezes, van Oorschot, and Vanstone's Handbook of Applied Cryptography (Menezes, A., van Oorschot, P., and Vanstone, S. Handbook of Applied Cryptography, CRC Press, Boca Raton, Florida, 1996.). The HAC, by generosity of the authors and publisher, is available completely free online, and is the best conceptual overview of the issue raised in this question.

Now that I've danced around it enough, the general idea in 1363 is to generate numbers of the form $2k + 1$ for some random $k$ before testing the result for primality. There's a longer algorithm for generating "strong" primes, where a strong prime $p$ satisfies:

$p ≡ 1\ ($mod$\ r)$ for some large prime $r$,
$p ≡{}–1\ ($mod$\ s)$ for some large prime $s$, and
$r ≡ 1\ ($mod$\ t)$ for some large prime $t$.

This maybe begs the question a bit, since you asked about random bit generation, and some random k is required for the basic algorithm here. That part of the algorithm isn't specified likely because it's no longer a component of RSA, we're assuming you have some method to generate random numbers, maybe through a hardware random number generator. This is going to come up in all the methods, generating random bits is prerequisite and separate from generating random primes.

(If you intended to ask primarily about how random bits are generated rather than how random primes are derived from those bits, then at this point you may want to look at hardware random number generators (or more likely your OS, ie, /dev/urandom/ on Unix-like systems or CryptGenRandom in Windows).)

IEEE 1363 also points readers to ANSI X9.31-1998 for "an auditable method of generating primes by incremental search." X9.44 may include the updated version you'd be looking for.

III. FIPS 186-4

(Note: You may see references to 186-3, but this standard was updated in July 2013 to 186-4.)

RSA key generation is introduced in Sec. 5.1 (pp. 22-3), which was updated in -4 to guide the retention (or preferably, destruction) of seeds used to generate random primes. The real meat you're looking for is in Appendix B.3.2-6 (pp. 53-61) though. And while this section is too large to fully detail here, this appendix is probably your best resource for practical implementation guidelines on this question, as it is freely available, clearly written, and very comprehensive as to different methods based on which types of primes you wish to generate (provably prime? probably prime? even... probable primes with conditions based on auxiliary provable primes? et al.). All methods include readable algorithms.

NIST also references ANSI X9.31 and ANSI X9.80, as well as
Special Publication (SP) 800-90A, Recommendation for Random Number Generation
Using Deterministic Random Bit Generators (RBGs), and, SP 800-57, Recommendation for Key Management, further detailing the specifications for suitable RBGs.

In a nutshell, RBGs are rated by security strength, and different applications will require different security strengths. Non-deterministic is better than deterministic? You asked for "state of the art," which could mean the RBGs with the highest security strength, but actually, the real art is allocating the appropriate security strength to the task at hand without going overboard, and in auditing. Auditing isn't sexy, but it's really the important bit.

IV. ANSI X9.44, X9.31, and X9.80, ISO/IEC 18033-2, etc.

Like IEEE 1363-2000, also not free. I think NIST incorporated the relevant ANSI material into FIPS 186-4, though.

NIST's pubs are free, and arguably more straightforward than the publications from the other shops anyway.

V. Other Recent Research

I believe the consensus developed over the last couple decades that the primes should be selected of roughly equal size, as it allows some simplicity in implementation, and the drawbacks have been found insignificant. (I'll dredge up a cite for the comments if there's interest.)

Loebenberger and Nüsken's "Notions for RSA integers" from late 2012 compares some of the methods listed in the standards. It provides a solid baseline for analysis in an area that's easily neglected, and provides through its citations a great review of current literature. It's where I'd head next if I wanted to read every recent piece of research on the topic. Tracked on arXiv as arXiv:1104.4356 [cs.CR].


Can every signature scheme be transformed into a public-key encryption scheme?

No, we know no general way to build a public-key encryption scheme from a signature scheme.
And accordingly, we have some signature schemes with no known way to build a public-key encryption scheme from the same primitives. An example is the eXtended Merkle Signature Scheme, built from symmetric hash and PRF.
[It was not asked, but: I learned from Maeher's comment that we can build a signature scheme from any public key encryption scheme. And I can't tell from memory a public-key encryption scheme that does not have a related  signature scheme built from similar primitives or underlying problem(s)].


Existing works on pre-computing ElGamal ephermal keys

It seems you want to decrypt the final value without revealing the private key. First, if someone knows the private key, they can issue a very simple non-interactive zero knowledge proof that the plaintext is a decryption of the ciphertext (the ciphertext being the accumulation of all the ballots) without revealing the actual value of the key. This is the standard way of approaching the problem. (I can add the proof if you are interested).

Second, the approach of pre-committing to the random factors for Elgamal has been examined in the literature however for completely different reasons. There is a worry that if a voting machine chooses the randomness, they could try a few values until the ciphertext comes out with a certain pattern (e.g., the 5th bit is a 0 if the vote is for Alice and a 1 if it is for Bob). Your scheme incidentally avoids this. A more thorough approach is considered in On Subliminal Channels in Encrypt-on-Cast Voting Systems
.

If you insist on your approach, note that you never need to use $c_1$ at all. $c_2$ alone is a simpler primitive called a Pedersen commitment. The approach of encoding votes with Pedersen commitments, adding them up (under commitment), and then revealing the sum of the random factors is considered in Improving Helios with Everlasting Privacy Towards the Public. The difference is that voters choose the random factor and submit an encryption of it rather than using factors chosen for them. (It also is being done for totally different reasons: Pedersen commitments have a property called everlasting privacy).

In terms of the security of your approach, it is not clear who knows R and how voters get their value of R. For example, if I give voter 5 the value ($R_5$ - 1) and give voter 6 the value ($R_6$ +1), they will still add up to the correct value of $R$. However voter 5's message will be $m^x/k_1$ and voter 6's will be $m^x*k_1$. These may be sensible values for a vote: for example say that $k_1=m^2$. If voter 5 votes for 0, then this can be counted as a -1 and if voter 6 votes for 1, it can be counted as a +3. In other words, you end up with 2 votes for candidate 1 instead of one vote for each.

It may be sufficient to choose $m$ in such a way that no one knows the discrete logarithm between $k_1$ and $m$ but I'd have to think about it some more before endorsing it.


Ways to make a "doomsday" cryptocurrency which becomes untradable

I would generate this key, then encrypt it in such a way that it would take years (but not decades!) to crack, then release it publicly.

Yes, you are in effect putting the master key in a time capsule. The problems of time capsules in general apply: the release time will not be exact and a breakthrough in e.g. CPU design could hasten it. If no one's trying, it may never be broken.

  I also do not know if I would be able to guarantee that I myself don't own the super-key in its unencrypted form.

A simple way would be a nothing up my sleeve number. For example, generate a "random" public key using e.g. the digits of $\pi$ in an obvious way. Have all the relevant information be encrypted using this public key. Then brute forcing the private key will reveal it all. The size of the key will determine the difficulty of breaking it.

The problem is how to make sure the users really encrypt data for that key, instead of pushing some dummy data into the block chain. There is no way to prove a given value makes sense when decrypted, if you don't know the private key.

One option would be to instead of going after accounts, tie the proof of work function to this key pair. E.g. instead of looking for values that hash to a certain kind of value, look for signatures that verify to a given number number of bits. For the owner of the private key that would be trivial, allowing easy 51% control and maybe even flooding the market with coins if you made the difficulty calculations slow enough to adjust.


The problem with a hash function like you ask for is that, if you hash an $n$-bit string and give the hash to someone else, they can recover the string using $n$ hash calculations with a binary search.

For a simple example, let's say the $n=8$, your string is $01011001$ in binary, and its hash is $Y = H(01011001)$.

To recover the string from the hash, I start by calculating $X_1 = H(10000000)$ and comparing it with $Y$.  Since $10000000 > 01011001$, and since $H$ is order-preserving, $X_1 > Y$ and I therefore now know that the first bit of your string is $0$.
Next, I'll calculate $X_2 = H(01000000)$ and again compare it with $Y$.  Since $01000000 < 01011001$, this time $X_2 < Y$, and thus I now know that the first two bits of your string are $01$.
Using this knowledge, the next hash I'll calculate will be $X_3 = H(01100000)$.  Since $01100000 > 01011001$, now $X_3 > Y$, and thus I know that the first three bits of your string are $010$.
The next hash I'll calculate will be $X_4 = H(01010000)$, which I'll compare with $Y$ to find the fourth bit of your string, and so on, until I've recovered every bit of your string.

This flaw is inherent in the idea of order-preserving hashing: if I can obtain the hash of any valid string, then I can always carry out such a search.  In fact, even if I can't get the actual hashes, but can only ask you for the result of the comparison between $H(s)$ and $Y$ for some input string $s$, I can still recover your original string without even seeing its hash value!

Basically, if you ever played the "guess what number I'm thinking of?" game as a child, this is exactly the same situation.  You have a secret string, and I get to guess a string and see if it's less than or greater than your secret.  As in the game, with the right guessing strategy I won't need too many guesses to find the right answer.


ChaCha20-Poly1305: Can my salt/pass for a KDF also be the nonce?

If you have a PSK then you don't need a password. You can just derive new session keys from the PSK, e.g. using a salt within HKDF. It is also possible to derive a key and IV if you're already using a salt. You could also use a counter starting at zero as nonce / IV instead because the resulting key is considered "fresh".

Generally, you simply need a unique key nonce combination for any encryption operation for stream ciphers. If you always apply a random salt to derive both than that requirement is fulfilled, because the key is always fresh. Reusing the salt is however immediately fatal to the security, so the salt should consist of say, 12 bytes / 96 bits or more generated by a secure random number generator.

Using a random salt together with a PBKDF is also possible, but as indicated, I'm not sure if you need a password and therefore a password stretching function such as a password hash / PBKDF.


Yes, AFAIK the original TEA is safe and generally fine when

keys are random (key change should be atomic and with a fresh random key);
the 64-bit block size is not a concern (say, an operating mode other than ECB is used and the key is changed before a gigabyte worth of data);
the relative slowness is not a show-stopper;
side-channels are not an issue, or are taken care of (which is not especially hard; in particular TEA is inherently immune to timing attacks).

I'm not aware of any attack in a random key setup requiring much less work than $2^{126}$ encryptions (as required for brute force given known equivalent keys). The best result I know is Jiazhe Chen, Meiqin Wang and Bart Preneel's Impossible Differential Cryptanalysis of the Lightweight Block Ciphers TEA, XTEA and HIGHT (AfricaCrypt 2012) (alternate link to free, updated paper), which claims success against 17 rounds out of 64. This suggests there is some safety margin.

Vikram R. Andem's thesis (University of Chicago, 2003) also concluded TEA is safe, but the work is a bit outdated.

Answering the comment, reasons TEA is not much used:

TEA came much after DES, which was standard and pushed by authorities (initially, because DES could be broken if needed due to its purposely small key size).
3DES is adequate for many uses, and most importantly is standard.
TEA came significantly after IDEA, which was faster on most CPUs of the time.
The security claims made by David J. Wheeler and Roger M. Needham in TEA, a Tiny Encryption Algorithm (proceedings of FSE 1994) where non-committing ("It is hoped it is safe") and came only with very basic justification.
TEA was not defined in a manner suitable for interoperability: the mapping of octet strings to key and data has no standard definition (if I want TEA test vectors as octet strings endorsed by some official body, I do not know where to look! DES is much better in this regard). Even the number of rounds was not carved into stone: the article says "sixteen cycles may suffice and we suggest 32"; notice that this sentence recommends 64 rounds!
TEA quickly turned out to be vulnerable under related-key attacks. This is not a problem when the key is random, but does not inspire confidence (especially since that, and the trivial equivalent keys, was not considered in the original article).
XTEA was introduced shortly after TEA to fix related-keys attacks; XTEA did not meet its design goals, and needed a correction XXTEA; the later lost some of the simplicity of TEA, and requires slightly more rounds for equivalent security under random key when used as a 128-bit block cipher; also, XXTEA is badly broken in its wide-block variant (essentially because it uses too few rounds), see Elias Yarrkov's Cryptanalysis of XXTEA (2010).
Each TEA key has a trivial equivalent key; normally this is a non-issue (when keys are 8-octet strings, DES is much worse); but amazingly, one of the few notable uses of TEA (as a building block in a poorly designed hash used in the original XBOX) fell precisely because of that!
The above 4..8 tarnished the image of TEA (decision-maker often choose ciphers based on how they perceive its security or professionalism, or even on how they believe customers will perceive the choice!); 5 and 7 even created confusion about what TEA actually is (as illustrated by linking to the wrong algorithm in the initial question, and my mistake about the number of rounds in my initial answer).
In hardware, TEA would be high-latency (and thus slow in CBC, OFB, CFB modes), because of its many rounds; as a mater of fact (and perhaps consequence) there is no hardware for TEA when there is for DES, 3DES and AES, including for the later in many modern CPUs; that often makes TEA much slower than competitors.
Nowadays, 64-bit ciphers are passé.

Note: The most recent related-key attack on TEA that I know is by John Kelsey, Bruce Schneier, and David Wagner, Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA (ICICS 1997); it claims success with only $2^{23}$ chosen plaintexts and single related key query, but of a kind quite unrealistic: the related key swaps the halves of the original, plus other minute changes. However attacks only get better, and any key used for TEA really should be random.


Inversion Free Elliptic Curve Operations

Pick pretty much any projective coordinate system, and there is a plethora of inversion-free addition formulae.  For example, here's a library of inversion-free formulae for addition and doubling in short Weierstrass curves with $a = -3$, which covers all the NIST prime curves and many curves deployed for DH and signatures before Curve25519, using standard projective coordinates: https://hyperelliptic.org/EFD/g1p/auto-shortw-projective-3.html

However, if you want affine coordinates in the end, I don't think you're likely to find a way to avoid inversions altogether—at best you can put off inversions until the end and do only a small number of them, possibly only 1, depending on what you're doing.  E.g., $x$-restricted scalar multiplication on a Montgomery curve—as used by the X25519 Diffie–Hellman function—requires only one inversion at the end of the computation.