What is meant by - computational complexity $2^x$?

The "many attacks" you're referring to, don't exist.
There are two main attacks on AES. One needs related keys and drops security level signifantly (to about the half of the bits).
You're referring to the other one, the biclique attack on AES.

This is the first attack on the full-rounded version of AES (without related keys) that performs better than brute-force. It weakens AES, but only by a mere 2 bits, which is negligible for practical applications.

  What is meant by $2^{126.1},...$?

These numbers identify the workload the attack requires. You need to perform $2^{126.1}$ "steps" to recover the AES-128 key. One step usually means one call to AES-128. The same applies for the other numbers and AES versions.

EDIT: The following paragraph was obsoleted by an edit to the question. The paragraph after this one now fully applies.

  How can I measure it's [my algorithm's] complexity?

First, I think you're using the wrong term. The complexity of an algorithm usually means the run-time the algorithm needs to be performed. (like ~3.5 cycles for AES with AES-NI). The complexity can aswell mean "how complex is it to describe the algorithm", which is usually measured in lines of code.

But from the context you give I assume you mean "How can I measure my algorithm's strength?".
The strength of an algorithm usually is equal to the complexity of the best known attack. So initially this is brute-force making an 128-bit keyed algorithm having a stength of 128-bit or $2^{128}$. Usually attacks sooner or later lower this boundary, whereas usually the impact on homebrew algorithms is rather severe against the moderate advances in the cryptanalysis against AES.


Why are there so many different elliptic curves?

Why is there not just one or two curves that have been widely accepted as useful?

Several reasons; some of it is politics (for example, I suspect a good part of the reason behind national curves is, in fact, national pride), some of it is multiple teams working independently (for example, the Brainpool team, the NUMS time, the people behind the million dollar curves)

However, what can't be discounted is that people have different opinions on what makes a good curve.  Here are some of the highlights:

