Are hash trees an alternative, quantum-resistant signature scheme which can replace RSA?

Hash trees alone wont do that. But hash trees in combination with one time signatures (this is called the Merkle signature scheme).

If you use hash based one time signatures such as Lamport-Diffie, then yes.

Basically, the hash tree is used to "aggregate" $k$ public keys by representing the hash values of the public keys as leaves of the hash tree and recursively computing the hash values of inner nodes of the tree as hash of the concatenation of its children till you obtain the "root public key hash". Then every leave public key can be used for a single time with a one time signature scheme and allows you to produce $k$ signatures in total.

Therefore, you compute a signature with public key $i$ and you have to add the "root public key hash" and the authentication path of public key $i$, i.e. the hash values of all siblings of public key $i$ on the unique path to the root of the tree (this is required to check if public key $i$ is "contained" in the tree by recomputing the root). Latter contains $\log n$ hash values for a tree of height $n$.

The key and signature sizes depend on the used one time signature scheme and in turn on the hash function.


Secure Cipher Suites supported by JDK versions

(Meta: if we're going to improve formatting might as well improve content too. However, I haven't looked at at 10 yet; I'll try to come back and re-edit when I have time to do so.)
Java Cryptography Architecture (JCA) is designed around the concept of replaceable providers. Originally (in the 1990s) this was necessary to easily support US and limited 'foreign' versions with a single codebase.
(This applies to all crypto: codesigning and other things as well as SSL/TLS.)
If you use the Sun-now-Oracle providers (which is the case if you use the 'standard vanilla' JRE or JDK packages from Sun-now-Oracle) or if you use the open-sourced equivalent OpenJDK packages in at least some Unix distros, then the official documentation is at http://docs.oracle.com/javase/8/docs/technotes/guides/security/SunProviders.html#SunJSSEProvider -- and has been there or the corresponding 7 and 6 and 5 directories for a long time.
(Update: Java 9, Java 10.)

In summary, and expanding a bit on some points that may be unobvious:
Protocols

Java (JSSE) 6 implemented only the SSLv3 and TLSv1 (meaning 1.0) protocols. There is also a protocol name SSLv2Hello but this is not an actual protocol, rather the option to use backward-compatible negotiation as per rfc2246 or rfc4346 E.1.

Java 7 and 8 implemented SSLv3 through TLSv1.2, but SSLv3 was disabled in updates beginning Dec 2014 because of POODLE. (6 was past end-of-life and so was not updated, at least not in public/free versions.) Although 7 implements 1.1 and 1.2, on client side it does not enable them by default; 8 does. 7 and 8 still implement SSLv2Hello, but do not enable it on client by default.

In the 2000s there were still some SSL2 servers around, and using SSLv2Hello allowed you to get a more specific error when encountering them, but by now they should all be gone (and SSL3 as well) so there is no good reason to enable SSLv2Hello. If you are stuck running on Java 6, it may be worth the trouble to disable it, because modern systems may implement a rigid no-SSL rule that prohibits any SSL2-format hello, even when it would allow negotiation to an otherwise acceptable TLS version. Plus, if you want to enable ECC on 6 (see below), ECC negotiation may not work (or not well) without extensions while SSL2-format doesn't have.

Cipher suites
JSSE 6 and 7 implement (AFAIK all) public key and Kerberos cipher suites from TLS1.0 and 1.1 (which are the same), although the EXPORT and NULL (!) and anon and KRB5 ones, plus in 7 those using original (single) DES (versus 3DES), are disabled by default. The first three were designed to be insecure, and the last has become so, and they should not be enabled. Suites using Kerberos for key-exchange can be secure but it requires special infrastructure, so if you don't already know about Kerberos you probably can't use it.
But the ECC suites can actually be used only if the JVM has a (separate) cryptoprovider for the needed ECC primitives, which Sun/Oracle JRE/JDK 6 does not but 7 up does (SunECC). You can add a third-party ECC provider to 6; my favorite is BouncyCastle. OpenJDK may be more variable; in particular RedHat (hence CentOS, Fedora, SL, etc) packages used to exclude ECC crypto from (AFAIK all) crypto/security programs even when it was provided upstream, although I believe these have now been fixed.
Also, the cipher algorithm RC4 has become seriously weakened by attacks in recent years and since 2015 is officially prohibited although not everyone implemented this change promptly -- or at all. 8u60 and up disable it using a setting configured in JRE/lib/security/java.security which you can change if you need to, and 9 similarly in JRE/conf/security/java.security.
TLS 1.2: SHA2 and GCM suites
JSSE 7 also implements the CBC-SHA2 suites in TLS1.2; 8 adds the GCM suites in TLS1.2. GCM is one form of AEAD (Authenticated Encryption with Additional Data) which is now considered superior to all former TLS cipher suites, which combine a cipher with separate HMAC in the more vulnerable order MAC-then-Encrypt. GCM suites should be preferred when possible (in 8 up).
SCSV
In addition, 6 starting with 6u22, and all versions of 7 and 8, implement a cipher suite name TLS_EMPTY_RENEGOTIATION_INFO_SCSV which is not actually a cipher suite, but an option to implement rfc5746 using the (registered) pseudo cipher suite value; if 'disabled' JSSE client still supports rfc5746 but uses the extension field instead. In 2010 the SCSV was slightly more interoperable/robust than the extension; today it usually doesn't matter.
Strength Policies
Sun-now-Oracle JREs and JDKs until 2017 install with a default 'policy' that prohibits symmetric encryption over 128 bit strength; for SSL/TLS this has the effect of disabling cipher suites using AES-256 (in either CBC or GCM). To use AES-256 on these you must download and install the Unlimited Strength Jurisidiction JCE Policy applicable to your major version. Only 8 is still on the download page (but may not be much longer); older versions used to be in the archive but I no longer see them. Update: 8u161 and 8u162 in 2018, and 9.0.0 in 2017, remove this obsolete policy restriction, and allow AES-256 out of the box; OpenJDK (AFAIK all versions) never had this misfeature in the first place.
Server keys limit available cipher suites
On server side, of course, a public key suite can be agreed only if the server's keystore (or more precisely keymanagers, normally derived from a keystore) contains a privatekey with certificate (chain) for the applicable publickey algorithm. For example, using an RSA-based cipher suite requires an RSA key and cert. In particular, keytool by default generates a DSA privatekey and selfsigned certificate; this supports only ciphersuites with DHE_DSS key exchange. JSSE supports keymanagers containing multiple key+cert pairs of different types, although some applications configure only a single keystore entry (alias) and can't benefit from this.
For ECC (if supported, per above) in addition the curve used must be among those offered by the client; this is rarely a problem for keytool generated keys since it uses the widely supported curves P-256 P-384 P-521, but may matter if you generate your key by other means.
Other providers
IBM Java replaces the Sun/Oracle providers with IBM providers, and I don't have relevant experience with them. And of course you (or anyone) can write your own provider(s) and substitute it(them) in which case you are on your own.
Update: recently BouncyCastle releases began including a provider BCTLS which is an alternative to JSSE, and provides a modern set of features, depending (only) on the BC version, that work the same on all Java versions back to 5. (BC had implemented TLS
years earlier, but using a separate and incompatible API; with BCTLS you just instantiate your SSLContext from BCTLS instead of JSSE and the rest of your code can stay the same.)


What is the difference in designing an MPC protocol by ring or field?

[...][Most] of the MPC protocol is built on a ring $\mathbb{Z}_{2^\ell}$(usually $\mathbb{Z}_{2^{64}}$) or field $\mathbb{Z}_p$($p$ is a big prime), why?

The relevant protocols for $\mathbb{Z}_{2^\ell}$ most likely use boolean sharing / boolean garbled circuits (representing each individual bit as a shared value) whereas the ones for $\mathbb{Z}_p$ use arithmetic sharing and in some rare cases arithmetic garbled circuits.
The core difference between these two is the set of operations that can be performed cheaply on each:

Bit-wise XOR tends to be extremely cheap with boolean sharing but is usually prohibitively expensive with arithmetic ones
Normal addition is not too-expensive for boolean sharings but tends to be free for arithmetic ones
Bitwise / -oriented gates and reductions in general tend to be much cheaper for boolean sharings than for arithmetic ones - e.g. equality comparisons or bitwise operations commonly seen in symmetric ciphers
Arithmetic operations tend to be much cheaper in the arithmetic case, especially multiplication which is a primitive operation there but requires $O(\ell^2)$ ish non-free operations for boolean sharings


You appear to have computed things correctly. However, you have quoted their Corollary 1 wrong: you've included an extra $-q^22^{-128}$ term in the confidentiality part  (don't know if that was what confused you though). To get their $2^{-89.4}$ instead of your $2^{-89.5}$ simply include more decimals of $\log_2(95)$.


Are quantum computers a sign that we should phase out RSA?

I don't think so. We are still an incredibly long way away from quantum computers being built that can deal with RSA (if they ever happen). It's certainly a good idea to get ready and have alternatives in hand. If you are really paranoid then you can start encrypting things today that still need to be secret in 10-20 years using a combination of RSA and lattice-based encryption. Otherwise, I would just wait.


I understand the question as you have a single 4-bit S-box, which you first apply rowwise, and then columnwise.

As already mentioned, this is equivalent to a large S-box $\mathcal{S}$
$$
c = \mathcal{S}(m\oplus k_1)\oplus k_2.
$$

This is a well-known Even-Mansour cipher, and it can be broken with complexity $2^{n/2}$, which is $2^8$ for your $n=16$. The idea by Daemen is to try $2^{n/2}$ plaintext pairs with the same difference $\Delta$ both for the entire cipher $E$ and the S-box $\mathcal{S}$.

So the answers to your questions are

No advantages.
Breakable in seconds.
Maybe in some marginal ciphers or hash functions. Note that it is quite inefficient in software.


Secure scheme to share symmetric key using asymmetric keys and certificates with N parties

This is easy, if you are willing to take a huge storage overhead, just encrypt the AES key with all the public keys and store the ciphertexts along with the public key hashes for retrieval.

So let $K$ be your AES key. Let $(pk_i,sk_i)$ be your, e.g. RSA, public key encryption keypairs, where the private key is unextractable on a smartcard. Then you want to have a data-structure, which doesn't reveal any information about $K$ by itself, but allows for retrieval of $K$ using any $sk_i$.

The solution to this is simple: Store $\large{\parallel}^n_{i=1}$$\left(h(pk_i),E_{pk_i}(K)\right)$, that is a list of pairs of public key hashes and the corresponding encrypted AES key, on each endpoint for an arbitrary (potentially insecure) hash function $h$ and a secure public key encryption scheme $E$ e.g. RSA-OAEP. The idea being that when you want to access the key with any given smartcard, you compute the hash of the public key you have on your card and iterate over the list of public key hashes, to find the ciphertext most relevant to you. If you wouldn't do that and would just try to decrypt each ciphertext, which is a possibility, then this would be quite slow, because smart-cards are not exactly known for their speed when it comes to private-key operations.


