Why does Carter-Wegman (and AES-GCM) use different keys for PRF and keyed-hash

Let's consider a degenerate case. Suppose you're authenticating 16-byte messages, your DUF (better known as (almost) xor-universal hash) is $\text{AES}_k$, and your PRF is also $\text{AES}_k$. Then you have
$$
\text{WC}(m, n) = \text{AES}_k(m) \oplus \text{AES}_k(n)\,,
$$
where $m$ is your 16-byte message, and $n$ is a 16-byte nonce. This is obviously forgeable by simply switching the nonce and the message! Yet, it would be perfectly secure if we used independent keys for each primitive.

In less degenerate cases, such as GCM, you could possibly use the same key for both. But you would have no easy way of arguing the security of the scheme, since the hash and the PRF would not be independent.


There are two different primes being used here.

Using your notation, $q$ should be the prime defining the field $\mathbb{F}_q$ over which the curve is defined.

$n$, instead, indicates the (prime) order of your generator $G$.

The coordinates of points, and therefore the computations of scalar multiplications and point addition, are done in $\mathbb{F}_q$.

So, your point $R$ will have coordinates $\bmod q$. But you still need to apply the modular reduction with respect to $n$ to $x_R$ in order to make verification work.
This is because the $r$-part of the signature is also computed $\bmod n$ and $n$ is allowed to be smaller than $q$.


Could time lock encryption be implemented through indistinguishable obfuscation?

Time-lock puzzles can be built from indistinguishability obfuscation through succinct randomised encodings: see the work of Bitansky et al. [BGJ+,BGL+] for more details.

[BGJ+]: Bitansky et al. Time-Lock Puzzles from Randomized Encodings. ITCS'16

[BGL+]: Bitansky et al. Succinct Randomized Encodings and their Applications. STOC'15


I won't give the answer; here are some hints:

Suppose we have a valid cipher text $(A, B) = F(k, r), r \oplus F(k, m)$.  What happens if we modify the ciphertext to be $(A, B \oplus C)$ and get that decrypted?
How can we use this?  What can we do if we have two ciphertexts that encrypt the same message $m$?


Examples of multi output bit balanced Boolean functions

As in the other answer a vectorial boolean function with $m$ coordinates $f : \{0,1\}^n\to\{0,1\}^m$ are viewed as $m$ boolean functions $f_i : \{0,1\}^n\to\{0,1\}$.
However, it is not enough to consider $f$ to be balanced when the $f_i$ are all balanced.
For example consider $m=2,$ and $f_i(x_1,x_2,x_3)=x_1\oplus x_2,$ for $i=1,2.$
The truth table for $f_i$ is $[01100110]$ in the natural order. However, the function $f(x_1,x_2)=(f_1,f_2)$ does not have a property that we would call balanced since its truth table would be $[00,11,11,00,00,11,11,00].$
A natural requirement for a balanced vectorial boolean function with $m$ output coordinates is that all $2^m$ output $m-$tuples occur equally often in its truth table.
One way to ensure this holds is to stipulate that for all nonzero vectors $(a_1,\ldots,a_m)$ in $\{0,1\}^m,$ the boolean function $\langle a,f \rangle=a_1 f_1\oplus a_2 f_2 \oplus a_m f_m$ is itself balanced.
So if we had $f_1=x_1,f_2=x_1\oplus x_2,$ in the above example our function would be balanced with truth table $[00,11,01,10,00,11,01,10]$.
Usually we require other properties in addition to being balanced, such as high algebraic immunity, correlation immunity [=resilience if balanced], high nonlinearity, etc.
There is a good survey by Claude Carlet easily discovered online entitled "vectorial boolean functions". Early papers by Nyberg gave examples of nice balanced vectorial functions. Clearly if $m=n,$ and the function is balanced, you a nice $m\times m$ S-box, since each output pattern occurs exactly once and we have a permutation.


Magic Number to calculate number of rounds for M-R in FIPS 186-4

This constant is used to approximate $(\pi(2^k) - \pi(2^{k-1}))^{-1}$, as shown in (4.1) of the Damgard et al. paper:

$$
p_{k,t} \le (\pi(2^k) - \pi(2^{k-1}))^{-1} \sum\nolimits'_{n \in M_k} \bar{\alpha}(n)^t \,.
$$

Most of the formula in the NIST document, between the square brackets, is dealing with the $\bar\alpha$ sum. The left side is dealing with the prime difference approximation.
From Propositon 2 of the Damgard et al. paper, we have

$$
(\pi(2^k) - \pi(2^{k-1})) > 0.71867 \frac{2^k}{k}\,,
$$

from which we can replace $(\pi(2^k) - \pi(2^{k-1}))^{-1}$ by $\frac{1}{0.71867 2^k / k}$ $=$ $1.39145 \cdot k \cdot 2^{-k}$ $=$ $2.00743 \cdot \ln(2) \cdot k \cdot 2^{-k} $.

The $\ln(2)$ term probably comes from the approximation $\pi(2^k) \approx \frac{2^k}{ \ln(2^k)} = \frac{2^k}{k \cdot \ln(2)}$, as in the proof of Proposition 2.


How can a block cipher in counter mode be a reasonable PRNG when it's a PRP?

For a random function you'd expect all outputs to be different if you generate fewer than $2^{n/2}$ blocks (birthday problem). Thus PRPs and PRFs are indistinguishable unless you observe about $2^{n/2}$, at which point you'd expect collisions using the PRF but not using the PRP.

For a 128 bit cipher this is a lot of data, so we generally don't care about this. But using a 64 bit cipher, you shouldn't encrypt more than a few gigabytes of data using the same key.

  are there any alternative examples of CSPRNG constructions that generate quality values for arbitrarily large amount of bits?

In principle yes. I think using a variant of CTR mode which uses a secret IV and xors the counter+IV into the output might work. It'd get rid of the trivial "no duplicates" pattern, but it might be distinguishable in other ways.

128 bit blocks should be good enough as a stream cipher/CSPRNG. But if it's a bit too low for your taste (Generating $2^{64}$ blocks is feasible with sufficient effort), you can simply use larger blocks. Typically hash functions (like SHA-2), which want to avoid collisions, use 256 or 512 bit block ciphers.

I've changed the paragraph on wikipedia to

  A secure block cipher can be converted into a CSPRNG by running it in counter mode. This is done by choosing a random key and encrypting a 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Assuming an n-bit block cipher the output can be distinguished from random data after around $2^{n/2}$ blocks since, following the birthday problem, colliding blocks should become likely at that point, whereas a block cipher in CTR mode will never output identical blocks. For 64 bit block ciphers this limits the safe output size to a few gigabytes, with 128 bit blocks the limitation is large enough not to impact typical applications.

