How was the complexity of the Biclique Attack calculated?

The usual convention on attack cost is the following: "the cost is N" means that running the attack, with a success probability of at least 50%, requires no more than:

N bits of memory space (RAM),
N plaintext/ciphertext pairs,
N*x clock cycles, where x is the number of clock cycles to compute one instance of the attacked algorithm (in the case of AES, "one instance" is encrypting one block).

The generic exhaustive key search (aka "brute force") on AES-128 has cost 2127, and that's entirely CPU cost (when trying many keys, you do not need much RAM, and one plaintext/ciphertext pair is sufficient). The cost is 2127 because trying out half of the possible keys is enough to make the success probability exceed 50%. Correspondingly, no attack can be deemed "real", in an academic way, unless it does better than that.

The biclique attack pretends to do better, with a cost of 2125.1, which is about 73% less than 2127 (if you prefer, the biclique attack is about 3.7 times more efficient than exhaustive key search). But note that nobody is talking about actually running it ! This kind of comparison is mostly formal, which is why we allow ourselves to consider that having N bits of RAM, obtaining N plaintext/ciphertext pairs, and computing N times the block encryption, have the same cost. This does not make practical sense.

(Note: in a previous version of this answer, I had used 2126.1, which is the figure with the article, but Christian Rechberger pointed out to me that it was computed for 100% success rate, and it scales like brute force. For 50% success rate, the complexity is 2125.1.)

For instance, buy a simple PC, and you'll be able to compute 248 AES encryptions per week, but 248 bits is 32 terabytes: that could prove a bit expensive. And convincing your target to encrypt 4096 terabytes worth of data might be somewhat challenging. That's comparing apples with oranges, and also with pickled herrings. Academics can get away with it because they are playing a game which has only indirect links with reality. It is about computing a lower bound for security.

When security is down to the realm of the potentially feasible, the proper measure is not the number of encryption or the RAM size, but the dollar.

Also, note that the biclique attack lowers security by less than two bits. This means that learning two bits of the key (by some leak) actually gives the attacker a bigger advantage than the biclique attack. This is why this attack is not scary. It is academically interesting, but not a danger in any way.


Perform ENT / Dieharder on raw entropy or on whitenened entropy?

It depends on the goal of performing the test:

If the goal is to test for a problem in the whitening, then the test should be run on the whitened output, of course. If the test fails (more often than predicted by the P-value), the whitening is demonstrated bad. If the test pass, we can deduce nothing cryptographically useful (the source or the whitening could be badly defective, or/and the tested output could be totally predictable by who knows how it was generated). The test is slightly less pointless if the source is replaced with a very low entropy source during the test.
If the goal is to test for a problem in the noise source, then the test should be run on the noise source before whitening. If the test fails (more often than predicted by the P-value), then the noise source is demonstrated not good enough to be used for cryptographic purposes without whitening (but it might still be excellent and perfectly usable with whitening; many if not most good truly raw sources fail Dieharder, some fail ENT). If the test pass, we can deduce nothing cryptographically useful without knowledge of how the noise source is actually operating, and of how the test works.
If the goal is to pass a conformance test, then the rule it to perform things as satisfies the person with the rubber stamp. If s/he does not care, the easy route is to use the whitened output, so that a good whitening is a sufficient way to pass the test, irrespective of the source. I guess that happened (for FIPS 140-1 and -2 conformance, some tests where mandatory and too stringent for most practical sources; reason prevailed and the tests have been removed, yet the tests remain what some suppliers of RNGs brag about).

There is no other rational goal met by solely performing a RNG test on a sequence, when it passes. Repeating the first bullet: if the test is a blackbox test on the whitened output of a source, then a pass indicates nothing cryptographically useful about the source, the whitening, or the combination.

I have assumed the test is at least correct (and in particular, fails with likelihood comparable to its stated P-value when given truly random input), and correctly used. That's more often than not disproved by repeatedly applying the test to the output of a known-good CSPRNG. The test should pass (with occasional failures per its P-value) regardless of the CSPRNG's input (as long as it is arbitrary rather than tailored to the test being tested).

Note: ENT is a terrible test from a cryptographic standpoint, especially for a whitened source. For example, a PRNG that 90% of the time outputs a byte equal to one more (modulo 256) than the previous one, and is random the other 10%, is still considered perfectly OK.

Note: Temperature or process variations, EMI, aging, adversarial influence, or Murphy's law, can ruin a noise source. In cryptographic devices it is thus critical that the proper operation of the noise source is continuously monitored. A technically valid security certification process aims at checking source, whitening, and that monitoring puts the whole device in a safe state (as a minimum: squelches the whitened output) on detection of failure. This goal is antagonist to field reliability, and it is hard to get both.


Using e-ID Number for Encryption and Digital Signing

The number of your ID card is not really a secret, and probably shouldn't even considered one. You could use it as a key for symmetric encryption (but for this purpose you'd have to share it with your communication partners, and everybody knowing the ID could read the communication), but not for public/private key cryptography.

This is the reason why the cards often are (or can be) equipped with public/private key pairs, at least when they provide any cryptographic features.

An interesting way to work around the fact the basic key pair stored on the card is not really released to general usage is available for the German "Neuer Personalausweis" (the digital ID card issued for some years now): you can use the card to prove your identity to an OpenPGP key signing service (German website), which again will sign your key as certificate authority.

  Generating PGP key-pair using e-ID Number (pass-phrase protected)

Specifically discussing this point: If you want to use the card's identifier for generating the key, be aware that likely the key space is much smaller than necessary, which will heavily reduce the key's security. Brute-forcing the key might boil down to simply enumerating all possible IDs (which might be made harder using repeated hashing like often done for passwords). Also, everybody getting hold of the ID will be able to calculate the key without problems: the government, possibly also private entities getting hold of your ID card for verification purposes (hotels, airlines, ...).


What is modulo switching, in a nutshell?