For SHA3-512, SHA512, and Whirlpool, which algorithm has least probability for collision and preimage collision?

Generic expected pre-image resistance for a hash function with $n$-bit output is  $\mathcal{O}(2^n)$
Generic expected collision resistance for a hash function with $n$-bit output is $\mathcal{O}(\sqrt{2^n}) = \mathcal{O}(2^{n/2})$ due to the generic birthday attack on the hash functions.

\begin{array}{|c|c|c|c|}\hline
\text{name} & \text{output size} &  \text{pre-image resistance} & \text{collision resistance} \\ \hline
\operatorname{SHA-512} & 512 & \mathcal{O}(2^{512})& \mathcal{O}(2^{256}) \\ \hline
\operatorname{SHA3-512} & 512 & \mathcal{O}(2^{512}) & \mathcal{O}(2^{256}) \\ \hline
\operatorname{Whirlpool}& 512 &\mathcal{O}(2^{512}) & \mathcal{O}(2^{256}) \\ \hline
\end{array}

Therefore they have the same as long as there is no attack better than these on any of these.

Note 1 There is not pre-image collision. There is pre-image attack or pre-image resistance.

Note 2 SHA-512 is vulnerable to length extension attack. Prefer the SHA3-512 or Blake2 series.


Do these new insights into prime numbers affect encryption security?

No, because these new insights only affect the discovery and patterns regarding finding new prime numbers.  In order to break existing encryption algorithms that rely on primes such as RSA, you'd have to have a breakthrough in discovering how to factor integers into primes.

Primes are used in encryption keys as the basis of their generation:  two large primes are multiplied together to form a very large number.  The difficulty of factoring this large number to discover its prime roots is essentially the protection the cryptosystem offers.  Since you already have the primes (the private key, essentially), you need not factor the number and can immediately decrypt it.

Since the new discovery only relates to patterns prime numbers take which may assist a search for even larger prime numbers than already known, and not in factoring multiples of prime numbers, this discovery should be inconsequential for cryptography.


Stream slicing operation in block cipher and side-channel attack

The key schedule should be considered secret. Your side channel reveals the key schedule. Even if your key schedule is indistinguishable from random an attacker can usually still derive the key. Since your key schedule is the same as your encryption algorithm it would be inherently vulnerable to the same attacks as your encryption. Even if it isn't, your key schedule probably still isn't a secure hashing algorithm and therefore the original key can even be obtained.
Most (all) modes of operation are broken even if only the key schedule is revealed but not the key. Some are (slightly) less broken than others.
Side-channels are enabled by any data-dependent memory accesses. Even if the total number of memory accesses is constant, this cannot be assumed to provide security. If I perform some computation on bits $1,...,a$ and I perform another (possibly the same) computation on bits $a+1,...,128$ I've just performed a different pattern of memory accesses, and revealed the value of $a$ (which is nearly impossible to fix in implementation). Nevermind the fact that for loops require an if statement to tell when to break (the compiler adds it implicitly). That means that you've allowed cache-timing, branch-prediction, and branch-timing attacks.
On the impact of various side-channels

Cache-timing is fixable in hardware that doesn't cache memory. Memory caching exists in all major architectures, and can't really by bypassed or disabled.
Branch-prediction (also known as speculative execution) only exists in hardware that tries to predict branching. This behavior exists in all major architectures, and can't be bypassed.
Branch-timing attacks, however, are hardware-agnostic and will affect every system identically... For this reason these are among the worst of all side-channels.

All side-channel attacks, even if hardware-dependent, are considered crippling to a secure cryptographic implementation.


Does the position of the salt improve its effectiveness when hashing?

If the hash function is a random oracle, then the salt can go wherever you wish, it will do its job.

On the other hand, there is, arguably, no such thing as a random oracle. On an existing, real, tangible hash function, details on how you input things may or may not trigger slight structural weaknesses in the function, which could impair the role of the salt, which is to prevent an attacker from doing exhaustive searches ("dictionary attacks") in a parallel way (time-wise or space-wise). In particular, on Merkle-Damgård hash functions (such as MD5, SHA-1 or SHA-256), the so-called "length extension attack" may be relevant.

So this is a matter of some delicacy. It seems best, generally speaking, to use constructions which have benefitted from wide scrutiny by many people. Salts are from the password-hashing business, and known good constructions for transforming passwords into keys are PBKDF2 and bcrypt.


Will there always be 256 collisions for the output of the MD5 hashsum function for 17-byte inputs?

Your math is wrong — not the numerical calculation, but your interpretation of it. There are $256^{17}$ possible inputs and $256^{16}$ possible outputs. On average, there are $256$ inputs for each output. But there are no guarantees that this is the case for all outputs: it's in fact overwhelmingly likely that some outputs have more and others have fewer. For example, we don't even know whether every possible output is in fact the MD5 of a message of any length.

What you can state for sure is that there exists at least one 256-bit string $H$ such that there are at least 256 17-byte messages $M_{1}, \ldots, M_{256}$ such that for all $i$, $\mathrm{MD5}(M_i) = H$. Since we don't know any MD5 collision with a 17-byte output, we are unable to come up with an actual value for $M_i$ or $H$, we just know that it exists by the pigeonhole principle.

See also

Is SHA-256 a one way permutation when restricting the domain to {0,1}^256?
Is it theoretically possible to construct a string that contains its own hash value?
What is the MD5 collision with the smallest input values?


Can a "pattern" in a series of passwords be detected from their hashes (and maybe a single raw password)?

In what sort of circumstances would an attacker potentially be able to detect a pattern from a series of hashed passwords?

I think the most direct answer is: When the hashing algorithm is not cryptographically secure. The main four points of cryptographic hash function evaluation are as follows (quoting wikipedia):

it is easy to compute the hash value for any given message
it is infeasible to generate a message that has a given hash
it is infeasible to modify a message without changing the hash
it is infeasible to find two different messages with the same hash

As Gumbo pointed out, strong hash functions result in wide variation of output for narrow variations of input. This is true for nearly every hash function ever considered secure, even the now discredited MD5 and Sha-1 algorithms. With most hash algorithms, the main attack vector is a collision and a close second is a decryption. I expect in my lifetime that MD5 and Sha-1 will be broken, either through a thorough decryption effort or exhaustive lookup tables (for inputs under a certain length). Pattern detection in hashes may receive some further analysis. I expect that the capability to detect the presence of a pattern will arise, but the ability to definitively state what the pattern is will hinge on the ability to retrieve the plain text.

Consider the hash values of your provided example passwords:

Password                            Hash
545h9yEQ8k37t!VW53d7g6263!&D4grz    466f4dff9339bd8837a8fa960f41fc44
645h9yEQ8k37t!VW53d7g6263!&D4grz    16731f2026d9d600e7dbf66b46db7dde

I only see 5 characters that match up between the two hashes. If you took the comparison down to the bit level, maybe half of the remaining bits are equal. This is a reasonably high degree of difference between the output, considering the similarity of the inputs.

In other words, this is likely:

  We can say with 90% confidence that the plaintext of these hashes are a maximum of x-degree difference from each other.

This is extremely unlikely:

  Clearly, the user is following a pattern of incrementing the highest bits of their password every week.

Especially considering that all of the attacks on hash functions are actually interested in this:

  Oh, the hash is x? y, z, a, b and c plaintexts all map to that hash for this algorithm.

This is the rainbow table approach to password cracking, and it is very common. Most large security breaches that make headlines come from the store of passwords being leaked (most commonly through a web-based SQL injection attack).

Since you phrase it from the perspective of a hacker obtaining hashes of your password, let me put it to you another way. How much do you trust the security of the entity storing your hashes? Supposing that said entity is storing your previous hashes (which given the requirement to change it every week, I also find it likely that they will enforce a difference or minimum degree of difference which pretty much requires them to store a history), if they are breached such that the complete list of your previous password hashes are taken, it's not that much more unlikely the attacker can compromise the systems in an ongoing way and simply start recording password plaintexts as they come in.

There is a particular situation where you may be at risk in the way you imagine. If you are ever told that your new password is too similar to a previous password, then the authority almost certainly storing a list of information about your previous passwords which is less cryptographically secure. If this list is taken along with the hashes, then you're much more likely in danger of your pattern being found out. Read up on string metrics if you're interested in this - most of those metrics (as solutions for enforce password differences) would certainly require your password to be stored in plaintext.

Update: The previous two paragraphs are not necessarily true. It is possible to calculate similarity between old and new passwords, if the change password procedure requires you to provide the old password(s). See this security question for details.

If you suppose that one of your plaintext passwords is known by an attacker (through some other attack vector), that does change the problem by quite a lot. I feel I should emphasize again, however, that this would be really a very outlandish attack on your password - if an attacker can gain one plaintext password, it is almost certainly easier for them to repeat that attack than to use some type of extrapolation for your other passwords. Furthermore, if one of your plain text passwords is known, you had darn well better change your pattern for generating new passwords, preferably starting with new, distinct high-entropy starting point.

Almost all attacks on cryptographic hash algorithms remain theoretical. If there were to be a sudden break through in a pattern/similarity attack on hashes, it would certainly make headlines (in certain circles). If we really are talking about an attack target that justifies major research efforts here, and we suppose that a number of your password hashes are known and a plaintext version from your history is also known, the attacker would probably also need to know what hash algorithm is being used and what salts are used for the given passwords. These are things that may be difficult to discover, but do not provide any additional robustness to your security: once they are known, and an attack is feasible, you need to redo your entire security apparatus.

But, if a plaintext is known, it's far easier attack, in my opinion, to simply compute variations on the plaintext yourself. Given a plaintext password, a known algorithm and salt values, and just one other hash result, your example pattern could be detected in just n attempts (where n is the length of the password, multiplied by some small, constant factor). Such a cracking attempt would follow this procedure:

increment a character
compute the hash
not a match? next character

If you complicate the pattern, the amount of attempts required increases. For example, you have a pattern for choosing which character you increment each time, then for the attack to predict your next password, they must have at least as many hashes for the length of your pattern to repeat. This is essentially defining a search space for the number of permutations. So if the attacker accurately predicts that only one character changes by one bit in each new password, then only n * m possibilities exist. So for your example passwords with 32 character length (n) and call it a-zA-Z0-9!-+ 72 possible values, that's only 32 * 72 = 2304 possibilities to search, far, far less than the 220 possibilities in the theoretical lower bound of MD5 algorithm security.

Changing a second character to an arbitrary value (not an incremental value), squares the search space, which gets you back into the range of cryptographic security (2304^2 ~ 2^22). But if they have a history and know you're only changing one character at a time, then it's only 2304 searches for each step in the history (multiplicative, i.e. linear growth of the search space instead of exponential).

Hope that helps, even if I didn't provide the actual complexity of pattern detection in hash values (because such an attack does not yet exist for any cryptographic hash function).

Edit: I should probably provide a disclaimer. I am not a crypto expert, just a hobbyist/novice applying reasoning and analysis from what little I know.