I mention the $2^{n/2}$ birthday bound limitation. Removed the part about the period, since it doesn't matter in practice (it's far above both practical output size and safe output size). I also removed the part about keeping key and plaintext (what plaintext? It's a CSRPNG, not a cipher) secret. I'm not really happy with the formulation, so feel free to improve it.


When a program using openssl library is using a certificate, does the server check if the issuer(s) are still valid

The server may react as it pleases. The TLS spec doesn't come with application instructions in this regard.

The client should definitely reject any certificate chain it manages to build with an expired certificate. That means that the handshake should fail and the TLS session will not be instantiated. This requirement depends on a clock available to the client - which may be tricky in itself for certain environments.

It doesn't matter that the chain only consists of two certificates; root and leaf certificate.


Partial key recovery from linear equations

Firstly consider the simple case where we know that there is only a simple x-or relation between two key bits. $k_i \oplus k_j = 1$ and $i \neq j$ and call it $R1$. If we consider the x-or table we will see that only half of the rows for $k_i$ and $k_j$ will satisfies this equation.

\begin{array}{cc|c}
 k_i & k_j & k_i\oplus k_j \\ \hline
 0 & 0 & \color{blue}{0} \\
 0 & 1 & \color{red}{1} \\
 1 & 0 & \color{red}{1} \\
 1 & 1 & \color{blue}{0} \\
\end{array}

An equation with equal to $0$ has the same result, i.e. x-or splits the table into half.

Now, lets look at a key search by brute-force.

   for key in possible_keys
       if ciphertext = Enc(key,m)
            return key

Clearly, this will take $\mathcal{O}(2^n)$-time for n-bit cipher.

Now using the relation update this key search

   for key in possible_keys
       if the key doesn't satisfy R1
           continue
       if ciphertext = Enc(key,m)
            return key

What is the gain here? For half of the keys, the loop will not compute the Enc this means that the keyspace is reduced by one-bit due to the R1.

One might say that we are still looping as the number of all possible keys. The cost of an Enc is not considered in the $\mathcal{O}(2^n)$-time. If you add it then you will see that, you will get an approximately a double speed up. It might possible to design an iterator that only loops valid keys, however, that is a software issue. There is a another approach for this see, below.

A relation having more than two key bits will have the same result. Half of the time we don't need to calculate the Encryption.

If we have more than one relation for the speed up calculation we will use fixing bits by equations. Lets look at your your equations to see this:

  $k_{1} \oplus k_2 \oplus k_{63} = 1$

  $k_{1} \oplus k_3 \oplus k_{17} = 1$

  $k_{43} \oplus k_{56} \oplus k_{60} = 0$

While iterating we if we know $k_1$ and $k_2$ than the value of $k_{63}$ is fixed. Even if one of $k_1$ and $k_2$'s is flipped $k_{63}$ is also flipped. So, you iterate overall, expect the $k_{63}$ since it is fixed. To benefit this you can use a permutation on the keys for better iteration.

Similarly, for your second and third equations. So, you have fixed three keys depending on the relation. This can result in a 3-bit key search advantage. Roughly, we can say, $l$ equations gives $l$-bit advantage.


How was the 5 digit random number in the VIC cipher generated?

In the VIC cipher, that significant five-digit number was created by the user when doing the encryption. It was surely made on the spur of the moment without equipment. As you remarked, these people were spies, and they would not have wanted to get caught with some strange device.
The CIA's online library does not mention the five-digit number as a value that the user had to memorize. The agent already had four mnemonic keys stored in his or her mind:
 1. a date (in Russian this would be day/month/year; six digits)
 2. a snippet of a popular Russian song        (20 characters long)
 3. the user's personal identification number
 4. a Russian word (e.g., the word for "snowfall")

I do not know for sure, but I think it is most likely that agents came up with their own "random" number out of their own heads. One, admittedly thin, piece of evidence might be that the Russians were generating "one-time pads" at that time out of their own heads by pecking at a typewriter--and keys generated in such manner were considered "random" enough to encrypt important traffic.


Is it possible to identify a Serpent encryption key in memory?

Yes, Serpent also does a deterministic well-known key expansion. So it should be possible to identify the sub keys in memory. You will want to know what implementation you are looking for since there is more than one sensible order for the key material to be in.


Actually, for any group operator $\odot$, we see that $x \odot y$ gives perfect security, assuming that $y$ is uniformly random over all possible group members.

The $\equiv$ operation is a group operation, with the group members being $\{0, 1\}$, with $1$ being the identity.  Hence, yes, it gives perfect security.


How about this (and, at this level, it's not specific to RSA, but is equally analogous to any public key encryption method):

Max makes a safe with a slit on the top.  Max made the safe, so he knows the combination, but no one else does.  He gives the safe to Sam, who gives it to Dale.  Dale writes his note, and inserts it into the safe.  He gives the safe back to Sam.  Now, Sam can't open the safe, so he gives it to Max.  Max uses his combination to open the safe and read the note.

The nice thing about this analogy is that it captures some of the real concerns from a straight-forward use of public key crypto:

How does Dale know that the safe he was handed was actually made by Max?  That's quite valid, and is also a concern with public key cryptography.
What if Sam inserts his own message into the safe?  That's also a valid concern with public key crypto; as designed, Max has no way of knowing who wrote the message.

Both of these can be addressed, however that's a deeper topic.

(And, I'm pretty sure I read this somewhere, but I don't remember where...)


So my question is how do I continue from here? How do I figure out what encryption method is being used?

It sounds like you, in essence, have black box access to something that allows you to give it a key and a file, and it returns an encryption of that file (after adding some file format around it) using the supplied key.

Your goal is to figure out how the encryption works. There may be legal issues you want to consider before actually doing this, but legal issues aside, you have many options.

Your best option would be to reverse engineer the code that is doing the encryption. Is this software running on your computer or some sort of hardware device? In either case, you should be able to get the code and reverse engineer it by putting it in a disassembler and doing static analysis, or putting it in a debugger and doing dynamic analysis.

Let's pretend, however, that you do not have access in any way to the code. Maybe this black box is running on a remote server that you do not have access to. Your goal then is to figure out what cipher are they using (e.g., AES, DES, 3DES, RC4, etc) and what mode of encryption is being used.

You can start to do this by asking a few questions and using your black box access to start answering the questions.

Is the encryption deterministic? Or in other words, given the same plaintext (or file) and key, does it always return the same result?
If I flip a single bit in the plaintext, how does the resulting ciphertext change?
What happens if you feed a ciphertext in as the plaintext, do you get the original plaintext back? In other words, is the encryption mode the inverse of itself?
By flipping bits at different places, can you figure out the block size? Depending on the mode used, where you flip bits can change what blocks actually change?
Something else to investigate is why does the ciphertext appear to always be double the size of the plaintext? When you pass in 123, which as ASCII would have 3 bytes, why do you get 6 bytes back? Is there some sort of encoding going on?

This is how I would suggest continuing from where you are.


How much processing power should you assume an attacker has?

I'd say it depends of value of the assets. If you need to protect data worth let's say $10m, you can assume someone could throw at least money up to that value to get it. Converting money into computational power with AWS or Azure is pretty trivial today, and it can be done by virtually anyone.

And of course state-level parties might be interested in your data for whatever reason they like (for example NSA, interested even in your private photos - see Can They See My Dick?), and they might throw computational power of much higher value that traditional cyber-criminal could justify in given case.

So in short: always assume adversary might have supercomputer or powerful botnet.


In the STS Authentication Protocol, why are the signatures encrypted?

The encryption of the signatures

$\;$ keeps the identity of the initiator (Alice) confidential, even against active attackers
$\;\;\;\;$ and
$\;$ keeps the identity of the responder (Bob) confidential against passive eavesdroppers
$\;\;\;\;$ and
$\;$ provides some protection against identity misbinding attacks,

$\;$ although not as much as a good protocol should have

.


FHE over the integers - Is that paper's scheme known to be insecure against quantum adversaries?

According to the answer by Hilder Vitor Lima Pereira in the this question, the main scheme is believed to be quantum secure.


Using authenticated encryption along with signing

Signatures provide one property that MACs don't: non-repudiation. With only a MAC (or an AEAD) any party with the secret key could have sent the message. So Bob could forge a message and claim Alice sent it. With a signature only the party holding the corresponding private key could have created the signature.  MACs authenticate the message, not the sender.
When this property is needed one must accept the performance decrease of adding the signature. If this property isn't needed, then there's no need to sign.


find $a$ and $k$ for a given el gamal cryptosystem

I found the answer after getting a hint from my professor

basically if we have an equation in to form

$$m*x = (m*y) mod (m*z)$$
we can factor out m such that:
$$x = (y) mod (z)$$

but...
the only caveat is that there are m solutions for x:
$$
x, x+z, x+2*z, ..., x+(m-1)z = (m*y) mod (m*z)
$$
using this we can solve the equation in the question $$a(23972)=(23704) mod (31846)$$
even though 23972 is not invertable mod 31846.

start by factoring out 2 from everything
$$2a(11986) = 2(11852) mod 2(15923)$$

this gives:
$$
a(11986) = 11852 mod 15923
$$

solving for a:
$$
a = (11852)(11986)^{-1} mod 15923 = (11852)(182) mod 15923 = 7459 mod 15923
$$
now the multiple solution part:

where  $$m = 2$$ and $$z = 15923$$ in our case

a = 7459 mod mz and 7459 + z mod mz

so $$a = (7459) mod (31846), (23382) mod (31846)$$
and $$k = (1162) mod (31846)$$


Is message integrity possible without confidentiality? Are there any mainstream protocols?

Hash-then-encrypt is not a scheme that is used a lot. It may not be necessarily secure in all situations.

Instead message authentication codes (MAC) are used. These produce what is called an authentication tag (symbol: $t$); a fixed size, keyed hash over the processed data. Obviously, as a keyed hash it requires a key as input, preferably one specific for the MAC.

MAC can be split into hashes that are based on block ciphers or hashes. An example of a MAC is AES-CMAC; it is based on AES in CBC mode but it doesn't encrypt the plaintext (the intermediate ciphertext is not kept). It makes sense to use a block cipher based MAC if the block cipher - usually AES - can be used with hardware acceleration.

HMAC - which simply stands for Hash-based MAC - can be used with MD5, SHA-1 and SHA-2 as underlaying hash construct. As SHA-3 is already protected against length extension attacks it can be used with a more elegant approach called KMAC.

Nowadays authenticated ciphers such as AES-GMAC are becoming popular. Authenticated ciphers are usually AEAD ciphers: ciphers providing Authenticated Encryption with Associated Data. The associated data (AD) or additional authenticated data (AAD) within these schemes is also integrity protected and not encrypted.

This way you can decide yourself what data you want to keep confidential. If you want you can put everything in the AD, so you would not have any ciphertext, only plaintext and the authentication tag.

Usually you only need to provide a single key which can be used for both confidentiality and authenticity, simplifying key management somewhat.

Notes:

You may require additional constructs such as a message counter or session keys for each sending entity to create a secure protocol; just having a MAC or authenticated cipher may not be enough.
Most cryptographers agree that encrypt-then-MAC is more secure than MAC-then-encrypt in most situations, so please keep that in mind if you do need to keep part of the data confidential.
When in doubt: use HMAC; it's the most common MAC, it has aged really well and provides lots of security. HMAC-SHA-256 - HMAC with SHA-256 as underlying hash algorithm (configuration parameter) is a good, secure, generally available algorithm. If you think a 32 byte tag is a bit too large you can just the 16 leftmost bytes instead.


How to encrypt dates using format preserving encryption and avoid collisions

So, in the comments, you state that

  I'm using the original date as the key

This is the reason for the duplicate dates. The encryption is entirely deterministic for a fixed key. When you change the key, however, it is not. So it is entirely plausible that encrypting the number 215 with the key 215 could result in the same ciphertext as encrypting the number 10 with the key 10. But, encrypting the numbers 215 and 10 each with the same key, say 111, should be guaranteed to result in different ciphertexts (assuming you are not using the tweak, or using a fixed tweak).

If you had a fixed, random key, then you should get different ciphertexts. Adding in a random, per-message "tweak" can also cause this behavior.

So you can fix this "problem" by just using the same key everywhere and no tweak. This does, however, scare me. You are using deterministic encryption in an application that has a fairly small domain. Could make you vulnerable to frequency attacks, or other attacks, depending on the exact application.


Modifying an Enigma machine to allow unchanged letters

There was at least one late Enigma derivative, the Russian M-125 Fialka, that did modify the reflector to allow a letter to encrypt to itself.

Curiously, rather than simply making the cipher alphabet size an odd number (which would've been natural enough for Russian, with its 33-letter Cyrillic alphabet), the designers of the Fialka instead used a rather complicated (and, for its time, advanced) "magic circuit" to replace two wire pairs with a single "plaintext enable" signal (which caused the plaintext input to be output unchanged) and a set of three wires connected to a transistorized "binary rotator" that mapped an input signal on any of the three wires to an output signal on the next wire out of the three, as in (1 → 2, 2 → 3, 3 → 1).

Of course, the magic circuit also meant that the Fialka lacked the self-reciprocal property of the Enigma: encryption and decryption were not (quite) the same operation.  Thus, the Fialka also needed an "encrypt" / "decrypt" mode switch that simply swapped two of the three wires going into the magic circuit.

Quite why this feature of the Fialka was implemented in this specific manner is, as far as I'm aware of, not known.  One might suspect that the original Enigma-based design of the Fialka, with an even number of letters and an Enigma-style reflector, may have been finalized before someone became aware of the cryptanalytic significance of the Enigma never encrypting a letter to itself, and that this flaw was fixed in a manner that minimized changes to the rest of the design.  Or some Russian cipher machine designer might have just been eager to play with fancy new transistor technology.


homomorphic encryption special case of multi party computation?

You've got the relationship a bit muddled.  A scheme for fully homomorphic encryption can be used to perform secure multi-party computation (MPC).  However, it's not a special case of MPC.

The connection is a standard elementary result, which I will summarize here.  If you want to do secure multi-party computation, you can express the computation as a boolean circuit $C$, and you can easily transform any circuit so that it uses only AND gates and NOT gates.  Then, it turns out that you can compute $C$ on encrypted data, if the data was encrypted using a fully homomorphic encryption scheme, using the following relationship: when working with $\{0,1\}$, AND can be done by multiplication ($x$ AND $y$ $ = xy$), and NOT can be done with addition (NOT($x$) $ = 1-x$).  Since the fully homomorphic encryption lets you do addition, subtraction, and multiplication on encrypted values, it also lets you do NOT and AND on encrypted values, which is all you need to do secure multi-party computation.


Why would you use a weaker hash function than cipher strength?

Well, firstly, SHA-1 still seems to have 160-bit preimage and second preimage resistance, so using it in HMAC requires more than 128-bit AES keys to get equivalent security.

AES 192 would be sufficient, but isn't used in e.g. TLS – RFC 3268 says:

  The AES supports key lengths of 128, 192 and 256 bits.  However, this
     document only defines ciphersuites for 128- and 256-bit keys.  This
     is to avoid unnecessary proliferation of ciphersuites.

So with AES and SHA-1, you can pick between either MAC security (AES-256) or cipher security (AES-128) being the limiting factor.

As for MD5, there are no TLS cipher suites with AES + MD5 at all. In the case of password-based encryption, where a combination of MD5 and AES-256 is defined in Bouncy Castle, it's definitely a legacy algorithm.

In general, there's a difference between the integrity offered by the MAC (which the hash functions are used for here) and the privacy offered by the cipher. If you valued privacy above integrity, you could have a higher minimum security you desire from the cipher. An attack on the MAC would frequently have to be online, while an attack on the cipher could be done offline, even years after the fact.

Also, the MAC length requires space in each message, while the key length of AES does not, so you might want to use a short MAC even if you were fine with long keys and the resulting processing time.


What does this part of the SHA-3 algorithm mean?

It's simply separating an integer into bytes with naive encoding. This is directly the represntation of the number, before padding length encoding etc. Think of binary representation of the number and group the bits into bytes. Those bytes are the Xi values. With X1 being the most significant and Xn being least significant.


If RSA is only used to encrypt symmetric keys which are random, what's wrong with textbook RSA?

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed.

Now, the first important thing to note is that the RSA assumption states that RSA is hard to invert when given a random element in the ring. So, if you choose a random value $x$ between $0$ and $N-1$ and then compute $x^e \bmod N$, then according to the RSA assumption it will be hard to find $x$. However, this doesn't mean that it's hard to find some of $x$ (and knowing some of the key is disastrous), and it also doesn't mean that it's hard to invert RSA when $x$ is not a random element between $0$ and $N-1$. For example, what happens if $x$ is a random 128-bit string (converted to a big number)?

The good news is that we actually do have a (partial) answer for this. First, consider the case of $e=3$. In this (quite common) case, if $N$ is 2048 bits long then for any string $x$ of length at most 682 bits, it is trivial to invert and find $x$ when given $y=x^e \bmod N$. This is due to the fact that when $e=3$, the length of $x^e$ is 3 times the length of $x$. If the length of $x$ is less than 682 bits then the length of $x^e$ is less than 2048, and so $x^e \bmod N$ equals $x^e$ over the integers (this is because no modular reduction ever takes place). Note that finding a cube root over the integers is easy (just do a "binary search" over the possibilities). I stress that the conclusion from this is not to use a larger $e$; the conclusion is not to do plain RSA.

However, since people are often not yet convinced by this, there is another attack that works for any $e$, including large values. In this attack, when the input $x$ is of length 128 bits, it is possible to find $x$ in about $2^{64}$ time, given $x^e \bmod N$. In general, it is possible to invert RSA in time that is square-root of the string length of the input. So, this is not secure. Now, you may want to say: OK, so I'll use a 256-bit key! However, note that instead of having 256-bit security you'll have 128-bit security. More importantly, this attack that takes square-root time is an indication that this is a really bad idea. So, don't do it! (References for the attack: the basic attack on plain RSA appears in this paper by Dan Boneh et al. (Why Textbook ElGamal and RSA are Insecure), and removing the space requirement in that paper can be achieved using the technique in this paper by Oorschot and Wiener (Parallel Collision Search with Cryptanalytic Applications.)

This leads to another possibility which is to choose a random $x$ between $0$ and $N-1$ and to compute $x^e \bmod N$. Then, using a hash function $H$, derive a key $k=H(x)$ to use for symmetric encryption. In the random oracle model (with $H$ being a random oracle) this is actually secure, and will even be CCA-secure if the symmetric scheme is CCA secure (this is actually a CCA-secure KEM/DEM scheme; see the next paragraph for more on this). However, without a random oracle we have no idea how to prove this secure.

In general, we know that in order to get a CPA-secure hybrid encryption scheme, we need both the asymmetric and symmetric scheme to be CPA secure; likewise for CCA security. However, there are more efficient ways of working, which is the KEM/DEM paradigm. This is more relaxed than hybrid encryption, since the asymmetric part defines a random key for the symmetric encryption, but it's not necessarily in the hands of the encryptor to determine what the key will be. I will leave you to look up the KEM/DEM paradigm if you are not familiar with it.


Necessity of changing $p$ and $q$ when your private key is exposed?

If you know even a single key pair $(e,d)$, then you can factor $N$, so that's pretty much the ultimate attack — efficient, total key recovery. For a short, digestible proof of this, see the last fact on page three of Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.


Shannon entropy of string, not same in Binary form? But just as good as a password?

I'm going to telepathically make a wild guess.

My wild guess is that you generated the string Au+u1hvsvJeEXxky by asking a computer to choose sixteen characters independently and uniformly at random from the alphabet consisting of a-z, A-Z, 0-9, +, and -, which is, coincidentally, the base64 alphabet.

The distribution on individual characters has 6 bits of entropy per character.  The distribution on strings of sixteen characters chosen independently from this distribution is sixteen times that, namely 96 bits of entropy per string.

If I, as the adversary knowing this information about your process but not knowing the particular outcome, tried to guess your string, I would have a $1/2^{96}$ chance of getting it right.  If I kept trying guesses, the expected number of guesses before I get it right—that is, the average of number of guesses over all possible values of your string—is $2^{95}$.  That's a lot of guesses.

However, as the adversary, I often have more powers than that.  Often, what I have is some hash of your string $H(s)$, and not just yours but $H(s_0), H(s_1), \ldots, H(s_{9999})$ of ten thousand different users who all used the same process.  My goal as the adversary is to find at least one of the strings $s_i$—chances are if I can get a foothold by compromising one user, I can use that to compromise more users in a network.

If I do this intelligently, the cost of my attack—measured in joules, or USD, or EUR—is significantly less than $2^{95}$ times the cost of testing a single guess by evaluating $H$.  With the help of Oechslin's rainbow tables, if parallelized $p$ ways, at least hundred million, I can share work between attacking many targets at once, and it will cost only about $2^{82}$ evaluations of $H$, in the time for about $2^{82}/p \leq 2^{56}$ sequential evaluations.  The Bitcoin network spends this cost in about a year; $2^{56}$ nanoseconds is about two years.

That's a high cost, and a long time to wait, but it's absolutely within the budget of a major corporation or government.  I would recommend making sure that the cost is around $2^{128}$ evaluations of $H$ so that it is completely out of reach of foreseeable human engineering.  There are three ways to do this:

Have every user choose from ${\geq}2^{256}$ possibilities uniformly at random.  For example, instead of sixteen-character base64 strings, use forty-three-character base64 strings.  Or use sequences of twenty words chosen independently uniformly at random from a word list of 7776 words.
Store a salt unique to each user, and use $(\sigma_i, H(\sigma_i, s_i))$ where $\sigma_i$ is the $i^{\mathit{th}}$ user's salt and $s_i$ is the $i^{\mathit{th}}$ user's secret.  This thwarts rainbow tables and prevents the adversary from sharing work between multiple users.
Use a password hash that is costly to evaluate like scrypt or argon2id.

Method (1) is something the users can do.  Alternatively, the computer can choose the user's secret for them, and ask the users to remember it.  Methods (2) and (3) are things that whatever uses the secrets can do—something that the engineers of an application can put into their system to defend it against brute force attacks even if some users choose secrets poorly like human-chosen passwords.

All of the numbers above are premised on the model I telepathically guessed.  Not everyone guesses the same model.  The ent utility suggested by Paul Uszak and an entropy calculator on the web suggested by conchild instead guess the following probability distribution on symbols: probability 1/8 for u and v, probability 1/16 for {+, 1, A, E, J, X, e, h, k, s, x, y}, 0 probability for any other character.  They suggested this by (a) counting the number of appearances of each character in your string, and (b) dividing by the length of your string.  I, instead, used knowledge of common protocols on the internet to guess that you are using the base64 alphabet.  We all assumed independence between characters.  But nobody here knows anything about the process you used.


Symmetric-like cyphers with several steps

This is not possible with symmetric cryptography.
To show this, I will construct an asymmetric encryption algorithm from your scheme.
Consider $pub = (k_1, \dots, k_{n-2})$ as the public key and $prk = (k_{n-1}, k_n)$ as the private key.
The encryption algorithm will be $c = enc(pub, d) := P(k_{n-2},P(k_{n-3},\dots ,P(k_1,d)))$
The decryption algorithm will be $d = dec(prk, c) := P(k_{n}, P(k_{n-1}, c))$
Since there may be no relations in the sets $puk \cup \{k_{n-1} \}$ and $puk \cup \{k_{n} \}$ , the computation of prk from puk will be infeasible.
This is a property of an asymmetric cryptographic system.


The formulae on the linked page deal with curves in short Weierstraß form, that is $y^2=x^3+ax+b$. Your curve is not given in this format.
You can find the correct formulae for long Weierstraß curves (like yours, where the coefficients $a_1$ and $a_3$ are zero) on this page.


What are the “costs” to find a pre-image, weak collision, or strong collision?

Definitions:

In the pre-image attack, given a hash function $H$ and a hash value $h$, we try to find $x$ such that $h = H(x)$. The $x$ need not be the original input value used to calculate the hash $h$.

In the second preimage attack ( weak collison); we are given $H,x,h$ with $h = H(x)$ and we need to find another $x'$ such that $h = H(x')$.

Collision attack (strong collision); we are looking for two different inputs $a$ and $b$ such that  such that $H(a)=H(b)$.

Costs:

The cost of pre-image and secondary pre-image is $\mathcal{O}(2^n)$
The usual search for preimage and secondary pre-image is either iterating from 0 to $c\cdot2^n$ or randomly testing $c\cdot2^n$ values from a larger space then $2^n$.

The cost of the collision is $\mathcal{O}(2^{n/2})$ with 50% probability and this is due to the birthday attack.
The naive way is generating $2^{n/2}$ input hash pairs and sort them according to hash values. This costs around $\mathcal{O}(2^{n/2})$ space.
A better way is using Pollard's Rho *;

Pick a random hash value $h_1$ and set $h_1' = h_1$
Compute $h_2 = H(h_1)$ and $h_2' = H(H(h_1'))$. That is one is slow one is fast.
continue the process $h_{i+1} = H(h_i)$ and $h_{i+1}' = H(H(h_i'))$ until we reach an index $j$ such that $h_{j+1} = h_{j+1}'$