The basic idea:
In homomorphic encryption schemes, the ciphertexts are noisy and we want to refrain the noise from growing too fast as we operate homomorphically. So the idea here is to multiply a ciphertext $c$ defined over $\mathbb{Z}_{q_0}$ by $q_1 / q_0$ so that the noise term is also multiplied. Then, by setting $q_1 < q_0$, we go from a noise term $e$ to a smaller noise approximately equal to $\frac{e q_1}{ q_0}$.
Furthermore, the ciphertext we obtain is then defined over $\mathbb{Z}_{q_1}$.
What is the advantage of doing this?
Let's say that fresh ciphertexts have noise term bounded by $B$ and that one homomorphic multiplication increases the noise to (approx.) $B^2$.
Then, two multiplications gives us $(B^2)^2 = B^{4}$, three gives us
$(B^4)^2 = B^8$... A sequence of $L$ multiplications increases the noise to $B^{2^L}$.
Because the final noise must be smaller than the modulus $q$, the bit length of $q$ must be bigger than $\log B^{2^L} = \Theta(2^L)$, that is, exponential in the circuit depth.
Now, imagine that we have $q_L := B^{L+1}$, $q_{L-1} := B^{L}$, $q_{L-2} := B^{L-1}$, ..., $q_{0} := B$. Then, $q_{i-1} / q_{i} = 1/B$.
Now, the first multiplication increases the noise close to $B^2$, but multiplying by $q_L / q_{L-1}$ scales it down to $B$ again.
Then, the second product increases the noise to $B^2$ and multiplying by $q_{L-1} / q_{L-2}$ (modulus switching) reduces the noise to $B$ again.
Proceeding like this, after $L$ multiplications, we have a ciphertext defined over $\mathbb Z_{q_0}$ with noise smaller than $B$, which can be correctly decrypted.
Now, the bit length of the modulus we need to use is $\log q_L = \Theta(L)$, that is, linear in the circuit depth instead of exponential!
But how the modulus switching is really done?
Of course, we can't simply multiply $c$ by $q_0 / q_1$, because we will not obtain a valid ciphertext, thus, each scheme has it is own way of getting a valid ciphertext out of $c\cdot q_0 / q_1$, but this is basically done by rounding.
For instance, let's say that we have the following LWE ciphertext with secret key $\vec s$ and noise term $e$:
$$
\vec c = (\vec a, \, \underbrace{\vec a\cdot \vec s + e + m \cdot q_0/2}_{b}) \in \mathbb{Z}_{q_0}^{n+1}.
$$
Then, over the integers, we have $b = \vec a\cdot \vec s + e + m \cdot q_0/2 + uq_0$
for some integer $u$.
Since the rounding function satisfies $\lceil x \rfloor = x + \epsilon$ with $-1/2 \le \epsilon \le 1/2$,
it is clear that
$$
b' := \lceil b \cdot q_1 / q_0 \rfloor
= \vec a\cdot\vec s \cdot q_1 / q_0 + e \cdot q_1 / q_0 + m\cdot q_1 / 2 + \epsilon + uq_1 \in \mathbb{Z}.
$$
Using this trick again, we define
$\vec a' := \lceil \vec a \cdot q_1 / q_0 \rfloor = \vec a \cdot q_1 / q_0 + \vec \epsilon$, with rounding applied entry-wise, and obtain
$$
b'= \vec a' \vec s -\underbrace{ \vec \epsilon \vec s+ e \cdot q_1 / q_0 + \epsilon}_{e'} + m\cdot q_1 / 2 + uq_1 \in \mathbb{Z}.
$$
Finally, reducing $b'$ modulo $q_1$ removes the term $uq_1$.
Moreover, assuming that $||\vec s||$ is small, we see that the new noise $e'$ is close to original noise $e$ scaled by $q_1/q_0$.
Therefore,
$$\lceil \vec c \cdot q_1 / q_0 \rfloor \bmod q_1 = (\vec a', \, \vec a' \vec s + e' + mq_1/2) \in \mathbb{Z}_{q_1}^{n+1}$$
is a valid ciphertext of the same message, under the same key, but with smaller noise and with respect to a smaller modulus $q_1$.


If CA certificates are trusted by client and server both, than an CA certificate will work.
However, apart from CA Signer (CA certificates), you can also validate the certificate subject CN name. [ this functionality is not provided by all the product ]

Process in details:

Negotiation (SSL Handshake)
Server Sends its Server Certificate to Client. (s - > c)
2.a Client validate that signer of certificates provided by server is in its trust-store.
Client Sends its Client Certificate to Server (c -> s)
3.a Server validates that the signer of certificate provided by client is present in it's trust-store.
Than, they exchange master-key.
Handshake done, and data transmission over synchronise encryption.


What would happen in DSA/ECDSA if there were a collision in $r$ but not $k$?

If you happen to generate two signatures of different messages that have the same $r$ value but different $k$ values, does it break security?

No, it doesn't break security.

Suppose you happened up use two different $k$ values ($k$ and $k'$) that just happened to result in the same $r$.  Then, when you publish the corresponding $s$ values, you would publish:

$$s = k^{-1} (H(m) + xr)$$

$$s' = k'^{-1} (H(m') + xr)$$

with $s, s', r, H(m), H(m')$ known.

That leaves $k, k', x$ are three unknown variables; for any possible $x$ value (which is the private key), there are $k, k'$ values that make these equations fit, hence we cannot deduce the value of $x$ from these two equations.

In contrast, if we also knew that $k = k'$ (that is, if the actual $k$ value was reused), then that drops the number of unknown variables to two; in that case, it's just a pair of linear equations in two variables - quite easy to solve.


OpenSSL is not threadsafe by default:

  OpenSSL currently is thread-NOT-safe by default. In order to make it
  thread-safe the caller has to provide various callbacks for locking,
  atomic integer addition, and thread ID determination (this last has
  reasonable defaults). This makes it difficult to use OpenSSL from
  multiple distinct objects in one multi-threaded process: one of them
  had better provide these callbacks, but only one of them should.

  Currently the only moderately safe way for libraries using OpenSSL to
  handle thread safety is to do the following as early as possible,
  possible in .init or DllMain:

  Check if the locking callback has been set, then set it if not;
  CRYPTO_w_lock(CRYPTO_LOCK_DYNLOCK), set the remaining callbacks (threadid, dynlock, and add_lock) if not already set, then CRYPTO_w_unlock(CRYPTO_LOCK_DYNLOCK);

  In the future we hope that OpenSSL will self-initialize thread-safely
  to use native threading where availab


What's the industry standard for verifying phone number ownership?

I don't think there is any written 'industry standard', just as in any case when generating random numbers: Just use properly-seeded CSPRNG. Closest thing we have is TOTP/HOTP.

Both of your ideas are far more complex to get right from what TOTP/HOTP roughly does: Take CSPRNG, output 4bytes, truncate to 31bits, and take modulo 1000000 (Please note that TOTP/HOTP actually have bit more to it, refer to according rfc for details). This yields very small bias, which isn't a issue.

As SEJPM noted in his comment, SMS can be captured, and especially recently, some parties who used 'best recommendations' were hacked with SMS-reset of password. Therefore you should consider TOTP/HOTP, and SMS can be implemented as a variant of HOTP (which would allow you to check if one of previous tokens was reused).

So in short: neither 1 nor 2. Use properly seeded CSPRNG (/dev/urandom or CryptGenRandom can be used), then take 31-bits and modulo them to 1000000. Better yet, allow usage of HOTP/TOTP (which does basically same thing, without relying on channel security).


As SOJPM says in their answer, the proofs for AES-GCM assumes that AES is a PRP. I can't believe that there is anywhere in the proof that using a PRF (possibly truncated) would break things -- but I haven't looked carefully for this. Depending on how the GCM proof is structured, (using/not using) the PRP/PRF switching lemma [1] may suffice, but I don't remember well enough to say for certain.

I think that the closest reference you will find is [2], which analyses the ChaCha20-Poly1305 construction in IETF protocols [3]. As both ChaCha20 and Salsa20 can be assumed to be a PRF, this change is not significant; similarly GMAC and Poly1305 are fundamentally the same (a MAC based on a polynomial-evaluation hash). However, the scheme in [1] is not precisely ChaCha20-GCM; unless you want to dive into the GCM proofs (either to check that a PRF is ok at every point, or that you can use/not use the PRP/PRF lemma) I think it is the closest analysed scheme that you will find.

[1] https://eprint.iacr.org/2004/331

[2] https://eprint.iacr.org/2014/613

[3] https://tools.ietf.org/html/draft-irtf-cfrg-chacha20-poly1305-10


What are the benefits of algebraic eraser key exchange?

Beside speed and power efficiency, there's also claimed resistance to attacks by quantum computers; quoting Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells: Post Quantum Group Theoretic Cryptography (2016-12-05), at SecureRF website:

  (..) unlike the classic protocols, these group theoretic protocols are not based on finite cyclic abelian groups. Instead, the underlying algebraic object is the braid group, an infinite non-abelian group. The security of these group theoretic protocols is not based on any problem known to be susceptible to a quantum attack, which makes them viable candidates for post-quantum asymmetric cryptography. In addition, since the data transmitted over public channels is contained in the Braid group, linear algebra/permutation based attack are not applicable to the protocols (..)

Also, there is novelty, which allows a patent, which serves some interests; obviously those of the patent holder, but occasionally those of the customer: when one purchases a door cylinder or lock with a patented physical key feature (which abound), one might gain some small level of protection against unauthorized key reproduction by someone who temporarily gets hold of the key, and better insurance that extra keys ordered from a shop will actually work, if the patent holder actively uses it as a legal leverage to enforce a key reproduction policy including proving possession of the key reproduction card sold with the cylinder/lock, and quality control. Similarly, the holder of a patent for a cryptographic technique can try to use the patent as leverage to force implementations to pass some security and/or interoperability tests, both of which potentially beneficial to customers.

Note: I'm making no statement about the claims of resistance to attacks by quantum computers, the validity of the patents, or their licensing policy.


Since you tagged the question with "man-in-the-middle" then the answer is that the protocol is not secure after its first use because the eavesdropper can record the exchange and repeat it. Instead, each party should challenge the other party with a random value that will be used by the other party to construct the HMAC.


How to determine if $\{n \cdot g^a \mod P\}$ and $\{m \cdot g^a \mod P\}$ generate the same sets? (set size < $P-1$)

$G_n = G_m$ iff $n^S \equiv m^S \pmod P$

Proof:

If $n^S \not\equiv m^S \pmod P$, then $\forall e \in G_n : e^S = n^S$ (as $e^S = n^S \cdot (g^a)^s = n^S$); and similarly $\forall f \in G_m : f^S = m^S$.  Hence $\forall e \in G_n, f \in G_m: e \ne f$, and hence $G_n \ne G_m$ (and actually the two sets are disjoint).

Other direction (needed because we're asserting equivalence):

If $n^S \equiv m^S \pmod P$, then $(nm^{-1})^S = 1$, that is $nm^{-1}$ is in the subgroup generated by $g$, that is, $g^c = nm^{-1}$ for some integer $c$.

Then, for any member $e \in G_n$, we have $e = n \cdot g^a$ (for some $a$); we have $n \cdot g^a = n \cdot g^{-c} \cdot g^{a+c} = n \cdot n^{-1}m \cdot g^{a+c} = m \cdot g^{a+c}$, and hence $e \in G_m$.  Similarly, we can show that all elements $f \in G_m$ are also in $G_n$ and hence $G_n = G_m$

Extra credit for the reader: find the step where I implicitly assumed that $P$ was prime...


Constant number of rounds in Yao's Protocol for semi honest adversaries

The OT inputs/outputs don't depend on each other, so they can all be done in parallel.


Can $A$ assume that only $B$ can read the message?

Only someone with the private key corresponding to $P_B$ can read the message.  If $A$ can assume that only $B$ has it, that works.

  As $B$ does not know anything about $A$ what is the cryptographic purpose of the MAC?

So that someone else cannot modify the encrypted message.

What we want to prevent is someone can take the encrypted message $E_{P_B}{m}$, and modify it so that it successfully decrypts into a message $m'$, where $m$ and $m'$ are related.  Without the MAC, here is what someone might try:

Take the encrypted text $c = ENCRYPT_{k_1}(m)$
Replace it with a $c'$, that decrypts with $k_1$ into $m'$
Repackage it into $P|c'$ as the new encrypted message.

This is often feasible, because many encryption methods make modifying the encrypted message possible (even if you don't know the encryption key $k_1$).  One example of this is counter mode; if you flip any bit of the encrypted message, and the corresponding bit of the decryption will also flip (with no other change).

Because of this, then without the MAC, Eve might be able to take the encrypted message:

$ENCRYPT( \text{ "Transfer one million into Bob's account, password Rhinosaurus" })$

and change that into

$ENCRYPT( \text{ "Transfer one million into Eve's account, password Rhinosaurus" })$

With the MAC, this type of message modification is infeasible.

So in this case with the MAC Eve can still send "valid" messages to $B$, but as long as Eve does not have the password ("Rhinosaurus") Eve has no way to execute or modify a transaction.


Does decryption with a wrong key creates a new encryption?

In general this is a moot point, as modern encryption schemes are designed so that the recipient knows if they have used the correct key or not. It is an interesting question to ask about encryption primitives, like a block cipher. Put more precisely, you are asking whether there is always a $k_3$ such that
$D_{k_2}(E_{k_1}) = E_{k_3}$
This is essentially asking if encryption forms a group, and in general the answer is no. See e.g. Is Triple-DES a group?. There are notable exceptions. You've seen that Caesar cipher is one, and Vigenere is another.


Can perfect forward secrecy introduce vulnerabilities?

Yes, PFS could introduce new attack vectors.

PFS makes it hard to impossible to find / reconstruct a private key used for previous / future connections. It is not some special sauce that makes an algorithm invulnerable to attack.

Any change can always introduce vulnerabilities on an implementation level, as SEJPM already stipulated. This is also true on the protocol level, for instance it is possible to forget to authenticate the parameters, allowing for MitM attacks.

As for the algorithms used: well, it simply depends on the algorithms themselves. For ECDHE: you could forget to validate that a public point is on a curve for ECDHE. You must make sure that the security requirements for particular algorithms are met.

More broadly ECDHE is more vulnerable to attacks using quantum computers than RSA. So if quantum computers ever mature then a specific PFS algorithm could fall earlier than a previously used algorithm. However, you could also use finite field DHE for PFS and ECIES for "normal" key establishment, which would give the advantage to the PFS algorithm.

One pitfall is that servers may be more inclined to use smaller key sizes. Whereas a key in a RSA certificate is likely required to have a particular key size (by the Certificate Authority that needs to sign the certificate), nothing prevents a server to choose the smallest key size available for a protocol. For a long time DH implementations maximized the key size to 1024 bits, a key size that would be considered well below the minimum by now.

It might also be that the random number generator on the server could be bad. When using RSA encryption the pre-master secret is generated by the client. It could be that the server has a bad RNG and leaks information about the RNG state through the generated key pair. It may also use more random values and deplete the RNG of entropy. This again is more an implementation issue but it also shows that additional requirements may have to be met to support PFS algorithms.

Note that you asked for ways how PFS could weaken security. In general the advantages of PFS are very likely to outweigh the disadvantages. But if you ask a security professional to search for vulnerabilities you are likely to get a long list of possibilities, some more likely than others...


What are the advantages of MICKEY over Trivium and Grain?

MICKEY appears to be a good low-power stream cipher but, in the context of the eSTREAM portfolio, it does not seem to excel at anything in particular. Trivium and Grain have more implementation flexibility and lower area, if one wishes, and Trivium also allows for fast bitsliced software implementations that rival the software eSTREAM candidates in speed.

The one thing MICKEY appears to be better at than others is simplicity (in number of VHDL code lines), as seen in Table 8 of Chapter 19 of the eSTREAM book. This does not strike me as a particularly strong argument for it, since the line numbers between the best entries are all fairly close together.

MICKEY also appears more conservative when it comes to security; in particular, Trivium and Grain have been targets of more algebraic-type cryptanalysis. But this is something that is hard to quantify, and may be mainly a consequence of Trivium/Grain being more popular than MICKEY.


The best way to learn something is to do it right. So I'd suggest just using TLS, but perhaps use a different library, like BearSSL. That way if it does turn into something more than a learning project, you don't have to redesign everything or risk being very insecure.

That said, here are some things to think about given your current path.

You should definitely protect the EncryptedProtocol struct using the associated data portion.
You need to make your protocol "future-proof". This means that if someone broke GCM or AES tomorrow, you should be able to easily adapt to needing to use new ciphers for modes. Thus, in your protocol header, you probably need a cipher version field. Maybe for now you only support AES-GCM, but that cipher version field will make it so you can change in the future if needed.


Yes, homomorphic encryption operations are malleable by definition. The definition of "malleable" is something along the lines of "can be intelligently modified", which is what homomorphic encryption allows you to do.

  That you can preform operations on two unknown (encrypted) ciphertexts, $\epsilon(x_1)$ and $\epsilon(x_2)$, and recieve the result, $\epsilon(x_1\cdot x_2)$ by preforming $x_1^ex_2^e\bmod m$? Or is it just showing that $\epsilon(x_1)\cdot \epsilon(x_2)$ is the same as   $x_1^ex_2^e\bmod m$?

Those are the same thing by definition. The encryption operation will allow for the multiplication of two ciphertexts to equal the encryption of the multiplication of the two plaintexts (mod $m$, in your case).

And yes, you would use the RSA private key for decryption. The public key would contain the exponent e in your equation.

Edit, for completeness:

Note that textbook RSA usage (aka, simply taking the plaintext to an exponent) is not secure for several reasons. When security is necessary, we apply a padding scheme to the plaintext before encrypting it (aka, $m$ becomes $p(m)$ for some padding function $p$). But doing so causes the homomorphic usage to multiply the formatted plaintexts instead of the actual original plaintexts (aka, you wind up encrypting $p(m_1) * p(m_2)$ instead of $m_1 * m_2$), which won't yield the desired results. The padding schemes will completely mess up the ability to use homomorphic properties, since multiplying formatted texts yields garbage.

You mention this is for a game, so security may not be of utmost importance (it depends on what the stakes are and what data is involved), but take care before using RSA without any padding; if you do use it, investigate ways to mitigate at least some of the weaknesses of textbook RSA.


The whole purpose of base64 encoding is to take arbitary byte values and transform them into a limited subset of ASCII characters so that they can be "safely" sent (older transmission protocols could garble some byte values because e.g. some raw bytes had special meanings to those protocols; the only data that would be expected to not be changed was plain ASCII text.)

It does this by encoding three bytes (24 bits) into 4 characters (each of which has 64 values, so encodes 6 bits as $2^6 =64$) in a pretty simple fashion (some extra rules for incomplete groups). So every aligned identical three bytes in two messages get encoded into the same 4 characters every time. So changing 1 byte only will change at most 2 adjacent characters in the result, if you study the transformation this is obvious.

There is no expectation of more changes: it's just another representation of the same bits in the same order, and easily reversed on the receiving end.

In fact (IMO) in any sensible protocol your JSON-formatted data should be sent as is, as it's already all ASCII, and base64 encoding adds nothing but using more bandwidth. When encrypted it should be random-like binary data and could be sent in base64 format (and this is in fact customary: PEM and PGP send their messages base64 encoded, and very often binary mail-attachments as well.)


When truncating an AES MAC value by "w" , how do I justify that "w" is still negligible?

One of the factors that determines how hard it is to forge a MAC for a given message is how long the MAC is. If it's 1 bit long, you can definitely produce the correct MAC in two tries.

$2^n$ is the number of possible bit-strings of length $n$; $1/2^n$ is the probability that any random bit-string happens to be the MAC (of length $n$) for a given message and key.

Negligible depends on what you're protecting with your MAC, who your attacker is, and what information / oracles they have access to. In particular, if the attacker has to make some kind of service request to a single point to check that a MAC is valid, $2^{64}$ is an awful lot of requests – this is probably the assumption being made when it was stated that MACs of length 64 or more are secure.

Not all MACS can be truncated safely however. AES-GCM loses more security than expected by truncation, but HMAC is fine.

Given a MAC construction that can be safely truncated, truncating it to 128 bits is unlikely to pose a problem for a long time ($\gg$2020), for any attacker capability.


Malleability attacks against encryption without authentication

First of all, you stated:

  Because this message is encrypted using CBC mode, any modification of
  the first block of cipher text would propagate throughout the message.

Actually, that's not true.  Here's the CBC mode operation in the decryption direction:

(Public domain image from Wikimedia Commons.)

If you examine the process closely, you will see that a specific plaintext block depends only on two ciphertext blocks (or a ciphertext block and the IV for the very first plaintext block).

So, if you modify a ciphertext block $N$ (say, flip one of the bits), then the resulting plaintext will have block $N$ garbled (because the modified block goes through the decryption, and unless we picked a ciphertext block which we already knew the decryption of, the result will be unpredictable).  In addition, block $N+1$ will have the corresponding bits modified (in our example, the same bit will be flipped).  And, there will be no other changes; all other plaintext blocks will be exactly what they were in the original message.

So, how can we use this observation?  Well, if block $N$ is the one we want to affect, and we don't mind if block $N-1$ decrypts to something unpredictable, the obvious approach is to modify block $N-1$ of the ciphertext.  If we guess that the real plaintext is $A$ (which corresponds to \$1), and we want it to read $B$ (which corresponds to (\$1000000), then we exclusive or $A \oplus B$ into ciphertext block $N-1$; this will cause the last ciphertext block to read exactly as we want it to.


OFB output jth-block expression clarification

Is he implicitly saying that
[Cj-1 ⊕Pj-1] = Oj-1

Yes, this is true.

? If yes, why?

Well, we know that:
$$C_{j-1} = P_{j-1} \oplus E(K, O_{j-2})$$
(this is the first formula, replacing $j$ with $j-1$), and we know that:
$$O_{j-1} = E(K, O_{j-2})$$
Combining the two, we get:
$$C_{j-1} = P_{j-1} \oplus O_{j-1}$$
or, in other words:
$$C_{j-1} \oplus P_{j-1} = O_{j-1}$$


If I want to use this approach, do I have any option other than extracting and storing the bcrypt salt somewhere outside the password field?

No.  You need to store the bcrypt parameters (salt and iteration count) and the Argon2 parameters.


What is the difference between PKCS1 v1.5 and PKCS7? Is PKCS7 a superset of specifications in PKCS1 1.5?

What is the difference between PKCS#1 v1.5 and PKCS#7?

PKCS#7 makes use of cryptographic primitives defined by PKCS#1 v1.5.

PKCS#7 is defined in RFC 2315. The modern PKCS#1 is v2.2 (also RFC 8017), and has a modern description of the schemes in PKCS#1 v1.5, including RSASSA-PKCS1-v1_5.

  Is verifying a PKCS#1 v1.5 signature the same as verifying the PKCS#7 signedData structure?

Verifying a PKCS#7 signedData structure involves verifying a RSA PKCS#1 v1.5 signature, but also a number of important steps before that, including parsing that data structure, and checks which depend on context. signedData has features which might not be needed by in a bootloader, like certificates with revocation lists.


What is it known about the hardness of the factorization search problem in non-commutative crypto?

Q: What reductions exist to known problems on Group Theory, if any?

I would consider the factorization search problem to be a known problem in group theory. After all, the LU-decomposition and QR-decompositions of matrices are special cases of the factorization search problem. In group based cryptography, the decomposition problem is usually stated in the following equivalent but seemingly more general form:

Suppose that $G$ is a group and $A,B$ are subgroups of $G$. Suppose that $x,y\in G$. Then find $a\in A,b\in B$ where $axb=y$.

  Q: Is there any protocol based on this problem?

The Ko-Lee et al key exchange, one of the first two non-commutative group based public key cryptosystems, is the cryptosystem which is most closely related to the factorization search problem.

$\textbf{Ko-Lee key exchange classical formulation:}$ Suppose that $G$ is a group $c\in G$, and $A_{L},B_{L},A_{R},B_{R}$ are subgroups of $G$ such that $ab=ba$ whenever $a\in A_{L},b\in B_{L}$ or $a\in A_{R},b\in B_{R}$.

Alice selects $a_{L}\in A_{L},a_{R}\in A_{R}$ and sends
$r=a_{L}ca_{R}$ to Bob.
Bob selects $b_{L}\in B_{L},b_{R}\in B_{R}$ and sends $s=b_{L}cb_{R}$ to Alice.

The common key is $K=a_{L}b_{L}ca_{R}b_{R}.$

Alice computes $K_{A}=a_{L}sa_{R}$.
Bob computes $K_{B}=b_{L}rb_{R}$.

Note: Sometimes, in the Ko-Lee key exchange, one sets $A_{L}=A_{R},B_{L}=B_{R}$ and $a_{L}=a_{R}^{-1},b_{L}=b_{R}^{-1}$ so that the Ko-Lee key exchange is based upon the conjugator search problem.

$\textbf{Ko-Lee key exchange alternate formulation:}$ Suppose $G$ is a group and $A'_{L},B'_{L},A'_{R},B'_{R}$ are subgroups of $G$ such that $ab=ba$ whenever $a\in A'_{L},b\in B'_{L}$.

Alice selects $a'_{L}\in A'_{L},a'_{R}\in A'_{R}$ and sends
$r'=a'_{L}a'_{R}$ to Bob.
Bob selects $b_{L}'\in B'_{L},b'_{R}\in B'_{R}$ and sends $s'=b'_{L}b'_{R}$ to Alice.

The common key is $K'=a'_{L}b'_{L}a'_{R}b'_{R}.$

Alice computes $K'_{A}=a'_{L}s'a'_{R}$.
Bob computes $K_{B}'=b_{L}'r'b'_{R}$.

The alternate formulation of the Ko-Lee key exchange is a special case of the classical formulation of the Ko-Lee key exchange. To formulate the classical formulation of the Ko-Lee key exchange in terms of the alternate formulation of the Ko-Lee key exchange, one sets $A_{L}'=A_{L},B_{L}'=B_{L}$, $A_{R}'=cA_{R}c^{-1},B_{R}'=cB_{R}c^{-1}$ and $a_{L}'=a_{L},b_{L}'=b_{L}$ and
$a_{R}'=ca_{R}c^{-1},b_{R}'=cb_{R}c^{-1}$ and $K'=Kc^{-1}$.

  Q: What is the situation about the factorization search problem?

The decomposition problem on the braid groups has been attacked for example using length based attacks. Such an attack can be found in this paper. In general, one could more or less use length based attacks to attack any cryptosystem based upon the factorization problem in non-commutative cryptography. For example, length based attacks have successfully broken the Ko-Lee key exchange with Thompson's group as the platform (see this paper).


Performance of Counter mode (CTR) with Ciphertext Errors

What it means is that neither CTR nor OFB detects errors in a message, and that an adversary can flip arbitrary bits of their choice in the plaintext very easily—by flipping the corresponding bits of ciphertext.  This is because both CTR and OFB essentially work by using the block cipher as a stream cipher to pseudorandomly generate a one-time pad to xor with the plaintext.

This implies that an adversary can easily change one message like ‘Attack at dawn!’ to another message like ‘Attack at dusk!’ and the recipient of the message will be none the wiser.  Worse, an adversary can change a message like ‘Put the secret message in locker 42!’ to ‘Put the secret message in locker 41!’, and then by acting on the message your confidentiality goes out the window.  This is not merely theoretical; this actually happened in a major real-world protocol, OpenPGP, in EFAIL, because OpenPGP was badly designed.

To avoid this, you should generally use an authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305.  An authenticated cipher detect any errors, whether random errors or malicious forgery attempts, with high probability.

You should also forget that ‘block cipher modes of operation’ exist at all—just focus on the complete construction AES-GCM.  The fact that there's a block cipher somewhere in there is not important to anyone except a cryptographer designing a system.  What matters is the security contract which tells you what your obligations are for using AES-GCM and what security you get in exchange.


The verifier and logger start with a seed for a forward-secure pseudo-random number generator.

To denote a valid ending of a log, append the string of the next $b$ bits of the PRNG's output

to the end of the log. $\;\;$ To add a log entry, get the next $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits of the PRNG's output,

use the last $k$ of those bits to mac the new content, append the concatenation of the new

content with its mac to the log, and then erase those $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits and the previous PRNG state.

This allows you to replace "The untrusted party publishes the hashes"

with "The untrusted party erases the old PRNG state".


Yes. Salts are only there to make a particular key derivation globally unique. They have no requirement of secrecy.


Your idea seems secure, but it is more complicated than it needs to be.

If you only need to know if the "secure information" in the document matches some public information (stored on an insecure computer), it is enough to calculate a preimage resistant hash of the document (e.g. SHA-256). The document needs only to be unguessable, like a 256-bit random number.

Note that there are practical problems here, which may lead to side channel attacks. For example, doing anything on a general purpose computer usually involves a chance that the memory you are using hits the swap on the disk, unless you use something like mlock.

You would need to carefully consider which parts of the computer you consider secure and what kind of attacks may be possible.


No, in general, this is not secure, unless you make additional assumptions on the encryption method beyond the standard assumption of privacy.

To simplify things a bit, the assumption of privacy means that given a ciphertext $C$, the attacker has no information about what the plaintext might be.  However, in your case, we don't really care if the attacker can figure out what the plaintext of the encryption function; we also give him the data, and he can compute $hash(data)$ himself, should he care to.

What we are concerned with is (again, to simplify a bit) that an attacker, given a message M and a valid tag for that message, cannot come up with another message, and a valid tag for that message.  Translating that into your proposal, if the attacker was given $M$, and $E(Hash(M))$, can he pick another message $M'$, and come up with $E(Hash(M'))$?

Well, for a lot of encryption methods, he can.  For example, if we consider a block cipher in counter mode, well, if you flip a bit in the ciphertext, the corresponding bit in the plaintext also flips.  What that means that if the attacker computes $E(Hash(M)) \oplus Hash(M) \oplus Hash(M')$, well, that turns out to be precisely $E(Hash(M'))$, and so the attacker has won.

The additional property that we need to assume for the encryption method is nonmalleability; that is, given $M$ and the corresponding encryption $E(M)$, the attacker cannot modify the encryption so that it decrypts to any other specific message.

Of the standard encryption modes, well, ECB actually is nonmalleable, if (and this is a big if) the hash fits entirely within a single block output.  Given that 128 bit hashes are vulnerable to collisions (and a hash collision would be another way of producing a forgery), this means using a nonstandard block cipher (for example, Rijndael with a 256 bit block size).

Authenticated encryption modes are also nonmalleable.  However, this may be considered cheating; authenticated encryption modes work by effectively using a MAC internally; if the point of the exercise is to create a crypto primitive from other crypto primitives, well, this didn't do it.


Is it possible to decrypt an RSA ciphertext with only $N$ and $e$?

The current best way of decryption an RSA ciphertext (assuming good padding was used) is to factor $N$ into its prime factors $p$ and $q$, and from that, reconstruct the decryption exponent $d = e^{-1} \bmod lcm( p-1, q-1 )$

The current record for factoring an RSA-type modulus (with large prime factors, and not of a special form) is 768 bits.

It is likely that, in the next couple years, slightly larger modulii will be factored; the record for "largest general number factored" has been slowly increasing; someone might manage to factor a 1024 bit number within the next decade.  There is little reason to expect that RSA modulii significantly larger  will be vulnerable to factoring in the near future.


Exercise: Attack on a Two-Round DES Cipher

Your Formulas are alright, but there is some additional information from the exercise/setup:

The exercise states, that $F$ should be considered as a blackbox (otherwise you could use the internal stages of $F$, as poncho already suggested). However, as I understand it you can stil evaluate $F$ on any input of your choice.

At this point, you can do a couple of things. First, you're already done without knowing it. As a hint: Read the goal of the exercise and compare the complexity with a brute force on your formulas. You only need 1 ciphertext/plaintext pair.

A more complex idea: If you have a lot of ciphertext/plaintext pairs, and you just want to distinguish the permutation from a random oracle, then you can do the following: Look for two plaintexts, where $R_0$ (32 bit) is equal. What happens then to the output? And what would happen in a truly random permutation? This is a distinguishing criteria.


does starting the iteration from $k=1$ instead of $k=P'$ make a difference?

If you start iteration from $k=P'$ then you get;
$$P = A\cdot (P'+i) + P'$$
where $ i = 0,1,2,\ldots$. Take modulo $A$
$$P  = A\cdot (P'+i) + P' \pmod A$$
$$P  =  P' \pmod A$$
Therefore it will still work to reveal the $P'$

in the way $N'$ is generated, what is the best way to factor $N'$ given the information how it is generated? Is there a certain factoring algorithm that makes factoring $N'$ very easy?

The current factoring record in the open literature is 829-bit, however, the recommended key size is at least 2048, i.e each factor has 1024-bits. Therefore the size of $A$ must be around $1024$-bit. Once you set $A$, then you can seek $P = A\,k_1 + P'$ where $P$ is prime.
There is nothing that prevents one to generate small primes for $P'$  and $Q'$. The $P'$ and $Q'$ doesn't add much to $P = A\,k_1 + P'$ since they are added. The $A$ and $k_1$ is important.
Therefore you can choose $P'$ and $Q'$ as below as $829$-bits.
You can use the CADO-NFS to factor the $P'\cdot Q'$. Here some notes about it, too.


Diffie-Hellman and man-in-the-middle attacks

Well, as it says in your link the problem is authentication. So somehow Alice and Bob must set up an authenticated channel. One way of implementing such a channel is by Alice and Bob holding each others public verification key for a signature scheme.

A CA would probably not hold a secret key for Alice and Bob. However, using a CA to get an authentic copy of the other parties public key for a signature scheme that would allow to set up an authenticated channel between Alice and Bob, so they could do DH key exchange. Apart from not trusting the CA with secret information, this has the benefit that Alice and Bob can now generate many secret keys with out involving the CA.
It is true that if Alice has a public encryption key for Bob and Bob has a public signature verification key for Alice, they could use the protocol you describe. However in general public key encryption and signature schemes are not the same(although for the particular instance of RSA there may be some overlap). If Alice and Bob only have keys set up for a signature scheme, they could use DH exchange to get a secret key.


What does non-collusion assumption mean in server-aided protocol based on secret sharing?

Does the "collusion" mean any possibility that t shares in the servers are somehow assembled?

It refers to the possibility that t or more server admins/owners collude to pool their shares to break protocol.

Regarding the follow-up questions: non-collusion is in this context in regards to server operators being malicious. Malicious clients are considered a non issue in the context since clients should not have access to each others shares. Hacking of servers or data leaks is considered out-of-scope since it has nothing to do with the scheme in question.


Adaptive Hash Functions: How to tell how many iterations were used?

The plain hash itself does not give any indication of the number of iterations. But with practical schemes, such as most crypt based ones, the number of iterations is stored alongside hash and salt in the database.

Keeping the number of iterations secret doesn't gain you much security in practice. Figuring out the number of iterations isn't that hard in practice. Choose a few users who probably have weak passwords, and compare after each iteration. Or if you can register your own accounts, you can simply attack that single user whose password you know.

If you want to improve security in a scenario where the attacker obtains only the database, but not the source-code/config file, there are much better techniques than a secret number of iteration. For example you could concatenate the salt with a secret key, or encrypt the hash. That way an attacker has no chance of attacking the hashes without gaining access to the place where you store the key.


When using CBC-ESSIV for disk encryption, why does the generation of IV require a hash then encryption instead of only one hash?

Block cipher encryption $$\operatorname{Enc}(K,P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n$$

is a permutation where a $K \in \mathcal{K}$ select a permutation from all possible permutations of $\{0,1\}^n$. Using

$$\text{IV} = \operatorname{Enc}(\operatorname{Hash}(K) , S)$$ will guarantee that the output is unique, not repeating, since the $\operatorname{Hash}(K)$ is fixed key for the operation. This will also guarantee that the output is 128-bit as a required IV size for CBC.

If you use

$$\text{IV} = \operatorname{Hash} (K \mathbin\| S)$$ then due to the collision property - birthday attack - of the hash functions some sector can have the same IV that is not wanted. One has to trim the output of the hash function to 128-bit so for a $2^{64}$ sector numbers we expect an IV collision with 50% probability. This probability is not negligible and one must stop way earlier.

For a 3TB disk, there are 5,859,375,000 sectors which make around 33 bits. The probability of collision is quite low for this, like $$1-e^{-\big(\frac{{(2^{33})}^2}{2\cdot 2^{128}} \big)} \approx 1.08\cdot 10^{-19}$$

by using the approximation formula for the Birthday attack

$$p(n;H) \approx 1 - e^{-n(n-1)/(2H)} \approx 1-e^{-n^2/(2H)}$$

But never zero!.

Conclusion: the first guarantees that there is no collision and therefore the first approach is preferable to the second approach.


Final permutation table example with DES

The reference for DES is FIPS 46-3. See page 10 for the permutations.

Write $\texttt{0x0002 0000 0000 0001}$ in binary. Start with $\texttt{0x0002}$:

0: 0000 (bits 1-4)
0: 0000 (bits 5-8)
0: 0000 (bits 9-12)
2: 0010 <--bit 15 is 1 (bits 13-16)

Bits 17-48 are all 0. Now look at $\texttt{0x0001}$:

0: 0000 (bits 49-52)
0: 0000 (bits 53-56)
0: 0000 (bits 57-60)
1: 0001 <--bit 64 is 1 (bits 61-64)

Thus, bits 15 and 64 are set.

At this link, you can see the initial permutation and final permutation. It looks like the answer you're referring to is actually talking about the final permutation, so to match what you have, I'll be using that. Looking at the final permutation, the number "63" is the 15th bit, and the number "25" is the 64th bit. So your result is, in binary,

$\texttt{0000 0000 0000 0000 0000 0000 1000 0000}$ (bits 1-32, bit 25 set)
$\texttt{0000 0000 0000 0000 0000 0000 0000 0010}$ (bits 33-64, bit 63 set)

Or, in hexadecimal,

$\texttt{0x0000 0080 0000 0002}$.

This is the final permutation, not the initial one.


Is this a correct SSL explanation in layman's terms?

A TLS/SSL connection is possible if both the Web server and the Web browser are configured to recognize the same root certificate authority (CA).  Basically it's like the server telling the browser, "Such-and-Such root CA, or one of its subordinates, says that I'm OK" and the browser responds, "Any friend of Such-and-Such root CA is a friend of mine.  Trusted!"


Is SHA-1 secure when used to implement a PRNG

I read SHA1 is still a secured hashing function with no collision found as of now.

You read an old text, this is not the case anymore since SHA-1 was SHAttered.

In Java, we still use SHA1PRNG algorithm in SecureRandom class for the purpose of generating IV (let's say for CBC).
Is it enough secured as a PRNG generating unpredictable IV for CBC? Or even for a PRNG, SHA256 is recommended?

SHA-1 is still fine for key derivation, HMAC, MGF1 based padding and indeed random generation and many other use cases that do not suffer from collision attacks.
That said, attacks can only get better, never worse, so using a  more modern hash is always recommended. When it comes to random number generation the seeding is much more likely to be problematic though, and you should definitely make sure that your systems RNG is running correctly.
And, when it comes to Java's SecureRandom, you may want to consider my answer on StackOverflow and not use (or at least indicate) "SHA1PRNG" at all.


Proving G(x)=x||[x^2 mod 2^N] is not a PRG

Given as input a $2n$-bit string $x||y$, the distinguisher $D(x||y)$ outputs 1 if $y = x^2 \bmod{2^n}$ and $0$ otherwise.
If $x||y$ is uniformly distributed over $\{0,1\}^{2n}$, the probability that $y=x^2 \bmod{2^n}$ is $2^{-n}$. If $x||y$ is distributed as $G(X)$ where $X$ is uniform over $\{0,1\}^n$, the probability that $y=x^2 \bmod{2^n}$ is 1. The distinguishing advantage of $D$ is $1-2^{-n}$, which is non-negligible.


Elgamal problem on $\mathbb{QR}_p$ with $p$ a safe prime

$P[s(g^{ab}) = i] = \frac{q-1}{q^2}$ if $i \neq 1$ and $\frac{2q-1}{q^2}$ if $i = 1$.

We assume that $g$ is a generator of $\mathbb{QR}_p = \mathbb Z_q$. Then, as you said, in order to study the probability that $g^{ab} = i = g^c$ for a fixed $c$, we can calculate the probability that $ab = c\bmod q$.

In general, the probability that a random pair $(a,b)\in\mathbb Z_q\times\mathbb Z_q$ gives you a fixed non-zero number $c$ is $(q-1)/q^2$, and if $c=0$ then this probability is $(2q-1)/q^2$.

  2) I don't currently see how to take $s$ into play here.

ElGamal encryption scheme allows you to encrypt elements $m\in\mathbb{QR}_p$ as $m\cdot g^{ab}$. However, the message you want to encrypt is likely not to be an element of this set.
In practice, you encrypt bit-strings, which are easier to map into $\{1,\ldots,(p-1)/2\}$. Then you take an element $y$ in this interval and map it to $m\in\mathbb{QR}_p$ via $m = y^2$, and use $m$ as above.
Now you can see that you need $s$ for decryption in order to recover $y$ from $m$.

  3) I believe the reasoning is equal to point 1).

Agreed. The idea is that with a safe prime $p = 2q+1$ you know that $\mathbb{QR}_p = \mathbb{Z}_q$, whereas in general this structure could be more involved.
However, once you're working over $\mathbb{Z}_q$, the analysis is the same.


How do you apply bilinear mapping to attribute based encryption?

You can study pages and papers below to understand bilinear maps (or pairing) and ABE.
https://en.wikipedia.org/wiki/Pairing-based_cryptography
https://eprint.iacr.org/2004/086.pdf
https://eprint.iacr.org/2006/309.pdf


Is there an upper bound to the private exponent in RSA?

Mathematically speaking, there is no upper bound on the private exponent in RSA: assuming $d$ is a valid private exponent, then the valid exponents are the set of $d'=d+k\cdot\lambda(p\cdot q)$ with $k\in\mathbb Z$, where $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ since $p$ and $q$ are distinct primes; this set is unbounded.

If you compute $d$ as an integer with $d\equiv e^{-1}\pmod{\varphi(p\cdot q)}$, then by definition $d$ verifies $e\cdot d-1$ multiple of $\varphi(p\cdot q)$, and is unbounded. If you compute $d$ as the integer $d=e^{-1}\bmod\varphi(p\cdot q)$, by a common definition of that notation, $d$ is additionally non-negative and less than $\varphi(p\cdot q)$, which is then an upper bound.

In practice, available memory and time, existing software, or standards, limit the value of $d$. A most common standard, PKCS#1, requires $0<d<n$; the FIPS 186-4 standard requires $2^{\lceil\log_2(N)\rceil/2}<d<\operatorname{lcm}(p-1,q-1)$; some implementations allow $0<d<256^{\lceil\log_{256}(p\cdot q)\rceil}$; $d\ge\varphi(p\cdot q)$ is unusual.


The paper introducing the application of endomorphisms in arbitrary curves to cryptography was Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200, after the initial idea of Neil Koblitz, ‘CM-Curves with Good Cryptographic Properties’, in Joan Feigenbaum, ed., Proceedings of Advances in Cryptology—CRYPTO 1991, Springer LNCS 576, 1991, pp. 279–287 (after whom the class of curves with efficient endomorphisms is named) to exploit the Frobenius endomorphism when it has trace 1 in binary curves.

The basic idea is that sometimes there is a scalar $\lambda$ such that computing $[\lambda]P$ given the $(x, y)$ coordinates of a point $P$ on the curve can be computed much more efficiently than by the standard double-and-add algorithm on the binary expansion of $\lambda$.

Here's a class of examples.  Let $p \equiv 1 \pmod 3$ be a prime, and let $$E/\mathbb F_p\colon y^2 = x^3 + b$$ be an elliptic curve over the finite field $\mathbb F_p$ of $p$ elements.  Suppose $\beta \in \mathbb F_p$ is an element of order 3, so that $\beta^3 \equiv 1 \pmod p$.  The map $f\colon (x, y) \mapsto (\beta x, y)$ (and $f\colon \mathcal O \mapsto \mathcal O)$ is an endomorphism—if $(x, y)$ is on the curve so that $y^2 = x^3 + b$, then $$y^2 = x^3 + b = 1\cdot x^3 + b = \beta^3 x^3 + b = (\beta x)^3 + b$$ so that $(\beta x, y)$ is also on the curve.  (Verifying $f(A + B) = f(A) + f(B)$ is left as an exercise for the reader.)  Of course, $\beta = 1$ satisfies $\beta^3 \equiv 1 \pmod p$, but the map is interesting only if $\beta$ is a nontrivial cube root of unity, a root of $\beta^2 + \beta + 1$, which exists iff $3 \mid \phi(p) = p - 1$ so that $p \equiv 1 \pmod 3$.  It turns out that if $B \in E(\mathbb F_p)$ is an element of prime order $n$, and $\lambda$ is a root of $\lambda^2 + \lambda + 1$ modulo $n$, then for any scalar $k$, $f([k]B) = [\lambda \cdot k]B$.  (Obviously, this requires that $n \equiv 1 \pmod 3$ too.)

In brief, in the subgroup generated by $B$, computing $(x, y) \mapsto (\beta x, y)$, which costs only a single multiplication in the coordinate field $\mathbb F_p$, is a much cheaper way to compute $P \mapsto [\lambda]P$ than the standard double-and-add algorithm on the binary expansion of $\lambda$, which costs $H(\lambda) - 1$ additions and $\lfloor\log_2 \lambda\rfloor$ doublings, where $H(\lambda)$ is the Hamming weight of $\lambda$.

To take advantage of this, for any scalar $k$, write $k \equiv k_1 + k_2 \lambda \pmod n$; then to compute $[k]P$, you can reduce it to

\begin{align*}
  [k]P &= [k_1 + k_2 \lambda]P \\
       &= [k_1]P + [k_2]([\lambda]P) \\
       &= [k_1]P + [k_2]f(P).
\end{align*}

The GLV paper goes into a little more detail about how to turn this into a complete scalar multiplication algorithm.  Unfortunately, the recursive decomposition of $k$ itself has costs, so the net improvement is only a modest 50% or so.

To generate a new prime Koblitz curve, or GLV curve, exploiting this particular endomorphism, lay out candidate primes $p_0, p_1, p_2 \ldots$ and curve parameters $b_0, b_1, b_2, \dots$ in some order of preference (say, primes nearest a power of two below it, and smaller parameters), and pick the first $p_i$ and $b_i$ such that

$p_i$ is prime,
$p_i \equiv 1 \pmod 3$,
the number $\ell_i$ of $\mathbb F_{p_i}$-rational points on the curve $E/\mathbb F_{p_i}\colon y^2 = x^3 + b_i$ is prime,
$\ell_i \equiv 1 \pmod 3$, and
all other security criteria of interest are satisfied.

Next, pick a generator $g$ of $\mathbb F_{p_i}$, and let $\beta = g^{(p_i - 1)/3} \bmod{p_i}$; and pick a generator $h$ of $\mathbb Z/\ell_i\mathbb Z$, and let $\lambda = h^{(\ell_i - 1)/3} \bmod{\ell_i}$.  These are by construction cube roots of unity, since, e.g., $\beta^3 \equiv (g^{(p_i - 1)/3})^3 \equiv g^{p_i - 1} \equiv 1 \pmod{p_i}$, and they are nontrivial because if $g$ generates $\mathbb F_{p_i}$ then it must have order $\phi(p_i) = p_i - 1$ and so $g^{(p_i - 1)/3} \not\equiv 1 \pmod{p_i}$.  Since there are two nontrivial cube roots of unity in each group, they may be mismatched like socks: you may have to use $\ell_i - \lambda - 1$ instead, or $p_i - \beta - 1$ instead, to make them match.

For binary Koblitz curves, see Koblitz's original paper.  The endomorphism in this case, on the $\mathbb F_{2^m}$-rational points, is the Frobenius map $f\colon (x, y) \mapsto (x^{2^m}, y^{2^m})$, with which $[2^m]P$ can be computed by $f(P) - f^2(P)$.  The trick is to find an appropriate extension field $\mathbb F_{2^m}$ over one of the four curve shapes $y^2 + x y = x^3 + a x^2 + b$ where $a, b \in \{0,1\}$.


Generating a SHA256 pkcs1v1.5 Blind RSA Signature using Chaum's Blind Signature Scheme

I can't believe it but I actually found an answer.
The following js code does exactly the padding scheme as detailed in the EMSA-PKCS1-v1.5 message encoding specification
function messageToEMSA_PKCS1_v1_5(message){
    // https://tools.ietf.org/html/rfc3447#section-9.2
    SHA256_DIGEST_INFO = "30" + "31" + "30" + "0d" + "06" + "09" + "60" + "86" + "48" + "01" + "65" + "03" + "04" + "02" + "01" + "05" + "00" + "04" + "20" ;
    T = SHA256_DIGEST_INFO + sha256(message);
    t_len = 51; // Just T.length 19 octets from the Digest Info + 32 octets from SHA-256

    ps_len = 256 - t_len - 3;
    PS = "ff".repeat(ps_len);

    EM = "00" + "01" + PS + "00" + T;
    console.log(`EMSA-PKCS1-v1_5 encoded Message: ${EM}`);
    return EM;
}

Following this, the blind signature after being unblinded, would be a valid pkcs1v1.5 signature


Bit decomposing a polynomial in BGV cryptosystem

To understand that, we have to understand how it works for a single polynomial (which means, for $n = 1$).

First of all, think about the binary decomposition of an integer value: given $m \in \mathbb Z_q$, it is always possible to write $m = \sum_{i=0}^{\log q} b_i 2^i$, with each $b_i$ in $\{0, 1\}$.

Now, just see that if you decompose each coefficient $a_i$ of a polynomial into the binary representation $\sum_{j=0}^{\log q} b_{j,i} 2^j$ , you get $\log q$ polynomials:

$\begin{align}
p(x) &= a_dx^d + a_{d-1}x^d_{d-1} + ... + a_1x + a_0\\
     &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^j \right)x^d + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j \right)x^{d-1} + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^j  \right)x^1 + \sum_{j=0}^{\log q} b_{j,0} 2^j\\
    &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^jx^d \right) + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j x^{d-1} \right) + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^jx^1  \right) + \sum_{j=0}^{\log q} b_{j,0} 2^j\\
     &=  \sum_{j=0}^{\log q} \left(b_{j,d} 2^j x^d + b_{j,d-1} 2^j x^{d-1} + ... + b_{j,1} 2^j x^1 + b_{j,0} 2^j \right) \\
     &=  \sum_{j=0}^{\log q} \left(b_{j,d} x^d + b_{j,d-1} x^{d-1} + ... + b_{j,1} x^1 + b_{j,0} \right)  2^j \\
     &=  \sum_{j=0}^{\log q} u_j(x)2^j