Presuming this documentation is correct, the answer is no, these numbers are not cryptographically secure. The Random class uses a linear congruential formula with a 48 bit seed. For most purposes it is not enough even if you only require 48 bit security. Given a fairly low number of outputs from a LCG, it is possible to derive the seed, even if only a few bits of each seed iteration are used. That question has been answered here.


Have any PAKE extensions been added to TLS 1.3?

Has anything been done since then to add PAKE support to TLS 1.3? Are there any active proposals?

No, nothing has been done, and there are no active drafts.
One possible reason for this (I don't know if this is the reason; it sounds plausible to me) is that the TLS working group is waiting for the CFRG [1] to complete its study of PAKEs; the CFRG is mostly done; they have selected OPAQUE as the recommendation if you need an asymmetric PAKE (the server doesn't need to know, which fits how TLS would use it) [2], however just selecting the winner is not sufficient - they need to put together an RFC that explains exactly how to use it (and how to avoid various subtle pitfalls).
Once the CFRG has put together such an RFC, I would expect that a proposal to use it within TLS will be submitted (of course, you are welcome to submit such a proposal)
[1] The Crypto Forum Research Group; that's a group whose purpose is to make recommendations about cryptography to the various IETF working groups
[2] And the winner in the symmetric case would be CPACE; however that is less likely to be used in TLS, as it requires the server to have a copy of the password


Is this an effective obfuscation technique?

It sound like you're using something like an XOR cipher to obfuscate your code.  It will appear to be encrypted, but this can still be broken by frequency analysis since the use of a constant shift means that the encryption effectively has no key.  An example of how to break a similar XOR cipher can be found here.  As @iismathwizard mentioned, decryption requires no more knowledge than the fact that XOR is in use, in the same way as as ROT13 cipher might be broken


Meaning of "integers modulo 4 " in "Fully homomorphic encryption modulo Fermat numbers" scheme

"Integers modulo 4" is usually the finite ring $(\Bbb Z_4,+,*)$ which internal laws are

+ | 0 1 2 3     * | 0 1 2 3
--+--------     --+--------
0 | 0 1 2 3     0 | 0 0 0 0
1 | 1 2 3 0     1 | 0 1 2 3
2 | 2 3 0 1     2 | 0 2 0 2
3 | 3 0 1 2     3 | 0 3 2 1

but here, the question's citation only deals with the finite group $(\Bbb Z_4,+)$.

  difference between "integers" and "integers modulo 4"

In the later, everything is reduced to four values, which can be expressed on two bits, the two lower bits of normal integers.


Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive？

In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published.

Consider a malicious algorithm $M^*$ that picks a random individual's record from the input database (of size $n$) and outputs it. Note that this $M^*$ should not be considered secure for a good differential privacy definition because it compromises the privacy of a random individual.

However, the additive differential privacy definition regards $M^*$ as a secure algorithm for $\epsilon=1/n$. To see this, consider two input databases $X,Y$ (both of size $n$) differ with a single element $d$ (where $d\in X$ but $d\not\in Y$). Then, it's not hard to see $\Pr[M^*(X)\in S]\leq\Pr[M^*(Y)\in S]+1/n$ holds for any subset $S\subseteq R$, i.e., $M^*$ satisfies the additive $1/n$-differential privacy.

The above issue is fixed by the standard multiplicative definition. Note that for $S=\{d\}$, there is no $\epsilon$ such that $\Pr[M^*(X)\in S]\leq\Pr[M^*(Y)\in S]\cdot e^\epsilon$ because $\Pr[M^*(X)=d]=1/n>0$ and $\Pr[M^*(Y)=d]=0$. That is, $M^*$ does not satisfy the standard $\epsilon$-differential privacy.


is it correct that for a nbit LFSR (galois algorithm in particular) the maximum number of unique 32byte keys can only be 255?

An $n-$ bit primitive LFSR generates the $2^n-1$ unique nonzero $n$ tuples exactly once in a cycle.

Take $n=8$ and your questions all have the answer yes, except the all zero seed will not give any tuple other than the all zero tuple.

However, such an $n$bit primitive LFSR generates all $k$ tuples, for $k\leq n,$ (provided its initial loaading is nonzero)

$$2^{n-k}$$
times if the $k$tuple is not all zeroes, and
$$2^{n-k}-1$$
times if the $k$ tuple is all zero.

So these $k$ tuples are not unique, repeat at pseudorandom times along the cycle, but you do get the all zero $k$ tuple occur naturaly in the scheme.

Example: $n=4,k=3.$ There should be 2 of each nonzero 3-tuple in
a period while the zero 3 tuple should occur exactly once. The sequence below is a primitive LFSR sequence. I have taken $2^4-1+2=17$ symbols instead of 15, so I can examine the 3-tuples starting within one period from position 1 to position 15. I grouped in 5's to make it easy to see positions

00100.11010.11110.00

001 occurs twice, starting in position 1 and 4

010 occurs twice, starting in position 2 and 8

100 occurs twice, starting in position 3 and 14

etc.

000 occurs once, starting in position 15


Generating ElGamal parameters in a mix net

The generation is actually quite straightforward.

I'm just paraphrasing the beginning of section 3.1 of A Threshold Cryptosystem without a Trusted Party by Pedersen.

Every participant $P_i$ (for $i=0\ldots n$) picks a secret key $sk_i$ and computes the public key part $pk_i = g^{sk_i}$. $P_i$ then publishes a commitment to $pk_i$.
When all commitments have been broadcast all the $pk_i$ are revealed and the commitments checked.
The global public key is $pk = \prod_{i=1}^n pk_i$


Can you help me understand multiplication of points when using Curve25519?

The Curve25519 paper gives you some hints about this. In Section3, it says:

  Responsibilities of the user. The legitimate users are assumed to generate independent uniform
  random secret keys. A user can, for example, generate 32 uniform
  random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the
  last byte, and set bit 6 of the last byte.

Curve25519 lets you use as secret key any 32-byte sequence that fulfills this restrictions. Although in principle multiplication assumes that you introduce a valid secret key fulfilling all these conditions, the code you mention tries to enforce this on its own. Note that it doesn't perform a validation check on the secret key, but directly modify it in case it didn't comply.
So, clearing bits 0, 1, and 2 of the first byte is this line of code:

mysecret.bytes[0] &= 0xf8

Clearing bit 7 of the last byte is this one:

mysecret.bytes[31] &= 0x7f,

And setting bit 6 of the last one is the next line:

mysecret.bytes[31] |= 0x40;

With respect to your last question, I think there may be a misunderstanding. In the comments, you seem to be asking about commutativity of Curve25519 (i.e., $ab == ba$), rather than associativity. Remember that you are performing scalar multiplication. That is, the multiplication of a scalar $x$ by a base point $G$. In this case, the scalar is the secret key. Therefore, it doesn't make sense to think of commutativity.


Question about the definition of a secure PRF

You have the math right, but you seem to have mis-interpreted the formulas.  So, let me try to walk you through it.

The "advantage" of an attack is the difference $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]|$.
The advantage is a measure of how effective the attack is.  If the advantage is large (significantly greater than 0), the attack is successful (and the function is not a secure PRF). If the advantage is negligible, the attack is ineffective.

You suggested we look at an attacker whose algorithm always returns one.  In this case it turns out that the advantage is 0: in particular, $\Pr[Exp(0)=1] = \Pr[Exp(1)=1] = 1$, so $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]| = 0$.  Since the advantage is 0, this attack strategy is ineffective -- exactly as you'd expect.


Understanding Unique-SVP and Kannan's Embedding