We can visualize this algorithm as below; The algorithm eventually enter a cycle (the Rho-Shape)

The path to $h_5$ is a collision. The cycle length and the collision points can be found by Floyds algorithm.
This requires $\mathcal{O}(2^{n/2})$ operations to find the collision.
If we ask, what is the average cycle length is? If we model the hash function as uniform random then this is shown by Harris in 1960. For a hash function with $\ell$ bit output, the average cycle length is $\frac{1}{ 2} \sqrt{2 \pi \ell}$ for SHA256 that makes $2^{127} \sqrt{\pi}$. That makes it quite unreachable for a hash function with 256-bit output to run the cycle to find a collision

*In other context this is also known as Floyd Cycle detection algorith (Floyd's Tortoise and Hare).  Knuth attributing it to Floyd, without a citation. The origin is not known.


Key management and derivation - Allow changing of the passphrase

If you want to allow sharing of files between users without sharing their master key and/or pass phrase, you need to allow for something like this extra layer of "indirection" complexity.

However, per-file keys must be crated from HKDF(master_key, file_nonce) or a similar one-way key derivation function. Using simple XOR in this case would expose the master key to anyone with whom a per-file key is shared.

A file share would be simply taking the per-file key and wrapping it using some key known to the "destination" user. The "owning" user doesn't need this information, as they can always re-derive the per-file key using their master key and the per-file nonce.

Note that you will want to use a string such as "per-file key derivation" as the info parameter to HKDF to provide "domain separation". That is, you are using the source key and a nonce as input, and then deriving a key for a specific purpose. You don't want to generate the exact same key and use it for a different purpose later on, you would use for example a different info parameter if you were going to generate something else from the same master_key and file_nonce.


Block Cipher Mode Amicable to Fast Key Change/Rotation Like XOR?

A better way to solve your problem is: on the server, encrypt the document under a document encryption key (a unique key that's specific to that document).  The document remains encrypted in storage encrypted under this document key.  When a client requests the document, send the client a copy of the encrypted document, as well as an encryption of the document key encrypted with the client's key.  Now the client can recover the document key and then decrypt the document.

This will be very efficient and will meet all of your requirements.  And, it is implementable using only standard cryptographic primitives approved in FIPS 140-2.

If you ever need to change the document, you should change its document encryption key to a new, unique key chosen independently of the previous version.  Re-encrypt the new version with its new unique key.  This way, users who have previously downloaded the old version of the document don't automatically get access to the new version (unless you decide they should be allowed to).  This lets you implement revocation to the extent that revocation is possible in this setting.  Thanks to DrLecter for this suggestion.


In step d) $Q_1$ is a point after applying the Frobenius map on $Q$. Then in step e) there is $T=T+Q_1$. Confusion: According to my calculation above, $Q_1$ should not be on the same curve where $T$ is. Is it correct to calculate $T=T+Q_1$? Or is my calculation wrong?