\end{align}$

Therefore, what this BitDecomp function does when it receives a single polynomial is to return a vector with those $\log q$ polynomials $u_j$.

Thus, when given a vector with $n$ polynomials, it returns a vector with $n \cdot \log q$ polynomials.

Maybe this answer will be useful to you, since it is very related to your question ($Dec_{w,q}$ is a generalization of BitDecomp that uses a parameter $w$ to the base instead of fixing the value $2$).


Is there a crytographic scheme for "ciphertext consistency verification"?

Well, I've come up with one potential answer.  I'm not sure how practical it is, however it does indicate that their exists a solution (and maybe a better solution can be found).

After writing it up, I decided that it's not a very good answer (likely going way over your head, and certainly not something you should try to implement yourself), however I'll keep the answer just in case someone else could improve o it.

It is based on "ECElGamal on a pairing friendly curve".

In ECElGamal, we work on a curve with order $n$ and well-known generator $G$; for a secret key, we select a random value $k$ between 1 and $n-1$; we compute the public key $K = kG$ (which we can publish).

To encrypt a message to us, someone first encodes their message into an curve point $D$ somehow (it doesn't really matter how, except it needs to be invertible), and selects a random value $r$ between 1 and $n-1$, and then generates a ciphertext that consists of the two points $rG$ and $rK + D$ (remember, $K$ is our public key).

Then, to decrypt a message that consists of two points $A, B$, we compute $B - kA$ (using our private key $k$), if $A = rG$ and $B = rK + D$, the result of this is $B - kA = rK + D - k(rG) = rkG + D - krG = D$; hence, we get the encoded curve point (and so we then convert the curve point $D$ back into the original message).

Now, suppose we publish a ciphertext $(A, B)$ encrypted with public key $K$, and then publishes a ciphertext $(A', B')$ encrypted with public key $K'$; how can we check if they encrypted the same message?  Here's where the pairing-friendly part comes in: we check if:

$$e(A, K) / e(A', K') = e( G, B - B')$$

Here's how it works: if $A = rG$, $A' - r'G$, $B = rK + M$, $B' = r'K' + M$ (that is, encrypts the same message with a different $r$ and key values), then,

$e(A, K) / e(A', K') = e(rG, K) / e(r', K') = e( G, rK ) / e( G, r'K')$

$e( G, B - B') = e( G, rK - r'K') = e( G, rK) / e(G, r'K')$

That is, if the two ciphertexts encode the same message, the test passes.

So, if it solves the problem, but it does have these drawbacks:

It uses nonhybrid public key cryptography; hence it is inefficient (and each ciphertext encodes a relatively small amount of data, say, a few hundred bits).  To encode more than that, you'd have to encode each block separately, which is not going to be fun...
Worse, the "key hash" is actually the public key; what this means is that if someone has a guess to the data $D$, all they need to do is encrypt it with a random public key (doesn't matter which), and then use the above procedure to check if the two ciphertexts (the one under test, and the one they just generated) have the same plaintext.  If this is an issue, then you'd need an alternative method where the hash isn't a public key.


RSA: Probalistic algorithm to compute $x$ from $y$ and $(n,e)$ with probability $\epsilon>0$ given set of weak ciphertexts?

Let $d_k$ denote decryption and $x = d_K(y)$. I further assume that $\epsilon < 1$.
First note that $A_1$ calculates a randomly chosen cipher text $y$ with probability $\epsilon$.
But the task is to construct a probabilistic algorithm $A_2$ which decrypts a fixed cipher text $y$.
Therefore, proceed as follows:

choose a random $r \in Z^*_n$
calculate $y' = y* e_K(r)$
Use $A_1$ to decrypt $y'$ to $x'$
calculate $x = r^{-1}*x'$

This algorithm calculates the decryption of $y$ with probability $\epsilon$:
 - In step 2, $y'$ lands with probability $\epsilon$ in $S$
 - In step 3, the calculation yields
$$x'= d_k(y') = d_k(y*e_K(r)) = d_K(y)*d_K(e_K(r)) = d_K(y)*r = x*r$$


Are there any noisy homomorphic encryption schemes?

Yes, on the paper Homomorphic Encryption for Arithmetic of Approximate Numbers, Cheon et al. propose a scheme in which the error is not completely eliminated during decryption.

That is, if $c$ is an encryption of $m$, then $Dec(c) = m + e$, where $e$ is some small error.

Roughly speaking, that scheme simulates floating-point arithmetic, since this type of arithmetic also accumulate errors.

With that, the authors manage to perform operations that are hard to do with exact homomorphic encryption schemes. For example, in Algorithm 2 (page 15), they show how to compute homomorphically $\frac 1 m$ with $r$ bits of precision (with other schemes, that is only possible using bootstrapping...).


Distinct cleartexts that are invariant under encryption

Why is it at least 9?

Actually, we have to assume that $p$ and $q$ are distinct odd primes, and that $d$ is odd; this is presumably covered by the assertion that $n = pq$ is an RSA modulus.

With that assumption, we can proceed as follows: we have $m^d \equiv m \pmod n$ iff both these hold:

$$m^d \equiv m \pmod p$$

$$m^d \equiv m \pmod q$$

This is a consequence of the Chinese Remainder Theorem, which we'll be using a lot.

For the relation $m^d \equiv m \pmod p$, for odd prime $p$, we have at least 3 values of $m \bmod p$ that satistify it, namely $m \equiv 0, 1, p-1 \bmod p$ (and the later is often written as $-1$, as $p-1 \equiv -1 \pmod p$).

Similarly, we have at least 3 values of $m \bmod q$ that satify $m^d \equiv m \pmod q$, $0, 1, -1 \pmod q$.

Now, by the Chinese Remainder Theorem, and because $p, q$ are relatively prime, then for any pair of integers $a, b$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$.

As a consequence, for any one if the values $a \in \{0, 1, -1\}$, and any one of the values $b \in \{0, 1, -1\}$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$.  Such an $m$ satisfies both of our original relations modulo $p, q$, and hence satisifies $m^d \equiv m \pmod n$.

There are a total of 9 such sets of $a, b$ values, and hence 9 such values of $m$.

  can it be more ?

Actually, if we have $d = 3$ (or if $d$ is the decryption exponent corresponding to $e = 3$), then no, we can't; for the relation $m^3 = m \pmod p$, there can only be at most 3 solutions (as $p$ is prime); as we have listed 3 such solutions, that must be all of them (and similarly for $q$).

However, if we consider larger values of $d$, then yes, there can certainly be more.  As an example, if we have $pq = 65$ and $d = 5$, there happens to be 25 such 'value preserving cleartexts' (and it should be easy to reconstruct why this is).

  And is there any proof for this ?

The above explination can be expanded to a formal proof; if you want, you can find explicit representations of all 9.


DH Elliptic Curves: Why choose a fixed base point?

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

If you could create such a rainbow table that allows you to compute discrete logs of random values to a base $G$ with nontrivial probability $p$, then you can solve the discrete log to any base (with work that takes an expected $O(1/p)$ time.
Here's how it works:

You're given the point $H$ and $J$, and want to compute the discrete log of $J$ to base have $H$, that is, the value $x$ s.t. $xH = J$

First step, compute the discrete log of $H$ to the base $G$, that is, the value $y$ s.t. $yG = H$.  What you do is pick random values $r$, compute $rH$, and use your rainbow table to find try to find the discrete log $y'$ of $rH$.  This takes an expected $1/p$ attempts (because $rH$ is a random point), and one we stumble on an $r$ that works, we have $y = r^{-1}y'$

Second step, use the same procedure to compute the discrete log $z$ of $J$ to the base $G$; again, this takes an expected $1/p$ attempts.

Third step is easy; $x = y^{-1}z$; we're done; that works because $yH=G$ hence $H = y^{-1}G$, and $J = zG$, hence $J = z(y^{-1})H$

On the other hand, for any curve we believe is secure, creating such a rainbow table is infeasible; if the order of the curve is $n$, then the creation would take at least $pn$ point multiplications; for all practical purposes, the standard discrete log algorithms that take $O(\sqrt{n})$ time are more feasible.

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

In addition to having the same security, it turns out that, if we know $G$ in advance, we can compute $rG$ considerably faster; hence it makes the system faster for the honest parties, and just as secure.


If we note $|m|$ the number of bits in the bytestring coding the message $m$, the first padding considered is $m\mapsto \tilde m=257\cdot2^{|m|}+m$, and the signature is $m\mapsto\tilde S(m)=S(\tilde m)=\tilde m^d\bmod N$, where $S$ is the textbook/naked RSA signing $m\mapsto m^d\bmod N$. Notice that for any $m$ small enough that $m^2$ can be signed, we can derive $S(m^2)$ as $\big(S(m)\big)^2\bmod N$; and if $n^2$ is too big, we may still have $S(m^2\bmod N)=\big(S(m)\big)^2\bmod N$.

NO, we can not derive $\tilde S(m^2)$ as $\big(\tilde S(m)\big)^2\bmod N$. That equality holds if and only if $\tilde m^2\equiv\widetilde{m^2}\pmod N$. At least, when $m$ is small enough that $\widetilde{m^2}<N$ or some similar huge bound (not explicit in the statement), that simplifies to $\tilde m^2=\widetilde{m^2}$, and there is no $m$ matching that: notice that the square of an integer which two leftmost bytes after removing leading zeroes are 0101 has its two leftmost bytes after removing leading zeroes among {0102, 0103, 0104}. I conjecture, without proof, that above said bound, we can not efficiently come up with any solution without knowing the factorization of $N$.

But NO, the scheme is not secure. Even with the (unstated) constraint of messages of the same width, it is easy to come up with distinct messages $m_0, m_1, m_2, m_3$ such that $\widetilde{m_0}\cdot\widetilde{m_1}=\widetilde{m_2}\cdot\widetilde{m_3}$; and then we can derive $\tilde S(m_3)$ as $\Big(\tilde S(m_0)\cdot\tilde S(m_1)\cdot\big(\tilde S(m_2)\big)^{-1}\Big)\bmod N$, where the inverse is computed $\pmod N$.

More generally, linear padding schemes (such as the second one proposed) are weak in RSA, and subject to attacks. See Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem, section 4.1.

Even non-linear padding schemes may be quite weak; for example (INCITS/)ISO/IEC 9796:1991 (informally known as ISO/IEC 9796-1, and mostly described in section 11.35 of the HAC) was trounced in 1999, then withdrawn.

Using a padding scheme with a hash helps, but is not an insurance of security against such forgeries, even in combination with a linear padding scheme; for example ISO/IEC 9796-2:1997 was shown to have a vulnerability (not practically exploitable in any setup that I know of), even in its strengthened variant of 2002, now officialy designated as ISO/IEC 9796-2 scheme 1 and in wide use, that prescribes a hash of at least 160 bits. However I do not know of any attack (even theoretical) on the padding of RSASSA-PKCS1-v1_5 of PKCS#1.

Conclusion: when at all possible, and in any setup where an adversary could obtain the signature of chosen messages, use RSA signature schemes with provably secure padding based on Full Domain Hash, like RSASSA-PSS of PKCS#1, or when message recovery is needed ISO/IEC 9796-2 schemes 2 or 3 (although I have never seen a complete formal proof of the later ISO/IEC 9796-2 schemes, I trust them enough).


How difficult is it to practically detect a forgery in a cryptosystem?

Confidentiality does not imply authenticity.  Many common ciphers are trivially malleable—an attacker that doesn't know the key can nevertheless modify ciphertexts in ways that cause predictable changes to the plaintext.  Authenticated encryption solves this problem.

  I wanted to know how will one know that the decrypted text is not correct? My point is that whether the decryption was successful or not can be checked by seeing if the either the decrypted text is same as what we expected it to be or follows the syntax of the language in which it was expected.

There is no general criterion to be had here.  If the attacker has partial information about the plaintext (e.g., the language or protocol, the application that sends the message, the context in which the message was sent, etc.), they may be able to leverage this to produce an undetectable forgery.

Keep in mind that most encrypted data is not read by humans, but rather processed by computers, or as I like to call them, "error multiplication machines."  Attackers don't have to fool a human, only a computer—a fairly stupid machine that may act in very literal and potentially catastrophic manners when given unanticipated input, and which will happily do the wrong thing over and over and over.


Fiat-Shamir transform to Sigma protocols to turn into NIZK

The idea is that the hash function replaces the random pick of the verifier at step 2. So you must hash the public statement ($h$ for protocol 6.1.1, $(u,v)$ for protocol 6.2.2) with  the commitment sent by the prover at step one ($a$ for protocol 6.1.1, $(a,b)$ for protocol 6.2.2).

The prover cannot guess the challenge $e$ before he generates the commitment  $a$, because  the commitment is used to generate the challenge.
The intuition is that since the random oracle act as an honest verifier, it is equivalent to interact with an honest player or with the random oracle. There is no other change.

If the prover hashes only the public parameter, then he can choose the challenge $e$ before he generates the commitment $a$. For instance, in protocol 6.1.1, the prover can forge a proof $(a,z)$ such that $g^z=ah^e$ by computing $e=H(h)$, choosing $z$ at random  and computing $a=g^z / h^e$.

On the other hand, hashing the public parameters prevent the attacks where an adversary has access to a proof oracle that forges proofs for chosen statements. For instance, for any chosen $x$, knowing a proof $(a=g^r,z=r+H(a)w)$ for the statement $h'=hg^x=g^{w+x}$ (where the statement is not used in the hash) for the non-interactive version of protocol 6.1.1, you can forge a proof $(a, z + H(a)x = r+H(a)(w+x))$ for the statement $h$.

Finally, the non-interactive proof for protocol 6.1.1 can be defined as follows:

chose $r$ and compute $a=g^r$
compute $e=H(a||h),$ where $H$ is a hash function and $||$ denotes the concatenation.
compute $z=r + ew$
return the proof $(a,z)$


Knowing a valid salted hash for an unknown secret, is it possible to compute another valid hash?

Let's get terminology right. If you talk of "unknown s" then s is not a salt; when some piece of data is secret, we call it a key. And your "hash function" is then a MAC. In the context of "password hashing", such things are sometimes called "peppering" (as always, technical terminology is, at its core, a collection of bad puns).

If your MAC is correct (i.e. "cryptographically secure"), then no, it is not possible to produce new pairs message+hash value without knowing the key; being able to do that would be called a forgery. The length extension attack is a forgery attack on some poorly-designed MAC algorithms, which work by simply hashing the concatenation of the key and the message, with a Merkle-Damgård hash function like SHA-256. Don't take it wrong: the "length extension attack" does not mean that SHA-256 is cryptographically weak as a hash function; it just means that making a MAC out of a hash function is not as immediate as it initially seems to be. The proper way to turn a hash function into a MAC is HMAC.

Bcrypt is not a MAC, and, arguably, not a hash function either, since it does not accept as input a sequence of bits of arbitrary length. The salt in bcrypt is not secret at all; it is often encoded in the bcrypt output; moreover, if you are using the salt as a secret for some passwords, then you are reusing the same salt value for several hashed passwords, and that's very wrong. The whole point of the salt is to be distinct for every instance (every user has his salt; when the user changes his password, a new salt must be generated).

On the concept of password hashing, read this.

Edit: it has been brought to my attention that I misread the question somehow: the salt is known to be public. The question being: can we transform a hash for some secret password with some salt value, into another hash for the same secret password, but with another salt value ?

If such a thing is feasible and the new salt value can be arbitrarily chosen, then this would be a severe flaw in the hashing function, because it would allow the attacker to transform a bunch of hashed passwords into another bunch of hashes of the same passwords but all with the same salt -- thereby nullifying the advantage of the salt: parallel and precomputed attacks are again possible. Even if the attacker could just turn the salt into another "random" salt, then it could be used to make salt collisions more probable. No such flaw is currently known for bcrypt.


Since you encrypt just a single letter, there are $26^2$ combinations of $p$ and $c$ where $c=E(p)$. This is because there are $26$ possible shift keys in the key space, an therefore each $p$ can be mapped to one of $26$ letters in the code space. Now, assuming that the key is distributed uniformly in the key space, each of those combinations of $(p,c)$ has a probability $\frac{1}{26^2}$. From base low we have:
 $$P(P=p\mid C=c) = \frac{P(P=p\text{ AND }C=c)}{P(C=c)}.$$ Now,
 $$P(P=p\text{ AND } C=c) = P(p,c) = \frac{1}{26^2},$$ and assuming uniform distribution $P(C=c) = 1/26$, you get $P(P=p|C=c) = \frac{1}{26} = P(P=p)$. QED


$J_A \cdot a^e \: \equiv \: 1 \:\: \pmod{n} \;\;\;\;\; \iff \;\;\;\;\; a^e \: \equiv \;\; $$\operatorname{modinv}$$(J_A,\hspace{-0.02 in}n) \:\: \pmod{n}$

Since that is the RSA problem, the fastest known way to solve it is to factor $n$ which reveals $\lambda$$(n)$,

and then try $\;\;\; a \: = \: \operatorname{mod}\left(\hspace{-0.03 in}(\operatorname{modinv}(J_A,\hspace{-0.02 in}n))^{\operatorname{modinv}(e,\hspace{.02 in}\lambda(n))},n\hspace{-0.03 in}\right) \:\:\:\:$.


You should think of Rijndael's S-box as a function that maps bytes to bytes, where a byte (octet) is considered to be a member of a finite field of size $2^8$ (with xor as addition). It's not seen as a 16x16 octet array, really.

The substitution is then just done byte-wise: every octet in the 4x4 block is replaced by its function value under the S-box table.

The mix column is just a matrix multiplication of the column with a 4x4 matrix, all in the field of size $2^8$. See the wikipedia entry for a worked example.


TLS Key Exchange content in DHE vs. ECDHE

TL;DR: The public key and the name of the group.

RFC 4492 (especially section 5.4) has all the details for you.

What you basically do is the following:

You send a point on the curve (your public key, ie $Q=y\cdot G$)
You send a description of the curve, this is either:

Some identifier for the curve, for example 23 if you wanted to use the most-commonly used P-256. This is what happens always in practice, in fact many browsers don't even support explicit curve parameters.
A full description of the prime or binary curve, ie the relevant values to define the field, the relevant values to define the curve parameters over the field and the relevat base point.


DDH and pairings are not contradictory in RingCT 2.0?

For the following explanation, let $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. It depends on the setting you are using whether DDH can hold or not. In the symmetric setting ($\mathbb{G}_1 = \mathbb{G}_2$, i.e., Type 1 pairings) the pairing serves as a DDH oracle for both, $\mathbb{G}_1$ and $\mathbb{G}_2$ and DDH can neither hold in $\mathbb{G}_1$ nor in $\mathbb{G}_2$. In the asymmetric setting, we distinguish two different settings, i.e., Type 2 and Type 3. The important difference in this context is that in the Type 2 setting there exists an isomorphism $\psi: \mathbb{G}_2 \to \mathbb{G}_1$ while such an isomorphism is unknown for the Type 3 setting. Now, in the Type 2 setting, the pairing together with the isomorphism serves as a DDH oracle for $\mathbb{G}_2$, while DDH is assumed to hold in $\mathbb{G}_1$. Finally, in the Type 3 setting, DDH is assumed to hold in both $\mathbb{G}_1$ and $\mathbb{G}_2$.

The particular combination you are asking about is in the Type 1 setting, so DDH can not hold for both source groups of the pairing.

Additional note: In the paper you are citing, actually a group (i.e., $\mathbb{G}_q$) which is independent of the pairing groups is used. In such a setting DDH can of course also hold in $\mathbb{G}_q$. However, using an independent group also means that the order of this group is different to the order of the pairing groups, which makes ZK consistency proofs between elements of the different groups - as required in this paper - quite complicated. I can not find anything in the paper which would address this issue.


UC-framework: Simulating specific cases (proof in PVW)

These two cases are trivial cases, usually don't need to argue about because they are definitely simulatable.

In the first case, both parties are controlled by the adversary. In the simulation, the simulator simulates both the corrupted sender and the corrupted receiver. The simulator can simply use the adversary as a subroutine to simulate each party, generates the messages to be relayed by environments. There is no need for the simulator to extract the adversary's input when all parties are corrupted by the adversary. The view will be indistinguishable from a real view because the adversary is the same in the simulation and in the real execution. Note that in this case simulation can be done but no security can be achieved, as the adversary has already corrupted all parties (nothing is left to be secured).

In the second case, both parties are honest, thus they will follow the protocol (which means they will use whatever input they have). The simulator is given their inputs  at the beginnning at the simulation and can just follow the protocol to generate the messages. The view will be identically distributed as in a real execution where the two parties are honest. This case is trivially secure because there is no adversary at all.


Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)

Suppose I had an enormous exponent $B$. To compute $g^B\mod G$ (I'll omit "mod $ G$" from now on), I would use a square-and-multiply method: I would compute $g$, $g^2$, $g^4$,\dots, $g^{2^t}$, where $t$ is the bit-length of $B$, then multiply all $g^{2^i}$ for $i=1$ in the binary representation of $B$. Note that this involves, at most, $t$ squarings and $t$ multiplications (I'll assume squaring and multiplication take the same amount of time, which isn't exactly accurate but is good enough for this explanation), so the delay is at most time $2t$ times the time for a single square/multiplication.
However, the exact time is less clear; it will depend on the Hamming weight of G, how we store intermediate values, or whether we keep a running product of all $g^{2^i}$ that we have reached so far, etc. And note that we had to compute $g^{2^t}$ anyway to find $g^B$.
The proof of exponentiation for a big number shouldn't vary that much from the proof of repeated squaring. I'm also not sure the Pietrzak verification method works with arbitrary exponents (probably? but it will need some modification).
So basically, arbitrary large exponents should work, but it will be more complicated than just repeated squaring.
The generator cannot be an arbitrary number because it needs to change for every use. If the same generator were used in two different applications, someone could save all the values of $g^{2^t}$ and just look them up in memory the second time, and thus they would not have the required delay. The time-lock game in Definition 2 says that $g$ is uniformly random; the construction doesn't mention this but I think this is a basic assumption of all VDFs.


Short answer: You could do this, but (a) it would be dramatically more expensive, (b) it would not improve security in the way you think it would, and (c) it would by design have back doors.

  Every now and then, we read that some hashing function has been weakened or broken, but we almost never hear this for asymmetric cryptosystems like RSA or ECC. That's because while asymmetric encryption uses mathematical impossibilities (discrete logarithm or prime factorization computation in polynomial time), hashing functions obfuscate their working by complexification, but it seems impossible to make a collision-free hashing function (that is, there is no algorithm to find collisions faster than bruteforce). Symmetric encryption is in the same case than hashing functions, because these algorithms (like DES) seem to have a shorter lifetime than RSA for example, which has been used for more than 40 years.

  My assumption is that there is a difference of nature (and not degree) between on the one hand asymmetric encryption (that isn't vulnerable to cryptanalysis) and on the other hand hashing and symmetric encryption (that are vulnerable to cryptanalysis).

On the contrary, quite the reverse is true.  This notion is a red herring, even if this is a common trope (or perhaps, a common tripe?).

Public-key cryptosystems  are designed out of rich mathematical theories that are rife with exploitable relations.  This is necessary for them to have separate public keys and private keys—the private key, in some sense, is a back door.  But it also exposes them to a rich theory of vulnerabilities, and tends to make them very expensive to compute.

The first RSA challenge published by Martin Gardner in his August 1977 Mathematical Games column in Scientific American (sorry, I don't have a paywall-free link!) with a 125-digit semiprime was estimated to take over 40 quadrillion years to solve, yet was solved in 1994 (paywall-free)—coincidentally revealing my name.  The RSA proposal published in 1978 (paywall-free), considering 40 quadrillion years not enough, recommended 200-digit semiprimes out of an abundance of caution—that is, about 664 bits.  The RSA-200 challenge was broken in 2005 (archived), fifteen years ago, only 27 years after the 1978 RSA paper.

Why did this happen?  It's not because silicon technology sped up by a factor of over a quadrillion.  It's because factoring is full of mathematical relations that turn out to be helpful, and we had tremendous mathematical advances—first with the quadratic sieve, and then with the special number field sieve, and then with the general number field sieve.  These mathematical advances reduced a 40-quadrillion-year computation into a few bucks on Amazon EC2.

(There's a similar story of dramatic breakthroughs for many classes of elliptic curves, and for newer pairing-based designs that have an even richer mathematical structure, but I'll leave that story to Koblitz, Koblitz, & Menezes who tell it better.  Some parts of the ECC story seem to have stabilized, but there's plenty more rich mathematical theory to explore.)

Symmetric cryptography tends to be much easier to make secure.  For comparison, we might take a look at DES, which was developed around the same time.  Martin Hellman predicted in 1979 that DES would be totally insecure within ten years (paywall-free).  Sure enough, within a mere nineteen years (off by less than a factor of two, rather than off by a factor of a quadrillion!), EFF's Deep Crack performed a brute force key search to recover a DES challenge key.  Today, again, it's a few bucks on Amazon EC2.  Meanwhile, cryptanalytic advances against DES have been quite modest—especially in comparison to RSA, and the ratio is even starker if you take into account the cost to compute DES and the cost to compute RSA for the legitimate user.

Today, we have a plethora of symmetric ciphers and preimage-resistant hash functions have withstood scrutiny for decades with essentially no serious cryptanalytic advances against them.  The reason ‘RSA’ persists today is that it is actually a family of cryptosystems that can be scaled up to defend against cryptanalytic advances: we no longer use 512-bit RSA keys; we use 2048-bit RSA keys today—and we're getting nervous about those.  But there's only one DES—so we replaced it by AES to raise the generic security, reduce the cost, and address the mild cryptanalytic advances against DES.

What about collision resistance?  Generally, collision resistance seems harder to achieve—and costlier to compute—than preimage resistance, or pseudorandomness.  The hash functions MD4, MD5, SHA-0, SHA-1, RIPEMD, and HAVAL-128 originally advertised with collision resistance have all been broken.  But many of them share common design elements—MD4, MD5, SHA-0, and SHA-1 in particular—which is why we all got really nervous in the mid-2000s about SHA-2 (which shares the design elements) and NIST launched the SHA-3 competition to choose a very different design in case SHA-2 should fall.

But since then, the story seems to have stabilized (archived).  We now have a number of hash functions that have held up quite well for much longer than MD4, MD5, SHA-0, or SHA-1 ever did, and they've held up well enough that cryptographers are comfortable reducing the costs—the popular hash function BLAKE2 is like the SHA-3 candidate BLAKE, but cheaper; the newer KangarooTwelve is like the SHA-3 winner Keccak, but cheaper—without losing collision resistance.

‘But I wanna collision-resistant hash function built out of number theory!!’
OK, OK, here you go.

Pick an RSA modulus $n = pq$.  (Make sure it is big enough to resist 1994 researchers!)  Pick $g \in (\mathbb Z/n\mathbb Z)^\times$ uniformly at random.  For an integer $x$, define $H_{n,g}(x) := g^x \bmod n$.  (To extend this on bit strings, pad them appropriately and interpret them as integers in, say, little-endian.)  Anyone who can find a collision in this can factor $n$ without much more difficulty.  (Proof and references to related ideas.)

Of course, there's a back door!  Anyone who knows $p$ and $q$ can trivially find collisions: $x$ collides with $x + \operatorname{lcm}(p - 1, q - 1)$.  You were asking, after all, for asymmetric cryptography—which means, just like with Dual_EC_DRBG, that there's a back door!

Maybe stick with SHA-2, SHA-3, or BLAKE2?


Can we use a Merkle Tree structure to reduce digest size?

The problem is that your construction (the whole second picture) still constitutes a compressing function with 128bit output. Hence, we can find collisions at complexity about $t\cdot2^{64}$, where t is the runtime of your construction.
Indeed, it seems that a little misconception motivates your work: You sound as if it was harder to find a collision than a second-preimage. However, it is the other way around; finding a second-preimage is (generically) a lot harder than collision-finding. The complexity of a generic second-preimage attack is equal to that of a generic preimage attack. The complexity of a generic collision attack is only the square root of the complexity of a second-preimage or preimage attack.


Concatenating "words," is it possible to create a key that is indistinguishable from one made in a truly random manner?

No. From 3 “words” as in the question, there can't be any fast public transformation (like the one considered in the question) creating a key of more than about 10 letters in A…Z that is indistinguishable from a key made in a truly random manner, in the sense that has in crypto.
Taking the question's numbers, we pick 3 words in a set of 180,000. That's $(180,000)^3$ choices (ignoring the requirement of length being coprime, which reduces the number of choices significantly; and assuming the position of the letters kept is known, or found by trial and error). Whatever deterministic transformation we make of this input, it can't have more outcomes. If the transformation has for outcome 12 letters in A…Z, not all such strings can be obtained, since $(180,000)^3\ll26^{12}$. Given a string of 12 letters in A…Z, it can in principle be tested if it could have been generated by the transformation applied to the input words, or not (at least by enumerating the $(180,000)^3$ choices and applying the transformation). For 12 letters in A…Z chosen "in a truly random manner", the probability is at most $(180,000)^3/26^{12}<6.2\%$, when that's $100\%$ when using the transformation. That's "distinguishable from a key made in a truly random manner", in the sense that has in crypto, if the test "could have been generated by the transformation applied to the input words" is feasible.
For the question's transformation, that test is feasible, and much faster than testing the $(180,000)^3$ possible input words. One way is to consider only the $(180,000)^2$ combinations of two words, deduce what the selected letters must be considering the key tested, and see if that exists in the dictionary. I estimate that such test lasts a fraction of an hour on a single computer.
Even if we used a cryptographic transformation like SHA-256, the test remains feasible, since $(180,000)^3\approx2^{52.4}$ SHA-256 hashes is within reach.
The first paragraph says "more than about 10 letters" rather than "more than 11", because even with 11 letters, we can still distinguish outputs of the transformation from random, with a few example outputs. Problem is that no transformation can make all the $26^{11}$ outcomes of 11 letters equally likely, because $26^{11}$ does not evenly divide $(180,000)^3$. At best, some (41%) 11-letter outputs will have probability $1/((180,000)^3)$, and the others (59%) twice that. Which is distinguishable from true random with a few examples. With 10-letter outputs, we could still pull that trick with some more examples. That's for the best possible fast cryptographic transformation, and is much easier for the question's simple transformation, where we could recognize the output from random based on a large sample of the first few characters of the output keys.

The best crypto has to offer here is a password-based key derivation function such as Argon2, which is a purposely slow hash, and can be used to a generate a key (of any length) that is indistinguishable from random for practical adversaries, given an input with enough combinations (and here, we have $(180,000)^3\approx2^{52.4}$, which is quite respectable if we are willing to wait 1 second for the Argon2 transformation to run on a computer).


Mostly because when the command was created DES was the thing, and "no des" meant "don't encrypt".  Now the default is different:

$ openssl req -new -newkey rsa:1024 -keyout rsa.enc.p8 -out rsa.enc.p8.csr
Generating a 1024 bit RSA private key
...................................++++++
...........++++++
writing new private key to 'rsa.enc.p8'
Enter PEM pass phrase:
Verifying - Enter PEM pass phrase:
<snip />

$ openssl asn1parse -i -dump < rsa.enc.p8
    0:d=0  hl=4 l= 710 cons: SEQUENCE
    4:d=1  hl=2 l=  64 cons:  SEQUENCE
    6:d=2  hl=2 l=   9 prim:   OBJECT            :PBES2
   17:d=2  hl=2 l=  51 cons:   SEQUENCE
   19:d=3  hl=2 l=  27 cons:    SEQUENCE
   21:d=4  hl=2 l=   9 prim:     OBJECT            :PBKDF2
   32:d=4  hl=2 l=  14 cons:     SEQUENCE
   34:d=5  hl=2 l=   8 prim:      OCTET STRING
      0000 - e9 37 68 99 cb 9c 4f 10-                          .7h...O.
   44:d=5  hl=2 l=   2 prim:      INTEGER           :0800
   48:d=3  hl=2 l=  20 cons:    SEQUENCE
   50:d=4  hl=2 l=   8 prim:     OBJECT            :des-ede3-cbc
   60:d=4  hl=2 l=   8 prim:     OCTET STRING
      0000 - 16 ad ce 41 47 e8 ba 85-                          ...AG...
   70:d=1  hl=4 l= 640 prim:  OCTET STRING
<snip />

The algorithm that it actually used was des-ede3-cbc, aka 3DES-CBC.  While AES has almost entirely supplanted 3DES, 3DES isn't considered insecure.

NIST SP 800-57 Revision 4, Table 2, says that 3DES has 112 bits of security, putting it on par with RSA 2048.  Table 4 then says that 112 bits of security is good through 2030.


With SHA-3 Derived Functions (SP 800-185, pdf) there is now a standardized parallel hash based on SHA-3, called ParallelHash, appropriately.

However, it is not a tree hash, but more of a hash-list-based mode. The string to be hashed is divided into equal-sized blocks, which are hashed, concatenated and then hashed again.

While it is not a tree hash it should cover the use case of hashing very large files across many machines. The arbitrarily small blocking size allows you to get to your $O(\log n)$ requirement if you base it on an appropriate function of the input size.


Indeed, the SpongeWrap paper does not claim CPA security (or, really, any kind of privacy protection at all) unless a nonce is included in the associated data, or the associated data can otherwise be guaranteed to be unique for each message.  In particular, if you look closely at section 2.2, you'll find the following note at the end of page 3:

  For privacy, we consider only adversaries who respect the nonce requirement. For a single header-body pair, it means that, for any two queries $(A, B)$ and $(A′, B′)$, we have $A = A′ ⇒ B = B′$. In general, the nonce requirement specifies that for any two queries $(\overline{A, B})$ and $(\overline{A′, B′})$ of equal length $n$, we have $${\rm pre}(\overline{A, B}) = {\rm pre}(\overline{A′, B′}) ⇒ B^{(n)} = B′^{(n)},$$ with ${\rm pre}(\overline{A, B}) = (A^{(1)}, B^{(1)}, A^{(2)}, \dots , B^{(n−1)}, A^{(n)})$ the sequence with the last body omitted. As for a stream cipher, not respecting the nonce requirement means that the adversary can learn the bitwise difference between two plaintext bodies.