The columns of matrix $B'$ generate a lattice $\Lambda'=\{\mathbf v'\in\mathbb Z^{n+1}\}$ where the first $n$ entries form a vector which differs from a vector of $\Lambda$ by some multiple of $\mathbf e$ and the last entry is the same multiple of $M$. We also need some guarantee that $\mathbf e$ is shorter than the shortest vector of $\Lambda$ by some amount and that $\mathbf {As}$ is the closest vector to $\mathbf b$.
$M$ is not necessarily an integer, but is some value such that e.g. $M=||\mathbf e||$ when we know $||\mathbf e||<\lambda_1/2$ where $\lambda_1$ is the length of the shortest vector of $\Lambda$. It follows that the vector $(\mathbf e, M)^T$ has length at most $\sqrt 2M<\lambda_1/\sqrt 2$. This is shorter than any vector of the form $(\mathbf x, 0)^T$ which corresponds to a vector $\mathbf x$ of $\Lambda$ and so is of length at least $\lambda_1$. It is shorter than any other vector of the form $(\mathbf y, M)^T$ by the definition of the closest vector. It is also short than any vector of the form $(\mathbf z, kM)^T$ for any $|k|\ge 2$ as such a vector has length at least $|k|M>\sqrt 2 M$ based on the final component. It follows that $(\mathbf e, M)$ is the unique shortest vector of $\Lambda'$.


When does the first rotor in Enigma machine rotate?

Having had the privilege of using one of the original machines, I can tell you the sequence is the following:  set the plugs, and set the rotors.  Once you push the key, you can feel the force of the rotors turn, and the light turns on for the encrypted letter.  The light turn off when you take pressure off the key.

This was on a 3-wheel Enigma, and I do not have any personal experience with the later models, but I will assume they work the same way.


OpenSSL cipher suite support / key requirement for ecdhe_ecdsa_with_aes128_cbc_sha256

Why does the server say there was no shared cipher when I explicitely set up the server to support only that one cipher suite?

The chosen cipher suite requires that an ECC certificate gets used. Likely you have a RSA certificate instead since most instructions on how to create a certificate cover only this. If you have a RSA certificate you cannot use an ECDSA cipher and thus the server has essentially no cipher to choose from - which results in no shared cipher.

How can I make this work?

Create an ECC certificate for the server. See for example Create a self-signed ECC certificate for instructions.


If we can find prime numbers larger than 17 milion digits, why can't we find all 1024bit primes?

Due to the prime number theorem the number of primes with length $2^{1024}$ is approximately

$$\pi(2^{1024}) - \pi(2^{1023})\approx  \frac{2^{1024}}{\ln(2^{1024})}- \frac{2^{1023}}{\ln(2^{1023})} \approx \frac{2^{{1024}}}{709.8} - \frac{2^{1023}}{709.1}\approx 2^{1013.5}$$

The number of atoms in the universe is approximately $10^{80} \approx 2^{265.75}$, which means...

Edit, fixing math:

... you would have to fit just around $2^{748} (\approx 2^{1013.5 - 265.75})$ prime numbers in every single atom in the universe in order to store this list.

To further break this down:
Assume you could program atoms to output 1 prime at a time for 1 attosecond (shortest measured time, $2^{-18}s$), you would still need $2^{663.1}$ years, and it's been "only" $2^{33.7}$ years since the Big Bang.

Short: It's far, far beyond the anything ever achievable. And this is not due to our technical limitations, it's just not possible in existence.


How to find the decryption algorithm for this encryption scheme?

How do decrypt?  Lets do the easy part first:

Given the ciphertext $(a, b) = (g^r, g_0^{m_0} \cdot g_1^{m_1} \cdot h^r)$, with the private key, we can compute $a^{-x} b = g^{-rx} g_0^{m_0} g_1^{m_1} h^r = g_0^{m_0} g_1^{m_1}$

Now comes the tricky part, now that we know $g_0^{m_0} g_1^{m_1}$, how do we solve the discrete log problem to recover $m_0, m_1$?

Without making additional assumptions on the group $\mathcal G$, the best we can do (assuming that $m_0, m_1$ are known to be at most $k$ bits long) is a generic log algorithm that takes $O(2^k)$ time.

One way is to do this is to have precomputed the values $g_0^{-0}, g_0^{-1}, g_0^{-2}, ..., g_0^{-2^k+1}$ and $g_1^{0}, g_1^{1}, g_1^{2}, ..., g_1^{2^k-1}$, and for each $0 \le i < 2^k$, compute $g_0^{m_0} g_1^{m_1} \cdot g_0^{-i}$ and see if it matches any of the $g_1^j$ values; if so, then we have the decryption $m_0 = i$ and $m_1 = j$.

Of course, there is a possibility (given that $g_0, g_1$ was selected randomly) that the decryption might not be unique.  This possibility can be checked at key generation time, and a different $g_0, g_1$ pair be selected.


I think you have some misunderstanding here. Finding collisions when knowing the trapdoor is a required feature, but leaking the trapoor when knowing collisions is an undesirable "feature" (which some constructions suffer from).

A chameleon hash function (aka trapdoor commitment) allows you given the trapdoor to find pairs $(m,r)$ and $(m',r')$ with $m\neq m'$ such that $Ch(m,r)=Ch(m',r')$. This means that given the trapdoor you can produce such pairs and it should be computationally infeasible otherwise. There are many theoretical and practical applications of chameleon hash functions. One nice practical application are sanitizable signatures, where the knowledge of the trapdoor allows a sanitizer to sanitize an already signed message without invalidating the signature.

However, there are some constructions of chameleon hash functions (trapdoor commitments), that leak the trapdoor if one such pair has been computed and is publicly known. Note that the chameleon hash functon in the linked paper (Section 2.2.) is essentially a Pedersen commitment and the trapdoor is the discrete log between the two group elements. When knowing $Ch(m,r)=Ch(m',r')$ for two pairs $(m,r)$ and $(m',r')$ with $m\neq m'$ this allows to extract the trapdoor (just take a look at the binding proof for Pedersen commitments to see how this works - or just look at the equation under figure 3 in your linked paper and solve for $x$).

Chameleon hash functions which suffer from this "undersirable feature" are known to suffer from key exposure (which clearly often is a very undesirable feature). You should take a look at this paper for constructions that do not suffer from this limitation and there are also some other constructions which do not suffer from key exposure as well.


Solving a quadratic equation for a variant of Rabin

The tricky point is that modulo a Blum integer (the product $n = pq$ of two primes $p$ and $q$ that are equal to 3 modulo 4), in general, a quadratic residue (a value that is a square of something) has four square roots, not two.

Consider the "normal" Rabin algorithm. Message $m$ is encrypted into $c=m^2\bmod n$. To decrypt, you work modulo $p$ and modulo $q$. Modulo $p$, you first compute $c_p = c \bmod p$, then $d_p=c_p^{(p+1)/4} \bmod p$
. The value $d_p$ is a square root of $c_p$ modulo $p$; however that is not the only square root. The other one is $d'_p=p-d_p$ .

Similarly, working modulo $q$, you get two square roots of $c$ called $d_q$ and $d'_q$. By combining these square roots with the CRT, you end up with four candidates for $m$. This is the usual problem with Rabin encryption: you have to include some redundancy of format in the message (e.g. deterministic padding computed through a hash function) to determine which of the four candidates is the right one.

With the variant, things are similar: you must still work modulo $p$ and modulo $q$, and get two candidates modulo each prime, hence four combinations. With encryption $c=m^2+Bm \bmod n$ , you solve modulo $p$ the equation:

$$c_p \equiv  d_p^2+Bd_p \pmod p$$

which is equivalent to:
$$d_p^2+Bd_p-c_p \equiv 0 \pmod p$$

you solve it by computing $D_p=B^2-4c_p$, then extracting one square root $S_p=D_p^{(p+1)/4} \bmod p$. The two candidates are then:

     $d_p=(-B+S_p)/2 \bmod p$

     $d'_p=(-B-S_p)/2 \bmod p$

You also get two candidates $d_q$ and $d'_q$ modulo $q$, and the CRT gives you the four candidates for the decryption result.

Note that whenever you extract a square root with the $(p+1)/4$ exponent, you should verify that you indeed get a square root (by squaring it and checking that you indeed get the source value). Modulo $n$, only about one value in four is a quadratic residue. If the encrypted message is correct, then all square root extractions shall succeed, and you get four candidates; if it is not, then you get wrong values, and you should report an error.


Key derivation with Curve25519 for data encryption

What you actually want is called a key-based key derivation function (KBKDF).
The most prominent KBKDF (and really the standard solution here) is HKDF.

This is a function that takes a secret key (e.g. a KEK or a root key or something) and outputs (a set of) derived keys enjoying some nice properties.

You can customize the keys to get different keys for different purposes, e.g. you can add a purpose-string to them which ensure you won't accidently re-use some key material
You can salt the key material. This way you can store a (non-secret) salt with the object to be encrypted and this will ensure all files enjoy distinct encryption keys (and the customization ensure each key-based operation on an object has a different key)
Given a derived key it is impossible to find any other keys except for those derived from the leaked one.
The derivation process isn't computationally expensive (especially compared to PBKDF2 and Curve25519)

Now for a short clarification:

Curve25519 is an elliptic curve used to perform signature operations and derive keys between two distinct parties such that no passive attacker can obtain the negotiated key. This clearly doesn't apply to you as you already have the key material.
PBKDF2 is an (old) password based key derivation function which is used to process passwords such that the operation takes more time and thus it is more computationally expensive for an attacker to brute-force a password out of a given key. This one does not apply to you because your key material has such high entropy that an attacker doesn't have a chance at brute-forcing anyways.


What is the last value in a cipher suite?

HMAC is the underlying primitive used to construct the PRF. The cryptographic hash is used to construct the HMAC.

It is (at least) used to derive the session keys. The only thing that changes is that records that transport the data do not rely on the HMAC function anymore.

The PRF (and therefore the underlying HMAC) has one configuration parameter: the underlying hash function. This is what is specified at the end of the ciphersuite.


How is Blakley's Secret Sharing Scheme perfect?

Okay so SEJPM's comment just gave me an answer or better made me realize my flaw:

Since the secret is only one coordinate (e.g. $x$) the information that the secret is on a specific infinite line is as much information as having none at all, since guessing $x$ of a point on $y = 5*x$ is worth as much as guessing $x$ of a point on $y = z * x$

The information would only be revealed if the secret would be the entire point, not just one coordinate.


TLS: How is the shared secret (via Diffie-Hellman) used in the symmetric crypto function?

The shared secret that Diffie-Hellman produces is known as the premaster secret. This is then passed through the cipher suite's PRF to get the master secret, which is then passed through the PRF again to get the various keys and IVs. The master secret is always exactly 48 bytes long; the keys can be as long as needed.

Now, the PRF. TLS tends to use a PRF based on HMAC, using a hash specified by the cipher suite. The PRF takes three inputs: a secret, a label (which is generally "the thing this is calculating", and a seed (which, for key derivation, is derived from random values in client and server handshake messages). It outputs as much data as is needed. While this is a key derivation function, it is not a password-based key derivation; it is a key-based key derivation function. A PBKDF must be slow, as that's the only hope to stop someone from brute-forcing a password. But TLS's cipher suites produce high-quality premaster secrets: it is infeasible to guess them. So, all you need to do is to make it infeasible to figure out one key given a different key, and a PRF is sufficient for this.

For small values of $k$: First, keep in mind that these are constant-width data types. The output of 1024-bit Diffie-Hellman is always 1024 bits, regardless of the numeric value. If you mean "what about brute-forcing," this is what "high-quality premaster secrets" is about. While it's possible DH might result in an output of 10, it's monumentally unlikely. Any attacker who's starting his brute-forcing at zero and going up is an idiot, who will almost certainly never break any connection. If the attacker guesses what your key is, he can break the connection, but the point is that he can't feasibly guess it.


What is the use of Mersenne Primes in cryptography

I can think of two places where we use a Mersenne Prime within cryptogaphy:

As a modulus within a prime elliptic curve.  $2^{521}-1$ is a prime, and so we can define an elliptic curve using $GF(2^{521}-1)$, which is in moderately common use.  One reason we use such a modulus (rather than another prime of approximately the same size) is that the special form of the prime makes computing $x \bmod 2^{521}-1$ easy.
In the (rather obscure) Carter Wegmen Counter mode, we use the fact that $2^{127}-1$ is prime; we use that prime, rather than another value, because it is approximately the correct size, and (as above) computing $x \bmod 2^{127}-1$ is easy.

In both cases, the special property that we take advantage of is that they make computing the modulo operation cheap (by using shifts and adds).


My SSH server public key is 2048 bits, but my account's private key is 4096. What is my effective security?

It appears that based on your description, the server has a 2048 bit key pair and the clients logging in have 4096 bit key pairs.

  In this case, do I have the brute force protection of 2048 or 4096 bits?

For someone to impersonate one of your users, they would have to break the 4096 bit key.

For someone to impersonate the server, they would have to break the 2048 bit key.

  My worry is that someone could brute force the private key and login to the server.

Unless you work for some huge financial institution or a government, if someone could break either of those key sizes they are likely not going to go after you. ATM, there is no publicly available way to brute force a 2048 bit key. Someone with the ability to do it could easily make millions of dollars. So I'd say you are safe.


Will the complement of a 64-bit key and message produce the complement ciphertext if ECB is used in DES?

In short, yes.

The complementation property of DES states that if $DES_K(P) = C$, then $DES_{\overline{K}}(\overline{P}) = \overline{C}$,  where $\overline{X}$ is the complement of a string $X$.

ECB with DES takes a message $M_1M_2\cdots M_\ell$ and computes $C_1C_2\cdots C_\ell$, where $C_i = DES_K(M_i)$, for $1\le i\le\ell$. Therefore, if you encrypt $\overline{M_1M_2\cdots M_\ell}$ with ECB and DES under $\overline{K}$, then you get $C_1'C_2'\cdots C_\ell'$, where $C_i' = DES_{\overline{K}}(\overline{M_i})$. By the complementation property we know that $C_i' = \overline{C_i}$, so the result is the complement of the ciphertext.


Can the RSA accumulator scheme be converted to Elliptic Curve math?

OK posting my own answer, not sure if this is correct, but:

The RSA accumulator scheme relies on the lack of knowledge of the totient function, which is used for computing inverse powers.

The EC scheme doesn't have this restriction so you're able to prove any value is a member of the set simply by computing its inverse.


Explain: An NTRU key for a lattice of dimension $d$ has size only $O(d\log{d})$

An NTRU public key is a polynomial of degree $d-1$ whose coefficients are elements in $\mathbb{Z}_q$.  So the number of bits you need to represent it is $d\log{q}$.  If q is of the same order as d, then this gives you $d\log{d}$.  The private key, on the other hand, can be represented with $O(d)$ bits since the coefficients are all in the set $\{-1,0,1\}$.


Eve shouldn't be able to find the shared secret easily from the messages Alice and Bob send.

In the questions 1 and 2, you said that the shared secret is the sum/the product of the two messages, but anyone can compute them. Therefore, you are wrong.
The shared secret should be:
1) $B=(128)(65)2 = (65)(128)2\mod p$,
2) $B=(2^{(65)})^{(128)}=(2^{(128)})^{(65)}\mod p$.