What sort of prime is the curve based on.  You can define an elliptic curve based on any finite field; recently, people have (mostly) settled on defining them based on large prime fields.  For these curves, a large part of the expense is performing modulo operations based on the large prime.  Now, if we select a prime with a simple binary representation, this modulo operation can be performed much faster than if we selected a random prime.  On the other hand, some people note that these special primes make some blinding operations (important for side channel protection) harder, and so they do prefer random primes.
Lack of suspicious design decisions.  If you look at the NIST curves, they are based on the equation $y^2 = x^3 - 3x + b$ where the value $b$ is a rather odd constant.  Some people worry that $b$ might have been selected to induce an obscure weakness; that's a good part of the motivation for a number of the curves.
Curve equation.  Traditionally, the curves have been based on the Weierstrass equation, $y^2 = x^3 + ax + b$ (for characteristic > 3), which can represent any curve (that is, if you have an EC curve formula, you can find a simple mapping from that to the equivalent Weierstrass curve).  However, some people say that there are advantages to other curve equations (even if they can't represent arbitrary curves); Curve25519 is the most prominent example here.

On the other hand, if we look at what curves people actually use, there isn't that huge of a variety.  We see P256 in wide spread use, we see some uses of P384 and uses of Curve25519 are becoming prominent.  Every other curve would appear to be to be, at least, niche; used for an application or two, but not really that wide spread (at least, in my experience)


Thanks to @kelalaka for pointing me in the right direction.

Let's say you're interested in finding all input pairs $(b^{i}_1, b^{i}_2)$ to the S-box for the input difference $k$ which generate some Hamming distance $l$. Here's how you do it :

  Generate all input pairs such that $b^{i}_2 = b^{i}_1 \oplus k$
  Find out the corresponding output pairs $(f^{i}_1, f^{i}_2)$ and the Hamming distance between these pairs $l_j$.
  Collect all the input pairs $(b^{i}_1, b^{i}_2)$ for the Hamming distance $l$


Why RSA uses {d,n} as private key instead of {e,n}?

The letters d and e are just a notation -- what matters is that there are two exponents, each undoing what the other does, and making one public does not intrinsically reveal the other. By tradition, the one made public is called e.

However, there is a twist: the exponent that is not made public, i.e. the private key, can be really private only if it is sufficiently big. If the private exponent is very small (e.g. it fits on 20 bits), then it is easy to rebuild it from the public key, if only by trying all possibilities. If the private exponent is not so small but still substantially smaller than the modulus n, more advanced attacks are possible, to the same effect (there is an attack by Coppersmith which works as long as the private exponent length is no more than 29% of the length of n).

Conversely, there is no issue in the public exponent being small. That exponent can be as small as the value 3, although, there again by tradition (and also out of a solid dose of historical confusion), 65537 is often used as public exponent. Small exponents promote faster computations. Since the public exponent can be small, we thus make them very small.

So if you generate your key pair and choose both exponents as big numbers (more or less the same size as n), then you can choose either one to be the public exponent (which will be thereafter called e). However, if you selected one of the exponents to be small, then the small exponent shall be the public one, because otherwise your key would be very weak and prone to cracking.

Some widespread implementations of RSA don't tolerate big public exponents; e.g. the one in Windows CryptoAPI, used by Internet Explorer when doing SSL, requires the public exponent to fit on 32 bits.


What is special about an entropy count (RNDGETENTCNT) of 160 for libsodium initialization?

The internal RNG uses a 256 bit seed, and on Linux, a byte is read from /dev/random to check that the pool is seeded.

The reason for requiring 160 bits to be available without blocking is unrelated.

During initialisation, the library reads and discards 32 bits from the RNG to check that it is available and working.

Shortly after, it will need 128 extra bits for the canary protecting guarded memory allocations.

Hence, if 160 bits are not immediately available, sodium_init() will block. This will happen even if the application doesn't need to generate any keys.


Let $n$ be the modulus and $d = \gcd(a,n)$. Then, $ax \mod n$ will be a multiple of $d$. If $d > 1$, this implies that there is no $x$ such that $ax \equiv 1 \pmod n$, and so there is no $x$ such that $f(x) = ax+b \equiv b+1 \pmod n$. So $f$ is not a bijection since it is not surjective.

P.S.: I am not certain how you got the idea of using the word "field" instead of "set", but you should refrain from using it until you have learned what a field is.


Cryptographic hash function for 32-bit length input keys

The question asks for a "cryptographic hash function" with 32-bit input and 32-bit output, such "that by changing even a single bit of the input integer, output varies (preferably drastically in Least Significant Bits)". In cryptographic terms, that criteria is reminiscent of good diffusion of input changes.

The non-cryptographic hash functions linked to in the question only vaguely aim at something similar (if we assume that unsigned is 32-bit, unsigned char is 8-bit, and some conversion from 32-bit input to void *key, int len bound to be messy or dependent on endianness). Many of the proposed constructions do not pass the stated criteria. From a quick glance, at least add_hash, xor_hash, rot_hash, djb_hash, sax_hash, fnv_hash, jsw_hash and elf_hash have the problem that some bit of the input never influence the low-order bit of the output.

Out of my head, here is some simple C code matching the stated objective:

#include <stdint.h>
// some arbitrary permutation of 32-bit values
uint32_t perm32(uint32_t x) {
    int n = 12;
    do // repeat for n from 12 downto 1
        x = ((x>>8)^x)*0x6B+n;
    while( --n!=0 );
    return x;
}

It uses techniques borrowed from cryptography, namely:

multiple rounds with equivalent structure, each performing a transformation of the state x; these transformations are reversible (avoiding a reduction in the number of possible results as the number of rounds grows), non-linear and with diffusion in both directions (insuring overall diffusion), and different at each round; the combination gives high confidence that near-perfect diffusion is reached after some moderate number of rounds, and remains so with more rounds;
x ↦ (x>>8)^x is a reversible transformation with right diffusion (8 allows a speed-up on common low-end CPUs, is high enough that the leftmost bit has traveled to the right in a reasonable 4 rounds, while being low enough that the eXclusive-OR acts on many bits);
x ↦ x*0x6B is a reversible transformation with left diffusion, amounting to repeated addition modulo $2^{32}$ (the multiplicative constant must be coprime with the modulus; 0x6B is high enough that the rightmost bit has traveled to the left in a reasonable 5 rounds, while allowing fast implementation on any CPU with an 8-bit multiplier, and has binary representation 01101011 with some irregularity);
x ↦ x+n for given n is a reversible transformation, introduced so that rounds are different, and x=0 is not a fixed point;
alternating bitwise eXclusive-OR and addition modulo $2^{32}$ results in non-linearity.

I guesstimate from its structure that the function already has fair diffusion at 6 rounds; and with 12 rounds is good enough for almost all uses where using an arbitrary reversible function (rather than an arbitrary function) is fit, and no intelligent adversary is involved.

Applying a cryptographic hash like MD5, SHA-1 or SHA-256, and truncating the output to the first 32 bits, matches the stated objective (in an extremely overkill manner). Each bit in the output is essentially a (different) function of all input bits, that behaves much like a random function among the $2^{(2^{32})}$ such functions, except that it has a short description: being that bit of the output of the hash. Notice that the resulting transformation is not reversible (much likely, some 32-bit outputs are reached for several different 32-bit inputs).

As test vectors for a possible implementation, here is an input-output table showing the effect of changing an input bit starting from input A7000AB9h, for the MD5 and SHA-1 hashes; all values are in hexadecimal.

 input        MD5     MD5 (BE)   SHA-1
A7000AB9    C4D1EA9D  4DDC786B  BF7C439D
A7000AB8    6F8D506F  9415C265  8C104649
A7000ABB    B140436D  60A906F5  607EA4C3
A7000ABD    55D15F80  C500E8C7  A4E02774
A7000AB1    34B3EFD1  D6EA08ED  7A0181D9
A7000AA9    2FBAC43D  CCF97629  E727356B
A7000A99    2D4BCF14  546B1E97  5707C499
(..)
A6000AB9    84DF82C6  E9319225  5DE2A3A7
A5000AB9    0D314C76  0D70D1D8  39DB8C96
A3000AB9    38A46809  62B798C4  BD586E3C
AF000AB9    E4F2D5DE  57A4E8E1  AF434967
B7000AB9    2E0671E2  25EFAE88  8D0C6003

Note: for MD5, I have also shown what happens if Big-Endian convention is used in converting 32-bit integers to octet strings and back rather than the little-endian convention used by MD5, because that's what you'll tend to get when asking the hash of A7000AB9 to an online tool (scroll down for the results).

While the above solves the problem as stated, it might not be what is actually needed in the (unstated) practical situation. In particular, the functions defined here are public, thus anyone can quickly compute them. And because the input is short, it is possible to try all input values to find those (if any) that give a particular output value, even if the transformation is not directly reversible.

Cryptography has other constructs that might be better suited. In particular we have Message Authentication Codes, that accept a secret key, and a message (which would be the 32-bit input, even though it is named key in the question), and outputs an authenticator (that can be truncated as we did for hashes). That would behave much like the above, but some adversary without the key is left totally in the blues about output that is not known from earlier observations. A common suitable MAC would be HMAC-SHA256.


What are the implications of limiting the private key space with elliptic curve Schnorr signatures?

How does reducing the upper limit for $k$ (to $2^n$) improve an attacker's chances to learn $k$

Security becomes at most $n/2$-bit. Baby step - giant step finds $k$ given the public key $\underline{[k]G}$ with computational cost $\mathcal O(2^{n/2})$. Pollard's Rho can be adapted to the same asymptotic cost, with feasibly little memory and efficient parallelisation. In order to keep the security level $\mathcal O(\sqrt\ell)$ of normal EC-Schnorr, we can't have $n$ sizably below $\log_2\ell$.

  How does reducing the upper limit for $k$ from $\ell$ to $2^n$ interact with short Schnorr signatures?

For the reason above, it reduces security.

Also, I fail to see how it reduces signature size in the signature scheme of the question if we keep $r$ random in $[0,\ell)$ with $\ell$ unchanged, because then $S$ also is random in $[0,\ell)$, thus we need to transmit $\left\lceil\log_2\ell\right\rceil$ bit for $S$.

For $n$-bit symmetric security (80-bit in the question), and as small a Schnorr signature as possible, we can

Use an Elliptic Curve group of reduced size $\ell\approx 2^{2n}$. That's precisely why we have secp192r1 and secp192k1 in sec2-v2, which are expected to give 96-bit security. However these use a base field $\Bbb F_q$ of roughly the same size as $\ell$, and I do not know if, much less how, we could construct a secure Elliptic Curve group based on $\Bbb F_q$ of much larger size (e.g. $\log_2 q\approx256$ as asked).
Reduce the hash width from the usual/modern $2n$ to the original $n$, for a $3n$-bit signature when combined with 1. The original Schnorr signature scheme works that way, with heuristic arguments of security that withstood at least the test of time.
As an alternative to 2., and when signing messages of bit size $m\ge n$, use a variant of Schnorr's scheme giving signature scheme with message recovery (see list there), which can embed $n$ bits of message into a $4n$-bit signature, thus achieve an effective $3n$-bit overhead just like the original Schnorr signature scheme in applications where the message is sent along the signature and is at least $n$-bit. The main advantage is a slightly more positive argument of security. The drawbacks are that the signature is no longer separate from the message, that some of the best schemes are patent-encumbered, and that (therefore) this is seldom used.

Note: if only signature size (but not public key size nor performance) is an issue, there is no reason to use an Elliptic Curve group. The original Schnorr signature scheme uses Schnoor groups over a subgroup of prime order $\ell$ constructed as a subgroup of $\Bbb Z_p^*$ for prime $p=2\,r\,\ell+1$, and the signature size is not impacted by the large $p$ (which needs to be in the thousands bits for modern security).

If one is (like me) prudently cautious about the heuristic security arguments (and complex modern proofs in some limited models) of the original Schnoor signature scheme, one can venture into improvements:

De-randomize the choice of $r$ by making it a deterministic PRF, keyed by the $2n$-bit private key, of a (wide, secure) primary hash of the message: $r=\operatorname{PRF}_k(H_\text{wide}(M))$. It removes the requirement for an unpredictable RNG (which is notoriously hard to get), and could only harm thru a side channel. That's used by EdDSA.
Construct the $n$-bit (thus uncomfortably narrow) hash $c$ part of the signature using a purposely-slow hash (like Argon2) in order to increase it's second-preimage resistance, which is one of (and arguably, the main) limiting factor of security in Schnorr signature. It can not harm. Even with parametrization yielding negligible impact on overall performance, it can increase resistance to that particular attack by at least 8 bits, which is nice to have.
Make the public key part of the input of said $n$-bit hash $c$. This is a belt-and-suspenders approach against multi-target attacks. It has negligible cost, and can not harm. Combined with the above, that makes the $c$ part of the signature $c=H_{n\text{-bit, slow}}(\underline{R}\mathbin\|H_\text{wide}(M)\mathbin\|K_\text{pub})$
[my personal fad] Rather than directly using the $n$-bit $c$ part of the signature $(c,S)$ in the computation of $S=r+c\,k\bmod\ell$, we can beef it back to the full $2n$-bit of $\ell$ (as used in modern variants of Schnorr signature having the strongest security arguments) by using a public transformation, e.g. a hash. With maximum belts-and-suspenders, that's $S=r+c'\,k\bmod\ell$ with $c'=H_{2n\text{-bit, slow}}(c\mathbin\|H_\text{wide}(M)\mathbin\|K_\text{pub})$. Arguably, it can't harm, and adds hurdles to various conceivable attacks.

The above leaves the signature size at $3n$-bit, needs only trivial adaptations to signature verification, and marginally slows down signature generation or verification. For large messages, $H_\text{wide}$ is the limiting speed factor, and we can use e.g. SHA-512 for that. Parametrization of the slow hash can be set for cost lower than one scalar multiplication, with perhaps 3/4 of that in the slow hash that builds $c$, and the rest for $c'$.


Authenticated Encryption Sheme with Random Access and proven security?

First, authenticated encryptions based on universal MACs (UMACs) can have their tags computed from blocks of message in random order. This is because UMACs are often based on integer or binary polynomial addition and multiplication, which are associative and commutative operations. Based on this, AES-GCM and ChaCha20-Poly1305 may satisfy your needs.
For these algorithms, recomputing the hash state for 1 block requires some addition, multiplication, and exponentiation, where the exponentiation can be done using square-and-multiply approach.
Second, authenticated encryptions are supposed to operate on whole messages. From your description I sensibly believe this may be some type of XY problem, and you may need to disclose your application blueprint so that we may tell if better solutions to your ultimate problem exist.


Risk of appending secret salt to plaintext prior to RSA encryption?

You are absolutely correct. If you hash or encrypt the password on the client, then pass the resulting digest over an un-encrypted channel, then any man in the middle can simply replay the digest value and log in. The original password is irrelevant now.

What you have effectively done is to turn the digest itself into the password.

The real issue is that you are not using HTTPS to protect your session. The underlying issue is a trustworthy exchange of encryption keys between the client and the server (an offline component of the encryption). This is the exact issue that HTTPS (SSL/TLS) addresses. I'm afraid that by doing your password encryption/hashing on the client and passing the resulting values over a plaintext channel, you're doomed to create a system that is either vulnerable to replay attacks, or too expensive to implement and maintain as a secure system into the future.

Why is HTTPS not an option? If security is the goal, I think HTTPS is probably your only reasonable option.

Your general approach was immortalized in an official Internet RFC 20 years ago, and has been known to be kind of broken for a very long time. Just read about HTTP digest authentication: https://tools.ietf.org/html/rfc2617

Regarding appending a session id... First, what does that matter if the channel is unencrypted and the attacker can just replay the digest (unless you are changing the session id on every call)? Also, there is is no magical session id--if the id is known to the server, then either the server or the client created it and passed it across the wire. So the session id isn't a secret.

To protect this kind of scheme at all, you need to use a nonce. You need to send your encrypted authentication package with every request, and you need to increment the nonce and re-encrypt for every call. That way, the server can see that the nonce is larger than it was on the last request, and thus reject a replay. So now the server has to track that nonce value, per user, in addition to the session id. That becomes more complicated if you have a web garden or server farm, because you have to update that shared state centrally, and that can become a scalability and concurreny issue for your system. And there are still more issues with a scheme like this, which is why one of the factors in the Kerberos authentication schema (for example), is that the server and the client must have their clocks synchronized within 5 minutes of eachother. Among other things, a simple incrementing nonce can leave you vulnerable to attackers with a lot of resources.

You're also doing this in JavaScript in your client, communicating over an unencrypted channel, thus making your system even more susceptible to things like script injection, meaning that some rogue JavaScript in the page could read out values of variables in your security script, including the value of the original password, and phone that information back home to whoever is listening. Do you completely trust every analytics script you include in your pages? Do you completely trust that some new XSS attack can't put a bad guy's JavaScript in your page?

And so on. If you want actual security, you need to implement something more in the league of Kerberos (which is heady stuff), and you probably need to implement it as a browser plugin to provide a bit of a wall between it and other scripts and plugins.

Or you just need to implement HTTPS, and send the password through the encrypted channel to the server, where the server will salt it, hash it (hopefully using an algorithm like scrypt, bcrypt or pbkdf2) and compare it to the digest you have stored on the server.

Otherwise, I'm afraid you're not accomplishing real security.


Is there a way one can combine two correlated hash outputs to maximize the collision resistance?

Collision resistance is a property of a family of hash functions $H_k$ for a key $k$, measured by the probability that a random algorithm can achieve at finding a collision given a random key $k$.  Specifically, it is measured by $$\Pr[x \ne y, H_k(x) = H_k(y)]$$ where $k$ is a uniform random key, and $(x, y) = A(k)$ are chosen by a random collision-finding algorithm $A$.  There are generic algorithms $A$, such as Pollard's $\rho$, achieving probability near 1 with modest memory cost requiring $2^{n/2}$ evaluations of the function, where $n$ is the number of bits in the hashes, and there are various area-time tradeoffs available.  If this probability is negligible for any algorithm $A$ limited to area*time cost below $O(2^{n/2})$, then we call $H_k$ collision-resistant.

Concerning MurmurHash:

First, 64 bits is too small for any useful notion of collision resistance, because it generically takes only about four billion evaluations of a hash function to find a collision, and that cost is affordable on your laptop today—as in, before the end of the day.
Second, MurmurHash2 and MurmurHash3 aren't even collision-resistant in the formal sense, because there are better-than-generic algorithms for computing collisions under any prescribed key.  Actually, it's worse than that: there are pairs of messages that collide under every key in MurmurHash.  For example, 390b2e1717dfba58 and b9e9ba6497bd47a6 collide under every key in MurmurHash2.  The same applies to MurmurHash3 (and CityHash64), and can be extended into $m$-way multicollisions for any $m$ you want.  You can create more of them nearly instantaneously in the privacy of your own living room.

To address the letter of your questions, simply concatenating hash values derived by any iterated hash functions (which is how ~all hash functions are made to work on arbitrary-length inputs, MurmurHash included) fails to achieve collision resistance much better than the individual hash functions alone.  Concatenating $H_k$ and $H_{k'}$ with independent keys $k$ and $k'$ doesn't necessarily give worse than 32-bit collision resistance (which would mean a cost of less than a few tens of thousands of evaluations of the function to find a collision), but it doesn't give much better collision resistance either—it certainly won't even reach 64-bit collision resistance.

But since you're asking about 64-bit non-cryptographic hash functions, I can't imagine you actually want collision resistance.  Here are a couple of alternatives that you might actually want:

You might want a universal hash family, or a $\varepsilon$-almost universal hash family.  This means that for any fixed messages $x$ and $y$, and for uniform random $k$, the collision probability is bounded: $$\Pr[H_k(x) = H_k(y)] \leq \varepsilon,$$ a property which we can often prove of specific constructions.  Note that this implies nothing about the difficulty of finding collisions if you know the key: it is only a bound on the probability of collisions under uniform random unknown key.

This prevents an adversary from furnishing you a data set that will, when you load it into a hash table, have many collisions with nonnegligible probability.  On the other hand, it doesn't prevent an adaptive adversary from measuring timing of hash table operations to learn about the key $k$ and then furnishing in more collisions.  For that you will need a PRF—see below.

You can get smaller collision probabilities by concatenating independent universal hash functions.  Pick keys $k_0$ and $k_1$ independently; if $H_k$ was an $\varepsilon$-universal hash family, then $x \mapsto H_{k_0}(x) \mathbin\| H_{k_1}(x)$ is an $\varepsilon^2$-universal hash family.  Proof: A collision $x \ne y$ means $H_{k_0}(x) = H_{k_0}(y)$ and $H_{k_1}(x) = H_{k_1}(y)$, which, since $H_{k_0}$ and $H_{k_1}$ are independent, has probability
\begin{align*}
    \Pr&[H_{k_0}(x) = H_{k_0}(y), H_{k_1}(x) = H_{k_1}] \\
      &= \Pr[H_{k_0}(x) = H_{k_0}(y)]\cdot\Pr[H_{k_1}(x) = H_{k_1}(y)] \\
      &\leq \varepsilon^2.
  \end{align*}

A variation on this theme is relevant in cryptography for message authentication codes: an $\varepsilon$-almost xor-universal hash family, where $$\Pr[H_k(x) \oplus H_k(y) = \delta] \leq \varepsilon$$ for any $x$, $y$, and $\delta$, and random $k$, makes a good one-time secret-key authenticator.  For example, Poly1305 and GHASH are $\varepsilon$-almost xor-universal hash families with $\varepsilon \lll \lceil\ell/128\rceil/2^{100}$ where $\ell$ is the message length.  AES-GCM uses GHASH in Carger–Wegman's construction to authenticate many messages; NaCl crypto_secretbox_xsalsa20poly1305 uses Poly1305 in a different construction to authenticate many messages.

There are other variations on the theme, like $\varepsilon$-almost pairwise independent hash families, where $$\Pr[H_k(x) = u, H_k(y) = v] \leq \varepsilon^2$$ for any fixed messages $x$ and $y$, any fixed hash values $u$ and $v$, and uniform random $k$.  Zobrist hashes are a popular choice of pairwise independent hash families outside cryptography.
You might want a pseudorandom function family, or PRF.  This means that no cost-limited adversary given oracle access to a uniformly randomly chosen member $H_k$ of the family can distinguish from a uniform random function with the same domain and codomain: $$|\Pr[A(H_k) = 1] - \Pr[A(U) = 1]|$$ is bounded by a small constant, for any cost-limited random distinguishing algorithm $A$, where $U$ is a uniform random function.

Note that the adversary isn't given $k$ here—they are only given $H_k$.  Obviously, they could try to guess $k$ and use the oracle to confirm their guess, but this succeeds with negligible probability as long as the family, i.e. the number of distinct keys, is reasonably large, say at least $2^{128}$.

This implies that even if the adversary knows $H_k(x_1)$, $H_k(x_2)$, $\ldots$, $H_k(x_{m-1})$, that doesn't help them to guess $H_k(x_m)$ for a distinct message $x_m$.  That means that even timing information about hash table operations—revealing when collisions happened—won't let them guess what other keys will also collide.  It also means that a PRF makes a good message authentication code.

Concatenating independent PRFs, $x \mapsto H_{k_0}(x) \mathbin\| H_{k_1}(x)$, does not confer better PRF-security than any one of them alone.  Why?  An adversary need only guess one of the independent keys to win the PRF game and distinguish it from a uniform random function, so the generic security attainable by this construction is at most half the generic security attainable by a PRF with a double-size key.  That doesn't mean concatenating independent PRFs damages security—just that it never provides higher security than one of them alone.

We don't know a way to prove that a hash family is a PRF, but typical examples that we conjecture are PRFs are HMAC-SHA256, keyed BLAKE2, and KMAC.  For short messages and short, ≤64-bit outputs, SipHash is another popular example, particularly intended to replace MurmurHash where it failed to provide security.

P.S. The comments you quoted on the orange site are, unsurprisingly, meaningless nonsense, compounded by the fact that they are responding to a meandering answer to a confused question on another stackexchange, none of which questions, answers, or responses are grounded by, say, articulation of actual goals in a system.


How many blocks can securely be encrypted with XTS

From what I understood, data units are sectors, so a sector can have at most $2^{128}-2$ blocks but you can only encrypt $2^{20}$ blocks which cannot be correct (it seems too little compared to a disk's capacity).

The data unit is the sector, yes, but both of those quotes only talk about the length of a single data unit. The larger number in the latter reference ("shall not"), is an absolute bound, while the second ("should not") is a recommendation.

The recommendation from the second reference is that a sector should be no larger than $128 \cdot 2^{20}$ bits, i.e. 16 MiB. SP 800-38E makes this recommendation a requirement:

  The length of the data unit for any instance of an implementation of XTS-AES shall not exceed $2^{20}$ AES blocks. Note that Subclause 5.1 of Ref.[2] recommends this limit but does not require it.

(The ref above is to the IEEE standard based on the draft spec you linked.)

The total disk capacity encrypted can be much larger, since it consists of many sectors. For recommendations, you can see appendix D.4 of the second specification, where $2^{36}$ and $2^{40}$ (1 TiB and 16 TiB) AES blocks are mentioned.


What if n of RSA is same for two people over the network?

How easy it becomes to attack one's system if you find out that you are using same n as someone else?

I'd be pretty easy to recover someone else's private key, even if they're using a different public exponent e; you know the factorization of n (your private key tells you that), and so it'd be simple to compute the private exponent that corresponds to their public exponent.

As a follow up, you might want to estimate the probability of two people, who are using good random number generators [1], just happen to pick the same value for n, for any secure size of n (hint: how many possible values of p and q are there?)

[1]: this 'good random number generator' cavaet is needed, because we have found duplicated RSA modulii in the field; this happened because they used a bad random number generator (more specifically, bad entropy)


Generating an (EC)DH key pair entails "producing" the group parameters (the curve or the modulus+generator), then the private key $x$, (a random integer modulo the group order $q$), and then applying the private key to the generator (i.e. computing $xG$ on the curve, $g^x \mod p$ for plain DH). Producing new group parameters would be the most expensive operation, especially for elliptic curves; however, there is no security issue in reusing the same group parameters for several key pairs.

Most ECDH implementation focus on a handful of standard curves (a subset of the 15 FIPS curves) and never generate new ones. Generating new group parameters for DH is quite easier, but still expensive, which is why some implementations just reuse a few pre-generated parameters. Thus, the remaining operations for (EC)DH key pair generation are fast; we are in the milliseconds range.

Your code for measuring generation time fails to take into account the idiosyncrasies of Java. The first time an application accesses a class, it must load that class, which entails locating it in the Jar archives, reading it from disk, uncompressing it, decoding the class file format, and launching the initialization code for that class, which may do a lot of expensive things. Then, for each method, the first call to the method triggers the verification which is a flow analysis by which the JVM makes sure that the code complies to the Java typing rules. Finally, the first few invocations of the method will use interpretation; only methods which are invoked sufficiently many times will be translated to efficient native code (this is known as "JIT compilation").

All this translates to the following: to benchmark Java code, you must allow for some considerable "warm up". Also, you will want to run the code several times in a loop so as to get an average execution time because any single invocation can be substantially delayed in case, for instance, of a garbage collector run (the JVM aims at perceived smooth execution, but human beings do not perceive hiccups below about 20ms). So your benchmark code should look like this:

/* warm-up */
for (int i = 0; i < 200; i ++) {
    generateKeyPair();
}

/* find the right number of loop iterations such that we loop for at
   least two seconds */
int num = 10;
for (;;) {
    long begin = System.currentTimeMillis();
    for (int i = 0; i < num; i ++) {
        generateKeyPair();
    }
    long end = System.currentTimeMillis();
    long time = end - begin;
    if (time >= 2000) {
        System.out.printf("average keygen time: %.2f ms",
            (double)time / num);
        System.out.println();
        break;
    }
    num *= 2;
}


HMAC construction based on the combination of two hash functions

This is proabably a bad idea.

There are several results that indicate there are problems with this design:

While $\oplus$ preserves the PRF property, it is not a robust combiner: it requires that $H_1$ and $H_2$ are independent to guarantee the PRF property is preserved.
i.e. consider what happens to your design if $H_2$ is defined as $H_2(2 \parallel data) = H_1(1 \parallel data)$
Boneh06 and Pietrzak07 proved a lower bound on the size for collision resistance preserving combiners, showing that they can't be significantly, i.e. $\theta(log_b)$, smaller than the concatenated size of both hash functions. These papers don't seem to directly address $HMAC$ style key data, but they appear to be quite general results.
Mittelbach13 removed the concatenated size limit for collision resistance preserving combiners, but at the cost of significant time complexity (well beyond the $Comb_{4P}$ combiner introduced in Lehman10 and the combiner you have described) and specific restrictions on the hash functions and the proof.
Part of your motivation for this design appears to be the complexity and expense of the $Comb_{4P}$ combiner, but aside from output size (2 x for $Comb_{4P}$) the schemes appear similar.
i.e. assuming hash functions like SHA-256, with a $block size = 2 \times  output size$, $Comb_{4P}$ requires hashing $M$ with both $H_1$ and $H_2$, followed by 4 further hash blocks and 5 $\oplus$s. With a similar instantiation your design appears to hash $M$ with both $H_1$ and $H_2$, followed by 6 further hash blocks and 1 $\oplus$s.

I'm still trying to get my head round all this, so I could be a little off-base with some of these, but in general this doesn't appear to be an area where easy shortcuts can be taken.

I'm not quite sure what to make of the $HMAC_{H0}(k_0,m) \oplus HMAC_{H1}(k_1,m)$ construction described by Ricky Demer - it looks like it would preserve the PRF properties well, but on the surface it seems to violate the Boneh result on the lower bound for a combiner that preserves collision resistance.


Quoting the obvious (Wikipedia article about the term “security parameter”.)

In cryptography, the security parameter is a variable that measures the input size of the computational problem. Both the resource requirements of the cryptographic algorithm or protocol as well as the adversary's probability of breaking security are expressed in terms of the security parameter.
The security parameter is usually expressed in unary representation (for example, a security parameter of $n$ is expressed as a string of $n$ 1s) so that the time complexity of the cryptographic algorithm is polynomial in the size of the input.
For example, in the RSA cryptosystem, the security parameter $k$ denotes the length in bits of the modulus $n$; the positive integer $n$ must therefore be a number in the set ${0, …, 2^k - 1}$.

Also note that the parties and adversary are assumed to run in time that is polynomial in the security parameter, and that security must hold except with probability that is negligible in the security parameter.


Which attacks are prevented by the different initial hash values for SHA-2 with truncated output?

The question's citation is likely the reason why it was chosen different initial starting values for SHA-2 variants of the same internal block size. It is a valid objective by itself that different hash functions yield independent results, linkable only knowing their common input. It is not necessary to have a specific attack in mind to make that conservative choice.

Otherwise stated: For an attacker knowing the SHA-1 of some secret, the best option to find the SHA-256 of that secret is to find the secret. Using different initial values makes it such that the same holds if the attacker knows the SHA-224 hash instead of the SHA-1 hash. That could be called (domain) separation of hash functions.

It is easy to construct artificial protocols where this precaution saves the day. For example: Alice draws a 80-byte random string $S$, reveals its SHA-224 (say, as a commitment or a Key Check Value), then uses $S$ as an HMAC key with SHA-256 as the underlying hash. HMAC will start by hashing $S$ with SHA-256, then use that as its internal key. With the different initialization values in SHA-224 and SHA-256, Alice is safe. Without, she's headed for disaster, as all but 32 bits of the HMAC key coincide with the leaked SHA-224.


Elliptic Curve-based Diffie Hellman: How is the shared key (mnp) calculated?

So my question is, how do you calculate $mnP$?

For Michael, he takes the value $nP$ he received from Nikita, and adds it to itself $m$ times; that is, it's $\underbrace{nP + nP + \dots + nP}_\text{$m$ times}$, that is the value $m(nP)$.

And, of course Nikita takes the value $mP$ he received from Michael, and adds it to itself $n$ times; that is, it's $\underbrace{mP + mP + \dots + mP}_\text{$n$ times}$, that is the value $n(mP)$.

And, because we perform these operations in a mathematical group (that is, associativity holds), we have $m(nP) = n(mP) = mnP$, so they come up with the same value.


plaintext and its encrypted version known

If it is a long text and you are sure it is a substitution cipher there are a lot of statistical methods to find the key.
Statistical methods rely on the frequency at which alphabets occur in a language. Not just single alphabets but even pairs. For eg in the english alphabet 'E' is the most frequent alphabet followed by 'T' and 'A'. Also some characters such as 'CH' 'QU' 'TH' are found together frequently. All these results can be used to identify the key for the substitution cipher. The longer the text you have the easier it is to identify these patterns.
There are quite a few tools online that help you analyse these patterns.
Also as mentioned in another answer if you already have parts of the plain text too it is trivial to find the mapping of those characters.

Detailed explanation:
http://people.csail.mit.edu/hasinoff/pubs/hasinoff-quipster-2003.pdf

simple explanation:
http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/


What is the difference between a 'cipher' and a 'mode of operation'?

A mode of operation is an explicit method by which we use a block cipher (eg AES) to do more than just encrypt one block of data. For example, it may allow us to encrypt multiple blocks of data (eg ECB,CBC etc), provide us with some authenticated encryption (eg GCM) or a method for encrypting disc storage (eg XTS).

Rijndael,DES etc are block ciphers. That means they provide a method for encrypting a fixed amount of data (in the case of AES, they encrypt blocks on 128 bits).

In practice, the amount of data you want to encrypt is often much larger than the block size. So, we either need to create more and more block ciphers of almost every size, or we come up with a way of using our block cipher to encrypt larger amounts of data.  This method is called a mode of operation.

To use the most simple case as an example, consider AES in ECB mode. ECB mode tells us that we need split our plaintext string into sections of 128 bits (possibly after some padding scheme). Then, each section is encrypted using AES, and the resultant encryptions are then concatenated to form our output ciphertext.
AES simply performs encryptions of the plaintext blocks we give it, whereas ECB allows us to encrypt arbitrarily large amounts of data.

For descriptions of many different modes of operation and a discussion of their merits/weaknesses, you might be interested in this paper by Rogaway, and section 2.3 provides his formalisation of a mode of operation.


There have been several attacks against Keeloq.  I cannot speak to the specific algorithm changes through the years to make it stronger against brute force; however, I am knowledgable in the hardware changes as of discussions I was privy to in 2009.   The Keeloq ICs were changed shortly after the power attacks came out to make them immune from power attacks through the use of dual rail encoding.  At the time, the core of the Keeloq ICs are based on the PIC12, which are very simple and could allow power attacks if you could instruction step them. Through dual rail encoding, you use the same amount of power in all data cases, but not necessarily instruction cases.   Even though the PIC12s are only one-time-programmable, you can still hook them onto a debugger to single-step them.  If you are interested on how this could be done, see if you can get the course notes from Tom Collins for his lab.


Should the identity of a sender be verified using additional means, or does a MAC suffice?

It is a recurring topic: what exactly is identity and how to prove it ?  But related to your question: a MAC (correctly implemented) proves that the author of the message was in possession of the secret key (like you are, if you can verify it).  Now, depending on the application you have in mind, that's a good enough proxy of identity, or it isn't.

In other words, a MAC takes as assumption that you trust that only the right entities have knowledge of the secret key (you included), and then prove that the message could only have been signed by one of these entities.  The question of whether the right entity has the knowledge of the key is then another issue.


Is the subset of hash digest collision-resistant if hash function is collision-resistant?

OK, assuming a setup whereby even if the location of the $k$ bits are unknown the guess or is told by an honest party whether his guess is correct, one can say the following.

Define a collision resistant hash with $n$ bit output as one which requires $O(2^{n/2})$ guesses before finding a collision.

If there was a way of finding a collision in an arbitrary $k$ bit subset in time strictly less than $O(2^{k/2})$ the the overall time would be reduced by attacking, say the $k$ bits and the remaining $n-k$ bits separately (in time strictly less than $O(2^{(n-k)/2})$) getting an overall attack time strictly less than $O(2^{n/2}).$

If $k$ needed to be bounded by some function of $n$ you could get the same result by partitioning into $\lceil n/k\rceil$ subblocks of length $k$ each.

If the multiplicative speedup factor for a k bit block was $2^{-\theta k}$ with $\theta \in (0,1),$ your overall speedup would be
$$
2^{-\lfloor n/k \rfloor \theta k}
$$

approaching

$$
2^{-  \theta n}.
$$
If the weakness was local for a specific $k$ bits, the saving would only be

$$2^{-  \theta k}$$
but still contradict the definition of collision resistant $n$ bit hash function.


80-bit collision resistance because of 80-bit x87 registers?

Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.

I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU.  Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout.  In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs.  You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.

Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation.  If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger.  MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up.  At NIST 8114, we've had the discussions but I've never seen these discussions formalized.  In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption.  Encryption often takes a backseat to economics in the same way that security does to convenience.


Understanding Lindell's proof of (semi-honest) oblivous transfer

The answer is that it's me and not you. There was a typo in the proof and indeed $x$ referred to here is $f^{-1}_\alpha(S(\alpha,r))$. I have made the change in the proof and updated the ePrint paper. Thank you for pointing out the typo.


The CCA1 security of ElGamal is a big open question. There are no attacks known, but standard reductions don't seem to work.

In 1991, Damgard proposed an ElGamal variant and proved it to be CCA1-secure (albeit under a very problematic non-falsifiable assumption, called the "knowledge of exponent assumption"); see the paper here http://link.springer.com/chapter/10.1007%2F3-540-46766-1_36.

More recently, Lipmaa here showed that ElGamal can be proven to be CCA1-secure under a non-standard (but falsifiable) assumption. The assumption is that DDH is hard even given access to a static CDH oracle (that computes the Diffie-Hellman function for a fixed "secret" exponent). [Caveat: I haven't read the paper so I can't vouch for correctness...]


Is sharing the modulus for multiple RSA key pairs secure?

I had a similar problem, and it took me a long time to figure out all the math, as some of the proofs can be rather terse.  So, I took it upon myself to write a full explanation of how to factor N, without all the symbols and relying on a bit less prior knowledge.

This is an application of the shared modulus attack explained by Boneh in his analysis of RSA attacks.

Anyway, such a system is not safe.  If you know a valid $e$ and $d$, you can factor $N$.
Stated more formally, given $(e, d, N)$, where $N = pq$ for some primes $p$ and $q$,
and $ed \equiv 1 \bmod{\lambda(N)}$, one can easily find $p$ and $q$.

Note:  $\lambda(N)$ is the Carmichael function.  If you're used to seeing RSA described in terms of $\phi(N)$, this is very similar. Carmichael's theorem is a generalization of Euler's theorem stating:
$$\forall a\,|\,\gcd(a,N)=1,\; a^{\lambda(N)} \equiv 1 \pmod{N}$$
where $\lambda(N)$ is the smallest integer that makes this statement true.  For $N=pq$, this number is just $\DeclareMathOperator{\lcm}{lcm}\lcm(p-1,q-1)$.  It is also true that $\lambda(N)\,|\,\phi(N)$, so the use of $\lambda(N)$ instead of $\phi(N)$ when describing RSA is just a generalization.

First, a few facts. Consider solving the equation:

$$\begin{aligned}
y^2 & \equiv 1 \bmod{N} \\
y^2 - 1 & \equiv 0 \bmod{N} \\
(y+1)(y-1) & \equiv 0 \bmod{N} \\
\end{aligned}$$

i.e. computing the square root of one. Now, note that $p\,|\,N$ and
$q\,|\,N$. Since the zero product property
holds in modular arithmetic when the modulus is prime, it is true that:

$$y \equiv \pm 1 \bmod{p} \;\, \text{and} \;\, y \equiv \pm 1 \bmod{q}$$

Therefore, we know:

$$\begin{aligned}
y \equiv 1 \bmod{p} & \, \text{or} \;\, y \equiv -1 \bmod{p} \\
y \equiv 1 \bmod{q} & \, \text{or} \;\, y \equiv -1 \bmod{q}\end{aligned}$$

This gives two choices of remainder for each factor of N. From this, you
can construct four systems of equations by picking one value from each factor.
Each of these systems of equations has a unique solution modulo $N$ (by
the Chinese Remainder Theorem).
However, not all solutions are created equal. Consider:

$$\begin{aligned}
y & \equiv 1 \bmod{p} \\
y & \equiv 1 \bmod{q}\end{aligned}$$

This has a solution $y = 1$, which is trivial. The solution where both
remainders are $-1$ is also trivial ($y = N - 1$), and is also not
useful. However, now consider the following case:

$$\begin{aligned}
y & \equiv 1 \bmod{p} \\
y & \equiv -1 \bmod{q}\end{aligned}$$

This has a non-trivial solution. Furthermore, if you know this solution,
you can factor $N$ by noting that $y - 1 \equiv 0 \bmod{p}$, so
$p\,|\,y-1$. Since $p\,|\,N$ also, it is easy to find $p$ by computing
$\gcd(y-1, N)$. The same can be said of the symmetric system of
equations swapping $p$ and $q$. Since $p$ and $q$ are interchangeable,
this has the same result.

We also know that any root that is non-trivial (i.e. is not 1 or -1) must
come from one of the two non-trivial cases we looked at because we know that
the solutions to these equations are unique.  This means that the above logic
works for any non-trivial root we may find.

Thus, we have fact 1: if $y$ is a non-trivial square root of one modulo
$N$, where $N$ is the product of two primes, one of the factors of $N$
is $\gcd(y-1, N)$.

The second is much simpler:

$$\begin{aligned}
a^b & = c \\
a^{{\frac b 2} + {\frac b 2}} & = c \\
a^{\frac b 2} a^{\frac b 2} & = c \\
(a^{\frac b 2})^2 & = c\end{aligned}$$

This is fact 2: given $a$, $b$, and $c$ such that $a^b = c$, the square root of $c$
is $a^{\frac b 2}$. This is easy to compute as long as b is even (i.e.
$2\,|\,b$).

Now for the actual attack. To begin, note that
$ed - 1 \equiv 0 \bmod{\lambda(N)}$. This value is important, so let
$k = ed - 1$. Because it is congruent to zero, $\lambda(N)\,|\,k$.
Furthermore, $2\,|\,\lambda(N)$, so $2\,|\,k$. Then $k$ can be written in
the form $k = 2^t r$ for some odd number $r$ with $t > 0$.

Then, picking any arbitrary $x$ (i.e. $\forall x\,|\,2 \leq x < N$):
$$x^k \equiv x^{k \, \bmod{\lambda(N)}} \equiv x^0 \equiv 1 \pmod{N}$$
Applying fact 2, we can find the square root of one modulo $N$ by
computing $x^{\frac k 2} \bmod{N}$. There are now several possibilities:

The result is $1$. This is a trivial solution. However, if the
exponent is even then it is possible to try again, dividing the
exponent by two again. If the exponent is odd, then pick a new $x$,
and try the attack again.
The result is $N-1$ i.e. $-1$. This is a trivial solution. Unlike in
the previous case, dividing the exponent by two again will not yield
a square root of one, but rather a square root of negative one.
Thus, pick a new $x$ and try again.
The result is neither of the above. This is a non-trivial solution.
All that remains is to factor $N$ by applying fact 1.

In other words, the algorithm can be stated as:

Compute $k = ed-1$
Determine the exponent of $2$, $t$, in the factorization of $k$,
i.e. factor $k$ into the form $k = 2^t r$ with $t > 0$ and $r$ odd.
Pick a random $x\,|\,2 \leq x < N$
Compute the sequence
$s = x^{\frac k 2}, x^{\frac k 4}, \dots, x^{\frac k {2^t}} \pmod{N}$
Determine the first index $i$ such that $s_i \neq \pm 1$ and
$s_{i-1} = 1$

If no such index exists, choose a new $x$ and try again.
Otherwise, let $p = \gcd(s_i - 1, N)$ and $q = \frac N p$.

Done.

The attack relies on the fact that you can easily generate numbers that
are congruent to one modulo $N$. Additionally, it is easy to take the
square root of these numbers by dividing the exponent by two. There is a
chance that taking this square root yields a non-trivial square root of
one modulo $N$, which allows you to easily compute a factor of $N$ by
using the euclidean algorithm. This is a probabilistic algorithm,
in that it relies on the solution being non-trivial.  If no non-trivial
solution is found, the algorithm needs to start over with a new $x$.

The chance of obtaining a non-trivial solution is an important
consideration when using this algorithm. So to determine this
probability, consider an approach which picks random $x$ modulo $N$.
$x^e$ for some exponent $e$, then, is also random. Also note
that, for any given modulus $m$, the set of integers are evenly
distributed modulo $m$ among the set of positive integers less than $m$;
i.e: $$P(x^e \equiv 1 \bmod{m}) = P(x^e \equiv m-1 \equiv -1 \bmod{m})$$
The proof for fact 1 requires the solution of a system of two
equations, each of which is “picked” from two possible equations. There
are four possible systems of equations, and each is equally likely because
of the equal distribution of numbers mod $m$.  Therefore,
the probability that the $x$ satisfies any one of these system is
$\frac 1 4 = 25\%$. Since two of these systems yield non-trivial
solutions, the probability of a non-trivial solution given a random $x$
is $50\%$. This probability is improved by continuing to calculate
square roots in the case that $\sqrt{x^e} \equiv 1 \bmod{m}$. However,
since this number is related to the previous number in the sequence, one
can no longer make a strict randomness argument that the next term in
the sequence also has a $50\%$ chance of being non-trivial. You can say,
though, that:
$$P(\exists \, \text{non-trivial solution in $s$}) \geq 50\%$$ for the
definition of $s$ given in the algorithm description above. Therefore,
the generation of a constant, finite number of sequences from random
values of $x$ can provide an arbitrarily high probability of yielding a
non-trivial solution.

Since computation of the entire sequence $s$ does not guarantee a higher
probability of finding a non-trivial solution, it is reasonable to
wonder why you should bother computing the entire sequence. However, it
is easy to get the entire sequence “for free” when computing
$x^{\frac k 2}$. By partially factoring $k$ into $2^t r$, $s$ can be
recursively defined as:

$$\begin{aligned}
s_t & = x^r \\
s_i & = s_{i+1}^2\end{aligned}$$

Note that this recursive definition defines the sequence back-to-front,
so in the process of computing $s_1$, one also computes all other terms
of the sequence. This squaring is the same computation the
pow-mod operation
would do anyway, so there is no added complexity in computing
the additional terms of the sequence.

Here, then, is code (in python) that performs the above partial factorization:

# Returns a tuple (r, t) | n = r*2^t
# Complexity O(lg n)*
def remove_even(n):
    if n == 0:
        return (0, 0)
    r = n
    t = 0
    while (r & 1) == 0:
        t = t + 1
        r = r >> 1
    return (r, t)

This can be implemented in $\Theta(\lg n)$ time. This implementation
does repetitive shifting, so in the worst case runs in
$\Theta((\lg n)^2)$ time. An implementation could achieve optimal time
by iterating through the bits of $n$ instead of doing repetitive shifts;
however, this is more difficult with python longs so this approach was
used for clarity.

This code will generate terms of the sequence $s$ until it finds a
nontrivial square root of one modulo $N$:

# Returns a non-trivial sqrt(1) mod N, or None
# Arguments:
#     x: random integer 2 <= x < N
#     k: multiple of lambda(N)
#     N: modulus
# Complexity O((lg n)^3)
def get_root_one(x, k, N):
    (r, t) = remove_even(k)
    oldi = None
    i = pow(x, r, N)
    while i != 1:
        oldi = i
        i = (i*i) % N
    if oldi == N-1:
        return None #trivial
    return oldi

In the worst case, this computes $x^k$ using the square-and-multiply
method, which is $O((\lg N)^3)$. As stated earlier, the probability of
the function returning a value (vice ‘None’), is at least $50\%$ for
random $x$.

Finally, here is some code to actually factor the modulus, given a valid
RSA key:

import random
import fractions

# Returns a tuple (p, q) that are
# the prime factors of N, given an
# RSA key (e, d, N)
def factor_rsa(e, d, N):
    k = e*d - 1
    y = None
    while not y:
        x = random.randrange(2, N)
        y = get_root_one(x, k, N)
    p = fractions.gcd(y-1, N)
    q = N // p
    return (p, q)

This algorithm runs in probabilistic polynomial time (ZPP). For example,
the probability of this algorithm succeeding after 14 iterations or less
is larger than $99.99\%$. Computing $k$ is $O((\lg N)^2)$, the
probabilistic portion is $O((\lg N)^3)$, and the euclidean algorithm to
compute the greatest common divisor is $O((\lg N)^3)$ as well.
Therefore, the entire algorithm will run in (probabilistic)
$O((\lg N)^3)$ time.

Finally, here is an example of running this algorithm to factor an RSA
modulus:

# A 98 and 99 bit prime.
p = 633825300114114700748351602573
q = 316912650057057350374175800819
N = p*q

print("RSA Modulus (p,q, N):")
print((p, q, N))

# A valid keypair mod N
e = 262139
d = 9451846527955896036458759652560972624637617897909079398699

print("Factoring N...")
print(rsa.factor_rsa(e, d, N))

This runs quite quickly, and demonstrates the algorithm does correctly
factor N. Note that the order of the factors changes from run to run,
depending on which root is found first. The order of the two factors
does not matter, though, so this is algorithm is sufficient for the
purposes of attacking a shared modulus cryptosystem.

To return to the original problem, if Bob shares his first private key,
and all his keys share a modulus, then Mallory can factor the modulus
using this algorithm. Once
the modulus is factored, she can compute $\phi(N)=(p-1)(q-1)$. With
knowledge of $\phi(N)$, computing the modular multiplicative inverse of
the other public keys (i.e. the corresponding private keys) is a simple
application of the extended euclidean algorithm.


Is it possible to translate a piece of language into your own without knowing the language?

A core assumption of natural languages is that conceptual frequency and the grammar to construct and articulate concepts is not evenly and randomly distributed; so pattern discovery can occur.

However, two problems can quickly arise:

If the language sample (or collection of samples) is too small, the patterns may not be distinct and consistent. Cretan Linear A for example lacks a large enough corpus for robust patterns.
If you have a decent corpus with lots of patterns, say a 1GB block of natural language text, the language could still be hermetic. You may know how symbols relate and which should occur when but you would still need intense in-depth knowledge of the human brain to map each pattern to the most probable human motivation or abstraction. So the language would have be of human origin with no explicit intent to befuddle the uninitiated reader.

If I chose a novel in a language I don't know (say Russian) and converted it into Wingdings; my brain would still feel that the text "fits" my innate idea of written language without knowing why. Ilmari Karonen is correct that this problem is inherently cross-disciplinary.

The cryptanalytic curio is that a natural language isn't secure according to mathematical models but can still be completely unintelligible, thus serving the same outcome. This is a security-through-obscurity irritant that some cryptanalysts love to scratch. :-)

So yes, it is possible with the right provisos. If you can decipher a previously unknown natural language with a large corpus, yet disassociated from all other languages - you will probably win a Nobel prize in something.


Encrypt without password, decrypt only with password

Wouldn't this be just the usual asymmetric encryption, as if you were encrypting e.g. email with GnuPG?

Create a private key, store it password protected (this is your master password). Anything you need to save, encrypt using the corresponding public key (no need for a password). But only the private key can decrypt your data items, and you need to enter the password to use that.


Are you sure you want 2-2-3, not 2-3-2? The latter is more common in my experience.

None the less, the first step is almost always done with a quadratic extension where i^2=-1. So you just need to implement complex numbers over your field of choice.

Multiplying complex numbers is simple if you just treat them as (x+iy) - I hope that's basic.

For inversion see See "Implementing cryptographic pairings", M. Scott, section 3.2. (ftp://136.206.11.249/pub/crypto/pairings.pdf)

And here's my code for this step: https://code.google.com/p/go/source/browse/bn256/gfp2.go?repo=crypto

For the cubic extension see http://eprint.iacr.org/2006/471.pdf. I used τ^3=i+3. The multiplication is little more complex, but still just an application of basic algebra. For inversion, I'll have to point you at the comments that I wrote in my code: https://code.google.com/p/go/source/browse/bn256/gfp6.go?repo=crypto#242

Now you're at q^6 you can work in the twisted curve.

Lastly, the quadratic extension to q^12 is similar to the original extension. After the cubic, it should be easy! I used ω²=τ because I was following http://cryptojedi.org/papers/dclxvi-20100714.pdf.

For exactly how you get from the twist over q^6 to the curve over q^12 depends on the exact homomorphism in question.


Given an elliptic curve, how do I calculate the order of the points manually, when we don't know about the curve's points?

Okay after some research: There is no shortcut. If you do it manually you need to proceed as suggested above. Realistically this is possible only for very small curves because of the complexity.


Fully Homomorphic Encryption over the Integers - Runtime Question

On the first question

The public key of DGHV's SHE scheme consists of $\tau+1$ $\gamma$-bit numbers, that is, $pk = (x_0,\dots,x_\tau)$, where $x_i$ is chosen from the distribution $\mathcal{D}_{\gamma,\rho}(p)$ over $[0,2^{\gamma})$.
Therefore, the length of $pk$ is $O(\tau \gamma)$, which is $\tilde{O}(\lambda^{10})$ if we adopt the parameters $\gamma = \tilde{O}(\lambda^5)$ and $\tau = \gamma + \lambda$ as the authors said.

In order to encrypt a bit $m$, we sample a random subset $S$ and a "relatively small" integer $r$, and compute $c = m + 2r + 2 \sum_{i \in S} x_i \bmod{x_0}$.
Here, we have to read the whole of the public key and the main task is adding $x_i$ randomly. Hence, the complexity of encryption is $\tilde{O}(\lambda^{10})$, which is the result of $\tau$-time addition of $\gamma$-bit integers.

In order to multiply two fresh ciphertexts, which are $\gamma$-bit integers,
we require about $O(\gamma^2)$ bit operations. (By using more sophisticated multiplication, it is reduced to $\tilde{O}(\gamma)$.)

As you said, the time of evaluating a circuit and encrypted data mainly depends on the depth of the circuit.
Getting worse, we are often required to adopt the FHE scheme and "refresh" intermediate ciphertexts.

On the second question

As an example, we take $\rho = \log^{2}(\lambda)$.
This results in $2^{2\rho} = \lambda^{2 \log(\lambda)}$, which is asymptotically greater than any polynomial of $\lambda$.
Hence, asymptotically speaking, the attack is not faster than the runtime of the scheme.
As you thought, if we take $\rho$ is very close to $\log(\lambda)$, the scheme is unsafe for small $\lambda$.


Is there a notion of "computational security" in quantum cryptography?

But is there also a notion of computational security in quantum cryptography (assuming a polynomial-time quantum adversary)?

No, not really, or at least, none that has been explored.  The goal of Quantum Cryptography is to be secure, even if the adversary has a Quantum Computer and that they are computationally unbounded; that is, the goal is to rely (as much as possible) on security-by-the-laws-of-physics alone [1].
One could include the assumption that they are computationally bounded; however if you did that, you would have a number of competing options available, including large key symmetric cryptography and postquantum (public key) cryptography.  These existing solutions already solve the problem, and are considerably cheaper and more versatile.  Hence, there appears to be little need to lower the security bar on Quantum Cryptography.
Kelalaka brought up the paper "Computational Security of Quantum Encryption"; however a close review shows that the security targets it makes do not rely on the security assumptions of Quantum Mechanics.  Instead, it examines the extension of classical cryptography into the realm of Qubits (and how that differs in nontrivial ways from the cryptography on bits).  This may be semantics, however I do not believe that falls into the realm of "Quantum Cryptography".

[1]: Of course, that's not the only assumption; they always need to assume that there are no exploitable side channels, that the equipment is operating as designed (and not in a way that looks correct, but is exploitable) and also for many QKD systems, the shared keys are used to AES encrypt the actual traffic (and hence those systems need to assume AES is strong as well).


Can ECDSA signatures be safely made "deterministic"?

There is a draft RFC which describes a way to implement deterministic (EC)DSA (with test vectors). In this draft, both $h(m)$ (the hash of the message) and $x$ are used as input to a deterministic PRNG which uses HMAC (that's HMAC-DRBG as specified by NIST); the PRNG output is used to yield $k$. I am not sure your simple multiplication with $x$ would be enough to guarantee security; ideally, a random oracle should be used, and HMAC-DRBG is the closest to a practical random oracle that I could find.

Note that $k$ must be generated uniformly in the $[1, q-1]$ range (where $q$ is the subgroup order). Any information on $k$, even partial (such as: values between $1$ and $2^{160}-q$ are twice as probable than values between $2^{160}-q$ and $q$), can be exploited by the attacker.

(There will be a new draft version with a few text changes in the draft -- but the same test vectors -- as soon as I find the time to do it.)

Edit: the RFC is now published as RFC 6979.


RLWE decision to search: probability that oracle work on all automorphic images

(The full version of the paper is at https://eprint.iacr.org/2012/230, and my answer below refers to it.)

The answer to your question is that a different part of the reduction ensures that the oracle has advantage very close to 1 over the random samples $(a_i, a_i s + e_i + r_i)$, i.e., the oracle outputs the correct answer for almost all choices of $s, a_i, e_i, r_i$. With this guarantee, Lemmas 5.5 and 5.9 give a reduction that solves the search problem using the automorphisms and the "guess and check" technique.

The other part of reduction to which I refer is described in Section 5.2, on "worst-case to average-case decision" (Lemma 5.12). This uses a pretty standard "amplification" technique to improve the oracle's distinguishing advantage, by repeatedly invoking it on independent samples and measuring how often it accepts.


Once you know (you didn't question that) that $a = 3$, then knowing 4 goes to 17, using $f(x) = 3x + b$, we just substitute $x = 4$ to get $3 * 4 + b = 12  + b = 17 \mod 26$, where we can easily see that $b= 5$ does the job.


Attacks on WinRAR volumes reusing same password?

The RAR5 archive format encrypts file data using AES in CBC mode, and generates a 256-bit key using PBDKF2-HMAC-SHA256 (32768 iterations default?).

If an attacker is able to view many files encrypted this way all with the same key, the attack is to recover the key from the ciphertext. This is not an easy task, even if the IV was reused. In WinRAR, the IV should be pseudorandom, preventing the same (or similar) plaintext from generating the same ciphertext blocks.

Additionally, a 128-bit salt is provided during key generation, which should prevent the generated key from being the same for 2 different archives, even if the password is the same. For decryption the salt is extracted from the archive header.

While there is no documentation I can find that specifically says the salt and IVs are pseudorandom, I would assume that it is, meaning that for a given file/password combination, the chances of the archive ciphertext being the same are near 0.

Clarification from RARLAB on exactly how they are generated will help. In the windows UnRAR utility, there is a fallback from CryptGenRandom to using the system time to generate random bytes, which is not acceptable during archive creation, but may be reasonable during decompression for whatever reason. Password data is encrypted in memory and cleared using appropriate methods. I also find it curious why there is a separate salt value in the file record header, as the one in the archive header should be used for KDF.


Does a regularly reseeded PRNG provide backtracking resistance?

Here's a perhaps better way to frame it that won't lead to tedious semantic disputes:

Consider a PRNG with 256-bit seed $s$ that, on each request, produces $\operatorname{AES}_s(2) \mathbin\| \operatorname{AES}_s(3) \mathbin\| \cdots$ as output, and updates its seed by $s' = \operatorname{AES}_s(0) \mathbin\| \operatorname{AES}_s(1)$.  This PRNG erases its key after every request.
Consider a PRNG with 256-bit seed $s$ that, on each request, produces $\operatorname{AES}_s(0) \mathbin\| \operatorname{AES}_s(1) \mathbin\| \operatorname{AES}_s(2) \cdots$ as output.  If you schedule a timer event to reseed it every second, then this PRNG erases its key after every second.

Of course, in this case, you need some source from which to reseed it, so the story doesn't end here and is necessarily more complicated than the story in (1) for prompt key erasure.

The terms backtracking resistance and forward secrecy are not as helpful because they don't emphasize when the keys are erased.  Both PRNGs could be construed to provide backtracking resistance in some sense, but PRNG (1) is largely a better engineering choice than PRNG (2) because it doesn't need reseeding at all (so fewer things to wire up, fewer things that can go wrong) and it provides even prompter key erasure.

The question, as stated, is essentially about PRNG (2):

  We have now two opinions:

  The PRNG does not provide backtracking resistance since it is possible to recover previous values within the compromised reseed interval.
  The PRNG provides backtracking resistance since values beyond the reseed interval can only be guessed with negligible probability

  Can someone explain who is right and why?

You're both right: it provides backtracking resistance every second, but not every request, so there is a window of time in which state compromise could reveal future outputs, but it's small.  It's arguable, not a priori clear, which of these ‘backtracking resistance’ means, which is why I recommend emphasizing when keys are erased.


How were the arbitrary values used inside SHA-256 determined?

In $W_t = \sigma_1 (W_{t-2})+W_{t-7}+\sigma_0 (W_{t-15})+W_{t-16}$

The $16$ is the number of 32-bit words in a SHA-256 block. It is here so that, when we consider $W$ as an array of $16$ rather than $64$ words (as most hardware and many software implementations do), the equation become adding to $W_{t\bmod 16}$ a feedback term $\sigma_1 (W_{t-2\bmod 16})+W_{t-7\bmod 16}+\sigma_0 (W_{t-15\bmod 16})$.
The $-2$, $-7$, $-15$ controls how far back in the formerly produced values of $W$ the feedback terms are taken from.

The $-15$ is as far back as it can go, given the $-16$. That maximizes the memory involved in the feedback.
The $-2$ indexes into a recently produced word (second only to what $-1$ would give), which promotes fast diffusion, and splits short-term feedback into two flows (even and odd indexes); also $-1$ could be a bottleneck to parallelization.
The $-7$ indexes somewhere else near the middle of the 16-word array, is odd so as to mix said two flows faster that $-15$ would ultimately do, and is slightly biased towards recent production, perhaps to promote faster diffusion.
Note: That later terms does not go thru a $\sigma$ function, contrary to the other two; that alternates XOR and addition (modulo the wordsize) in the feedback loop.

The shifts values are more difficult to justify. The pattern gives good diffusion, much better than a haphazard choice would do. But many other choices would be possible, and I can't pinpoint a selection process such that the choice made would be optimal.


Is this constant-time comparison secure?

Are there any problems with this constant-time comparison scheme?

One obvious issue is that it'll claim the strings "AB" and "BA" are the same; during the first character, it'll see 'A'-'B' = -1, for the second character, it'll see 'B'-'A' = 1; those two sum to 0.
On the other hand, that's actually fairly close to the standard way to do constant-time compare of equal strings, but instead of summing the differences, we bit-wise or them, as in:
total_difference = 0;
for (i=0; i<len_strings; i++) {
    int this_difference = a[i] - b[i];
    total_difference = total_difference | this_difference;
          /* | is the bit-wise or operator */
}
if (total_difference == 0) {
    /* The strings are the same */
}

The idea here is that the 'or' operation can set bits in total_difference, but never clear them.  Hence, the only way total_difference is 0 at the end is if in every iteration, this_difference was always 0, that that happens if each character of string a was the same as the character in string b.
Often, you'll see this_difference being computed by the bitwise-xor rather than subtraction; the algorithm works the same either way.


Recipe sans math

Given a non-empty $\text{final result}$ obtained as in the question, and $\text{key}$, we can find $\text{txt}$ as follows (see full answer for assumptions made and justification):

Extend $\text{key}$ to the same length as $\text{final result}$, by repeating $\text{key}$ as necessary, then truncating.
Form pairs of letters at same index in $\text{final result}$ and $\text{key}$, and decode per the following table, where $\text{key}$ determines the line, and $\text{final result}$ determines the column. The intersection should contain two possible letters for $\text{txt}$.
We now have two choices for each letter of $\text{txt}$ (or are certain that $\text{final result}$ was not obtained as in the question, if any -- was encountered). In the former case, redundancy in $\text{txt}$ is the only way to disambiguate.

   A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z final result
A  AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ --
B  -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ
C  MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY --
D  -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY
E  LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX --
F  -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX
G  KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW --
H  -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW
I  JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV --
J  -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV
K  IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU --
L  -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU
M  HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT --
N  -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT
O  GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS --
P  -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS
Q  FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER --
R  -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER
S  ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ --
T  -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ
U  DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP --
V  -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP
W  CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO --
X  -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO
Y  BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN --
Z  -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN
key

For example, given $\text{final result}=\mathtt{HOS}$ and $\text{key}=\mathtt{DOG}$

for the 1st letter we use the line for $\mathtt D$ and the column for $\mathtt H$; we read CP there, thus know that the 1st letter of $\text{txt}$ is $\mathtt C$ or $\mathtt P$
for the 2nd letter we use the line for $\mathtt O$ and the column for $\mathtt O$; we read AN there, thus know that the 2nd letter of $\text{txt}$ is $\mathtt A$ or $\mathtt N$
for the 3rd letter we use the line for $\mathtt G$ and the column for $\mathtt S$; we read GT there, thus know that the 3rd letter of $\text{txt}$ is $\mathtt G$ or $\mathtt T$

Thus $\text{txt}$ can be $\mathtt{CAT}$. In English, that's the most common of 8 possibilities including also $\mathtt{PAT}$ (a chess term), $\mathtt{PNG}$ (initials of an image format), and 5 others.

Detailed answer

I'll assume the usual definition of the Vigenère cipher, even though that's reportedly not the cipher promoted by Vigenère, which is closer to autokey. Consequently:

$\text{txt}$, $\text{key}$, $\text{etxt}$ and $\text{final result}$ are strings of letters $\mathtt A$ to $\mathtt Z$, which will be assimilated to integers $0$ to $25$ without explicit mention.
$\text{txt}$ and $\text{etxt}$ are unknown strings, while $\text{key}$ and $\text{final result}$ are known. They all are of equal length (with $\text{key}$ extended by repetition as necessary).
The question's $\,+\,$ is not regular addition, and I'll note the variant $\;\widetilde+\;$ to avoid confusion. It holds that

$\;\widetilde+\;$ applied to individual letters stands for addition modulo $26$, so that $\mathtt R\;\widetilde+\;\mathtt M=\mathtt D$, because $\mathtt R$ maps to $12$, $\mathtt M$ maps to $17$, $12+17\bmod26$ is $3$, and $3$ maps back to $\mathtt D$. See this table.
$\;\widetilde+\;$ applied to two strings of letters of equal length performs $\;\widetilde+\;$ on letters of same rank in each strings, producing a string of the same length.

For example, if $\text{txt}$ is $\mathtt{CAT}$ and $\text{key}$ is $\mathtt{DOG}$, then the question's equation becomes
$$\begin{array}{llllllllll}
\text{txt}\;\widetilde+\;\text{key} &=&\text{etxt}        &=&\mathtt{CAT}\;\widetilde+\;\mathtt{DOG}&=&\mathtt{FOZ}\\
\text{txt}\;\widetilde+\;\text{etxt}&=&\text{final result}&=&\mathtt{CAT}\;\widetilde+\;\mathtt{FOZ}&=&\mathtt{HOS}
\end{array}
$$

To solve for $\text{txt}$, we eliminate $\text{etxt}$ in the second equation by substitution with the value assigned to $\text{etxt}$ per the first equation. The equations are equivalent to $\text{txt}\;\widetilde+\;(\text{txt}\;\widetilde+\;\text{key})\,=\,\text{final result}$.

This implies that for each $t$, $k$ and $f$ designating letters of same rank in $\text{txt}$, $\text{key}$ and $\text{final result}$, we have $t\;\widetilde+\;(t\;\widetilde+\;k)=f$. Per usual rules of (modular) arithmetic in the ring $(\Bbb Z_{26},+,\times)$, including associativity and distributivity, this is $(2t+k\bmod26)=f$, and is equivalent to $2t\equiv f-k\pmod{26}$.

The modulus $26$ is the product of distinct primes $2$ and $13$. Therefore, by the Chinese Remainder Theorem, the above equation is equivalent to $2t\equiv f-k\pmod2$ and $2t\equiv f-k\pmod{13}$. And, since $2^{-1}\bmod13=7$, for given $f$ and $k$, and under the necessary condition that they are of the same parity, we can obtain the two solutions for $t$ as$$t_0=7(f-k)\bmod 13\quad\mathsf{then}\quad t_1=t_0+13$$

The recipe's table is a pre-computation of this formula. For example, given $f=7=\mathtt H$ and $k=3=\mathtt D$, we get that $t$ is one of $t_0=7(7-3)\bmod13=28\bmod13=2=\mathtt C$ or $t_1=2+13=15=\mathtt P$, and the table has CP for line D column H.

Notations for modular arithmetic

By definition, for positive integer $m$ and any integers $a$ and $b$

the notation $b\equiv a\pmod m$ means that $a-b$ is a multiple of $m$
the notation $b=a\bmod m$ additionally means that $0\le b<m$
Note: in the later notation, there is neither an $\equiv$ sign, nor an opening parenthesis immediately on the left of $\bmod$
equivalently to the previous statement, $a\bmod m$ is the integer defined as

for non-negative $a$, the remainder of the Euclidean division of $a$ by $m$
for negative $a$, the integer $m-1-((1-a)\bmod m)$

the notation $b\equiv a^{-1}\pmod m$ means that $a\,b\equiv1\pmod m$
the notation $b=a^{-1}\bmod m$ additionally means that $0\le b<m$.
Note: $b$ is called the multiplicative inverse of $a$. It exists when the Greatest Common Divisor of $m$ and $|a|$ is $1$. For small integers, $b$ can be found from $a$ and $m$ by trial and error. More generally, the GCD and $b$ can be computed using the extended Euclidean algorithm, or its half-extended variant.


To what extent would Bitcoin be private without address reuse?

This would not help, and would actually make things worse. Bitcoin transactions are public, the input and output addresses are known. This can therefore be traced. Simply tracking the transaction from an initial input (say, buying currency on an exchange that complies with Anti Money Laundering (AML) laws) through each of its single outputs to a destination address would de-anonymize any destination. Since addresses can't be re-used in this scheme mixer services (money laundering addresses) become impossible, so anonymity is impossible for anyone who uses an exchange compliant with AML laws.


Is there any protocol for proving that a message was written at a certain time?

In general, no.

You can prove a message was written no later than time T by hashing the message with a collision-resistant hash, and communicating the hash to some trusted third party that records it was aware of the hash at time T. The bitcoin blockchain can be used as a third party here. You don't need to put the whole message in the blockchain, just a hash.

You cannot prove a general message was written no earlier than time T. If there was an alleged way to prove that, you could just write a message earlier than time T, wait for time T, and perform the alleged proof, tricking any verifier.

If you can communicate back and forth with a verifier, you can prove you are writing the message during the communication, by hashing your message along with some random data provided by the verifier and passing the hash back to the verifier.


What is the security risk if an encryption key is not random?

A usual approach to security analysis is that the attacker knows everything about the system except the secret key, and often he has access to an "oracle" to produce related data. This is also known as Kerckhoffs's principle. For example in a chosen plaintext attack he can choose some messages, hand them to the oracle which encrypts them under the secret key and gets back the ciphertexts.

Back to your question: If the key is chosen poorly (and if there is some structure, the attacker knows it), it might be possible just to brute force it and try all possible keys. Today's computers can deal with complexities of testing $\approx 2^{64}$, therefore DES is no longer safe to use. If you know the first 100 bit of a 128 bit key are all 0 bits, then you probably are even able to find the key on any modern computer larger than a mobile phone.


Sounds like snake oil for me.
The phrase you cite can be easily googled and tracked back to a white paper by CipherLoc in which they suggest that AES can be broken by using frequency analysis of english text when reusing the same encryption key for many inputs. In their explanation they deliberately ignore the role of a random IV with AES which should make such attacks infeasible. And their "solution" against this is this "PKPA" thing which somehow scrambles the data before encryption to make such frequency analysis impossible. Apart from that this is not intended to replace AES but instead used additionally to it.


Efficiency of finding sub group order vs factorization

Concerning question 3, here is an answer assuming that the coefficients of $r$ are known to Bob and the coefficients of $s$ hidden in an exponential representation. [This is unessential, it can be easily generalized to hidden $r$, but it simplifies the presentation].

To further simplify, let's also assume that $s$ contains no constant term. In this setting, each pair $(a_i,b_i)$ as in the question is equivalent to a pair $(A_i,b_i)$ together with the information that $s(b_i)\equiv A_i\pmod{q_0}$. This can be easily rewritten as a linear equation $$\sum_{k=1}^{\ell}s_kb_i^k\equiv A_i\pmod{q_0},$$where $\ell$ is the degree of $s$. Collect $\ell+1$ such equations and form the matrix:
$$
M=\left(\begin{array}{ccccc}-A_1 &b_1 & b_1^2 & \cdots &b_1^\ell\\
-A_2 & b_2 & b_2^2 & \cdots &b_2^\ell\\
\vdots &\vdots & \vdots & \ddots & \vdots\\
-A_{\ell+1}& b_{\ell+1} & b_{\ell+1}^2 & \cdots &b_{\ell+1}^\ell\\
\end{array}\right).
$$
By construction the system $Mx=0$ has a non zero solution vector (formed by a '1' followed by the coefficients of $s$) modulo $q_0$. As a consequence, $\det(M)$ is a multiple of $q_0$. Form two such matrices, take gcd and you can recover $q_0$ directly.

Note that this can be made more efficient by taking a rectangular matrix $M$ (with extra equations) and computing a Hermite normal form.


There is a push by browser vendors to reduce latency. It seems that, in their measures, the initial latency by the TLS handshake is large enough to be detrimental to the perceived user experience. It is true that a complete TCP handshake + TLS handshake can have a large latency (three round trips, which may add up to a significant time, in particular when considering links through geostationary satellites).

Old theory is that TLS handshake latency does not matter since you can keep the connection open, so you just pay for it once. However, the modern Web user does not engage with Web sites like he does with a local application; he will jump from site to site. Also, Web sites are now complicated assemblages of scripts that load other scripts, possibly from other servers, and all the latencies just add up.

This has led browser vendors to explore other strategies, including the false start / early data thing for TLS, to reduce latency. At Google's, they even decided to dispense with the TCP three-way handshake by defining QUIC to use UDP instead.

You may note that all of the above is about Web browsers. Requirements for applications vary quite a lot, depending on context. The modern Web has a combination of many short-lived connections and impatient human users, which may explain the quest for a reduced latency.

Of course, these modifications are not purely a matter of optimization. For instance, with TLS "false start", the client sends its data before having verified the Finished message from the server: at that point, the client does not have any guarantee that it has been talking with the intended server(*); it only knows that what it sends won't be intelligible to a fake server.

The "0-RTT" feature of TLS 1.3 is inherently vulnerable to replay attacks, and it is quite hard to know when 0-RTT can be used safely. TLS 1.3 draft 23, section E.5, gives some guidance, but (characteristically) uses the term "idempotent" without defining it, leaving the reader a bit nonplussed as what is meant there.

It can be expected that, when TLS 1.3 is finally deployed beyond some specific Web browsers and servers, 0-RTT will be activated in unsafe contexts, because developers and administrators just want "more speed".


Why should I export my private key instead of well known asymmetric crypto mechanism on openkeychain?

It took me a bit to understand your issue. In summary, you want to use your passwordstore password manager on multiple devices, without copying the private pgp keys to multiple devices.
Yes, it can be done.
You need to create a separate key for each device, and configure your store to encrypt the passwords to multiple keys.
If you follow the steps at https://www.passwordstore.org/ it is mentioned at Setting it up:

pass init "ZX2C4 Password Storage Key"

ZX2C4 Password Storage Key  is the ID of my GPG key. You can use your standard GPG key or use an alternative one especially for the password store as shown above. Multiple GPG keys can be specified, for using pass in a team setting, and different folders can have different GPG keys, by using -p.

The man page details how it is used: you need to list the multiple keys on the .gpg-id file, one per line.
Each or your devices will need to have the public keys of all of the devices imported, so that they are able to encrypt the files for 'everyone'.


Hint: given $AES_k(seed)$ and the key $k$, what can an adversary compute? Should this be possible for a secure PRG?

A better option would be standard CTR mode, i.e. $AES_{seed}(0) \| AES_{seed}(1), ...$


What is the best way to accurately describe this statistical probability?

So, the full analysis for random trials is that the initial probability of a hit is $p_0=k/n$ and $k=10,$ and $n=1000$ for your case. Define the number of trials until the first hit as $N_0$ which is a geometric random variable with expectation
$$
\mathbb{E}(N_0)=p_0^{-1}=\frac{n}{k}.
$$
This is indeed 100 as you guessed.
If you wanted  to find 2 codes your success probability would now be $$
p_1=(k-1)/n$$
and the expected time to find a second (distinct) code would be
$$
\mathbb{E}(N_0)=p_1^{-1}=\frac{n}{k-1},
$$
which is a little longer.
The expected time to find $r$ codes is thus
$$
\mathbb{E}(N_0)+ \mathbb{E}(N_1)+\cdots+ \mathbb{E}(N_{r-1})=
n\left(\frac{1}{k}+ \frac{1}{k-1}+\cdots+ \frac{1}{k-r+1}\right)
$$
which is $n(H_k-H_{k-r})$ where $H_k$ is the k_th harmonic number  (the sum of reciprocals of the first $k$ integers) and is approximately $\ln k$ for large $k$. So the overall time complexity is approximately
$$
n \ln \left(\frac{k}{k-r}\right)
$$
for $r>1.$


How should a string be converted to a number for use by a hash function?

The input format of the data doesn't affect the security of the algorithm.

Any format that can be represented by a sequence of bits will be fine. You can use raw ASCII byte values, 6-bit Base64 values, anything which is in binary form.

If you convert your string into ASCII bytes, for example, you'll end up with a set of 8 bit numbers. Join them together and there's your input.

Since SHA256 uses 32-bit words, it's common to use a byte format for the data (4 bytes = 32 bits). After converting your input to a set of bits, your first task will be to append a 1 bit, pad with zeroes to 448 bits and then append a 64-bit length (the original bit length of the input data) to give you a 512 bit buffer.

I'm sure you can handle the rest.


Diffie-Hellman Secret Exponent Size and Shared Secret Usage

The scheme itself seems pretty standard, so it should be secure, if defined and implemented correctly. A simple textual descripion as you have provided here is not enough to prove your protocol secure. The authentication part only describes the RSA algorithm and key size - it does not specify how trust is established, nor does it define how the session keys are to be used.

I don't really understand your key derivation part; if you use HKDF and use the expand funtionality (with different info fields) you can generate multiple keys without having to resort to AES-CTR.

You may want to adhere to to NIST SP 800-56A Rev 2. This document also defines extract-than-expand key derivation schemes. One important issue with it is that it defines a lot of KDF's, so it will lead to another choice. It does certainly contain a lot of security hints regarding Diffie-Hellman which you may want to consider.

[EDIT]

As for the secret exponent size, the size of 512 bit is certainly enough, but the size of the modulus is very small. This means that the security is bounded by that of the modulus. It is very tricky to talk about effective key sizes within Diffie-Hellman. To get a good idea about possible key sizes, please take a look at the NIST or ECRYPT recommendations, e.g. at http://www.keylength.com/ . For good performance at higher key sizes, it is recommended - also by NIST - to switch to Elliptic Curve Diffie-Hellman. A 521 bit or 512 bit Elliptic Curve seems more appropriate for your needs.


Very simple and minimal replay prevention scheme

The main part of the scheme works, but your reset mechanism in the client has a potential weakness:

First, the attacker can easily get the information about what is the next expected counter, by simply replaying any old message and inercepting the answer.
Then, at some counter $c$, the attacker intercepts the message $m$, and saves it. If your answers are just unencrypted and not signed, he can easily send your client a fake-reply.
All subsequent messages are also intercepted, until the client is shut down.

And now the client is restarted, and does the "ask for the correct counter" by sending a message with counter 0. The return value will be something smaller than $c$, because the server never received that value or anything higher. At this point, the attacker could switch the new data for the old data instead. That isn't a replay attack, but the client might think he send something different than what was received at the server.

More complex, the server could actually keep track of the counter, especially if it is always increased by 1. And then replace new information with old ones.

The problem with your idea is, that the counter only changes after receiving a message. But if no message is delivered, the sender might send several messages with that same expected value in the counter. And then the attacker can choose which one he wants to deliver to the server.

A common mechanism to counter replay attacks is to have a challenge-response mechanism: The client sends a hello-message to the server, the server replies with a random challenge, and then you use that number in the response.