It looks like CurveEnthusiast verified your calculation in comments, so this is strictly for your final question:

The Frobenius map $\pi$ is a mapping from $\mathbb{E}′(\mathbb{F}_q)$ to itself. $T$ is a point on this curve, and since $\pi:\mathbb{E}′(\mathbb{F}_q) \rightarrow \mathbb{E}′(\mathbb{F}_q)$, $Q_1$ is also on the curve and so the sum is defined.


Differential Privacy: why $\delta$ negligible on the row numbers?

$\varepsilon$-differential privacy is absolute: for any pair of databases, you cannot gain more than a small amount of probabilistic information about a single individual. When you add or remove an individual in your database, all possible outputs of your algorithm can appear with similar probability.

By contrast, $(\varepsilon,\delta)$-differential privacy allows this process to fail sometimes: you can have an output that happens with $\delta>0$ probability if the individual is present, and never happens otherwise. If you're super unlucky and this output comes out of your algorithm, an attacker can know that the individual in question is in the set.

Now, how often does that happen? How many users in the dataset are at risk? Well, each user has a $\delta$ probability that this might happen to them. So on average, this will happen $\delta \cdot n$ times (expected value of a binomial law of parameters $(n,\delta)$).

You want $\delta \cdot n$ to be small, because you don't want to leave any user at risk. If $\delta=\frac{1}{100\cdot n}$, you can say "with 99% probability, this bad scenario doesn't happen". But if delta is not a negligible function in $n$, then on average, your algorithm will leave some users at risk when $n$ grows.


There is no known reduction from LWE to MLWE (or to RLWE). That is, it could be that both MLWE and RLWE are broken, yet LWE is secure.
However, this seems highly unlikely. To support the security of LWE, we have reductions showing that breaking the average-case hardness of LWE requires breaking the worst-case hardness of some lattice problems - which would be (in the language of Brakerski et al.) "earth-shattering". Now, similar reductions hold for both MLWE and RLWE (see also this): both can be based on the worst-case hardness of lattice problems. The main difference is that RLWE requires worst-case hardness over ideal lattices, and MWLE requires worst-case hardness over module lattices.
Some notes about the above:

everything strongly depends on the parameters. LWE-style assumptions are heavily parametrized, and saying "reduction" does not say much if we do not make explicit the parameters for which the reduction works. The reductions I mention above are for the most standard choices of parameters (e.g. polynomial modulus).
Worst-case hardness over module lattices sounds more plausible than worst-case hardness over ideal lattices, for a variety of reasons. Yet, up to some important loss in the reduction, we actually do have reductions of RLWE to MLWE. This further illustrate while being precise with the parameter choices is important when discussing this topic.
The main reason why cryptographers prefer using MLWE or RLWE over LWE is because they lead to much more efficient schemes. However, RLWE is parametrized by some polynomial, and requires hardness assumptions tailored to this very specific polynomial. This is a bit unsatisfying, because we don't really understand well the impact of the choice of polynomial on security. However, recently, a new problem was introduced, middle-product LWE. The latter gives us the best of both world: it allows essentially the same efficiency gains as standard RLWE or MLWE in many applications (see the paper, but also its follow-ups), yet it is as secure as RLWE with respect to any polynomial - hence to break it, you would need to break RLWE for every possible choice of the polynomial. This gives a very satisfying ground for the security of this assumption.


Establishing encryption key using shared secret

You don't need a hash function for this.  Given that you're already using AES-128, and that your master key $N_s$ is 128 bits long, a perfectly good method for deriving the session keys $K_s$ would be to encrypt the random number $R_0$ (padded to a full AES block) using AES-128 (in ECB mode, i.e. using the raw block cipher) with $N_s$ as the key.

Even if the attacker can choose the random numbers $R_0$, and could obtain all the corresponding session keys, recovering $N_s$ would still require a practical chosen-plaintext key recovery attack on AES.  No such attack is currently known, and if one was found, AES would be considered totally broken.

However, it's also worth noting that this key derivation scheme (either as above, or as proposed in your question) does not provide forward secrecy; an attacker who has captured a past session, including $R_0$, can easily decrypt it if they later somehow learn $N_s$.

It is, however, possible to achieve something similar to forward secrecy using key renewal.  That is, instead of deriving temporary session keys from a fixed master key, you regularly derive a new master key from the old one, and then erase the old key.  This erasure will protect old messages from decryption even if the new key is compromised; it will not, however, protect future messages from compromise of an old key in any way.

One way to do this would be to compute the new master key $K_n$ from the old key $K_{n-1}$ as $$K_n = \text{AES}_{K_{n-1}}(A),$$ and the corresponding session key as $$S_n = \text{AES}_{K_n}(B),$$ where $A$ and $B$ are any two distinct constant cipher blocks (e.g. all zeros and all ones).  You would then use $S_n$ to encrypt your messages using an authenticated encryption mode.