Once you understood these two examples, I am sure you will be able to solve the 2 other questions easily by thinking a bit more about it.

Edit: you're right about 2).


If I understand you correctly, you're asking, given C1 = AESK1(P1) and C2 = AESK2(P2), whether it is possible to obtain P1 or P2 in the case where K1 = P2 and K2 = P1. The answer is no, it is not.

There are no known cryptographic attacks that are made easier by having the ciphertext of two keys that are mutually encrypting each other. Obviously, it does allow an attacker to discovery both keys after having discovered only one of them, since they would be able to decrypt the second key once they know the first. Any cipher which becomes weaker when encrypting certain kinds of plaintext (whether known plaintext, all zeros, or even a key used by another cipher) would be considered badly broken. A strong cipher like AES does not have this problem as long as the key is secret and chosen randomly.


What is difference among eavesdropper attack, multiple message attack and CPA attack?

If we try to make an equivalent to these terms in intuitive cryptography (before its formalization into games became the norm)

In an eavesdropper attack, the assumption is that an adversary only intercepts a single ciphertext for any given key (and, perhaps, knows the plaintext except for a small portion).
In a multiple messages attack, the assumption is that an adversary intercepts multiple ciphertexts enciphered under the same key (and, perhaps, knows the corresponding plaintexts except for a small part of one); that happens in practice, where keys are reused.
In a Chosen Plaintext Attack, the assumption is as above, plus an adversary can obtain ciphertext for any plaintext submitted (typically: iteratively; that is, the adversary can submit a new message on the basis of ciphertext obtained earlier); that models an attacker dropping a message in an embassy's letterbox, hoping that it will be sent enciphered to the Department of State for analysis.

Different games model that in the current approach of cryptography. Theses games are typically designed for worst-case scenario, and a typical game for said eavesdropper attack is as follows (and summarized in the question):

the adversary chooses any two distinct plaintexts (yet that game is not intended to model Chosen Plaintext Attack; that choice is here to demonstrate that whatever knowledge the adversary may have of the message space won't help);
the challenger chooses a key at random, enciphers one of the two messages chosen at random, and gives the ciphertext;
the adversary bets on which of the two plaintexts was enciphered.

If an (algorithm (with cost polynomial to the number of bits in the key size) for an) adversary exists that succeeds with odds in excess of 50% (by some fixed $\epsilon>0$), the encryption is broken. This model is realistic (and I would say the only such one) for a relatively practical situation: enciphering the result of a referendum, using a key dedicated to that sole purpose.

There are different, more complex games that model the other attacks.


Would a Rubik's cube be a trapdoor function?

It might be a viable example for explaining the concept of a trapdoor function to a layman without a computer science or math background. But from a CS standpoint this is only half-true.

For a low number of n where n is the number of rotate-operations performed on the cube, it is true that finding a solution for the cube is more computationally expensive than applying the rotations. But with very high values of n this might change. It was proven that any rubic's cube configuration can be solved with 20 moves or less, and finding that 20 move sequence might in fact be faster than applying the "correct" sequence.


How secure is using a hash function as Key Derivation Function?

This is reasonable as long as (a) you mean some unique encoding of the seed and index $y$ when you say seed + y, (b) you never use the same seed and index for another purpose, and (c) you chose SHA3-256, or SHAKE128-256, or SHAKE256-256, and you are using the standard Ed25519 32-byte pre-master secret seed as the secret.  For (a): if, e.g., the seed is always exactly 32 bytes, you can use concatenation.  If the seed may vary in length, you might consider concatenating $n \mathbin\Vert \mathit{seed} \mathbin\Vert y$ where $n$ is the number of bytes in the seed so that there are no pairs of $(\mathit{seed}, y)$ that might be confounded by concatenation.

Note that the answer is specific to the SHA-3 functions above.  This does not apply to everything that might be called a hash function.  It is certainly not true of GHASH.  It doesn't even apply to SHA-256 unless you impose the additional constraint on the seed and the index that their lengths each be fixed, or that their encodings be length-prefixed.  This is because given $h = \operatorname{SHA256}(\mathit{seed} \mathbin\Vert y)$, it is easy to compute $\operatorname{SHA256}(\operatorname{pad}(\mathit{seed} \mathbin\Vert y) \mathbin\Vert y')$ without knowing the seed—the standard length-extension attack on SHA-256.  If you must use SHA-256 with variable-length seeds and indices (which it sounds like you needn't, but other passersby might read this), it may be simpler to just use it with HMAC to make a PRF, if not HKDF.

Generally, you should consider using something tailored for the purpose unless you have constraints ruling it out: KMAC, if you want a Keccak-based PRF; HKDF, if you must use SHA-2 and you want structured inputs for application and purpose labels.


libSTARK TinyRAM private inputs (Zero-knowledge proofs)

I would like to thank Jonathan Bootle who helped me answer my question.

TinyRAM has two tapes, the primary and the auxiliary. The Primary Input Tape is used for public inputs while the Auxiliary Input Tape is used to provide private inputs.


OpenSSL: Call X509_verify_cert on a certificate with OIDs unknown to openssl

Would it be possible to just replace the OIDs in the certificate so
  that openssl applies the correct algorithms?

No, this would alter the certificate and thus invalidate its signature, meaning you'd get a certificate error anyways with strategy.

However, I have searched around and by the looks of it, it's a "custom" version of the normal BSI issued ECDSA identifiers.

Normally, the OID-parent issued for plain ECDSA (BSI PDF) is 0.4.0.127.0.7.1.1.4.1, which makes sense because it is sorted under "algorithms -> id-ecc -> signatures -> 1 (ECDSA-plain)" under the BSI root node. Also note how this website says that 0.4.0.127.0.7.4 is unassigned, which means somebody could indeed have just used it "as a shortcut" to the desired signature algorithms.

Now there is one authoritative other mention, somewhere in the Doc 9303 series issued by ICAO for machine-readable travel documents, however I was not able to find this definition (and indeed there were no OIDs in the document where they allegdly were and the author making this reference left no contact info in his paper).

TL;DR: Chances are that this means that plain ECDSA with SHA-X was used and so I think standard ECDSA verification is worth at least a try.


How does a key actually work in symmetric ciphers

My sky-high level understanding of modern cryptography is as follows: there is an algorithm and a key.

Sure, a key is generally generated for a specific cryptographic algorithm that takes a key.

  The key or key pair is a randomly generated number (I think).

Not necessarily. AES and Serpent just take a key consisting of random bits. RSA uses two random primes that are used to create the key pair, where the keys consist of multiple parts, at least an exponent and modulus generated from these primes. Or it could be a random in a specific range for the private key of ECDSA or ECDH, where the public key is actually a point on the curve. That private key is probably closest to "a number".

  The algorithm describes transformations to be applied to the plain text in order to encrypt it.

If that algorithm is a cipher, then yes.

  The key is a specific piece of information that is needed by the algorithm to complete this process of encrypting the plain text.

Not sure about the emphasis in that description of the key, as there are other possible pieces like an IV that are required. It's a bit more than that; it is the piece of information that is at least required to complete the process.

  What I do not understand is how, precisely, do the algorithm and key interrelate.

That depends on the algorithm, the algorithm specifies what kind of keys are acceptable, and how large they may be (if there even is a maximum).

  One can look at a schematic for, say, Serpent and see lots of arrows, boxes, feedback loops and so on. To an interested lay person such as myself, I cannot see what the key (i) does to that set of processes or even where it fits in; (ii) how it is employed such that its uniqueness effectively 'locks' the cipher text.

That depends entirely on the algorithm. In block ciphers such as serpent there is a lot of transposition and diffusion going on, generally trying to create an avalanche effect so that many bits is affected even within a single round.

However, with the asymmetric RSA cipher the private key is used for modular exponentiation during decryption and in ECDSA for point multiplication during signature generation. Exponentiation and point multiplication are more mathematical constructs than the bit operations that are common in symmetric ciphers.

  Finally, I understand there isn't a single response to this inquiry given there are different types of keys used for different purposes. In the interests of addressing this, please assume I am referring to the encryption of plain text using a symmetric key algorithm that was fit-for-purpose in 2001 or later.

I've tried to explain it in the simplest way possible, also showing that it matters quite a bit what kind of algorithm we are talking about.

I'd study a bit more about block ciphers and try and e.g. implement S-AES (or SimpleAES, I'm not sure if there is an official name) if you're more of a developer type that learns by acting.


Collision and preimage resistance does not imply this; suppose we select a collision and preimage resistant function $H$ with a known value $I$ with $H(I) = 1$ (the group identity); this additional assertion does not contradict the assumptions of collision or preimage resistance. Then, given $a$, we can easily output the tuple $(I, a)$; as we have $H(I) \times H(a) = H(a)$.

In addition, we can see that this problem is strictly easier than preimage or second preimage problems.  Suppose that $H$ is a random Oracle, and that the group size is $n$; then, we can solve the problem by selecting $\sqrt{n}$ values of $b$, $c$, and computing two lists consisting of the values $H(b)$ and $H(a)^{-1} \times H(c)$ and looking for a value that occurs in both of the lists, that is entry $i$ of the list $H(b_i)$ is the same as entry $j$ of the list $H(a)^{-1} \times H(c_j)$.  If the random Oracle is acts randomly, then with good probability we find a common value; this gives us a pair $(b_i,c_j)$ in $\sqrt{n}$ time; this is faster than we can solve either the preimage or second preimage problem against a random Oracle (which takes $O(n)$ time).  If we had a reduction that took fewer than $O(\sqrt{n})$ calls to this problem, this would imply that we could solve the preimage problem faster than $O(n)$, which we know we can't do.

[Note: I updated this paragraph since the answer was accepted]

As for whether this problem is easier than the collision resistance problem (assuming we don't know a magic $I$ with $H(I)=1$), neither problem can be reduced to the other, as one can devise hash functions where one problem is difficult, and the other is easy.

For a hash function for which collision is hard and "preimage by product" is easy, take an RSA modulus $N$ (of secret factorization) and a value $g$ of order $lcm(p-1, q-1)$, and define the hash function $H(x) = g^x \bmod N$ for positive values of $x$ (and asking for $H(0)$ is not allowed; 0 is not positive).  Finding two distinct values $x, y$ with $H(x) = H(y)$ is equivalent to factoring $N$, and so that's difficult; however given any $a>1$, we can find the pair $a-1, 1$ with $H(a-1) \times H(1) = H(a)$.

For a hash function for which collision is easy and "preimage by product" is hard, take a random Oracle, and define $H(x) = Oracle(trunc(x))$, where $trunc$ strips off the lsbit of $x$.  Then, finding collisions is easy (just output two values that differ only in the lsbit), however solving the "preimage by product" for H is equivalent to solving it for the random Oracle.

My intuition says for realistic hash functions, these problems are likely to be approximately equally difficult; certainly, the generic attacks against collision resistance (forming a list, rho-based approaches) can be adapted to work against your problem.


How to choose the appropriate public (i, m) and private (j, m) keys?

I assume that $m = pq$ (85) is the modulus, and the number you computed (64) is $\phi(m)$. Now we must choose the exponents ($i$ for public, $j$ for secret? , weird notation) in such a way that $ij = 1$ modulo $\phi(m)$. In fact we can work modulo 16 if we like, because that is the least common multiple of $p-1$ and $q-1$. So if we choose $i = 3$, we choose $j=11$, as $33 \equiv 1 \mod 16$. Or $i=11$, $j=3$, this is symmetrical. Or we could choose $i = 5$ and then $j=13$ works, or vice versa again.

Then encryption of a number smaller than $m$ is exponentiation to the power $i$, modulo $m$ and decryption is exponentiation to the power $j$, modulo $m$.

Of course these numbers are way too small to provide any security, but that's the general idea.


I would say that whitening is a more general concept than randomness extraction.

In randomness extraction you have an input with some entropy that isn't perfectly random and an output that should be perfectly random and full entropy. In whitening there is not necessarily an entropy requirement on the output, it just needs to look perfectly random to an adversary.

For example, suppose you have a $b$-bit input $I$ with at least $e$ bits of entropy:

A randomness extractor would map it to at most an $e$-bit output, for example the first $e$ bits of $H(I)$. (Better yet, an $\frac{e}{2}$-bit output, as NIST recommends in 800-90B.)
A whitener could instead use encryption with a secret key $E_k(I)$. This gives a $b$-bit output that may only have $e$ bits of entropy, but still looks random as long as the key is secret.

With the above definitions, Von Neumann is both a randomness extractor and a whitener (when the input is a Bernoulli sequence).


If I concatenate two colliding SHA-256 messages with the same prefix and suffix, will the resulting hash output still collide with each other?

The Generic Collision attack

Finding a collision with the generic collision attack for SHA256 requires $2^{128}$ computations with %50 probability of success. This bound is given by the birthday attack. There is no attack on SHA256 better than a generic collision attack yet practical. Assume that you have luckily found one; $$\operatorname{SHA256}(x_1) = \operatorname{SHA256}(x_2)$$

The SHA256 padding

Let's remember the SHA256 padding that uses 512 block size with the message length added to the end with 64-bit. NIST 180-4 page 13

  Suppose that the length of the message, $M$, is $\ell$ bits. Append the bit $1$ to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $$ \ell - 1 - k \equiv 448 \pmod{512}.$$
  Then append the 64-bit block that is equal to the number $\ell$ expressed
  using a binary representation.

back to your questions;

  Now, will $\operatorname{SHA256} (p\mathbin\|x_1\mathbin\|s)=\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$ as well?

If $len(p)$ is a multiple of the 512 then the result of $\operatorname{SHA256} (p\mathbin\|x_1) = \operatorname{SHA256} (p\mathbin\|x_2)$ will be same, this is like an extension attack on $p$. Otherwise the you have $1/2^{256}$ probability to hit the collision with one try.

What about the suffix $s$. This is not like the length extension attack since we have to consider the padding of $x_1$ and $x_2$ in $\operatorname{SHA256}(x_1)$ and $\operatorname{SHA256}(x_2)$, repectively. If one choose $s$'s beginning as the padding of $x_1$ and $x_2$ then it can be extension attack as long as the $len(x_1) = len(x_2)$. Otherwise, the collision is random collision.

As a result; the combination $(p\mathbin\|x_i\mathbin\|s)$ requires so much condition about the $p,x_1,x_2,s$ to have the collision with $1/2^{256}$ probability to hit the collision with one try.

In short, NO.

  Will $\operatorname{SHA256} (p\mathbin\|x_1\mathbin\|s)$ still collide with  $\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$ in the first 80 bits as well?

No. Even you have the collision the value will be different.


Why is $-1$ an illegal message in the Goldwasser-Micali Encryption Scheme

I'm going to use the notation from here.

I'm still not sure why one wants to handle $-1$ as a message, but anyways. Simple solution is that you simply define: if message is $-1$ set message to $1$ and the other way round when decrypting. Second point is that you can only encrypt messages from a message space with two elements (independent from how you name them).

Ok, but maybe this is the question/answer:

Basically the idea is that you encrypt a message bit by bit and the security of the encryption scheme relies on the quadratic residuosity problem.

That is, it is hard to distinguish between quadratic residues modulo $n=pq$ for primes $p$ and $q$ (the set is denoted as $QR_n$) and pseudo-squares modulo $n$. Thereby, a pseudo-square $x$ modulo $n$ is an element with Jacobi symbol $\left( \frac{x}{n} \right)=1$. This means that from the Jacobi symbol it looks like a quadratic residue, but actually it belongs to the set of quadratic non-residues ($QNR_n$), i.e., it is a quadratic non-residue modulo $p$ as well as modulo $q$, giving $\left( \frac{x}{n} \right)=\left( \frac{x}{p} \right)\cdot \left( \frac{x}{q} \right)=(-1)\cdot(-1)=1$.

However, without knowing the factorization of $n$, i.e., $p$ and $q$, which would allow us to compute the Legendre symbols $\left( \frac{x}{p} \right)$ and $\left( \frac{x}{q} \right)$, we cannot decide whether $x$ is a square or a pseudo-square.

Now, such a pseudo square $x$ and $n$ is the public key and the factorization $p,q$ is the private key. Taking $n$ as Blum integer has the reason that you can efficiently find such an $x$ (i.e., set $x=N-1$).

Encrypting amounts to chosing a random square $y^2$ for $y$ random from $Z_n^*$ and for message $m\in\{0,1\}$ we compute $c=y^2x^m \pmod n$. This means

if $m=1$: $c=y^2x \pmod n$ (gives a non-square, but with Jacobi symbol 1)
if $m=0$: $c=y^2 \pmod n$ (gives a square)

Now, by the quadratic residuosity assumption, without knowing $p$ and $q$ given the public key and $c$, one cannot decide whether $c$ contains an encryption of $1$ or $0$.

Decrypting is simply deciding whether $c$ is in $QR_n$ (giving $m=0$) or in $QNR_n$ (giving $m=1$).

Your question is now: what if we use message space $M=\{0,-1\}$? When taking $m=-1$, we would have $c=y^2x^{-1}$, i.e., we can interpret this as using the inverse $x^{-1}$ of $x$ modulo $n$. The question is: Would this also be a pseudo-square?

Now, we know that $x\cdot x^{-1} \equiv 1 \pmod n$ and we know that the $\left( \frac{1}{n} \right)=1$ ($1$ is in $QR_n$) and we know that for $a\equiv b \pmod n$ we have that $\left( \frac{a}{n} \right)=\left( \frac{b}{n} \right)$. This and the fact that the Jacobi symbol is multiplicative gives us that:

$\left( \frac{x\cdot x^{-1}}{n} \right)=\left( \frac{x}{n} \right)\cdot \left( \frac{x^{-1}}{n} \right)=1$. Now, we know the Jacobi symbol of $x$, which gives us

$1\cdot \left( \frac{x^{-1}}{n} \right)=1$. However, since $x$ is in $QNR_n$ and $1$ is in $QR_n$, $x^{-1}$ must be in $QNR_n$. Since it, however, must have a Jacobi symbol of $1$ is must be a pseudo-square.

So, yes, GM encryption would technically also work for $M=\{0,-1\}$ (but you could then give $x^{-1}$ instead of $x$ in the public key and work with $M=\{0,1\}$ again). I see no real reason why one should do that anyways (costs an extra inversion). Maybe there is an (obvious) security problem if you have $x$ in the public key and use $x^{-1}$ in the encryption, which I do not see at the moment.


What is usually meant by "group encryption" is not what you are after. Group encryption algorithms strive to achieve the following: a given message is encrypted, and may be decrypted only if sufficiently many group members collaborate. This is not what you seek; what you want is a system such that a given message can be encrypted once and every member of the recipient group can decrypt it independently of all others.

The technical term for what you want is broadcast encryption. A specific and quite challenging case is what is done in Blu-ray discs, and is called AACS. Namely:

Each Blu-ray reading device has its own private key.
Disc contents ought be readable only by allowed devices (this is the "recipient group") but there are billions of them.
It is impractical to include in the disc some data specific to each target device (same disc for everybody, and too many target devices).
Communication is one-way only (devices are offline, so the disc contents must be sufficient).
Media producers wish to retain some "revocation capability" so that the contents of new discs cannot be read by some known "cracked" devices, while still being readable by other devices which (that's the crucial point) cannot be "updated" in any way (since they have no network capability).

For small groups (as a chat server, with only a few dozen recipients), the problem is rather easy:

Have each group member own a public/private key pair.
Make a symmetric group key K, known to all members by virtue of sending to each member the encryption of K with his public key.
To add a group member, just send him K encrypted with his public key.
To remove a group member, since forgetfulness cannot be enforced, you have to create a new group key K' and send it to all remaining members.

The biggest cost in that system is group key renewal, which is necessary only when a member must be removed, and the cost is proportional to the size of the group (an RSA-encrypted value with 2048-bit keys is 256 bytes, which is very tolerable as long as groups are no larger than, say, a few hundreds of people).


Rate my idea: is that a stronger GPG-like algorithm?

Your idea is no stronger than simply having a common shared password $P_1$ from which the symmetric encryption key is derived.

  If Alice encrypts a message with Bob's hashed password, even if someone knows the shared password, only Bob can decrypt the message

You assumed the hash of Bob's password – $H(B_1)$ – is public, so if Eve knows both it and the common password $P_1$ she can calculate $H(B_1)||H(P_1)$. She doesn't need to know $B_1$ itself.

A program can be written to require the password $B_1$, but Eve could write her own program that accepts either the hashes or the passwords.

I.e. unless you assume $H(A_1)$ and $H(B_1)$ are private, they do nothing. If you do assume that, they effectively become part of the shared secret.

  Only Alice knows the common password, so Bob's is sure that the cypher is surely made by Alice (no MITM attacks, fake identity like in GPG)

Yes, but the problem of sharing the common password $P_1$ remains. If you can securely exchange that password, you can likewise securely exchange GPG keys or any other encryption keys.


What is the difference between the adversary and the algorithm?

This statement is just stating that since there exists an algorithm that can factor a number in time sqrt(N), we can use what we know about this algorithm to calculate the probability that the adversary can win an indistinguishability game against a challenger using this encryption scheme.

In other words, the algorithm is used to calculate the advantage of the adversary. Since the algorithm can factor $N$ in time sqrt(N), we must pick big enough primes, so that no probabilistic polynomial time adversary can attack the system.


Is there any hardware available to calculate single sha256 hash?

Sure, designs for such chips are available on the internet (e.g. http://www.cast-inc.com/ip-cores/encryption/sha-256/cast_sha256.pdf) but you would probably have to integrate them yourself into a hardware module, which is going to be expensive and time-consuming. You will find those integrated in things like HSMs and cryptographic accelerators as well as mining modules (e.g. bitcoin miners), but it's unlikely you will find a fast, cheap, standalone IC specifically dedicated to computing SHA-256 hashes from an arbitrary input.

The reason is simple: bandwidth. Take bitcoin miners for instance, very little bandwidth is required, since the device can mine autonomously without a constant stream of data from the host (it's just searching for a block that hashes to a specific number of zeroes, so it can just hash an incrementing counter, for instance). But a general purpose SHA-256 hashing device would need to be fed data from the host, meaning it can only run as fast as the communication interface, which is necessarily going to be limited to a few gigabits per second, maybe a few tens of gigabits per second in the best case.

If this device is to communicate with a computer, USB is a no-go as it is too slow (it wouldn't be much faster, if at all, than just running SHA-256 on all cores of a modern CPU, for instance). Probably your best bet is to leverage PCI express 3, or maybe Thunderbolt, that would be fast enough to make it worth it. So you could make a "SHA-256 card" that is designed or at least programmed to compute SHA-256 hashes, and plug it into a PCI express port to start sending it data.

Guess what: such a device already exists, and is called a GPU. This is, by very, very far, the most cost effective hardware to perform SHA-256 hashes over arbitrary inputs, in terms of raw performance. It's also commodity hardware, which helps, and is quite straightforward to program for, as opposed to FPGAs. It's not designed only for hash calculations, but it's as close as you're going to get to that if you don't want to start doing some serious (and expensive) R&D with high-performance, expensive FPGAs and ASICs.


What is the security strength of an n-bit HMAC?

See NIST SP 800-107, section 5.3.4:

  The effective security strength of the HMAC key is the minimum of the security strength of $K$ and the value of $2C$. That is, security strength = min(security strength of $K$, $2C$). For example, if the security strength of $K$ is 128 bits, and SHA-1 is used, then the effective security strength of the HMAC key is 128 bits, since for SHA-1, $2C = 320$. Note
  that, in this example, even if the security strength of $K$ is greater than 320 bits, the effective security strength of the key is limited to 320 bits (the value of $2C$ for SHA-1). In general, there is no benefit in generating $K$ with more than $2C$ bits of security. In particular, it is not sensible to generate $K$ with a bit length that exceeds the input block size of the approved $L$-bit hash function employed in the HMAC construction. Such a $K$
  is hashed, and the resulting $L$-bit value is used instead. Returning to the SHA-1 example, suppose that the key $K$ has a bit length greater than 512 (the input block size for SHA-1). Instead of using $K$ directly, HMAC replaces $K$ by its 160-bit SHA-1 hash value, and so the effective security strength of that choice of $K$ is no more than 160 bits.

Note that $C$ is defined as the size of the chaining value in above, which is generally equal to the output size without any reduction (so 256 for SHA-224 and 512 for SHA-512/256).

This of course doesn't mean that the security of the HMAC isn't related to the output size. The above description shows the security of the key, not the security of the final hash. You won't get 512/1024 bit security when you only generate a 256 bit result. In general though the final strength should therefore be min(keysize, output_size).


Can or can not D-Wave's quantum computers use Shor's and Grover's Algorithm to find encryption keys? Why?

D-Wave's "Quantum computers" are NOT general purpose quantum computers. They can only do quantum annealing, which allows a small subset of problems to be solved. They can't run Shor's or Grover's algorithms, as these aren't quantum annealing problems. It's also still an open question whether D-Wave's machines even provide any speedup over classical simulated annealing systems.


What exactly is an $n$‑bit number?

In the context, number designates an element $m$ of the set $\mathbb N$, the non-negative integers. Such $m$ is $n$‑bit if and only if $n\in\mathbb N$ and $\lfloor2^{n-1}\rfloor\le m<2^n$, or equivalently $n=\left\lceil\log_2(m+1)\right\rceil$. When $n\ne0$, that simplifies to $2^{n-1}\le m<2^n$, or equivalently $n=\left\lfloor\log_2(m)\right\rfloor+1$.
Any $n$‑bit $m$ in $\mathbb N$ has a unique $n$‑bit bitstring representation $x$ in binary per big-endian convention, and when $n>0$ the leading bit of $x$ is $1$. It holds $\|m\|=|x|=n$ per the notation in Katz&Lindell's Introduction to Modern Cryptography.
Any $n$‑bit bistring $x$ represents an at-most‑$n$‑bit $m$ in $\mathbb N$ per such convention. It holds $\|m\|\le|x|=n$ and $0\le m<2^n$. In some contexts¹, it's (slightly incorrectly) stated that such integer $m$ is $n$‑bit, when really $x$ is $n$‑bit and $m$ is at most $n$‑bit. The question is making just this when it states

$3$‑bit would be a number no greater than $111$ in binary which is $7$ in decimal.

What do they mean by negligible probability within the context of this question?

It means that for any polynomial $r$ (with positive leading coefficient²), for $n$ sufficiently large, the probability is less than $1/r(n)$ that it does not hold that $p$ and $q$ output by the algorithm are $n$‑bit primes.
Equivalently: for all $k>0$ exists $n_k$ such that $n>n_k$ implies that said probability is less than $1/n^k$.
Still equivalently: it is allowed only with probability bound to vanish when $n$ grows (and faster than any polynomial in $n$) that $p$ or/and $q$ are not prime, or/and are more or less than $n$‑bit.
Said probability is computed over all the inputs of the deterministic version of the Probabilistic Polynomial Time algorithm considered, where the randomness is explicitly introduced as an extra parameter, rather than implicit.

I assume it means the two prime numbers $p$ and $q$ are guessable by an adversary with negligible probability.

No. Nothing is stated in the definition quoted in the question about the probability that $p$ or $q$ can be guessed. That comes later in the text.
The probability in the definition is there to formally accommodate a probabilistic primality test, which can let a composite $p$ or $q$ creep out on rare occasions³. In practice, that probability is made so low that it's neglected.

¹ Including textbook RSA when dealing with the message rather than key generation.
² That's left implicit in Katz&Lindell's Introduction to Modern Cryptography, ed. 3, definition 3.4
³ It additionally allows $p$ or $q$ to occasionally not be $n$‑bit, as could be the case for $n<2$ (there's no prime less than $2$‑bit); or for primes generated as the smallest prime at least $m$ drawn uniformly at random in $[2^{n-1},2^n)$, which outputs a prime larger than $2^n$ with probability $O(n/2^n)$.


There is nothing that stops a Feistel cipher from having injective Sboxes.

One could remove the $32$ to $48$ bit expansion map $E$ in the DES $F-$function and have an injective Sbox layer made up of $4\times4$ Sboxes and thus an injective $F-$ function for a modified DES. It would need round keys of $32$ bits and thus use less randomness and be weaker.

Also, there are many Feistel and generalized Feistel ciphers out there, including AES finalists MARS and RC5. Studying them may help you understand $F-$ function design better.


In 0.9.8 there is only PKCS5_PBKDF2_HMAC_SHA1.

Sample C code:

#include <openssl/evp.h>
#include <openssl/sha.h>

void PBKDF2_HMAC_SHA_1nat(const char* pass, const unsigned char* salt, int32_t iterations, uint32_t outputBytes, char* hexResult)
{
    unsigned int i;
    unsigned char digest[outputBytes];
    PKCS5_PBKDF2_HMAC_SHA1(pass, strlen(pass), salt, strlen(salt), iterations, outputBytes, digest);
    for (i = 0; i < sizeof(digest); i++)
        sprintf(hexResult + (i * 2), "%02x", 255 & digest[i]);
}

In 1.0.1 there is also PKCS5_PBKDF2_HMAC, which allows passing in different underlying hash functions.

Sample C code for PBKDF2-HMAC-SHA-512:

#include <openssl/evp.h>
#include <openssl/sha.h>

void PBKDF2_HMAC_SHA_1(const char* pass, const unsigned char* salt, int32_t iterations, uint32_t outputBytes, char* hexResult)
{
    unsigned int i;
    unsigned char digest[outputBytes];
    PKCS5_PBKDF2_HMAC(pass, strlen(pass), salt, strlen(salt), iterations, EVP_sha512(), outputBytes, digest);
    for (i = 0; i < sizeof(digest); i++)
        sprintf(hexResult + (i * 2), "%02x", 255 & digest[i]);
}


GPG encrypt performance degradence for thousands receipients

You don't provide much information on your setup or. testing, but I'll take a stab at helping you improve the performance of your system.

Yes, ECDH is actually supposed to be less demanding than RSA in terms of demands it makes on the system, so I'm surprised at your situation and would equally love to know what caused it!

Here are some things to look at to help isolate the fault.  Might not address ECDH specifically, but need a baseline of info to at least start with:

Firstly, different version of GPG- GPG and GPG2- have different performance characteristics.  So useful to know what version you're using:

gpg --version
GPG encrypts to binary format by default unless told to use ASCII with the --armor r -a switch.  This can have performance implications.  Try the following command with and without the -a switch to see how performance is affected.  Also read the debug info which is output to see if it's puking any errors.

time gpg --debug-all --batch --yes --trust-model always -r username@userdomain.com -a -e ./gpg-performance-test.txt
Encryption is CPU intensive, so having a snappy processor improves performance.  Also check your memory:
free -m
Myself, if I had a gazillion people I needed to encrypt a message to, I'd write a script that iterates through a list of email addresses with the above command and emails the message.  And I would run top while the script was executing.  But it's possible to run a single command with multiple recipients so any of them can read the message with their secret key.  You're not clear on how you're doing the encryption.

Might be enough to help you identify the bottleneck, or if not, at least exclude what is *not causing it. If you've already identified the source of the problem, please post your findings.


The approximate way

You don't need to be perfectly even if you can make the unevenness small enough to be undetectable. So you can realistically do this: take the first 128 bits (16 bytes) from the SHA-256 output (or more, if you like), read them in as an unsigned bignum (arbitrary precision integer) using your library of choice, take the remainder modulo 6, and add one. The distribution will not be even—1 will be very slightly more likely than 6—but not distinguishable in practice from an even distribution.  The probability of picking 1 is:

$$
{\lfloor 2^{128} \div 6 \rfloor + 1 \over{2^{128}}}
$$

...which Wolfram Alpha tells me is about:

$$
0.166666666666666666666666666666666666667646245292351906256...
$$

And the probability of picking 6 is:

$$
{\lfloor 2^{128} \div 6 \rfloor \over{2^{128}}}
$$

...which is about this much:

$$
0.166666666666666666666666666666666666664707509415296187486...
$$

These values are only $2^{-128}$ apart, as you can tell algebraically from the expressions above. Good enough for cryptographic purposes.

NIST Special Publication 800-185 (SHA-3 Derived Functions) recommends a similar method for hashing with SHAKE or other variable length output functions into an arbitrary integer range. SP 800-90Ar1 (Recommendation for Random Number Generation Using
Deterministic Random Bit Generators), in Section A.5.3, recommends this method as well.

The exact way

Looping over the unsigned bytes in the SHA-256 result byte array, at each step:

If result[i] % 8 is less than six, return (result[i] % 8) + 1;
Otherwise, if (result[i] >> 3) % 8 is less than six, return ((result[i] >> 3) % 8) + 1;
Otherwise, continue on to the next iteration of the loop;
If you looped through the whole thing, be very suspicious you did something wrong, and if you didn't (!) assign result := sha256(result) and try again from the top.

Whatever number is returned, it is equally likely as all the other five.

On any given iteration, the chance that iteration will return is 75%, so with 64 attempts, the probability that none of them will return is $(1 - 0.75)^{64} = (2^{-2})^{64} = 2^{-128}$. And if that happens you hit step #4.


At first glance

$r = s^{-1} (M - a^y) \bmod p-1$

would appear to be what you're looking for.

If $s$ isn't invertable modulo $p-1$, then you can work around this by working with the factors of $p-1$; in this case, $p-1 = uv$ where $s$ is a multiple of $u$ and $s$ is relatively prime to $v$.

So, we can solve:

$r_v = s^{-1} (M - a^y) \bmod v$

and so we have:

$r = r_v + kv$

for some integer $k$; if you know $y_1 = g^r \bmod p$, then you can recover the correct $k$ in $O( \sqrt{u})$ time.


What kind of attack does the current brokenness of SHA-1 allow?

That's true. There should not be any publicly known attack on SHA-1 that allows for a given $d1$ to find a $d2$ such that $h(d1) = h(d2)$.

SHA-1 is vulnerable  for finding a pair of $d1$ and $d2$ such that $h(d1) = h(d2)$.

The same, however, applies to MD5, which is unusable for SSL/TLS certificates and a successful attack has been performed. So, this kind of collision can allow (under some circumstances) more that you might think.

The notable difference between SHA-1 and MD5 attacks is the cost of such attacks. For MD5, the attack is very fast. For SHA-1, the attack would be very expensive, but for some groups (e.g. governments) feasible.

(There might be also some more differences that I am not aware of. However, both of them use the Merkle–Damgård construction, which implies some common security characteristics.)


As already hinted at in the comments, this is really just a matter of getting an equation in one unknown and then solving for the unknown. We start with:
$$\begin{align}n_1&=p\;q\\n_2&=(p+2)(q+2)\end{align}$$
One method is to turn the later equation into $q = \frac{n_2}{p+2} - 2$ and substitute in the other equation, to get an equation in one unknown:
$$n_1 = p\left(\frac{n_2}{p+2} - 2\right)$$

Multiplying both sides by $p+2$ and getting everything on one side, we obtain this equation, implied by given equations:
$$2p^2 + (n_1 - n_2 + 4)p + 2n_1 = 0$$

This is a quadratic equation with unknown $p$ and coefficients computable from the givens $n_1$ and $n_2$. One of the solution will be $p$, and the other will be $q$ (since $p$ and $q$ have symmetrical role in the problem). Note that this math is not using modular arithmetic, it is just algebra of the variant learned in grade school for real numbers, which also works for integers.

As an example, suppose $p = 5, q = 11$ which means $n_1 = 55, n_2 = 91$. Plugging into our equation we get $2p^2 - 32p + 110 = 0$. With such small numbers, we can plug this into a quadratic equation solver and voila, we get values $5$ and $11$ as roots, and have successfully factored $n_1$, and $n_2$.

The rest of the problem only asks performing textbook RSA decryption knowing public key, having factored the public modulus.


Would increasing the "target space" of MD5 collisions make it significantly easier to find a collision?

Note: The attacks you refer to in that thesis are structural attacks, I will consider the complexity of a brute force attack, which would be applicable to any hash function $H$ which is well designed, approximating a pseudorandom function. There are some good answers here on the complexity of the birthday attack on a hash function, which is $O(2^{n/2})$ for an $n$-bit hash output.
Let $b$ be the number of bytes and $n=8b$ be the number of bits in the output of $H.$ It seems to me that you are happy for the hex output to be "almost correct". So we should consider the $2b$ output nibbles in $\{0,1\}^4$ and say that the output is almost $f-$correct if there are up to $f$ nibbles that are different than the output you are trying to get near to. For your examples, $f=2.$
The crucial thing is to identify the size of your 'target space', which is
$$
T:=2^{4}\sum_{j=0}^f\binom{2b}{j},\quad\quad\quad\quad(1)
$$
since there are $2^4$ nibbles. Now, $T=2^4(1+2b+2b(2b-1)/2)$ or $T=2^4(1+b(2b+1))|_{b=16}=8464\approx 2^{13.05},$
which gives attack complexity (via the birthday paradox) of $$2^{(128-13.05)/2}\approx 2^{62.5}$$
for the pairwise XOR of any two outputs of the hash function to be in $T.$
However, this is not quite enough, if what you want is to be near a given fixed hash output as opposed to be near any of the outputs so far (so you want a near preimage as opposed to a near collision). If it is the latter, then proceed as below.
The probability that you miss the fixed target for $k$ randomly chosen inputs is
$$
p(f,k)\geq \left(1-\frac{T}{2^n}\right)^k =\left[\left(1-\frac{1}{2^n /T}\right)^{2^n/T}\right]^{Tk/2^n} \sim \exp[-Tk/2^n]
$$
which is only a lower bound but accurate for small $f.$ The reason we can't proceed as in the birthday paradox writing
$$
\left(1-\frac{T}{2^n}\right)\left(1-\frac{T+1}{2^n}\right)\cdots\left(1-\frac{T+k-1}{2^n}\right)
$$
for the probability is that we may be colliding with a previous hash output but this output may not be in the target set.
If we make the product $Tk=2^n,$ then we can have a probability of success of $1-e^{-1}\approx 0.63$. Since $T=2^{13.05},$ we need to perform no more than (and probably somewhat less than)
$$
2^{128-13.05}=2^{114.95}
$$
hash computations.
If you are happy with larger $f,$ then use the dominant term in (1) to obtain
$$
T\geq 2^4 b(2b-1)\cdots(2b-f+1)
$$
for a good approximation to $T$ but the direct computation of exact $T$ is not hard either.


Efficient setup for a Montgomery multiplication

The usual way is to calculate $2^k R \bmod N$ for a small divisor $k$ of $l$ where $R = 2^l$ and use Montgomery multiplication in a Square-and-Multiply algorithm. This does require a division, but as $R$ is usually chosen to be just a little bit longer than $N$, the division doesn't have to be optimized much.

But you should also consider the fact that in some occasions (like RSA key generation) one can do also without knowing $R^2 \bmod N$. You neither have to Montgomery transform the random bases for a Fermat or Miller-Rabin test nor a number you want to invert using Fermat's little theorem (in the second case just Montgomery multiply with $1$ afterwards).


How long does it take to brute force a Wordpress password?

If the password was 8-10 random characters with alphanumerics and some symbols, a lower bound estimate of the entropy would be something like 48 bits (eight random base 64 characters). Coupled with WordPress' weak 8-round MD5, that's just over 50 bits of security. Not terribly secure.

A low-resource attacker like you assume could maybe crack it in a couple of weeks. If they had nothing else to do with their computer. Or they could buy some cloud computing resources to tackle the job. According to this blog post, an Amazon GPU instance (from a couple of years ago) could calculate about two billion MD5 hashes per second. With eight instances you'd have the search space covered in 24 hours. And that costs maybe a hundred bucks if that. (You could also do it quicker with more instances without a significant cost increase.)

However, if you assumed the high end of 10 characters out of all printable ASCII (95 possibilities), you would have a 65 bit strong password. Which would cost more like ten million dollars to brute force. So the actual entropy is rather important. If the initial password wasn't generated with a random number generator, its entropy was probably much less than something like the site you linked would predict.

While it is possible, brute forcing the password sounds like one of the less likely ways a WordPress blog would be compromised. An unpatched vulnerability in WordPress itself, some plugin, PHP, the SQL database or some other software seems more likely. Or in the case or a shared host, even a privilege escalation from another account.


Practical differences between circuits and turing machines for cryptography

Just looking for a Turing machine vs circuit is a bit misleading. The important distinction is uniform (complexity class BPP) vs non-uniform (complexity class P/poly) adversaries. You can characterize P/poly in terms of circuit families, but also in terms of Turing machines with arbitrary "advice strings." In fact, the latter is the more traditional complexity-theoretic way to define P/poly. So just the fact that a definition mentions Turing machines doesn't mean it only applies for uniform adversaries.

If the authors are being careful, then their definitions will explicitly consider a TM adversary to take some advice string as input, and security must hold for all such inputs. Hence, security holds for P/poly adversaries. Even when the authors are not so careful with the definition, the results almost always carry over for non-uniform adversaries as well.

In general, I think it's safest to just assume non-uniform adversaries unless the paper explicitly says otherwise.

Of course, there are times when the distinction is important, and I can mention one way it might manifest itself. We generally have an asymmetry between wanting the "good guys" to be described by uniform algorithms, while protecting against "bad guys" who are non-uniform algorithms. Occasionally this becomes a problem when you want to convert an attack into a construction. For example, you can have a result like "an attack against scheme $X$ implies an improved construction for task $Y$." In these cases you often have to relax one of the definitions to bring them into alignment. For example, either:

"a [uniform] attack against scheme $X$ implies an improved construction for task $Y$."
"an attack against scheme $X$ implies an improved [non-uniform] construction for task $Y$."

Some examples:

Completeness for Symmetric Two-Party Functionalities - Revisited by Lindell, Omri, Zarosim: They show that certain protocols have some round at which Alice can distinguish some information about Bob's input. Then this distinguishing strategy can be used to construct an oblivious transfer protocol. But to incorporate this distinguishing strategy into another protocol, the strategy must be uniform, and the paper has to use a uniform definition of distinguishability. Alternatively, you could allow protocol constructions to be non-uniform.
In my own paper Universal Composability from Essentially Any Trusted Setup, I define a 2-player game between Alice & Bob. If Alice has a winning strategy in this game, then I create a protocol of one kind. If Bob has a winning strategy, then I create a protocol of a different kind. But in both cases I need the "winning" party's strategy to be uniform (they are the person whose strategy gets incorporated into a protocol), while the "losing" party's strategy can be non-uniform (the losing party corresponds to the adversary in the protocol I construct). So the result leaves a gap (what if non-uniform strategies can always beat uniform strategies)? As above, you could close the gap by allowing protocol constructions to be non-uniform.