Maintaining key synchronization between the two communicating sides can be a bit tricky.  One method would be to store the key renewal counter $n$ explicitly, and to transmit it in plain with each message.  Upon receiving a message tagged with a new counter value $n' > n$ (and $n' < n+2^b$ for some reasonable constant $b$, to prevent denial-of-service attacks), you'd compute $K_{n'}$ and $S_{n'}$ and try to use them to decrypt and authenticate the message; if the authentication succeeds, you increment your own counter to $n'$ and start using $K_{n'}$ and $S_{n'}$ as the new keys; otherwise, you assume the message was bogus and ignore it.

Note that it's enough to use a $b$-bit counter and let it wrap around.  For most applications, $b$ can be fairly small; say, $b = 8$, or even $b = 1$.  It's also possible to implement key synchronization without transmitting a counter at all, but this gets slightly more complicated.  (Basically, whenever you receive a message you can't authenticate with $S_n$, you need to retry authentication with $S_{n+1}$.)


Is using a rolling code as a constantly-changing shared secret effective for signing?

I'm confused at your suggestion that your clients would not have access to a public key signature facility, given that you assume that they have crypto hashes and can run code of your authorship.  More generally, the fact that you're trying to roll your own crypto doesn't bode well.

Also, I'd suggest that you have a hard look at the challenges implied by your idea of using a "one-time secure channel" to establish shared keys with your users.  What happens, for example, when one of your users tells you that their key has been compromised?  Invalidating your own copy of that key is easy, but now you need the (supposedly "one-time") secure channel once more to establish a new one.  What's the cost and inconvenience of that?

Or even worse, imagine the case where your database of pre-shared secret keys gets compromised.  You then have to establish a new shared key with every single one of your users, all at once.  Ouch.

Compare this to, say, the way GitHub uses public-key cryptography to manage access to users' repositories:

Users generate private/public key pairs on their own computer.
Users log in to the website using conventional user authentication mechanisms (e.g., passwords, security tokens, SMS, etc.)
Users can then upload public keys, or delete earlier ones that they'd uploaded.

Notice what you gain in this case:

"Self-service": users can add and delete keys at their leisure.  Now when your users' keys are compromised they just log in to your site, delete the compromised ones and upload new ones.
No secret keys are ever transmitted over the wire.  Which implies that you're never storing any secret keys on your side, so if your public key database is disclosed it's not a big deal.
You do need a user authentication system, but:

That can be outsourced (think of all those websites that allow you to log in with your Google or Facebook credentials);
Even if you built one in house, with strong user passwords and proper password storage then a compromise of your password database is would likely be much less damaging than a database of shared secret keys.

But to address your narrower questions, I'd make two observations.  First, your hash(message + secret) scheme is insecure.  Read up on HMAC, which is a standard and secure way of using a hash function as a message authentication code.

Second, you can avoid replay attacks by incorporating a counter into the message that you compute a MAC over.  No need for the random numbers; each client just keeps track of the most recent message number they received from the other party, and rejects messages numbered earlier than the most recent one.

A good MAC will be secure against forgeries.  An attacker who sees the messages and tags (but not the key) for...

tag[1] = HMAC(key, rand[1] + message[1])
       .
       .
       .
tag[n] = HMAC(key, rand[n] + message[n])

...will not be able to forge a valid

fake_tag = HMAC(key, rand[n+1] + fake_messsage)

even if they can predict rand[n+1].  The unpredictability of the RNG's output gains you nothing.  All you need is a way to spot replays—which a counter will do just fine.


Advantages of HS1-SIV over ChaCha20-Poly1305-SIV?

ChaCha20-Poly1305-SIV is not well defined, and does not have the advantages of SIV-mode if you do define it.

The SIV mode is essentially MAC-then-encrypt, with the MAC reused as nonce. The MAC in ChaCha20-Poly1305 requires a nonce, because it uses ChaCha20 to encrypt the Poly1305 authenticator (you cannot reveal the raw authenticator). So you cannot use it to derive a nonce without already having a nonce.

You can use a version of SIV where a nonce is included in the MAC calculation, but then you do not gain any nonce-reuse resistance – the MAC is broken with nonce-reuse. You also have the problem (not insurmountable) of defining how the 128-bit MAC is used as a nonce to an encryption algorithm that only takes a 96-bit nonce.

Essentially, then, there is no advantage of using the SIV mode over just using ChaCha20-Poly1305, and the clear disadvantages of performance and complexity. HS1-SIV solves this by generating new keys using a hash of the message instead. This means that nonce misuse is not the end of the world.

With the updated question, where the MAC is Poly1305 and a PRF applied to it, the requirement of a strong nonce is lessened. However, unless you do include a nonce, you get worse bounds so you would still want a nonce (also to make it non-deterministic, if you want that).

In that case the advantages of HS1-SIV are not so clear. However, it is hopefully a somewhat better analyzed construction – or will be if it does well in CAESAR. It also offers different parameter options, the highest of which uses a hash larger than the 128-bits you are limited to with Poly1305. That means a lower probability of collision, and a higher number of messages before running into the birthday bound.

Again, you would still need to define how a 128-bit nonce will be used in ChaCha20, how or if associated data is authenticated, etc., but it seems like a reasonable option to HS1-SIV's middle set of parameters. The main advantage of HS1-Hash, then, is its flexibility.

(I do not know if it has performance advantages, but it seems possible that especially with short messages it would have an advantage over using an extra ChaCha call as a PRF.)


How to recover private key in ElGamal when random value k is known

How can he recover the private key $a$?

They can't. First, note that $\delta=M(\alpha^a)^k\bmod p$ you can (as you already noted), recover $M$ and thus construct $\delta'=(\alpha^a)^k\bmod p$ given $\delta$, $\beta=\alpha^a$ and $k$. Now you are in a situation which is equivalent to that after a Diffie-Hellman handshake. You are given your own ephemeral DH key $k$, the generator $\alpha$ and the shared secret $\delta'$, if you now could actually find $a$, that is the other party's DH key, this would completely and utterly break any form of $a$-reuse which is assumed to be secure.

More formally:
Let $\mathcal O(\delta',k,\alpha,\mathcal G)$ be an oracle, that returns $a$ from $\delta'=(\alpha^a)^k$ in the group $\mathcal G$. Now let $(\beta,\alpha,\mathcal G)$ be an arbitrary discrete-logarithm instance, such that $\beta=\alpha^x$ in $\mathcal G$. Now note that if we call $\mathcal O$ with $\mathcal O(\beta,1,\alpha,\mathcal G)$, we get $x$ back, the discrete logarithm and have thus solved the discrete logarithm problem efficiently using this capability.

This means that if we could recover $a$ from $(\delta',k)$ we could solve the discrete logarithm problem efficiently, but as this is assumed hard, we can't efficiently recover $a$ from $(\delta',k)$. Of course you may also want to note that coming up with $(\delta',k)$ doesn't require any special knowledge, anybody who is ElGamal-encrypting $M=1$ constructs this pair.


Does a key derivation function always generate an even distribution of bits in the resulting key?

It will be uniformly random for such a simple statistical test. The problem is that you are treating the probability of bits having a particular state as independent of each other. You would need to look at the conditional probability distributions of certain bits being set given other bits.

The entire joint distribution of output and input bits for a function that maps $\{0,1\}^a \to \{0,1\}^b$ requires on the order of $2^{a+b}$ memory to store. Clearly it becomes prohibitive to store and sample it for even a small function that maps 32-bits onto another 32-bits through a fixed transformation (i.e., without including any key bits that define a particular permutation).

The full conditional distribution of a function completely determines it's output. It can be seen as a transition probability matrix in a Markov model. Because of this, the distribution will encode any bias of the function, such as a preference to produce certain bit patterns (with probability).


This "Blowfish" is actually bcrypt itself. Bcrypt was defined by reusing elements of the Blowfish block cipher, but modified. In particular, the key schedule part of the algorithm is expanded into a huge (and configurable) number of rounds.

The password (combined with the salt) is used as key for this modified Blowfish. Once the key schedule has been completed, the modified Blowfish is used to encrypt three blocks, normally the ASCII encoding of the constant string "OrpheanBeholderScryDoubt" (Blowfish, and the modified variant used in bcrypt, work on 64-bit blocks; ECB mode is used; so this yields 192 bits of output).

The man page is misleading, in that it both says that it uses Blowfish (it doesn't, it is a Blowfish variant which is distinct), and that it is encryption (it isn't; it is hashing, as you state).


Can homomorphic operations on many different ciphertexts be multiplied by a same constant?

Yes. Additive homomorphic encryption can also be used to obtain multiplication by a scalar. The way that this is done is by repeated addition, in exactly the same way as you do efficient exponentiation.

Recursively, define:

If $a$ equals 1 then $mult(a,Enc_k(m)) = Enc_k(m)$
If $a$ is even then $mult(a,Enc_k(m)) =
   mult\left(\frac{a}{2},Enc_k(m)\right)+mult\left(\frac{a}{2},Enc_k(m)\right)$
If $a$ is odd then $mult(a,Enc_k(m)) =
   mult\left(\frac{a-1}{2},Enc_k(m)\right)+mult\left(\frac{a-1}{2},Enc_k(m)\right)+Enc_k(m)$

Thus, you only need addition.


Is my AES-128-CTR implementation secure enough to encrypt private keys and mnemonic seed?

This is not secure at all. It's technically off-topic since it's a coding question, but this implementation contains many basic errors. One example is using an insecure random number generator, which utterly destroys the security of the encryption. Another is using AES-128-CTR without authentication.  Do not try to implement your own cryptographic primitives, it takes a ton of work and is prone to obscure errors causing total failure. Use an existing library that provides constructions based on secure primitives that do what you need. That pretty much means libsodium, libhydrogen, tweetnacl-js, or a similar library.

If you use libsodium there's a version compiled to JS: https://github.com/jedisct1/libsodium.js

Documentation here: https://download.libsodium.org/doc/

You're looking for the authenticated encryption functions (crypto_secretbox_easy and its helpers).

Libsodium can encrypt whatever you want. Also the bitcoin private keys are just bitstrings, just like the Ethereum private keys. They can be represented in hexadecimal just as easily as any other encoding.


hyperelliptic curve scalar multiplication

Is D the divisor? And can it be multiplied by a random integer to generate a secure parameter like the one used with elliptic curves?

Well...you're asking if the discrete logarithm problem can apply to hyperelliptic curves. The answer is yes. But it's a bit more complicated than for the elliptic curve case. This is a great introduction. I sketch out some details below if you want to take the plunge.

The problem is more complicated to formulate for hyperelliptic curves than for elliptic curves. This is because there is no natural group structure for points on the hyperelliptic curves like there are for elliptic curves. (Note that elliptic curves are a special case of hyperelliptic curves, with genus $g=1$.) However, you can formulate the discrete log problem over a group associated with hyperelliptic curve, called the Jacobian group. You have Jacobians in your Sage code, for example.

To understand Jacobians, you have to understand divisors. A divisor is a formal sum over points on the curve: $D := \sum_{P \in \mathcal{C}} c_P [P]$, where $c_P \in \mathbb{Z}$ and the number of nonzero $c_P$ is finite. By "formal sum", I mean bookkeeping. For example, if $P,Q,R$ are points on a curve, then a divisor may be $D = 2[P] + 4[Q] - 7[R]$. That's it.

You can also have divisors over functions. If a zero is a point where a function vanishes and a pole is a point where a function is undefined, then the divisor of a function $div(f) $ is a way of bookkeeping the relative number of zeroes and poles. For example, if $f(x) = \frac{x-a}{x-b}$, then you have a zero and a pole, and could write the divisor as $D = 1[a] - 1[b]$. (Notice poles are negative in the sum.) A divisor is called a principal divisor if it's equal to the divisor of a rational function. The set of principal divisors $Prin(\mathcal{C})$ forms a group.

The degree of a divisor is the sum of the divisor's coefficients. So in the above example, the degree is $1 - 1 = 0$. The set of divisors of degree zero is important and is called $Div^0(\mathcal{C})$. Since rational functions have as many zeroes as poles, they all have degree zero, which means $Prin(\mathcal{C}) \subset Div^0(\mathcal{C})$.

Finally, we can define the Jacobian group as the quotient group  $Div^0(\mathcal{C}) /Prin(\mathcal{C})$. You can "add" two divisors using Cantor's theorem. Now that we have elements and addition, we can talk about the hyperelliptic curve discrete log problem:

Given a hyperelliptic curve $\mathcal{C}$ of genus $g$, two divisors $D_1$ and $D_2$, both in the Jacobian group, with $D_2$ in the subgroup generated by $D_1$, and the order $q$ of $D_1$, find the scalar $s$ (modulo $q$) such that $D_2 = s\cdot D_1$.

It's harder to visualize, but the Wikipedia article has an example. It looks like you are using some Sage code. I haven't used Sage for this, but this documentation talks about how to do "divisor addition" (using Cantor's theorem on the Mumford representation of divisors). They reference another great introduction.


Why can't we use the IDEA's decryption rule for decrypting a block on CTR mode?

CTR uses only a block cipher's forward algorithm, not its inverse. Both sender and recipient compute $N_? = E_K(nonce || counter)$ for each block. Then the plaintext is XORed with $N$ to get ciphertext. The recipient XORs ciphertext with $N$ to get plaintext.

$C_i = E_K(nonce || i) \oplus P_i$

$P_i = E_K(nonce || i) \oplus C_i$

Note: XOR is it's own inverse. $A \oplus B \oplus B = A$


What makes this mixer function resistant to differential cryptanalysis?

From your picture I deduce that $A$ and $B$ are both 8 bits.
So this construction can be seen as a $16 \times 8$ bit S-box (not bijective). The fact that it's not square is probably what is causing confusion.
Usually, for SPNs, invertible S-boxes are used. Non-invertible S-boxes are less common, but they certainly have applications.

One of the things we can do to determine the weakness of an S-box with respect to differential cryptanalysis, is to look at the difference distribution table (DDT).
That's just a table where each row (column) represents an input (output)  difference. The entries are equal to the amount of times the output difference occurs for the  input difference. If a certain input difference $\Delta X$ often leads to output difference $\Delta Y$, then this is considered a weakness.

So, how is the value you compute related to the DDT?

  My testing algorithm is essentially to loop through all A and B values
  for all potential input differentials (ΔA or ΔB), and count how many
  distinct output differentials are seen for each input differential.

For a given input difference $(\Delta A, \Delta B)$ (this corresponds to a row), you compute the amount of columns (output differences) that have a nonzero DDT entry on that row.
For S-boxes that are not square, this doesn't really tell us a lot about the strength with respect to differential cryptanalysis. For square S-boxes, it may be some kind of average indicator (which is probably not very useful).

It does explain why you get 255 though. The amount of columns in the DDT equals $2^8 = 256$. The output difference $\Delta Y=0$ only occurs when $\Delta X = 0$. I assume you didn't count those (the result would be 1). This means that there are at most $256 - 1 = 255$ nonzero entries in a row.
For common $8 \times 8$ S-boxes that would indeed be theoretically optimal (unfortunately that's not possible, even in theory).
But in your case, given that there are $2^{16} = 65536$ (256 times as many) input values, you can indeed get 255 nonzero entries.

(Sorry if the above was not entirely correct, I may have misunderstood the way you compute the "score".)

I computed the DDT for this structure, scaled to an $8 \times 4$ system. With $S$ a very good $4 \times 4$ S-box, the result isn't a very good S-box. Of course it's dangerous to extrapolate to a larger size, but I see no reason why this structure would be particularly good.


In this paper it is shown that the security model under which HMQV was designed (CK-HMQV) and the eCK model are incomparable based on their security prerequisites, adversary model, and application domain. Essentially, there are known protocols which are secure in the eCK model but insecure in the CK-HMQV and other protocols which are secure in the CK-HMQV but insecure in the eCK model.

Specifically, for the HMQV model the author states:

  The HMQV protocol is insecure in eCK because the adversary can trivially reveal the session key in the two-initiators scenario, as in the proof of Theorem 3. The insecurity is based on a mismatch between the equivalence type of matching sessions and the equivalence type of derived keys.

The definitions of equivalence for session and keys can be found for Definition 3 and 4. The equivalences $\approx_A$, $\approx_B$, $\approx_C$ and $\approx_D$ for sessions basically define conditions that need to be satisfied for sessions to be equivalent and the key
equivalence means that sessions which are equivalent with respect to $\approx$ yield the same derived keys.

Theorem 3 states that: Role-symmetric protocols with key type $\approx_A$ or $\approx_B$ are insecure in eCK.

Where a protocol is said to be role-symmetric, when the messages of each role (sender, receiver) are identical up to their order (which holds for the HMQV protocol).

Now, HMQV is role-symmetric and the key equivalence type is $\approx_A$ and the matching sessions equivalence type used in the proof is $\approx_A$ (see Table 2). Unfortunately,
this means that HMQV cannot be secure in the eCK security model.

Consequently, the HMQV protocol as it is can not shown to be secure in the eCK model, although it may intuitively seem to be the case (but security models for AKE are quite complicated and
there can be very tricky issues which are not that obvious).

Observe that as stated by the author in Section 2.5 that eCK-matching is equal to CKHMQV-matching $\wedge$ $s_{role}\neq s'_{role}$.

This basically says that for matching sessions $s$ and $s'$ which are equivalent, i.e., lead to the same derived key, it must not be the case that they can be obtained when conducted
in the same role (sender or receiver) in the security game. Thats what is stated in the cited part above. This indicates that one way to modify HMQV to provide eCK security is to break the role symmetry and/or include session identifiers into the messages (but I am no expert in AKE and this my intuition :)


Vulnerabilities of encrypting data with known regularities

Typically the cost of brute force so greatly out weighs the cost of decrypting a single block, that the fact that an adversary can check for proper decryption after decrypting a single block is not a serious concern. Otherwise protocols like SSL would not be secure.

That said, as you point out, this relates to the key space. If the key space is too small, then decrypting the first block with every possible key would be feasible for an adversary. If you could make it necessary to decrypt every block in order to get the plaintext, that would slow down an adversary. But, with the speeds we see in encryption algorithms, you'd have to encrypt terrabytes for this to matter. For example, the throughput of AES running on a GPU was shown to be around 35,000 Mbps. That number will only continue to rise. The point is to use a cipher that supports a large enough key space and choose keys randomly from the entire space.

If you still feel this is a problem though, why not do the following $E^{ofb}_{k_1}(E^{cbc}_{k_2}(P)||k_2)$ where $||$ is concatenation and $P=p_1\cdots p_n$ (i.e., a number of blocks of plaintext). The use of OFB on the outside ensures that the entire ciphertext must be decrypted to get the last block ($k_2$), which is then used to get $P$.


Can I encrypt data with multiple keys and decrypt with one?

Here is a candidate system, based on an ordinary message cipher $\mathcal E_\kappa(p)$ and $\mathcal D_\kappa(c)$ so that $\mathcal D_\kappa(\mathcal E_\kappa(p)) = p$ and $\mathcal E_\kappa(p)$ is indistinguishable from uniform random noise to anyone who doesn't know $\kappa$.

Let $k_i$ be the $i^\mathit{th}$ encryption key, let ${E^i}_{k_i}(x)$ be the $i^\mathit{th}$ encryption function, let $k$ be the decryption key, and let $D_k(x)$ be the decryption function.  We want to define $E^i$ and $D$ so that $$D_k({E^{n-1}}_{k_{n-1}}(\cdots({E^1}_{k_1}({E^0}_{k_0}(x)))\cdots) = x,$$ but otherwise we want all the intermediate ciphertexts, ${E^i}_{k_i}(\cdots({E^0}_{k_0}(x))\cdots)$, to be indistinguishable from uniform random noise to an adversary who does not know $k$ or the $k_i$.

To this end, define

\begin{align*}
  {E^0}_{k_0}(x) &= \mathcal E_{k_0}(x), \\
  {E^i}_{k_i}(x) &= x, &&\text{for $i > 0$.}
\end{align*}

Decryption is easy: the decryption key is simply $k_0$, and $D_k(x) = \mathcal D_k(x)$.

If this doesn't satisfy your needs, you will need to be more specific about what your needs are so that they meaningfully exclude this system.  ‘Meaningfully exclude’ implies that you have to give some reason related to your application why this won't work, rather than just say you don't like it and the $E^i$ functions have to actually do something.

In particular, it will be helpful for you to identify who changes the key and why.  Are you the sender and recipient, and are you changing your password because it got compromised and surgically removing all traces of the previous key derived from it and ciphertexts encrypted with it from all storage systems everywhere?  Are there multiple parties involved, like members of an organization who have split administrative functions to avoid unilateral power to doctor records?  What are you or they all trying to accomplish?  What is the adversary you hypothesize able to do to manipulate the resources they are trying to accomplish it with?  What do you want to make sure the adversary can't do?


SCP03 - Does it always to depend on pre-provisioned static keys?

A few words on SCP03

As you said, SCP03 is based on the shared knowledge of some symmetric keys (refereed as static keys). This can be seen as a weakness more than a vulnerability since deriving multiple keys from common materials does not break the security guarantees offered by the protocol.

For each sessions, new keys are derived based on:

The shared static keys,
Some constants defining the length and usage of the key,
The session random challenges, one challenge generated by each peers. Each of the challenge is 8 or 16 bytes long (depending on the mode chosen by the Off-Card Entity), avoiding key collision.

In case of pseudo-random challenge generation (i.e not random), a 3-bytes counter is held on the card and involved in the generation process (only card-side). One counter is bind to a key set (i.e. a static shared keys collection), and the counter is is set to 0 whenever the key set is updated.

At each challenge generation, the counter is incremented and one. Once it take the maximum value, the card will refuse to generate a new challenge, making it impossible to complete a SCP03 session. This means that the session key set can only be used in a limited number of sessions, hence it can only be used to generate a finite number ($2^{24}$) of session key sets.

As a side note, the card send the counter to the Off-Card Entity as part of its response to the INITIALIZE UPDATE APDU, but it is not involved in the Off-Card entity side of the generation.

Asymmetric based SCP

Relying on public key cryptography, with a Diffie-Hellman-like scheme would be a better choice since it would namely:

Make key management more straightforward (no sharing)
Ensure forward secrecy

Due to the constraint of such an asymmetric scheme (PKI, large key storage, heavy computational cost), symmetric cryptography has been favored in a first time (SCP01, SCP02, SCP03). For long, RSA have not been available at all on smart cards.
As for today, the trend is slowly changing: GlobalPlatform has issued SCP10 (see the card specification, Appendix F) and SCP11 (see Amendement F) relying on RSA and ECC respectively. They both allow authentication and key exchange, before continuing with symmetric cryptography to communicate.

Smart card industry is a very slow-paced world when it comes to upgrade since deployed hardware can't be upgraded (usually). To give you an idea, SCP03 took almost 8 years to be implemented and deployed, despite its similarities to the widely deployed SCP02, and you can still find a lot of SCP02 in the wild, even so it is  has been shown to be vulnerable to some attacks.

Some say that SCP10 will be skipped altogether, and the SCP11 will be used instead, but RSA is more widely supported.
That being said, I couldn't manage to find any SCP10 or SCP11 open source implementation.


Can zkSNARK or other zero-knowledge proofs be used to proof message authenticity without revealing private key?

In a "fair trade" paper at Bitcoin workshop Financial Crypto 2016, a snark-proof was introduced to assure that a message (a Sudoku solution) could be properly decrypted.


Strength of Hash obtained by XOR of parts of SHA3

Truncating a hash does reduce the collision resistance. Mixing in an independent string does not.

$$
\text{random thing} \oplus \text{independent thing} \to \text{random thing}\\
\text{random thing} \oplus \text{independent random thing} \to \text{random thing}
$$

Truncating hashes is common and the reduction is relative to the bits lost. The truncated $\text{sha3}_{384[320]}$ should be stronger than $\text{sha2}_{256}$ and is weaker than $\text{sha3}_{384}$.

I recommend that you do not try to mix in the truncated $64$-bits.


In PKCS#1 V2.2, should MGF be based on the same hash function that RSA-OAEP-ENCRYPT uses?

The first hash is only used to hash the label. Most of the time the label will simply be empty, which means that a constant value can be used, identified just by the hash algorithm itself.

Although the hash values may differ and may have any SHA-x value, they are generally set to SHA-1 - which is the default. Note that SHA-1 is considered secure for MGF-1. It's also save to use over an empty string. So generally the use of SHA-1 is no issue and there is little to no reason to use another hash algorithm.

So in general you'll find two kinds of implementations: ones that simply keep to the default at all times (SHA-1 twice) or those that are configurable, such as the one in Oracle's Java (or Bouncy Castle for that matter). The configurable ones also will keep to the default unless specified differently.

Until today all the OAEP implementations that I encountered default to SHA-1 for both, but I guess in this world there could be one that chooses a different hash (if just to avoid SHA-1 altogether).

Et voila, an "unbalanced" OAEP encryption (using Oracle's Java 8):

MGF1ParameterSpec mgfSpec = new MGF1ParameterSpec("SHA-256");
// the "label", currently encoded to zero bytes
PSource pSource = new PSource.PSpecified(new byte[0]);
OAEPParameterSpec oaepSpec = new OAEPParameterSpec("SHA-512", "MGF1", mgfSpec, pSource);

Cipher oaep = Cipher.getInstance("RSA/ECB/OAEPPadding");
oaep.init(Cipher.ENCRYPT_MODE, kp.getPublic(), oaepSpec);
byte[] nothingEncryptedReallyWell = oaep.doFinal();
System.out.println(Hex.toHexString(nothingEncryptedReallyWell));


Brute force encryption keys base on their length

Your calculation gives the correct order of magnitude but is not correct.
Different assembly operations take a different number of clock ticks/cycles.
Also note memory access can be expensive, and it makes a big difference which cache layer if any you hit.
To make matters worse there is a difference between an instructions throughput and latency because several instructions can happen simultaneously.
If you really want to do micro optimizations yourself you can look up instruction cost here: http://www.agner.org/optimize/instruction_tables.pdf

For cryptographic operations we usually already have highly optimized code and we can just look up the cost in cycles of various cryptographic primitives. For instance SHA-3 is very efficient and can be implemented with a throughput of ~8 cycles/byte on modern processor.

Just in general you expect single cryptographic function invocations to take on the order of a few hundred cycles in efficient implementations.

In order to make brute-forcing low entropy passwords difficult we usually use tuneable Key Derivation Functions which can be made arbitrarily slow.


Can Stream Cipher be Used to Encrypt & Decrypt a File (Eg: .txt .docx .exe .zip)?

Yes, for sure.
Commonly block ciphers are used for disk encryption algorithms because disks (or partitions) have a particular size. So there is no place to store an IV or authentication tag. They are also optimized for local changes to occur w.r.t. confidentiality and locality of the change. Finally they have to operate for a specific sector size. A stream cipher would be less useful here.
However, the size files can generally be changed in both length and content pretty easily. This application level encryption has much more freedom, so any cipher can basically be used. You should however remember that stream ciphers often use XOR, which means that you may loose confidentiality if multiple versions of the same file are available to an attacker and the IV wasn't changed. In other words, you'd have to fully re-encrypt the file each time a change needs to be stored.


What is the correct elliptic curve representation?

In general case, each elliptic curve over field $K$ can be defined by the following equation:
$$y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6$$
If the characteristic of field be larger than $3$, then all elliptic curves over it are isomorphic to
$$y^2=x^3+ax+b$$
In the case that characteristic is $3$ or $2$, we have two form of isomorphic curves which are as follows respectively.
$$y^2=x^3+ax+b$$
$$y^2=x^3+ax^2+b$$
$$y^2+cy=x^3+ax+b$$
$$y^2+xy=x^3+ax^2+b$$
Edit: The representation of elliptic curve depends on your goal and the field.  Elliptic curves are not defined only on ordinary curves. As an example, we have Koblitz curves (which are non-supersingular) that are a class of computationally efficient elliptic curves. Several of these curves are recommended for cryptographic use by NIST. Supersingular curves are useful for cryptographic goal, too. In the 1,2,3,4 you can find several details.


Cipher Feedback mode turns the block cipher (AES) into a self-synchronizing stream cipher which feeds back the full ciphertext block as the next IV.

If you encrypt something smaller than a multiple of the block size, it will not use all of the block cipher output to create the ciphertext, just the amount it needs. Therefore there is not a padding requirement either. However it still needs the full output of the block cipher to "feed back" and create more stream output.

In your case, the ciphertext blocks are:

db 11 d7 9c a8 f2 1c 29 07 dc 6d 62 13 7a 5e bf
3a c2 fa 2f a1 0f 73 90 ae bd cf 57 cf 1f 82 a2
24 ac d1 de 29 6a e2 95 9c 0f ec

As you can see, the last one was truncated after 0xEC, since it did not need it. The remaining 5 bytes of the block cipher output stream are the final 5 bytes of your next IV. In reality if you decide to encrypt more data using the same stream, those 5 bytes will be XORed against the plaintext to create ciphertext, which will change them prior to feedback into the block cipher.

CFB, OFB and CTR modes are stream cipher modes, and therefore do not require padding. There is nothing stopping you from forcing padding, but unlike ECB/CBC modes, you don't need it for data that is not a multiple of the block size.


How can I implement ID based encryption using RSA?

Simple answer: you cannot. Identity-based encryption is an advanced cryptographic primitive, you cannot simply take any existing encryption algorithm and make it identity-based with simple modifications. There exists several constructions of IBE, but they all strongly differ from the standard RSA algorithm. You can find more information on the wikipedia page. There are several schemes that could suit you, such as Cocks QRA-based IBE (link on the wikipedia page) if you really want something that works in RSA groups (but note that it is not based on RSA). More classically, you could consider using a pairing-based IBE scheme, such as the famous scheme of Boneh and Franklin. Further details and links to implementations of IBEs can be found here.


Your initial definition is imprecise

A zero-knowledge proof is a method by which one party can prove to
another party that they know a secret value, without sharing any data
about this secret value.

This is not merely a zero-knowledge proof, but it is a zero-knowledge proof of knowledge. A zero-knowledge proof is more general, it can be proving a statement that may or may not relate to a secret.

Is the following assertion correct?
To implement a zero-knowledge proof, data can be exchanged but this
data should not contain any information about the secret value?

No this assertion is too loose. Not only the data must not contain any information about the secret value, but it must not contain any new information, or anything that could not have been generated without knowing the secret.
A digital signature is a piece of data that cannot be generated without knowledge of the secret. It is a proof of knowledge, but it is not zero-knowledge because it is leaking some information.
I can take that signature and use it on its own, to claim the following statement: "someone knows the secret". This was not possible before the exchange.
All of the data exchanged must be trivial to create on its own, the proof is only valid from the point of view of the verifier producing the challenges, in a statistical sense.


DES 1-bit changes to inputs: why when I change two inputs by only one bit I get predictable results?

DES block size is 64 bits, your input is 3 DES blocks, you change 1 bit in the first input block only and encrypt the whole input in ECB mode without padding; the first output block is completely different after the change, the 2nd and 3rd blocks are the same, as it should be.

Here's the ECB mode of operation:


Before continuing to read this answer, read my above hint:

  Try writing down all the equations for the different s and try to solve the system of equations.

If you still can't solve this one, you may read the remainder of the answer.

First observe that $s_1 \equiv k_1 \cdot h(m) + r_1\cdot x \pmod {53}$ and $s_2 \equiv k_2 \cdot h(m') + r_2\cdot x \pmod {53}$ where only $k_1,k_2,x$ are unknown. So 3 variables for 2 equations, which isn't solvable, right?
Here's where the special relation comes into play. Replace $k_2$ by $2k_1+1$ which yields

$s_2\equiv (2k_1 + 1) \cdot h(m') + r_2\cdot x\equiv 2k_1\cdot h(m') + h(m') + r_2\cdot x \pmod {53}$

Now subtract the first equation twice times $h(m')$ from the second equation times $h(m)$ which yields:

$s_2\cdot h(m) - 2\cdot h(m')\cdot s_1 \equiv h(m)\cdot h(m')+r_2 \cdot h(m)\cdot x - 2r_1 \cdot h(m') \cdot x \equiv h(m)\cdot h(m')+ x \cdot (r_2\cdot h(m) - 2r_1\cdot h(m')) \pmod {53}$

Finally multiply by the inverse of $r_2\cdot h(m) - 2r_1\cdot h(m')$ ($=(r_2\cdot h(m) - 2r_1\cdot h(m'))^{-1}\bmod 53$) and subtract $h(m)\cdot h(m')$. This gives us the following equation for retrieving $x$:

$x = (s_2\cdot h(m) - 2\cdot h(m')\cdot s_1)\cdot (r_2\cdot h(m) - 2r_1\cdot h(m'))^{-1} - h(m)\cdot h(m') \bmod 53$


Can one build a one-way function from AES?

As Mike asked, it's not clear if you're asking about onewayness, or collision resistance (as you call the function a 'cryptographic compression function').

Assuming you're asking about onewayness, well, given a single 128 bit value $h(M)$, we obviously cannot uniquely deduce the 1408 bit value $M$.  However (hint), let us assume that we can ask for the value $h(M \oplus \Delta)$, for 1408 bit values $\Delta$ that we pick; how can we use that to recover $M$?  How can we extend this observation to cases where the length of $M$ is a multiple of 1408 bits?

Assuming you're asking about collision resistance, well, how can we pick a value $M$ so that $h(M)$ is a predetermined value?  Hint: look at how the AES uses the last round subkeys.


Proof of correct construction of a private key in distributed cryptography

Here's what can happen if you don't do this verification:

Suppose Alice, Bob and company generate their public key shares honestly, $h_2, h_3, ..., h_n$

Now, Snidely Whiplash (who is also a trustee) is the last to contribute his share, he selects a private key $x_{evil}$ and computes $h_{evil} = g^{x_{evil}}$.  However, instead of sharing $h_{evil}$ as his share, he computes $h_1 = h_{evil} \cdot ( h_2 \cdot h_3 \cdot ... \cdot h_n)^{-1}$, and provides $h_1$ as his share.

Then, when we compute the public key, we get $h = h_{evil} \cdot ( h_2 \cdot h_3 \cdot ... \cdot h_n)^{-1} \cdot h_2 \cdot h_3 \cdot ... \cdot h_n = h_{evil}$

Hence, Snidely is able to decrypt any message encrypted with this public key, without the help from anyone else.

Asking Snidely (and everyone else) to prove that they know the discrete log of their share prevents this, because Snidely does not know the value of $log_g h_1$


A hash function for sets that from a hash of a set and a subset of it doesn't reveal the hash of the remaining elements in the set

Here is an idea which mostly addresses what you appear to want; I'm not happy with it, however I thought I'd share it just in case.

Our 'hashes' are vectors of $n$ elements, each element being either a number between 0 and $p-1$, or the special symbol $\bot$.

The hash of a singleton element $s$ (that is, a set that consists of a single element) is computed by selecting the $n$ elements to be numbers deterministically (e.g. using the bits from SHAKE(s)), and then selecting $b$ of the $n$ indicies (again, deterministically), and setting each of those $b$ indicies to $\bot$.

And, to combine two hashes (using Ilmari's notation, to compute $c = a \otimes b$), you perform the following operation element-wise to the two hashes):

$c_i = \bot$ if $a_i = \bot$ or $b_i = \bot$

Otherwise, $c_i = a_i + b_i \bmod p$

It should be obvious that the above operator is both associative and commutative.

And, assuming $p, n, b$ are properly set, then given $a \otimes b$ and $a$, it should be highly probable that $b$ cannot be recovered (as there is likely be to some element $i$ in $a$ for which you have $a_i = \bot$ and $b_i \ne \bot$; in that case, you have no information on $b_i$, and so any of the $n$ possible values are equiprobable.

Of course, the hashes are quite large, and this noninvertability is only probable (and even that is true only if the sets $a, b$ are not too large).


Explanation of trace function $\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$

All elements of $\text{GF}(q)$ are roots of $x^q-x$. In fact, this is a litmus test for determining membership in $\text{GF}(q)$: when working in an extension field of $\text{GF}(q)$, say $\text{GF}(q^m)$, we can determine whether an $\alpha$ is a member of $\text{GF}(q)$ by computing $\alpha^q$ and checking whether the result equals $\alpha$ or not.

So, in $\text{GF}(2^n)$, $\alpha^{2^n} - \alpha = 0$, and if we remember that addition and subtraction are the same operation in fields of characteristic $2$ and that this operation is often denoted by $\oplus$, we have that $x^{2^n}\oplus x = 0$.

The trace function from $\text{GF}(q^k)$ to $\text{GF}(q)$ is defined as
$$\operatorname{Tr}(x) = x + x^q + x^{q^2} + \cdots + x^{q^{k-1}}.$$
Verify that for all $x \in \text{GF}(q^k)$, $\operatorname{Tr}(x)$ belongs to $\text{GF}(q)$.  (Hint: apply the litmus test). So for the special case when $k=2$, the trace function from  $\text{GF}(q^2)$ to $\text{GF}(q)$ is just $\operatorname{Tr}(x) = x + x^q$. I will leave it to the OP see what happens when $q$ equals $2^m$ and whether the statements of the S-Box book are true or not.


CP-ABE (Bethencourt): How KeyGen computes $D=g^{(\alpha+r)/\beta}$?

Does he calculate $1/\beta$ and computes $D$ as below?

  $\qquad D = {(g^\alpha \cdot g^r)}^{1/\beta}$

Yes, that is what he does; as you know, ${(g^\alpha \cdot g^r)}^{1/\beta} = {(g^{\alpha+r})}^{1/\beta} = g^{(\alpha+r)/\beta}$.

He computes $1/\beta$ modulo $p$ (the order of $g$); this can be done by either the extended Euclidean method, or (because $p$ is prime) by using $1/\beta = \beta ^ {p-2}$


If you have $c_2$ and $m_2$ you can reconstruct the used key by

$$k' = m_2 \oplus c_2$$

Now I have the key to decrypt $c_1$.

Also know that using multiple keys for OTP does not increase the security as the resulting key is

$$k'' = k_2 \oplus k_3$$


Counter Mode with a sequence of zeros bits plaintext, is it secure?

This all depends on the IVs. If they are independently generated, the IVs will not only be different (so $IV_1 \neq IV_2$), but also their sequences will not overlap with overwhelming probability. In that case,  then everything should be fine, so $C_2 = E(K,(nonce,IV_2))$, and $C_1 = M_1 \oplus E(K,(nonce,IV_1))$.

However, if they are reused (so $IV_1 = IV_2$), then $C_2 = E(K,(nonce,IV_2)) = E(K,(nonce,IV_1))$, so $C_1 = M_1 \oplus E(K,(nonce,IV_1)) = M_1 \oplus C_2$, and therefore $M_1 = C_1 \oplus C_2$.


Yes it could be exploited to have a small performance advantage.
In pseudocode, the montgomery ladder is defined as:
 x2,z2,x3,z3 = 1,0,x1,1
 for i in reversed(range(255)):
     bit = 1 & (n >> i)
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
     x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
     x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
  return x2*z2^(p-2)

There is a line which uses $x1$ in the multiplication $x1*(x2*z3-z2*x3)^2$.
$x1$ is the x-coordinate of the input. It is possible to write an optimized implementation of that multiplication by hardcoding that value to 9 which will be faster than the generic multiplication by $x1$, where $x1$ could be any element of the field.
However I never seen an optimizations like that, mainly because the generic code is usable for all inputs and the speed-up could be around 5%.
You could try to put an conditional decision for that multiplication to have the best of both worlds (if the input is "9" then call the optimized multiplication otherwise the generic one) but putting branches in a constant-time code for a minimum speedup is not probably worth it. (even though I don't see security issue in doing that).
There are also better way to do optimized implementations if you know the input point in advance and don't have preconditions on the value of the x-coordinate. This achieves up to 44% speed up.


Using first, say, 50 letters from a public key as user identifier?

Should I be worried about collisions?

If these are RSA keys, yes, at least, if people find it in their interest to collide with someone else.
It is entire practical to generate an RSA key where to top 400 bits of the modulus are some specified value.  Since you use those 400 bits as your identifier, then that means the user can pick any identifier they want, for example, the same identifier as another user.
Whether that is a concern depends on whether users would actually gain an advantage.
As for how you would generate a (say 2048 bit) RSA key with the top 400 bits being the value $X$, here's what you do:

Select your 1024 bit prime $p$ as usual

Select a prime $q$ from the range $2^{2048-400}X / p < q < 2^{2048-400}(X+1) / p$; there will be plenty of primes in a range that large.

It's easy to see that $pq$ would be a valid RSA modulus with the top 400 bits being the value $X$.


How difficult is it to crack sha256(sha256(pin)) with a 6 digit pin and no salt?

Yes, it is possible to do this. You can just try each and every PIN, decrypt and then verify the private key; i.e. try a brute force approach. If you don't know the format, the toughest thing will be to think of a way to verify that the result is indeed the private key.

With 6 digits there is a maximum of $10^6$, i.e. a million times SHA-256, SHA-256 and then AES decrypt to try. You can just test part of the encrypted private key but with a million options I would not even bother and simply decrypt the key.

You should be able to pipe the result of CBC decryption to the Posix file utility, if it results in anything but unknown data you probably have a private key to test. Beware that the ciphertext may be prefixed with an IV, although if the salt is missing I would be surprised if it was present.


Why is D_K only required to be infeasible to derive from E_K for almost every key K?

As pointed out in the comments, this allows for a small and negligible number of weak keys which can be avoided.

Let us not forget that this pioneering paper was published before any examples of public key cryptosystems were known in the open literature. The authors took the astute position that if good cryptosystems were discovered, a few weak keys should not rule such algorithms out of contention for publication, analysis, and possible improvement.

Furthermore, from the theoretical point of view, one can sometimes prove strength of cryptosystems, for almost all keys, or for almost all choices of some design parameter, especially for randomized cryptosystems.


Understanding how to proof an encryption scheme is perfectly secret

Where is the problem? Your reasoning seems correct, but you obviously are uncomfortable with probability (at least).

You used the definition of the encryption scheme in (1) and then the standard expression of a probability with respect to the set of messages forming a partition in (2), which is valid since it includes all the messages with nonzero probability and their probabilities must sum to 1.

You then applied Bayes theorem. Standard stuff, really. Maybe you need a refresher in probability.


This is exactly the scenario that the Timestamp Protocol has been created for.

You need to provide your students with access to a trusted timestamping authority (TSA). This could be you yourself or someone else (like a CA offering that service). The TSA signes the hash of the document (the test with all answers) alongside the current date and if your student passes that timestamp along to you, you have the guarantee, that the answers were not created later than the signed timestamp says.

Pleas note that while this solution does not require your students to be able to connect to your servers, it does require a short online communication to the TSA server. This requirements holds true for any other alternatives that I am aware of (like tweeting the test's hash or storing the hash in a public blockchain), I do not believe that a completely offline solution exists for your problem.


What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

When decrypting in lattice-based cryptosystems, one computes a value $v \in \mathbb{Z}_q$ that is guaranteed to be congruent to a "small" integer $e \in \mathbb{Z}$, where $e$ encodes the message (e.g., as the parity of $e$ modulo 2).  By using the integer representatives between $-q/2$ and $q/2$, one can recover the small integer $e$ (and thereby recover the message) simply by "lifting" $v$ to its integer representative.

If we instead used the representatives $0$ through $q-1$, then the representative of $v$ would often be a little smaller than $q$ (specifically, when $e$ is negative), and would not have the proper parity.

Geometrically, using the correct representatives corresponds to "decoding" the lattice $q\mathbb{Z}$ under small error: given the coset $(v + q\mathbb{Z}) \in \mathbb{Z}_q$, we find the smallest element in the coset, which is $e$.

Many papers conflate $\mathbb{Z}_q$ with its set of representatives, but this can cause confusion about what operations are legal and meaningful. Values that are known to be "small" should be seen as elements of $\mathbb{Z}$, which are then reduced mod $q$ when combined with values from $\mathbb{Z}_q$. When we later want to recover a small value from its coset modulo $q$, we lift/decode to $\mathbb{Z}$ using the proper representatives.


Has the Linear Congruent Generator ever been used in any of the early crypto algorithms?

It is indeed the case that the linear congruential generator was used—or at the very least suggested—for cryptographic purposes early on. Below are three examples, but it is likely that there are many more.

In 1982 Vahle and Tolendino broke an encryption scheme based on a linear congruential generator. However, no details about where this encryption was being used were given.

In 1965, Maclaren and Marsaglia proposed a generator that combined two congruential generators, which in their specific instantiation were
$$
\begin{align}
x_{i+1} &= (2^{17} + 3)x_i \bmod 2^{35}, \text{and}\\
y_{i+1} &= (2^7 + 1)y_i + 1 \bmod 2^{35},
\end{align}
$$
after which the output $z_i$ is computed as $y_{x_{i \bmod 128}}$. This was, however, not meant as a cryptosystem by its authors. Nevertheless, in 1984 Retter did find this system used to encrypt real-world data at Data General, and furthermore broke it by reducing its strength to just one of the generators. He also found that another system, the CSI-10 cryptographic unit, using the same kind of encryption scheme.

Perhaps more famously, in 1980 Knuth devised a method to break truncated linear congruential generators. The paper starts by saying

  Therefore, it has been suggested that the leading bits of such a
  sequence might be useful for enciphering data.

There is no associated citation, but it is not unreasonable to deduce that this was a popular idea during this time period. Other contemporary attacks on LCGs include Reeds and Plumstead.

Another class of random number generators very popular during this period were ones based on LFSRs, which are more hardware friendly. Many LFSR-based schemes appeared in the 60s and 70s, the vast majority of which ended up broken. Ritter's survey, starting with the Twigg generator, is a good place to start.