is it possible to generate IV for a given block with AES GCM

Note: This answer is entirely theoretical and may not be implemented in your favorite software library.

  Is there any way I can decrypt the stream if I start reading it from
  some random byte?

Yes and no.
Yes, you can jump to some random byte in a AES-GCM cipher text and decrypt it, by just applying the underlying CTR decryption, i.e. by incrementing the counter appropriately.

No, you really shouldn't do that, because this way you can't verify the tag, because this requires parsing and processing of the entire cipher text (including the IV). And if you can't verify the tag, the cipher text can be altered trivially without you even knowing it.

Yes and no, you can just verify the tag, as it's a function of the ciphertext and that quite fast and afterwards, if the tag is valid, decrypt only the bytes that interest you. The pure verification is as couple of times faster than the full verification and decryption and hence you indeed would save some computational ressources.


Advantages to knowing $p$ and $q$ in Blum Blum Shub?

Short answer: knowing $p$ and $q$ allows building a more efficient generator, including one with random access. Further, for an adversary, at least if $p-1$ and $q-1$ can be factored, that allows finding a period, and at least if the generator allows random access past that, building a distinguisher.

With secret seed $x_0$, the Blum Blum Shub generator computes output $f(x_i)$ for $i\ge1$, where $x_i$ is defined by the recurrence $x_{i+1}={x_i}^2\bmod M$, and $f()$ is some function [such as extraction of the low bit, or eXclusive-OR or all bits], and $M=p\cdot q$ with $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod4$.

That implies $x_i={x_0}^{(2^i)}\bmod M$, but direct evaluation of that expression has cost $\mathcal O(i)$, and is equivalent to directly applying the recurrence.

With knowledge of the factorization $M=p\cdot q$, we can compute the output for large $i$ directly and efficiently [in time $\mathcal O(\log(i))$], by computing ${x_0}^{2^i\bmod(p-1)}\bmod p$ and ${x_0}^{2^i\bmod(q-1)}\bmod q$, then using the Chineese Remainder Theorem to combine them into $x_i$. The CRT may also slightly speed up a generator proceeding using the recurrence, as pointed my mikeaso and made quantitative by poncho in comments (computation time can be reduced by up to $1/4$ with textbook multiplication algorithms).

An adversary (with no access to the full internal state of the generator) knowing the factorization of $M=p\cdot q$, and also able to factor $p-1$ and $q-1$, can compute $u=\lambda(p-1)$ and $v=\lambda(q-1)$ where $\lambda()$ is Carmichael's function [or $u=\varphi(p-1)$ and $v=\varphi(q-1)$ where $\varphi()$ is Euler's totient function], then $\operatorname{lcm}(u,v)$ which is a multiple of the period of the BBS generator, because for all $x$, $x^{(2^u)}\equiv x\pmod p$ and $x^{(2^v)}\equiv x\pmod q$. From that it is trivial to build a distinguisher between

a BBS black box accepting $i>0$ and returning the output of index $i$ in the BBS sequence for some fixed unknown random seed $x$;
a random oracle black box accepting $i>0$ and returning random output if that $i$ was not previously submitted, else returning its previous output for this $i$.

The distinguisher works by submitting $i=1$ and $i=\operatorname{lcm}(u,v)+1$, bets on BBS if the answers are equal, and on random oracle otherwise.

When

the BBS black box only outputs sequentially,
or proceeds sequentially by squaring modulo $M$,
or otherwise bounds $i$ to remain small,
or was built without knowledge of the factorization of $M$,
or $p-1$ or $q-1$ are hard to factor,

then I fail to exhibit a distinguisher (but would no be all that surprised if one could be devised).


Does complicating a flawed algorithm make it secure?

There's a problem with boundaries here; how much "complication" is allowed? I could argue that SHA-2 is a complication of SHA-1 because they both use a Merkle-Damgård construction and have other similar elements. Then again, they are significantly different internally.

On the other hand the addition of a single bitwise rotation did make SHA-1 significantly more secure. Of course it has now proven to be not secure enough but that was after decades of good service.

  SHA-1 differs from SHA-0 only by a single bitwise rotation in the message schedule of its compression function; this was done, according to the NSA, to correct a flaw in the original algorithm which reduced its cryptographic security.

This also shows another problem with the question: what is secure enough? Obviously SHA-1 is not secure enough, but it is at least protected against some attacks on SHA-0. SHA-2 is much more secure than SHA-1, but it is still vulnerable against length extension attacks which SHA-3 is not.

In general you cannot just apply some random function to the inner workings or output of an insecure function. Cryptographic functions need proof (or at least a well reasoned strong indication if a prove cannot be constructed) to be secure. For instance, if the bitwise rotation was only performed on the output of SHA-0 then the result would not have been secure.

So unfortunately the answer is: it depends on the change being made and - in a practical sense -  the reasoning behind it.

With regard to your scheme: it only changes the end result of the hash, using operations that - according to your own text - should be reversible. Furthermore, you require the algorithm itself to be secure.

There are two major problems with this:

you lack a clear indication why this would make the MD5 hash more secure, trying a lot of mathematical constants and operators would likely break the scheme;
keeping the algorithm itself safe breaks the Kerckhoffs principle, you should not rely on keeping the algorithm safe.

Kerckhoffs principle and the reasons for making an algorithm public is clearly explained in this answer on Crypto.


Sending information covertly when using legitimate systems is a well-studied field. As another question mentions, key words are covert channel and subliminal channel.

Designing systems with no covert channels is difficult, but not impossible. The main difficulty is to ensure that if any randomness is sampled incorrectly, the legitimate recipient must detect and reject.

For your case, deterministic signatures (as you had almost arrived at yourself) would be sufficient. The main interesting system is RSA-FDH (full-domain hash) which is trivially deterministic. There are also systems that have deterministic signature generation (if you sign the same message twice, you get the same signature), but where someone with the signing key could generate different signatures without the verification algorithm noticing.

For more complicated systems, this becomes much more difficult. For some symmetric cryptosystems, you can use counters instead of random nonces.


Implementing the Mceliece Encryption - making the Generator Matrix

I'm going to assume you are using binary Goppa codes. That means, that you take a support $\mathbf{L} \in \mathbb{F}_{2^m}$, a Goppa polynomial $\Gamma$ of degree t with coefficients in $\mathbb{F}_{2^m}$ and build all codewords of a GRS code, and then intersect these with $\mathbb{F}_2^n$, resulting in a code that is actually a subset of $\mathbb{F}_2^n$ (and not of $\mathbb{F}_{2^m}^n$). This is the classical definition used by McEliece in his original proposition.

As you might have already read, the binary Goppa code has a check matrix (there is an error in the Wikipedia article, this one is correct):
$$H_{grs} = \begin{pmatrix} 1 & \dots & 1 \\
L_0 & \dots & L_{n-1}\\
L_0^2 & \dots & L_{n-1}^2\\
\vdots & & \vdots\\
L_0^{t-1} & \dots & L_{n-1}^{t-1}\end{pmatrix}
\begin{pmatrix}
\frac{1}{\Gamma(L_0)} & & \\
& \ddots & \\
& & \frac{1}{\Gamma(L_{n-1})}
\end{pmatrix}$$

Now, are you are well aware, this is a $t \times n$ matrix in $\mathbb{F}_{2^m}$ and will thus give you codewords in $\mathbb{F}_{2^m}^n$. But we are interesed in code words only in $\mathbb{F}_{2}^n$. One can get a check matrix that gives only codewords in $\mathbb{F}_2$ by expanding every entry in the matrix in a basis of $\mathbb{F}_{2^m}$.

This means, if your entry of the matrix is represented as as vector $0101$ in $\mathbb{F}_2^4$ (for $m=4$), you would expand this entry as four entries and write them in four rows: 0, 1, 0, 1.

Example:
Let one of your rows of your check matrix $H_{grs}$ be
$$\begin{pmatrix}0101& 1010 &0001& 1000\end{pmatrix}$$
then you would write this as
$$\begin{pmatrix}
0 & 1 & 0 & 1\\
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
1 & 0 & 1 & 0\end{pmatrix}$$
You do this for all your rows and you will end up with a check matrix $H$ of size $mt \times n$, since you are expanding every row by $m$ rows. From now on, you only work over $\mathbb{F}_2$; using this check matrix, you'll get code words in $\mathbb{F}_2^n$. Note: You will have to do Gauss elimination at this point to get rid of rows that give the same equation. This will reduce your row number and give you a reduced check matrix of size $(n-k) \times n$, where k is the dimension of your binary code.

Now, to get a generator matrix $G$ for that code, you look for a full-rank matrix with $H^\top G=0$. There are many ways to achieve this, and you should find enough material on this. For example: http://en.wikipedia.org/wiki/Parity-check_matrix. Keep in mind, that if $H$ is a check matrix for $G$, then $G$ is a check matrix for $H$. So you build $G$ by pretending $H$ is a generator and you want to find a check matrix for that code.

I hope this is what you asked for.


How to find a triple of keys that maps plaintext to given cipherext using EDE

Indeed, that's a case for Meet-in-the-Middle.

Notice that $E_{K_3}(D_{K_2}(E_{K_1}(P)))=C$ if and only if $D_{K_2}(E_{K_1}(P))=D_{K_3}(C)$. Therefore, finding $(K_1,K_2)$ and $K_3$ making the two sides equal solves the problem. Both sides take random-like values when $(K_1,K_2)$ and $K_3$ vary. Therefore trying $2^{b/2}$ values (e.g. incremental) of $(K_1,K_2)$ and $K_3$ leads to collision with fair probability (where $b$ is the block size in bits).

For an actual implementation with $b=64$ (as in DES), I would

fix an arbitrary $K_1$ and compute $Q=E_{K_1}(P)$
tabulate values of $D_{K_2}(Q)$ for incremental values of $K_2$ in a data structure allowing fast access given the result and recovery of $K_2$. Well over $2^{31}$ values of $D_{K_2}(Q)$ fit in my computer's available memory of 30 GB.
compute $D_{K_3}(C)$ for incremental $K_3$ until getting a match.

Success is expected with about $3\cdot 2^{32}$ DES operations, which is very feasible.

Note: in the above, incremental must deal with the fact that the low-order bits of DES key bytes is ignored, so as to lower DES's resistance against brute force attack.

That has cost $\mathcal O(2^{b/2})$ effort and memory. The memory, but not the effort, can be reduced a lot, and the attack made parallel (reducing time), using techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999. That would be a must for $b=128$ of AES.


how to get top 10 numbers after using Pallier cryptosystem

So how would it be possible to get the top 10 biggest Integers out of those 1000 Integers  when the numbers are encrypted?

That's easy; decrypt them with the private key, and then pick out the top 10 plaintexts...

If you don't have the private key (and can't interact with someone who does have the private key), then we hope it's impossible.  I say 'hope', because if it were possible, then you could deduce the contents of a Paillier ciphertext with just the public key (and hence, Paillier would be insecure).

Suppose we did have a way to find the top 10 out of a group of 1000; here's how we can test a ciphertext $C$ to see if its plaintext $P$ is $> k$ or $< k$ (for an arbitrary integer $k$); we would encrypt the value $k$ 999 times, and give those 999 ciphertexts, plus the ciphertext $C$ we're testing, to our method to find the top 10 - if the plaintext we're trying to deduce is $P > k$, then $C$ will be one of the 10; if $P < k$, it will not be.

Doing that technique, we can do binary search to reduce the possibilities for $P$ to a range of two values $k, k+1$; we can then homomorphically add $C$ to itself, and then perform the above test one last time to see if $2P$ is greater than or less than $2k+1$ - this gives us the final answer.

We hope that someone cannot do this, and so we hope that the problem you're asking to solve is infeasible.


Simple way to extend AES to 256-bit block size

It turns out that this "mode" is distinguishable with two chosen messages; one in decrypt mode, and one in encrypt mode.

The first query is in decrypt mode, it is of the ciphertext $(C, 0)$ (where $C$ can be any nonzero value), and with an arbitrary IV.

Because of how decrypt works, $P_1$ of the resulting plaintext is $D_k(0) \oplus C$; this gives us the 128 bit value $Z = P_1 \oplus C$ with $E_k(Z) = 0$.

Our second query is in encrypt mode, it is of the plaintext $(Z, Z)$ with $IV=Z$.  If you go through how encryption works, we see that $C_0 = 0$, $C_1=0$, $C_2=0$, $C_3=0$, and so the resulting ciphertext is $(0,0)$.


Can an RSA private key have several public keys?

@pg1989 has not only the right answer but the only answer if you assume the goal is to have multiple RSA encryption exponents that correspond to the same decryption exponent.

\begin{align}
e_1 \cdot d & \equiv 1 \pmod{\phi(N)}\\
e_2 \cdot d & \equiv 1 \pmod{\phi(N)}\\
(e_1 - e_2) \cdot d & \equiv 0 \pmod{\phi(N)}
\end{align}

But since $d$ is relatively prime to $\phi(N)$, by Euclid's lemma $\phi(N)$ must divide $e_1 - e_2$ :

$$e_1 \equiv e_2 \pmod{\phi(N)}$$

In other words, any two public RSA exponents that share a private exponent must differ by some multiple of $\phi(N)$.

I highly suspect this is what your professor was thinking. Although, as @Thomas points out if the multiple is small and someone gets hold of both public keys, they can factor $N$. Now, maybe if you use a big multiple...

[Update]

As @fgrieu notes in a comment, I have conflated $\phi(N) = (p-1)(q-1)$ with $\operatorname{LCM}(p-1, q-1)$. Replace the former with the latter in the above derivation for the right answer.


How can I determine the GPG/PGP key ID from the RSA modulus?

It depends on the version of the GPG format. In V3 the Key ID it is indeed the bottom 64 bits of the modulus, but in V4 it's the bottom 64 bits of the key fingerprint, which in turn is the  "SHA-1 hash of the octet 0x99, followed by the two-octet packet length, followed by the entire Public-Key packet starting with the version field" according to the RFC.


Will a SHAKE128 stream cipher be vulnerable to related key attacks?

There is no way to know for sure, but it seems unlikely to me.

SHAKE128 is an extendable output function, basically a hash function with variable output. It must be secure with completely attacker controlled input. If you use it to build a stream cipher (perhaps using KMAC (draft pdf), which is supposed to be PRF), it seems unlikely that related keys would be a concern without the hash function use case also being broken.

However, the security goals of hash functions and stream ciphers are different and SHA-3 itself could be broken, so only time will tell.

  My guess is no because seed is already "absorbed" before the key stream is "squeezed" out.

This particular argument does not really make sense, since RC4 also absorbs the key first and only then produces output. Yet it is vulnerable to related key attacks.


Shamir Secret Sharing data limitations per share?

In principle, the secret is a single field element. Thus, this is exactly what you can store. However, there is a notion called "packed secret sharing" that enables you to store more than a single value. However, it cannot always be used, and it depends on the required thresholds. For example, assume that you wish that no less than $t$ parties will be able to learn anything about the secrets, but you can assume that $t+\ell$ parties will be able to come together to reconstruct. Then, in this case, you can share $\ell$ values using a single polynomial of degree $d=t+\ell-1$. In order to do this, you can define $p(-i)=s_i$ for $i=0,\ldots,\ell-1$ for secrets $s_0,\ldots,s_{\ell-1}$, and then use other points for the parties' shares (use $p(i)$ for party $i$'s share). Of course, in this case, you also need the field to be larger than $n+\ell$ where $n$ is the number of parties.


Can I determine if a user has the wrong symmetric encryption key?

I really don't have an answer (other than saying that storing a hash of the password is good as any other way of solving your immediate problem; there are other ways, but they all allow an attacker to run a dictionary attack on the database).

On the other hand, I do have these comments on what you're doing:

If getting decrypted gibberish will really crash your application, well, I suspect that you might want to consider better error handling.  There are reasons other than "the user gave us the wrong password" for getting bad data (the database server might have gotten a hiccup, the encryptor might have used the wrong password when writing the database record, perhaps an attacker might sprinkle random data over your database); I think you might want to have better error reporting than "Memory fault: core dumped"
Your requirement that there be absolutely no ciphertext expansion limits what you can do; it gives problem to most common encryption modes.  In particular:

If we encrypt the same record value twice to two different fields, does those show up as the same encrypted value?  If so, an attacker will be able to realize that they share a common value (even if he doesn't immediately know what that value is).  Common encryption modes handle this by including a randomization value (IV) as a part of the encrypted data; however, you can't explicitly include an IV in the record.
If we write (and encrypt) a record value A, and then later update that record to be a value B, can an attacker who sees both encrypted records deduce the relationship between A and B.  Common encryption modes handle this as using an IV as well; again, that's not available to you.
If we write (and encrypt) a record value A, is an attacker able to modify that record so that when we read it, it decrypts to a value B (where B has some attacker-chosen relationship to A)?  Common encryption modes handle this by either by being an authenticated encryption mode, or by using an explicit MAC -- neither works for you.

Given these potential problems, you probably should think about what are the security requirements, and how you can meet them.


Yes, there are. The following table is taken from this paper of Ducas and van Woerden, although the results are not derived there (in the below, $p$ is an odd prime, and $n, m$ are coprime).
\begin{align*}
\mathbb{Z}[\zeta_{2^k}]&\cong \mathbb{Z}^{2^{k-1}}\\
\mathbb{Z}[\zeta_p] &\cong A_{p-1}^*\\
\mathbb{Z}[\zeta_{p^k}]&\cong \bigoplus_{i = 1}^{p^k-1}\mathbb{Z}[\zeta_p]\cong I_{p^k\times p^k}\otimes \mathbb{Z}[\zeta_p]\\
\mathbb{Z}[\zeta_{nm}]&\cong \mathbb{Z}[\zeta_n]\otimes \mathbb{Z}[\zeta_n]
\end{align*}
Conway and Sloane's book Sphere Packings, Lattices, and Groups is the canonical reference on the topic of lattices. Chapter 8 discusses "algebraic" constructions of lattices. This means two things:

Constructions of lattices as $R$-modules of a certain rank for $R\neq\mathbb{Z}$
Constructions of lattices as ideals within (the ring of integers of) an algebraic number field

Note that these things are slightly different. For example, an ideal lattice has rank at most the degree of the underlying number field (as it is a sublattice of $\mathcal{O}_K$), but there is no such restriction on the first case.
Anyway, chapter 8, section 7.3 gives a general equation for the lattice $\mathbb{Z}[\zeta_m]$, in particular its Gram matrix $A$ has $(j, k)$ entry:
$$A_{j, k} = \frac{\mu(d)\varphi(m)}{\varphi(d)},\quad d = \frac{m}{(m, k-j)}$$
They then summarize constructions of $E_6$ as an ideal of $\mathbb{Z}[\zeta_9]$,
the Leech lattice as an ideal of $\mathbb{Z}[\zeta_{39}]$ (note that $\varphi(39) = 24$).
There are a few other constructions given as well, but those are the "biggest names".
Edit:
One can further realize Craig's Lattices as ideals (again within the ring of integers of a cyclotomic number field).
Craig's Lattices are a family of lattices $A_n^{(m)}$ obtained by starting with $A_n^{(0)} = \mathbb{Z}^{n+1}$, and performing a "repeated differencing" operation.
I will not define the construction here, but notably:

$A_n^{(1)}=  A_n$ is the (primal) $A_n$ root lattice.
According to Conway and Sloane, Craig's lattices are the densest packings known for dimension $148 \leq n \leq 3000$. I do not know how/if this knowledge has changed in the last 20 years.

One can then obtain $A_{p-1}^{(m)}$ as the ideal $(1-\zeta_p)^m$ within the ring of integers of $\mathbb{Z}[\zeta_p]$. The minimal norm (which I believe Conway and Sloane uses to denote the squared norm) is not explicitly known, but can be lower-bounded (in the case that $n = p-1$, and $m < n/2$) by $2m$.
See chapter 8 section 6 of Conway and Sloane, or Proposition 5.4.7 of Martinet's Perfect Lattices in Euclidean Space.


Why is it OK for secretbox to leak the message length?

It is usually assumed that the length of the message is not secret. Even with padding the approximate length is leaked, and necessarily any encryption reveals a maximum length – or at least information content if compression is used – because the ciphertext cannot in general be shorter than the message.

NaCl's secretbox does not use a block cipher, but a stream cipher – XSalsa20 (pdf) – so it requires no padding and the exact message length is revealed.

If you have a situation where the message length should remain secret, you must ensure that yourself, e.g. by padding the message to a fixed maximum length. Doing that automatically would be wasteful and would limit the message size the algorithm could be used with, which is why it is left for the user.


Can you help me understand how RC4-52 is done using pen-and-paper?

You can do RC4 using a 52-entry table, instead of a 256-entry table.  All you do is change the modulo-256 arithmetic in RC4 to use modulo-52 arithmetic.  There are no special changes needed, and no need to describe a special algorithm.  If you want to see a  description of how to perform it manually using a deck of cards, you can find that here:  http://www.mail-archive.com/cryptography@wasabisystems.com/msg00065.html  See also https://groups.google.com/forum/?fromgroups#!topic/sci.crypt/dw3FaK4lf2M

Related: If you've read Neal Stephenson's Cryptonomicon, you may have seen a reference to an encryption algorithm that can also be carried out with a deck of cards.  The cipher is called Solitaire.  It was invented by Bruce Schneier and was apparently inspired by RC4.  However, it has cryptanalytic weaknesses.  (If you haven't read Cryptonomicon, and you like science fiction, check it out: you're in for a treat!)

Keep in mind this is entirely theoretical.  Performing RC4-52 with a deck of cards will be extremely slow and tedious in practice.  And while I don't know of anyone who has seriously studied its security, there are reasons to doubt whether it will be secure against a serious attack.  While it's fun to contemplate, I would not recommend that anyone use this to protect real secrets.


How do RSA and ECDSA differ in signing performance?

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good random number generator may compromise the ECDSA private key). The RSA PSS signature scheme also requires the use of random numbers, negating this performance advantage for RSA for this particular padding scheme.

[EDIT: well, the use of a random salt in RSA / PSS is at least the default option, and many implementations won't allow you to use an empty salt to make the scheme deterministic. RSA / PKCS#1 v1.5 padding for signature generation is fully deterministic and could be used instead; it doesn't come with a security proof like PSS does, but it hasn't been broken either]

RSA is generally much faster for signature verification as verification is performed using the public key. If a small exponents such as F4 (65537 or 10001 in hexadecimals) are used then RSA is generally faster than ECDSA, as only a minimum of modular multiplications is necessary.

The time required for RSA operations with the private key quickly rises for larger security strengths. ECDSA times also rise, but at a much slower rate.

ECC is much much faster than RSA for key generation. Finding large primes for RSA is a tough job even for current CPU's given a high enough key size.

Most RSA libraries have been around for a long time, are used much more often and are therefore more likely to have been optimized. So an RSA implementation may be faster than an equivalent ECDSA implementation (for small key sizes). ECC, in general, is a more complex algorithm to implement - but not necessarily to optimize, as CodesInChaos points out below.

Anyway, real world results will rely heavily on the speed of the implementations used. Note that the security level of such libraries also differs wildly, and selecting a crypto library just based on performance is not a good idea.


Choosing between different Gaussian Sampling algorithms?

KY is indeed the faster than the method you referenced. However, it also uses a lot of memory (it needs to store a little more than the probabilities of each possible output in high precision). Depending on the available memory and the width of the distribution you are trying to sample from,  this can be prohibitively large, especially when implementing it on a constrained device. This is what the paper by Ducas et al. addresses: their method is relatively fast (much faster than rejection sampling, but not as fast as KY) and uses much less memory. In essence, it simply gives you a different time-memory trade-off.


Does information theoretical security definition imply DDH, RSA, QR does not hold?

Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary?

That is correct; a computationally unbounded adversary could trivially solve any of these problems.  For example, to solve the DDH problem ("given, $g, g^x, g^y, g^z$, does $g^{xy} = g^z$?) a computationally unbounded adversary could go through all possible values $x, y, z$ (between $0$ and $p-1$), and check if they match the $g^x, g^y, g^z$ values they were given, and if so, does $g^{xy} = g^z$.  This sort of solution works for all the other problems you mentioned.

Note: there are computationally far easier ways to solve this problem; this is just the generic strategy that works against any computationally bounded problem.


Help understanding lattice-based aggregate signature scheme

"Given parameters $n$ and $PP$, the KGC provides public/secret key pairs $(pk; sk)$ for all single signers."

Yes, the key generation center (KGC) generate the key pairs $(pk; sk)$ and distributes them. It is also clear from figure 3 of the article.

  What are the sizes of public keys, signatures, and aggregated signatures (in bytes)?

The parameters are used in $TrapGen(n,q,m)$, which actually generates for SIS parameters. You can find example secure paremeters from here or similar work.


Since both values are randomly generated, no, there are no scenarios in which you could determine C from h and R or where your ability to brute force C is made easier by having this information as opposed to just having h.


Any ideas to make an Electronic Voter Machine more secure?

We can't make satisfactory Electronic Voting Machines. Their design face conflicting goals that are impossible to reconcile, even in the simplest conceivable use case: a yes/no vote, a single machine.

Count votes (or at least: determine if there was more yes than no) with the result public.
Limit voting to one per registered voter.
Keep individual votes secret, even from organizers or/and if a person casting vote is actively trying to prove how s/he voted (that requirement helps freedom of vote despite attempted bribery/duress), within the limits inherent to what gets published of the result.
Resist denial of service.
Convince reasonable observers with ordinary skills that the above goals are met, even if observers do not trust the organizers and designers of the machine, understandably so [*].

Among the few non-electronic approaches that work is one that evolved over time: paper ballot freely available to all, put in opaque envelope mandatorily in a private booth, with the envelope publicly inserted in a transparent urn (with mechanical interlock preventing unauthorized insertion), check of the voter's identity and that the voting role is unsigned right before that insertion, and signing the voting role right afterwards, with the urn and envelopes publicly opened in the end and counted, under public scrutiny all along.

Alternatives have been tried:

Mechanical counters, with interlocks preventing multiple voting. There have been jams (perhaps intentional). Only people understanding mechanical machinery (similar to watchmaking) can observe and confirm that counting work as intended before and after voting. And it is to fear that various side channels (lifting a cover hidding the value, sound, ...) can compromise vote secrecy. On the positive side, it can be me made slow and noisy to covertly alter the counters.
Electromechanical counters: reportedly more reliable, but side channels are rather worse, altering the counters might be faster and easier, and (because wires and air gaps can be hair-thin) an observer (needing basic understanding of electric circuit) could miss something redirecting counting to the wrong counter. While it would be conceivable and useful to make counters that the voter (only) can see moving when casting vote, without being able to tell the count, I have not heard that it was used.

The more we go towards modern electronics and complex cryptography, the worse the "convince reasonable observers with ordinary skills" goal is met. Finding backdoors in silicon and software is extremely hard, and entirely impossible at the voting location. For most reasonable observers, a finite field is a bounded piece of land.

[*] Voting machines in use in (few and mid-sized) French cities are purchased, stored, serviced and operated (with supervision from the ministry of home affairs) under the authority of the Mayor, yet are used to (re-)elect the Mayor. Their specification and type approval is under the authority of the ministry of home affairs, which head is chosen by the prime minister, which is chosen by the Président de la République, which the machines contribute to (re-)elect. In 2007 that election was won by the former head of the ministry of home affairs that gave delegation for establishing the specifications as law, and was again head of that ministry weeks before his own election and days before a software change was made to the most common type of machines. BTW that software is secret, and it's integrity is publicly demonstrated by a checksum that the software computes and displays. Descartes reportedly turned in his grave.


Why do "nothing up my sleeve numbers" have low entropy?

You're absolutely correct: numbers (or a given binary string) don't have entropy. However, a number can be sampled from a distribution that has entropy. In other words, the entropy is a property of the process used to generate a number, not of the number itself.

So if I just give you the number 4, and assure you that I picked this number uniformly at random from between 1 and 6, you have no way of knowing if I'm telling the truth. Depending on the scenario, maybe I had an ulterior motive for picking 4, rather than choosing a number at random.

The issue comes up in cryptography because when it comes time to choose the constants for an algorithm (such as SHA1, or any of the other examples in the Wikipedia article you linked), there might be mathematical arguments suggesting, "If the constants are chosen at random, then with high probability, no attacker will be able to break it." But cryptographers, being a paranoid lot, are skeptical when someone says, "Let's use this set of constants. I picked them at random, I swear." So as a compromise, they'll use constants like, say, the binary expansion of π. While we no longer have the mathematical benefit of having chosen them at random from some large pool of numbers, we can at least be more confident there was no sabotage.

These nothing-up-my-sleeve constants have low entropy because the process of choosing them didn't involve very many random choices --- compare the number of "reasonable" nothing-up-my-sleeve numbers to the number of, say, 128-bit strings they are used to produce. This is by design. If there were a large number of nothing-up-my-sleeve numbers to choose from, then it would be easier for a malicious algorithm designer to find some that suited his agenda.

A very recent and very alarming case of someone not using nothing-up-my-sleeve numbers to create a backdoor is the Dual EC DRBG standard, which is used to generate random numbers. This algorithm included two constants, P and Q, and would be secure if no one could compute f(P, Q), for a specific function f.
Given randomly chosen P and Q, this would be hard. However, if you get to choose P and Q, then you could choose P, decide what you wanted f(P, Q) to be, and then solve for Q rather easily. Now you have a backdoor.


The utility of elliptic curve cryptography

If you are restricted to Diffie-Helman, RSA, and ElGamal, I believe you cannot do pairing based cryptography which has applications to attributed based encryption and identity based encryption. These applications are not used heavily in practice, but could be in the next decade or two.

For more information on speed benefits of ECC, see this question and answers. Based on my own testing comparing the elliptic curve variant of exponential ElGamal (which is additively homomorphic) with Paillier (also additively homomorphic and similar-ish to RSA), the elliptic curve cipher was 2 orders of magnitude faster for both encryption and decryption (with a few realistic assumptions as decrypting exponential ElGamal can be tricky). Thus I believe encryption was something like 100ms on one device for Paillier vs 1ms on EC-ElGamal. Decryption was similar.


Demystifying homomorphic multiplication in RNS FV variant

Yes, this can be confusing at first. Maybe starting with a more recent paper could help: https://eprint.iacr.org/2018/117

In the paper I cited above they have improved the base conversion and scaling in RNS, but also made the procedures simpler as a side effect.

First, they expend the base of the ciphertext from $Q$ to $Q*P$, then they do the tensoring in $QP$, then they scale it down by $t/Q$ getting the result mod $P$, and then expend again the ciphertext (which is now in base $P$) to $Q*P$ and only keep the $Q$ part.

As for your question, if you have the ciphertext in base $QP$, and you want it  only in base $P$, you can simply throw away the base $Q$ (delete the rows of the polynomial mod each $q_{i}$). Of course this is only valide If the value of the coefficients are within $0,P-1$. But this will always be the case since the auxiliary base $P$ is at least as big as $Q$. After multiplication this is not anymore the case because the coefficients will be of size $Q^2$ (unless $P > Q^2$). However after having them scaled down, they are back within the range of $Q$.


I'm not sure if I really believe that this is of any use at attacking a stream cipher, but I'll answer your question anyways.

What $gf = 0$ means is that, for any input $x$, we have either $f=0$ or $g=0$.

Now, in the case of $g = x_0x_1$, then this $g$ will be 0 unless $x_0 = x_1 = 1$.

In that case, the first term of $f$, namely $x_0x_2(x_1+1)$ will be 0 (as $x_1+1 = 1+1 = 0$).  And, the second term of $f$, namely $x_1x_3(x_0+1)$ will be 0 (as $x_0+1 = 1+1 = 0$).

Hence, whenever $g \ne 0$, we have $f=0$, and so $gf = 0$.

This observation gives a fairly obvious way to create a nontrivial annihilator of any function $f$ (other than $f=1$ for all inputs); namely:

Find a set of inputs that give $f=0$ (technically, this is an NP-hard problem (!), but in practice is fairly easy).
Create a $g$ that is 1 for that specific input, and 0 otherwise.

For example, if $f=0$ for $x_0 = 0, x_1 = 1, x_2 = 0$, then this annihilator would be $g = (x_0 + 1)x_1(x_2 + 1)$


Avoid:

Using secret data in table based lookups on machines that have a cache

The table is just a memoized function; Just compute the function explicitly each iteration instead of looking the answer up in a table

Accessing an array using indices whose values are supposed to be secret
Using functions that take a variable amount of time to compute on secret data

Do:

Use instructions that are generally implemented in a constant amount of time (at the hardware/gate level)

ADD, XOR, AND, shifts, and rotates are almost guaranteed to operate in a constant amount of time

Use functions that facilitate countermeasures more easily

Note that side channels target implementation details, and not the abstract algorithm. An implementer can still make choices that create vulnerabilities.

All that an algorithm designer can do is make the design straightforward to implement in a constant time manner. For example, AES can be implemented without a table lookup, but this tends to lower the overall throughput, potentially significantly.

There are apparently some tools for testing an implementation for weaknesses.


Reusing characters from plaintext in salt

My gut feeling is that it increases security through obscurity [...]

Security through obscurity is the name of an antipattern, for good reason.  Generally, the way we analyze security measures is by trying to give the attacker as much power as we can get away with.

So we just assume that the attacker knows your construction:

$salted_plaintext = $plaintext[1] . $plaintext[7] . $plaintext;

...and then we can observe that since the salt is a function of the password, two users who use the same password will get the same salt and thus the same hashed password, meaning that for each password guess the attacker is able to test every user's password entry.  Same as with unsalted password hashes.

  [...] existing rainbow tables wouldn't be applicable and would have to be re-made with this "salt" in place.

The proper answer to that is "meh."  GPU password cracking is so fast these days that an attacker might not even consider rainbow tables.  See Troy Hunt's article on GPU password cracking, where he demonstrates how he cracked 24,710 out of 40,000 salted SHA-1 hashed passwords in 45 minutes with a $500 GPU and a cracking dictionary he downloaded.

You really ought to read the Information Security Stack Exchange's site popular entry on how to securely hash passwords, particularly the top answer.


The role of Shift Register Cascades in Cryptography?

Linear Feedback Shift Registers can not safely be used as Cryptographically Secure Pseudo-Random Number Generator (e.g. for the keystream of a stream cipher), because the state  of any LFSR is easily recovered from this output. Even it's structure can, using e.g. the Berlekamp-Massey algorithm.

In cryptography, Shift Register Cascades combine multiple LFSRs (or variants) into hopefully more secure CSPRNGs. Examples include the Alternating Step Generator, and A5/1. Arguably, the modern Trivium is a sort of Shift Register Cascade (which does not use clock control like the previous two, but instead uses a more complex feedback scheme).

Shift Register Cascades tend to inherit the main quality of LFSRs: simple hardware implementation.


Is differential calculus related to RSA?

Generally, no. There is no calculus in the design and implementation of the RSA.
There are two things that could add some analysis in the whole scheme of things:

Maybe involving the Prime Number Theorem, which explains why we won't run out of prime numbers to choose from. Some proofs of the theorem use complex analysis (including the simplest known proof, from Donald J. Newman).
About primality testing: In the paper describing the AKS algorithm, "PRIMES is in P", there is a lemma (3.1) which is proven here. Analysis is used in the proof.

You can see that calculus is not directly connected to the RSA cryptosystem but there are some fundamentals that need calculus to be proven.

The quote below is generally true:

  Every part of math is related to any other if you try hard enough. –  Thomas


Energy consumption by mobile or sensor node when executing xor / encryption / decryption

There's a degree of electronics twiddling necessary for this.  You start with:-

A stiff power supply passing through a shunt resistor is typically used, which is then monitored with a storage oscilloscope. A low resistance is necessary, say 0.1 Ohms, but that really depends on the operating point consumption of your sensor device. You can't have the power supply dipping below operational thresholds as that will nullify the experiment.  Control the device to perform your required operations, and you'll read a voltage off the scope.  Then simply $consumption = \frac{voltage}{resistance}$.

This is called power analysis, and Wiki has an entry level article. You'll see from the graphic on the RHS that the power signature is not really as simple as I implied.  That's where a lot of statistics and probability matching will become necessary.  Some don't even bother with power consumption (amps) calculations and go with purely graphical approaches.  A wibbly waveform might indicate a correct key, and a wobbly waveform might indicate a bad key. This part is entirely characteristic of the individual device under test. And how you intend to exactly distinguish various cryptographic operations within the sensors.

Also one of the challenges will be in managing to grab and isolate the power consumption at the point of cryptographic operation, rather than simply running the status LEDs. You may need additional wiring between the control inputs and the oscilloscope's trigger input.

But it's a start...


May it be possible that the trusted third party knows the parties' private keys in an "ideal model" of a Secure multiparty computation protocol?

Yes.
Trusted party setup is just way to think about what the end goal of a particular MPC system is. So you may start with a party (lets call it the dealer) that sends it's private key to the trusted party, and then the trusted party uses it to commit a transaction.
Now replace the trusted party with a multi-party setup. The dealer here sends shares of its private key to each of the parties. The parties then can regenerate the private key or commit a transaction with it.


How trivial is it to derive a private key from two public keys?

Responding to comment-implied intended question:

The RSA alternative public keys revealing the secret factors of $N$ is not a suitable means to implement threshold protocols. Instead you should be using actual threshold protocols, such as t-of-n or n-of-n signature schemes.

ECDSA uses DSA, not Schnorr, so my usual suggestions do not apply. Although a quick search for "threshold dsa" yields:

Securing Bitcoin wallets via a new DSA/ECDSA threshold signature scheme

Old answer (kept for alternative interest)

This sounds like key-blinding, where you derive a subkey from a master pair. Say you have the secret key $k$, public key $Gk$ and the blinding factor $b$, the subkey secret is $kb$ and the subkey public is $Gkb$.

$Gkb$ and $Gk$ cannot be used to recover $k$ nor $b$, without breaking Diffie-Hellman. $b$ may be derived from $Gk$ plus some contextual string, this allows someone with the master public and master secret to compute the subkeys respectively. These keys are tightly related, given $kb$ and $b$, you can recover $k$. If you give someone $kb$ but keep $b$ secret, they cannot recover $k$. If $kb = k * b$ then $k = kb / b$.

If deriving a subkey from a public key gave you any information useful to recover the secret key, the scheme is broken with only one public key.


Circular hash collision where digest is pre-image: Could hash(a) = b, hash(b)=c, then hash(c)=a?

We like to think of hash functions as random functions, and there is no reason a random function shouldn't have a cycle of size 3 which is what you describe.
Obviously it would be very difficult to find such a cycle, we can discuss how likely is it a random function over space size $n$ has a cycle of size 3.

Ignoring cycles of size 1 and 2 which acount for a small portion of the space we have $n/3$ independent size 3 prefixes. each of these has probability $1/n$ to close a size 3 cycle. the chance they all miss is $(1-1/n)^{(n/3)}$ which is $(1/e)^{(1/3)}$ or 0.71653131057.
so the chance of at least 1 such cycle is 28% which is consistent with simulation results in comments above by poncho.


Using 32 hexadecimal digits vs ASCII equivalent 16-character password

They are both equal.

Passphrase security is based on the amount of entropy that the passphrase contains. In your case, both of your pieces of data are only different in the encoding. The actual entropy that they contain is the same.

You are generating a secret that is (assuming that the random source is really random) 16 bytes long. So it has 128 bits of entropy.

I should note that this answer assumes "cryptographically speaking". However, encoding your passphrase in UTF-8 or ASCII may (in practice) screw up your data. The other answers do a good job at explaining why.

Update: fgrieu correctly notes that this answer assumes that all the entropy in the passphrase is actually used. An example when this is not the case is when you generate a 256 bit key, from which you derive a 128 bit key for 128-bit AES encryption. Here the entropy is reduced to 128 bits.


Does a key need to be signed if it is being used to decrypt a message that is already signed?

I am trying to better understand authentication. Lets say I have posted my 128-bit AES symmetric key on some forum, encrypted asymmetrically to my friend using 256-bit ECC (25519). The forum isn't controlled by us so this key message could potentially be tampered with.

Well first of all, note that encrypting with curve25519 isn't as trivial as encrypting with say RSA, you'll probably have to use ECIES or something along those lines. You usually see (and use) ECC used for digital signatures and key exchange, just so you're aware.

  I then post a bunch of actual communication messages onto the forum that are encrypted with that AES key, and I sign them using a ECC 25519 signing key that my friend can safely use to verify the messages have not been tampered with.

  Did I also need to sign my AES key message, or is it an adequate authentication check that the key decrypts my signed message correctly? If the key was tampered with it would fail to decrypt my message to something meaningful?

Let's consider what can happen if you don't sign your AES key. Worst case a malicious forum admin modifies your message and replaces your AES key with their own key (encrypted with your friend's public key). If they succeed and send messages to your friend encrypted with their own key one of three things can happen:

Your friend decrypts the message, sees e.g. some valid English text and says OK this message looks good, key must be fine.
Your friend does not decrypt the message because there is no signature on the message.
If the attacker did sign the message with their own key (since they can't forge your signature) your friend tries to verify the signature with your public key, which will fail (at which point your friend should discard the ciphertext).

In 2 out of 3 cases the attack will fail, but there is the chance that the attack will succeed if your friend is willing to decrypt ciphertexts without checking their integrity (known also as The Cryptographic Doom Principle). So it depends on what your friend does.

I recommend the a slightly different construction in this case. Assume you have private / public keypair $(sk_A, pk_A)$ and your friends is $(sk_B, pk_B)$, the notation $function_{key}$ means perform $function$ using the key $key$ and $||$ represents concatenation:

Generate two keys, one for AES ($k1$) and one for a MAC e.g. HMAC ($k2$)
Sign your generated keys ($sig = \text{Sign}_{sk_A}(k1 \text{ || } k2)$) and send the signature and keys encrypted to your friend: $\text{Encrypt}_{pk_B}(k1 \text{ || } k2 \text{ || } sig)$.

Your friend should decrypt, verify the signature, and then grab the keys.

To send a message $m$ to your friend encrypt it to yield $c = \text{AES}_{k1}(m)$ and then send the message $(c \text{ || } \text{HMAC}_{k2}(c))$. This is the "Encrypt-Then-Mac" construction, whose security you can read about more here.

Your friend should upon receipt of a message verify the MAC and if it is OK then decrypt the ciphertext.

Note that the authenticity of your messages is established from the MAC, which in turn is established by the fact that you used your private key to sign the key ($k2$) used when computing the MAC.


A second reason that a hash is usually present in RSA signature schemes (apart from being able to sign long messages) is to prevent existential forgery attacks. These look like this:

  Assume we have the public key $n$, $e$. Choose some random garbage $s$ (smaller than $n$), and calculate $m = s^e \mod n$ (i.e. "RSA encryption"). If you used "text book RSA signature" (without a hash and any padding), you now have a message $m$ with a fitting signature $s$.

With a hash, the signature checking equation is $H(m) \equiv s^e \mod n$ instead of $m \equiv s^e \mod n$, and this does not allow to create a message $m$ fitting to an arbitrary signature $s$ (assuming the hash function is preimage-resistant). Beware however that it is remains possible to create working $(m,s)$ pairs given the capability to obtain the signatures $s_j$ of chosen messages $m_j\ne m$, using an attack devised by Desmedt and Odlyzko (see section 3 of this paper).

(The padding scheme normally present in signatures serves the same purpose, and is designed to also resist chosen-messages attacks.)


This is - in a way - Functional Encryption.

From Wikipedia:

  Functional encryption is a type of public-key encryption in which
  possessing a secret key allows one to learn a function of what the
  ciphertext is encrypting.

So, YES, it is possible.

For more information this paper might prove useful.


Responsibility of quantum-weak cryptography

Should we consider it irresponsible to design new systems that assume hardness of problems already known vulnerable to quantum computers, such as factoring of large numbers or discrete logarithms?

Some would answer that it is irresponsible to design new systems at all, regardless of the threat of quantum computing. It's hard to prove something is secure even in a classical computing setting, as it requires valuable time from highly skilled people.

Others might argue that Quantum Computing might never take off and become a real thing, and so designing post-quantum algorithms is a waste of time.

We usually (arguably have to) assume the worst-case scenario when designing algorithms, and the worst-case scenario in this day and age implies a quantum computer. You could design new cryptosystems based off of problems that are known to be vulnerable to quantum algorithms and hope that quantum computers never become relevant.

If you are disinclined to include "hope" in the justification for your design, then you need to avoid problems that are already known to be broken. This means using hard problems other then the discrete logarithm/factorization.

  Likewise, do we have a moral obligation when answering questions about cryptosystems based on these, to ensure readers are aware of the coming insecurity?

It depends on your specific audience.

If it's just someone who is asking a question on crypto.se about discrete logarithms in general, then it may (or may not) be off-topic to bring up quantum computing.

Anyone who is capable of designing their own public key algorithms is probably already aware of the threat of quantum computers and hopefully does not need to be told.

Someone who is designing a new protocol should be informed that the standard go-to primitives may not provide long term security against quantum computers. Again, they may already be aware.

If your audience is someone who is instantiating a specific, already defined protocol that uses DH or RSA, then telling them that DH or RSA is broken against quantum computing is possibly not helpful or relevant - it's not up to them to make such design changes. Although, such information may cause them to select a new protocol to implement.

I would say that if it the information is relevant and they are unlikely to know it already, it certainly should be mentioned.


X3DH protocol - What are One-time prekeys for?

The short answer is ‘for forward secrecy’, but that glib term obscures the meaning of the property we hope for.

Suppose Alice sends a message to Bob.  If Alice and Bob both erase the message, what is the time at which all key material that can ever decrypt a transcript of network packets on the wire is erased?

Without prekeys, the following are all the sets of keys that can decrypt the wire transcript:

Alice's long-term identity key $\mathit{IK}_\mathrm A$ and Alice's ephemeral key $\mathit{EK}_\mathrm A$.
Bob's long-term identity key $\mathit{IK}_\mathrm B$ and Bob's long-term signed prekey $\mathit{SPK}_\mathrm B$.

While Alice will erase her ephemeral key immediately, Bob is intended to never erase his long-term identity key—at least, as long he wants to maintain his identity—and to rotate his long-term signed prekey only occasionally so that delayed messages can get through.  Thus, a set of keys that can decrypt the wire transcript can be found on Bob's device long after the message has arrived.

With prekeys, the following are all the sets of keys that can decrypt the wire transcript:

Alice's long-term identity key $\mathit{IK}_\mathrm A$ and Alice's ephemeral key $\mathit{EK}_\mathrm A$.
Bob's long-term identity key $\mathit{IK}_\mathrm B$, Bob's long-term signed prekey $\mathit{SPK}_\mathrm B$, and Bob's one-time prekey $\mathit{OPK}_\mathrm B$.

Alice will again erase her ephemeral key immediately.  Bob won't immediately erase anything, because he might be offline—this is an asynchronous protocol.  But as soon as he receives the message, he will erase his one-time prekey.  Thus, as soon as Bob has processed the message, all sets of keys that can decrypt the wire transcript will be erased.

Of course, Alice or Bob might keep a copy of the message on their respective devices for all eternity.  But one-time prekeys guarantee that they have the option to erase messages without leaving targets on their devices for retroactive decryption of wire transcripts.


What are the security implications of knowing the private polynomial $\mathcal{F}$

Let's answer my question after revisiting the research. Start by quoting the following text from [2]. Note that I've changed the variables names to fit my description. Here $P(X) = T \circ F \circ S(X)$.

  An open question is to know whether or not these schemes remain secure
  if the set of polynomials $\mathcal{F}$ is public. In this situation,
  the security of these schemes relies not only on the difficulty of
  finding a common zero of a system of non linear equations but also on
  the difficulty of $\mathcal{IP}$ (Isomorphism of Polynomials) problem
  (when $\mathcal{F}$ and $\mathcal{P}$ are given, the problem is to recover the
  pairs $(A_1,v_s)$ and $(A_2,v_t)$).

In this post the private polynomial $\mathcal{F}$ is public, moreover described methods reduce IP2 to IP1 if $T$ is known, and IP1 is totally insecure [2]. In the other hand, if $S$ is known $T$ is recovered by basic linear algebra.

Then I conclude that a cryptosystem where $\mathcal{F}$ is known depends on the IP2 assumption (finding $(S,T))$ and the $\mathcal{MQ}$ problem implicitly. You can follow up from [2] section $6.2$

EDIT: Moreover, it results that IP1 is totally broken when the private polynomial is known. However if the polynomial $\mathcal{F}$ is unknown, having access to an oracle then querying for canonical vectors as a plaintext will reveal $S$ too. A secure cryptosystem based on MPKC must satisfy the IP2 assumption from design, between others.


Is the following s-box more linear or more non-linear?

Yes, your table is perfectly linear: The output is the sum of the inner four bits plus left outer bit*0101 plus right outer bit*1010.


The ECIES (Elliptic Curve Integrated Encryption Scheme) should be used for encrypting file and data. ECC(P-521) is over kill, P-256 is enough secure and more efficient.


Relations between Number theory/Algebra and Lattice based cryptography

Studying lattices (and lattice-based schemes) does not necessary involves algebraic number theory (or other somehow advanced topics). The security reductions uses more aspects of complexity theory and probabilities. And the algorithms to solve lattices problems (for instance, to solve SVP, CVP, BDD, etc), in general, use more linear algebra.

I think you should check the structured versions of lattice-based problems (like RLWE and RSIS). For instance, the description of RLWE typically involves Cyclotomic number fields and the their rings of integers.

The manual A Toolkit for Ring-LWE Cryptography can be a good starting point.

But even if they use a lot of concepts from Number theory and Algebraic Number Theory, they are not necessarily based on problems studied in these fields (the security of schemes based on ring variants of LWE and SIS relies basically on the assumption that SVP and other lattice problems are still hard over the lattices generated by such structured problems... e.g. ideal lattices).

One problem that is maybe more related to algebra but is also studied in cryptography is the problem of finding short generators of principal ideals. You can easily find papers about it. For example, this one: Recovering Short Generators of Principal Ideals in Cyclotomic Rings.


Is there a zero knowledge proof to show an encrypted blob is the key for a given public key?

I am assuming that you are encrypting $x$ under a different public key from potentially a different scheme. The answer is yes, since every language in NP can be proven in zero knowledge. The question, of course, is can this be done efficiently. The answer to that depends on the schemes involved.


Why constrain the message lengths in indistinguishability in the presence of an eavesdropper?

Well, the problem is that -- as long as your encryption algorithm accepts messages of arbitrary length -- it is impossible to hide the length of the encrypted message.

This is actually quite natural. Think about it, when I encrypt a 1000 bit message I simply need more bits to represent the ciphertext than when I encrypt only a single bit.

Therefore, if one of the messages is allowed to be longer than the other, it is in general quite easy to distinguish between the two cases, because in the one case the ciphertext will be longer.


Is there a flaw in this ECC blind signature scheme?

This paper—if I have guessed correctly through the broken link—is bogus.  It fails to distinguish points on the curve from elements of the coordinate field and doesn't prove anything and even if you fix that by pretending any of it makes sense the whole thing is trivially breakable.  Throw it away and forget the whole ordeal—except don't forget that the ‘Journal of Networks’ is a bullshit-publishing paper mill.


Finding the private key for this signature scheme

Let $m'$ be an arbitrary message. Then, the triple $(m', a', b')$ with:
\begin{align}
a' &= -\mathcal{H}(m') \pmod{p-1} \\
b' &= g^{-\mathcal{H}(m')} \cdot y^{-1} \pmod{p}
\end{align}
is a valid signature on $m'$. Since we forged a signature on an arbitrary message, we've achieved total break for this scheme.


What is the meaning of the overlapping region on OTP-perfect secrecy diagram?

Your diagram is a Venn diagram that illustrates the information measures between the correlated random variables $X,Y$ and $Z$.

$H(X)$ refers to a complete circle and is the entropy of $X$,
$H(X|YZ)$ is the entropy of $X$ under the observation of $Y$ and $Z$,
$I(X;Y|Z)$ is the mutual information between $X$ and $Y$ under the observation Z,
$R(X;Y;Z)$ seems to represent $I(X;Y;Z)$, the mutual information between X,Y and Z.

The region $R(X;Y;Z)$ is thus the amount of information that is shared by the random variables $X,Y$ and $Z$. If the random variables are completely independent, then this region is empty.

I don't know exactly how this is related to OTP. I guess that you typically want maximal entropy for OTP, and you don't want to have any mutual information between the variables.

PS: After writing most of this answer I found a wikipedia page about multivariate mutual information, which seems to correspond exactly to this question.


Does this satisfy the properties of a MAC?

No, it doesn't, however a tweak to it does.

The issue is that flipping a single bit of $m$ always changes either every bit of the MAC (if $n$ is odd), or none of the bits (if $n$ is even); hence it is trivial for the attacker to modify the message, and adjust the MAC.

What you really meant is $b_i = \bigoplus_{j=1}^{n}(m \wedge k_i)$ (where $\wedge$ is the bit-wise and operation.  This still needs a bit of tweaking (because of the all-0 message; either include an artificial 1 bit in the message, or cheaper, do a final xor of yet another $k$ vector into the final $b$ result).

This method is equivalent to selecting a random $(n \times n)$ matrix in $GF(2)$, and then doing a matrix multiplication of the message to form the output; this is a well-known universal hash method.

  Does this satisfy this definition?

With the above tweaks, yes.

  Could this be done with a smaller key?

Of course.  I suspect that most universal hash methods could be made to do this; here's one approach (polynomial hashing) that uses quite a small key.

Lets pick an integer $z$, and a field representation of $GF(2^z)$ (actually, any field of about this size can be made to work).

Then, for our one-time keys key, we pick two random $z$-bit values $h$ and $c$.

Then, we divide our $n$-bit message $m$ into $z$-bit sized chunks $m_{i-1}, m_{i-2}, ..., m_0$ (where $i = \lceil( n / z ) \rceil$, and we compute:

$$MAC = m_{i-1} h^{i+1} + m_{i-2} h^{i} + ... + m_0 h^2 + i h + c$$

The above computation is done in $GF(2^z)$

This is also a secure MAC (any modification to the message and tag will pass the checks with probability at most $(i+1)2^{-z}$; we can select $z$ to make this arbitrarily small), and it also meets your requirements (to fake a MAC, we can select an arbitrary $h$ and compute what the $c$ value had to be); using a total of $2z$ OTS bits per message.


You have to distinguish between "theoretically" and "practically" breakable. Pretty much any cryptosystem can be broken in practice by violating the assumptions that the theoretical security proof uses.
For example, with Quantum Key Distribution and a OTP, you might have theoretical perfect secrecy. However, the proof for such a scheme does not address the possibility of "Wait for them to receive the message and then threaten them to obtain it" - and there is nothing that QKD + OTP or any cryptography can do about to prevent this type of attack. This is because such an attack specifically targets what the security proof of the cryptography does not cover.
So in that sense, when an adversary has such options, achieving "unbreakable" security in practice is not a realistic prospect: In the best case scenario, with theoretically perfect crypto (i.e. QKD + OTP), there still exists a trivial solution to breaching the confidentiality of the information: Simply extract the information physically from the recipient, after they receive it. The implementation might be complex and expensive, but it is certainly possible in a practical sense.
Edit
This rather scathing blog.cr.yp.to post reiterates the the importance of the used assumptions and raises some technical points aside from the ever present threat of rubber hose cryptanalysis:

A company named ID Quantique has been selling quantum-cryptography hardware, specifically hardware for BB84-type protocols, since 2004. ID Quantique claims that quantum cryptography provides "absolute security, guaranteed by the fundamental laws of physics." However, Vadim Makarov and his collaborators have shown that the ID Quantique devices are vulnerable to control by attackers, that various subsequent countermeasures are still vulnerable, and that analogous vulnerabilities in another quantum-key-distribution system are completely exploitable at low cost. The most reasonable extrapolation from the literature is that all of ID Quantique's devices are exploitable...
...how can a product be broken if it provides "absolute security, guaranteed by the fundamental laws of physics"? The correct answer is that the hypotheses of the theorems, the assumptions made in the theorems, are not the laws of physics. The hypotheses include

an embarrassingly oversimplified model of physics that can express some quantum concepts but that ignores critical long-distance interactions, notably electromagnetism; and
an embarrassingly oversimplified model of the attacker that allows the attacker to inspect photons being sent between quantum-cryptography devices but that does not allow the attacker to interact with the devices in any other way.


Explain the 'Breaking 104 bit WEP in less than 60 seconds' paper

According to the paper, it takes up to 53 seconds for enough data to be transferred for the attack to be attempted. Then it takes 1-3 seconds with 50% probability on a 1.7 GHz Pentium-M to perform the crack (presumably this actually means between 1 and 6 seconds for 100% probability?).

I would do a back of the napkin calculation how long the same attack would take against a "proper" wifi network using the same hardware (or even better, on a laptop with a decent GPU for 3D games), and then say something like this:

"It takes less than 60 seconds to crack WEP and X years to crack WPA with a 12 digit password."

I would not say anything like "104 bit" or go into properly long alpha-numeric passwords because you'll just confuse people with stuff like that. It's bad enough you even need to tell them that "WEP" and "WPA" are different, you already lost some people by mentioning two acronyms they've never heard of.

I would sum it up by also saying:

"WEP was designed by idiots. WPA was designed by experts."

Which is a bit harsh on the WEP guys but is basically true. They probably had no idea how insecure their protocol was until long after everyone started using it (to be fair, security wasn't really their goal either).


Meet in the middle attack: Why would it be easier to get elements of one of the 2 sets?

In many cases you are memory bound and you can't keep everything you compute in memory. So you can compute as much as fits in memory to get group A and then compute without storing in memory a potentially much larger group B. Checking for a collision is done efficiently because one group is in a hashset you have stored.
The memory limit could be RAM limit so lookup is very fast but it could also be disk limit, you really can not store more data.


Setting up of polynomials for CP-ABE or KP-ABE Access Trees

I suggest, you look into the code how that works. Basically, you start with a secret that you want to share according to some tree. You share the secret with a Threshold Secret Sharing Scheme like Shamir's Secret Sharing and put the resulting shares into the children of that node (in the beginning this is the root node). Then you can re-share each of the shares if this is necessary. Here is an example:

In the end, every non-leaf node in the tree has its own polynomial that has to be evaluated and every leaf node has a share. In the reconstruction phase, you apply Lagrange interpolation at each node from the bottom up.

Of course, it is possible to make some optimizations. For example, if the root node is an OR gate and the left subtree is large, but the right subtree is only a single leaf, then you should first check whether the right subtree is satisfied and reconstruct the root secret only from one leaf.


Forgery attack for Merkle–Damgård MAC scheme with prefix method

A lot of this is explained well on the wikipedia article.

The function $f$ is called the compression function. It is a function $$f:\left\{0,1\right\}^n\times\left\{0,1\right\}^\ell\to\left\{0,1\right\}^n.$$

That is, it takes as input an $n$-bit value and an $\ell$-bit value, and outputs an $n$-bit value. This function is a building block for the function $H_0$. This function $H_0$ is called a hash function, with the restriction that its input is a multiple of $\ell$ bits. So we can think of it as a function
$$H_0:\left(\left\{0,1\right\}^\ell\right)^*\to\left\{0,1\right\}^n.$$
By definition, $H_0$ is defined as
\begin{align*}
H_0(M_0||\cdots||M_t) &= f(\cdots f(f(f(IV,M_0),M_1),M_2)\cdots,M_t).\\
\end{align*}
So we compute $f(IV,M_0)$, followed by $f(f(IV,M_0),M_1)$, etc.

The function $H$ is a hash function without the length restriction. We build it on top of $H_0$, so to do so we may have to pad the message to have length a multiple of $\ell$. That is, $H$ is a function
$$H:\left\{0,1\right\}^*\to\left\{0,1\right\}^n$$
defined by $H(M)=H_0(M||pad(M))$.

So what is the relation between $f$ and $H$? Well, it can be shown that if $f$ is a collision-resistant one-way function, then $H$ is a collision-resistant hash function. So the idea of the Merkle-Damgard construction is that we can build collision-resistant hash functions from collision-resistant one-way functions.

You can make this hash function into a MAC function by prepending a key, so defining ${\tt MAC}_K(M)=H(K||M)$. The exercise asks you to show that this is not a good idea, i.e. for this MAC we can find forge a signature.

Constructing a forgery:

I feel this is the type of question that becomes hard by overload of notation. The best way (in my opinion) to get through this is to calmly figure out what all this notation means (which the above should help with), and then figure out what the question is asking. This is not always easy.

  Show that given the MAC of a known message m the adversary is able to output a forgery on a message m′≠m

So, what does this mean? We are given a MAC of known message $m$, and are asked to output the MAC of any other message $m'$, as long as $m'\neq m$. Thus, the question can be rewritten as

  Given ${\tt MAC}_K(m)$, compute ${\tt MAC}_K(m')$ for some $m'\neq m$.

Assume for simplicity of the argument that $K$ has length a multiple of $\ell$.
By definition, we have
\begin{align*}
{\tt MAC}_K(m)  &= f(\cdots f(f(f(IV,K),m_0),m_1)\cdots, ..||pad(m)).
\end{align*}

From this, we see that the key is used only once. Moreover, it is used right at the start of the computation. The idea should thus be to choose $m'$ in such a way that the start overlaps with $m$. For example, take some $\ell$-bit message $m'_0$ and take $m'=m || pad(m) || m'_0$. By definition,
\begin{align*}
{\tt MAC}_K(m')  &= f(f(\cdots f(f(f(IV,K),m_0),m_1)\cdots, ..||pad(m)),m'_0) \\
                 &= f({\tt MAC}_K(m),m'_0).
\end{align*}

Hence we know ${\tt MAC}_K(m')$, and $m'\neq m$ since $m'$ is longer. The crux of the argument was appending $m'_0$ to $m$, which is a so-called length-extension attack. You can generalize this to appending any message of any length.


Is there a practical security difference between XXX-bit encryption?

From my understanding of crypto functions, a password is typically used to create a xxx-bit secret key... Given that typically something like an 8 digit alpha numeric case sensitive password would supply 30 bits of entropy, my assumption is that in almost all cases the password would have significantly less entropy than the cryptographic secret key, hence the logical target for brute force attacks.

First, many (if not most) secret keys should be generated by a cryptographically secure source of random numbers. This will generate a key with maximum entropy: 128 bits, or 256 bits, depending on the size of the key. This is well out of the range of brute force.

If you do need to generate a key from a password, there are algorithms like PBKDF2 which attempt to increase the cost of brute-forcing the key. They have a configurable work factor which, when increased, exponentially increases the amount of computing power required to turn a password guess into a key. You still should avoid using trivially weak passwords, but if the work factor is configured such that each brute force attempt requires around one second to compute (using today's hardware), it would take 17 years on average to break an 8-character alphanumeric key.

That's still obviously far short of the amount of time it would take to brute force a 128-bit randomly generated key, so the use of strong passwords is still absolutely mandatory. Something like a 10-digit password consisting of any of the glyphs on a standard US keyboard would take over 800 billion years to crack given a work factor requiring roughly one second to generate a key from each password guess, given today's hardware.

  Why do we worry about 1024-bit and 2048-bit encryption?

The strength of a key given a certain size is based upon how that key is generated. For 128-bit and 256-bit keys, we are almost inevitably talking about symmetric encryption. For these types of algorithms, the key is randomly generated.

Asymmetric (public/private key) encryption is a different beast. For algorithms like RSA, the key is not simply a very large random number: it is a very large semiprime. In simplified terms, your private key typically will consist of two large prime numbers, and the public key is the 1024-bit or 2048-bit semiprime that results from multiplying those two primes. The difficulty of breaking the key is the amount of effort an attacker would need to spend to factorize the public key in order to discover the two primes that make up the private key — this is a task we believe to be extremely hard.

Based on how hard we think that problem is, we currently believe the effort to factorize a 1024-bit semiprime to be roughly equivalent to brute-forcing a 128-bit keyspace. Likewise for 2048-bit semiprimes and 256-bit keyspaces. There are other asymmetric cryptosystems that rely on other "hard" mathematical problems, and their key lengths are likewise based on how hard we believe those problems to be.


A mathematical explanation of the DES encryption system

The DES standard (FIPS 46-3) is actually a rather straightforward description of DES. It tells with precision and detail where each bit goes. It is a specification for implementers (who can be thought as "computer specialists" but anybody who wants to learn about DES should be able to understand that specification). What FIPS 46-3 does not tell is why DES was designed that way. If you want more mathematics, you can have a look at the Handbook of Applied Cryptography (free download !), in particular chapter 7, which goes over the case of DES.

For the initial and final permutations (called "IP" in FIPS 46-3), they were defined not for security (they are fixed, key-less permutations which anyone can readily invert), but to ease implementations in hardware contexts of the 1970s' era: they make it easier to make an hardware implementation which plugs on an 8-bit bus. See this question for some details.

There is nothing about fields in DES. It is all bit-by-bit manipulations; to some extent you could say that a bit is a value in GF(2), the field with two elements (0 and 1), but that's quite stretching it.


As tylo correctly notes, when we hash multiple values, the important feature that any method we choose should have is that it should be unambiguous: there should not be any way to construct two valid sets of values that produce the same hash value — or at least it should not be any easier than breaking the collision resistance of the underlying hash function by constructing two strings with the same hash value.

In practice, there are many ways to do this.  Some are only valid for ceratin kinds of inputs:

Plain concatenation of the input values before hashing them can be problematic, since, as tylo notes, e.g. "12" || "3" = "1" || "23".  However, in some special cases it can be safe, e.g. when all the inputs (or all but one of them) are known to have a fixed length, or when there some other way to always tell where one input value ends and the next begins.
Using a separator string works well, if we can guarantee that the separator will never occur in any of the input strings (or at most, that it can only occur in one of them and that the number and order of the inputs is fixed).  When hashing ASCII or UTF-8 text, null bytes are popular separators.

Other methods are more general, and can be used for (almost) any input tuples:

Prepending the length of each input string to it before concatenating them, as suggested by fgrieu in the comments, makes the encoding unambiguous.  One potential issue is that, if a fixed-size length field is used, this limits the length of the allowed input strings.  This can be avoided if a variable-size encoding is used for the length; perhaps the simplest way to do that is to just write the length out as sequence of decimal (or hexadecimal) digits, followed by some non-digit separator.
There are also several existing data serialization formats that have already solved the problem of uniquely encoding arbitrary data structures into strings.  Perhaps the best known example in cryptography is ASN.1 DER, but there are several other alternatives such as csexps.  One advantage of using such a format is that they typically support more complex data structures than just tuples of strings; another is that you can find pre-made encoders instead of having to code your own.
Finally, instead of just encoding the inputs into a single string and hashing it, it's also possible to modify the hashing method to directly support multiple inputs.  One general way to do that is to use a hash list, in which every input value is first hashed separately, and the resulting hashes (which have a fixed length, and can thus be safely concatenated) are then concatenated and hashed together.


KDF2 is a KDF defined in ISO 18033.  You can find a draft of that spec here.  See section 6.2.3.

As to why it's listed as a PRNG, remember that a KDF relies on a pseudo random function (PRF), so it's output needs to be random.


Using crypto_sign then crypto_box_seal for anonymous messages

No, it is not!.
If you signed a message to someone before then they can use this to send an anonymous message to Bob and Bob may consider that it is coming from Alice.
The solution is easy, use crypto_box (Authenticated encryption of the NaCl) to produce a message and send it with crypto_box_seal.
$$\text{crypto_box_seal}(\text{crypto_box}(m)).$$ Here we are using short form of the boxes, no details.
The outer layer provides anonymity for all, the inner layer provides the identity. Since only Bob can reveal the crypto_box_seal, then only Bob can reveal the crypto_box and will understand the message is coming from who; Alice.
Note that Bob may not be aware that there is a crypto_box in the crypto_box_seal, put an additional message in the crypto_box` for indication.
$$\text{crypto_box_seal}(\text{After the columns there is a crypto box:}||\text{crypto_box}(m))$$


CPA distinguisher for matrix multiplication in GF(256) with randomized padding

While Ilmari answered the specific question you asked (Chosen Plaintext Distinguishers), I would like to note that the attack can be sharpened into a Known Plaintext Key Recovery attack (where, by key recovery, I don't mean recovering the $E_k$ matrix, but instead allowing an attacker to reconstruct enough information to decrypt arbitrary texts).

One straightforward way to see this is to observe that the decryption process is entirely linear; that is, if we know that:

$Decrypt(C_1) = P_1$ and $Decrypt(C_2) = P_2$

then

$Decrypt(aC_1 + bC_2) = aP_1 + bP_2$  for $a, b \in GF(2^8)$

So, all the attacker needs to do is collect $2n$ linearly independent ciphertexts with corresponding known plaintexts:

$Decrypt(C_1) = P_1$

$Decrypt(C_2) = P_2$

...

$Decrypt(C_{2n}) = P_{2n}$

Then, do decrypt an arbitrary ciphertext $C_x$, he solves the linear equation for $a_1, a_2, \ldots a_{2n}$:

$C_x = \sum_i a_i C_i$

and then he knows that

$Decrypt(C_x) = Decrypt( \sum_i a_i C_i) = \sum_i a_i P_i$


Creating multiple independent keys for cascading - recommended approach?

$\newcommand{\concat}{\mathbin\Vert}$Use a key derivation function, such as HKDF, to expand a master password-derived key into subkeys for each cipher.

Compute $k = \operatorname{scrypt}(\mathit{password}, \dots)$.
Compute $k_\mathrm{AES} = \operatorname{HKDF}_k(\text{‘AES’})$.
Compute $k_\mathrm{Serpent} = \operatorname{HKDF}_k(\text{‘Serpent’})$.
Compute $k_\mathrm{Twofish} = \operatorname{HKDF}_k(\text{‘Twofish’})$.
Throw out Applied Cryptography and get Cryptography Engineering to replace it, but make sure to print out the unauthorized errata and glue them into your copy of it.
Step back and write down a clear security model for your application, because higher-level logic in your application will be attacked long before the crypto.


Secure multi-party random number generation

Looks like I can achieve this by simply hashing all d[i] values in predictable order.

That doesn't quite work; the issue is that the last one to contribute their d[i] value has seen all the previous ones, and can then quickly test candidate d[i] values, looking for one when produces the random padding they like.  This is probably not a huge vulnerability (if the protocol expects a d[i] value within a few seconds, an implementation might be able to test a few million to billions of candidate values (depending on attacker resources) before having to select one); however it is something.

The fix for that is for to have everyone submit commitments to their shares before revealing them.  For example, party i first publishes $\text{hash}( d[i] || r_i )$ to everyone, and not until everyone has published their commitments, everyone then publishes their $d[i]$ and $r_i$ values (and everyone can check that their revealed values matches their commitments).  Then, everyone can combine all the $d[i]$ values, and you then get a hash value that no one has control over.

The best an attacker can do is arrange to be the last person to reveal their $d[i], r_i$ values, and then, if the combined value isn't what they like, just refuse (or misopen their commitment).  This does allow the attacker a veto over the randomness; however for the attacker to use their veto, they have to give a hint that they are the malicious party.  You could try to avoid this by using a function that is hard to compute quickly (e.g. Argon2 with appropriate parameters); I'm not sure if it's worth the trouble...


In order to achieve very high security for privacy, would it be cryptographically secure to use one time pad ciphers in emails?

OTP offers perfect secrecy, so if it's feasible to use it, it is secure.

However, OTP alone offers no authentication and leaves the message malleable. If Alice sends a message Y to Bob, standing for 'yes', Mallory can guess this and modify the message to say N instead (but he would garble the message if he thought it said something different).

You would need to add a MAC to get authentication as well.


Authentication without decrypting the password?

This can be done with a cryptographic protocol called Password-Authenticated Key Exchange (PAKE). It comes in a few flavors:

Plain PAKE is a good fit for peer-to-peer connections. Both participants know the password in the clear, and use it as input to the PAKE protocol. If they both agree on the password, then they establish a shared secret key, safe from eavesdroppers. If the passwords disagree, they fail to establish a key.
Asymmetric PAKE (aPAKE) is a good fit for client-server connections. The client knows the password in the clear and the server holds only a "hash" of the password. (In practice, it's not exactly a hash but something more involved. The point is that the server doesn't know the password in the clear.) The two participants will establish a shared secret key only if the connecting client uses the correct password.

A good, accessible introduction to the state of the art can be found in this talk by Hugo Krawczyk earlier this month at the Real World Crypto symposium. Among other things that you can do with PAKE, he explicitly talks about aPAKE as a replacement for password-over-TLS (the typical approach for authentication that you described).


secp521r1 elliptic curve base point coordinates

The compressed form of the base point only provides the X coordinate. It is identified by a leading $\mathtt{02}$ or $\mathtt{03}$ byte. The remaining bytes are the hex-encoded X coordinate. Y can be recovered using the curve definition $y^2 = x^3 + ax + b \pmod{p}$. As both Y and -Y can satisfy the equation, the leading $\mathtt{02}$ indicates the that the positive value should be taken, and the leading $\mathtt{03}$ indicates that the negative value should be taken. You can read more details in this answer.

The uncompressed form of the base point provides both the X and Y coordinates. It is identified by the leading $\mathtt{04}$ byte. The remaining bytes are the hex-encoded X and Y coordinates, concatenated as X || Y.

Looking at SEC2 Ver1, "2.9.1 Recommended Parameters secp521r1", we have:

G =       04 00C6858E 06B70404 E9CD9E3E CB662395 B4429C64 8139053F
    B521F828 AF606B4D 3DBAA14B 5E77EFE7 5928FE1D C127A2FF A8DE3348
    B3C1856A 429BF97E 7E31C2E5 BD660118 39296A78 9A3BC004 5C8A5FB4
    2C7D1BD9 98F54449 579B4468 17AFBD17 273E662C 97EE7299 5EF42640
    C550B901 3FAD0761 353C7086 A272C240 88BE9476 9FD16650

In other words, the uncompressed encoding of the basepoint G = 04 || X || Y. Using that we can parse the coordinates of G as:

X =     00C6 858E06B7 0404E9CD 9E3ECB66 2395B442 9C648139 053FB521
    F828AF60 6B4D3DBA A14B5E77 EFE75928 FE1DC127 A2FFA8DE 3348B3C1
    856A429B F97E7E31 C2E5BD66
Y =     0118 39296A78 9A3BC004 5C8A5FB4 2C7D1BD9 98F54449 579B4468
    17AFBD17 273E662C 97EE7299 5EF42640 C550B901 3FAD0761 353C7086
    A272C240 88BE9476 9FD16650


In DSA (and ECDSA), it is possible and common to share the same domain parameters, across multiples users. AFAIK (and according to common wisdom, including FIPS recommendations) this introduce no known security weakness. The only common reasons to change domain parameters are to increase key size, or purposely introduce on interoperability barrier (e.g. to force an upgrade).

One advantage of fixed domain parameters $(p,q,g)$ in DSA is that it simplifies the choice of a user's key: basically one selects a random private $x\in[1, q–1]$ and computes the public $y=g^x\bmod p$.

As pointed in this other answer, sharing domain parameters increase odds that several users share the same key. However, for a good RNG, $2^n$ users and the lowest security level in FIPS 186, odds that it happens are less then $2^{160-2⋅n}$; that's negligible even for one key per day per human on our planet during a century. And if the RNG is flawed, all bets are off anyway.


You are not missing anything, the calculation is wrong. The calculation of the key schedule that is.

If you postulate the round calculations are correct, the round keys must be wrong, and in fact that byte of the round key is indeed wrong. Reversing the AddRoundKey calculation from the round example, the valid round key byte resulting in 0x77 is 0x87, not 0xB7.

Therefore the slide was just wrong, the values may have been entered by hand, and 8 looks like a B, so that is very likely.


Pairing-friendly curves in small characteristic fields

To my knowledge the answer is no.

Informally, the only known method to construct pairing friendly curve is the CM method, which allows you to find an elliptic curve with strong constraints on its number of points if you put few constraints on the cardinal of the base field, or conversely a curve over a very constrained base field with only little constraints on its number of points.

(If you're interested in more precise statements and explicit examples, I suggest looking at Lay and Zimmer, Constructing elliptic curves with given group order over large finite fields, which despite its title covers both aspects. Article behind a pay wall unfortunately.)

This works well to find pairing-friendly curves in large characteristic because you have plenty of room to let the cardinal of the base field vary. But it doesn't work well at all over small characteristic fields, because you put both huge constraints on the cardinal of the base field (it has to be a power of the characteristic) and on the number of points on the curve (to achieve a small embedding degree).

In fact, I'd be curious to see even a single example of an ordinary curve with small embedding degree over a not too large binary field, like $\mathbb{F}_{2^{31}}$ say.

Note that this problem is entirely unrelated with the question of constructing ordinary pairing-friendly curves of higher genus over large prime fields, which Freeman's article mentioned above addresses.


Cycling hashing in PBKDF's and their limitations in strength?

Encrypting the salt is actually equivalent to just using the cipher as an initial step. That is, you could redefine the scheme as follows:

tmp := D(hash(password), salt)
password_hash = F(password, tmp)
output := salt, password_hash

Where D is the decryption function and F is the actual iterated password hash you defined.

The addition of the cipher is not significant from the point of view of slowing down dictionary attacks if it's a typical fast cipher like AES. It can only make a difference if the underlying hash function (which you call Hash) is completely broken to a degree e.g. MD5 is nowhere near being.

Note that the intermediate value, which I called tmp above and you called salt must be kept secret. Knowing it an attacker would be able to avoid the whole looping part and just test the encryption/decryption output. For that reason calling it a salt is a bit misleading.

The actual iteration function is very close to PBKDF1, as Richie Frame observed in the comments. It adds the salt at each iteration, but I do not see why that should be significantly stronger. It does not seem to offer any advantage over PBKDF2, but like PBKDF1 it is likely not significantly weaker either – with an iteration count that gives equal running time. (Any advantages PBKDF2 has are likely theoretical, but using HMAC may be a slightly better security margin. Or at least a security blanket...)

Compared to bcrypt it shares most of the advantages and disadvantages of PBKDF2. See e.g. Thomas Pornin's post on Security.SE for a treatment. The main difference being, of course, that yours is non-standard and could have undiscovered weaknesses. TL;DR is that bcrypt is superior due to having some GPU resistance, but does have some limitations like on password and output lengths.


Changing encryption key without revealing the original key

As CodesInChaos already answered in the comments, this seems to be a perfect fit for proxy re-encryption (PRE). The basic idea of PRE is that a ciphertext encrypted under the public key of user $A$ can be transformed (i.e., re-encrypted) into a ciphertext decryptable by the private key of user $B$; the re-encryption process does not reveal any information about the underlying message.

Note then that proxy re-encryption is a type of public-key encryption. Therefore, users in your scenario should have pairs of public and private keys. Proxy re-encryption schemes come in all flavors (unidirectional vs. bidirectional, single-use vs. multi-use, interactive vs. non-interactive, etc.). Depending on your scenario, you would choose one or another.

However, from your question, one could think that users were using symmetric encryption. In case you were asking for the symmetric counterpart of PRE, then this can be constructed using other mechanisms, such as Key-Homomorphic Pseudo-Random Functions.


Let $G$ be a PRG. Are the following $G'$ constructions based on $G$ necessarily PRGs?

Looks good to me! My intuition is that the PRG property means "random in, random out".

In 1. the input is not random so we get no guarantees - indeed, formally one could take any PRG H with 2s-bit inputs  and then define G to be H except on strings where the last s bits are 0, in which case G outputs the all-zero string. Now G is still a PRG, because the probability of hitting one of those modified points is at most $2^{-s}$ which makes a negligible difference overall. But $G'$ is now the function that always outputs the all-zero string.

What I've added here is the step from the intuition to a formal proof: I've given a case where $G$ is provably a PRG (ok, I didn't prove it here, but that's an easy exercise) and $G'$ is provably not a PRG.

In 2. if $s_1 \ldots s_n$ is uniform in $\{0,1\}^n$ then $s_1 \ldots s_{n/2}$ is certainly uniform in $\{0,1\}^{n/2}$. So applying $G$ to this string produces something uniformly distributed in the range of $G$, hence the whole thing is a PRG, just like you said.


What might be the intuition for this scheme to be AEAD and what is the problem with this?

A critical part of any AEAD scheme is that it ensures the authenticity of the header data and the ciphertext. Your scheme only protects the header data, leaving the ciphertext vulnerable. Protecting the key is not enough.

CBC mode is affected by certain bit-flipping attacks, that allows an attacker to change part of the message. This results in one block being completely garbled, and the next block having the exact bits flipped that were flipped in the attack. The rest of the decrypted message is untouched. If you don't authenticate the ciphertext, you will be vulnerable to this attack. This attack also extends to certain padding oracle attacks.

As for the IV and key: using a static IV with a unique per-message key may be secure, but it's a non-standard way of implementing CBC. Best case, it doesn't gain you anything over the standard way of implementing CBC. In the spirit of "Don't roll your own", it would be best to use CBC the standard way, with a random, unique and unpredictable IV.


Encrypting structured data (text) with RSA

I'll assume the question is about RSA encryption of a message consisting of a random symmetric key and non-random data (a filename).

The question's "before encryption" could be referring to before using:

Textbook RSA encryption, that is changing message $m$ to $m^e\bmod N$, where $(N,e)$ is the RSA public key.
PKCS#1 v2.1 RSA encryption, that is with OAEP padding.
Hybrid encryption, which is RSA encryption as most usually practiced: RSA is used to send the secret key of a traditional symmetric cryptosystem.

What is meant by Bruce Schneier's quote is that (1) could be bad; and before applying the transformation in (1), a transformation should be applied to $m$ that makes it much like a random integer somewhat less than $N$, with little other structure.

Yes, that can be achieved with "XOR it with some pseudo-random byte stream", provided that the receiver has a way to recover than pseudo-random byte stream and undo the XOR; and that byte stream has approriate length, so that the result of the XOR is somewhat less than $N$.

In fact, this is part of what OAEP performs, and thus is built in (2). There's a caveat though: the maximum payload in (2) is reduced compared to (1). For example, with a 2048-bit (256-byte) RSA key, (1) could encipher any payload of $256-1=255$ bytes, when OAEP using SHA-256 (a 32-byte hash) limits the payload to a maximum of $256-2*32-2=190$ bytes. In both cases, the ciphertext will be 256 bytes. Thus that works for a moderate symmetric key (e.g. 16 bytes) and a small filename (up to 174 bytes). OAEP decryption will restore the payload's length.

Another option would be (3), which removes any size limit, at the price of a larger ciphertext, and often of leaking the payload's size (here, the filename's length).

Notice that (1) and (2), and many forms of (3), will not insure that what's deciphered is genuine; that's the job of authenticated encryption, which requires something secret on the sender side (beyond the message to send), contrary to RSA encryption.


How does KECCAK operate on a state array filled with zeros?

I personally find the Keccak.team Psuedo Code document very helpful to understand how Keccak-p works.
As DannyNiu said in the comments, most (all?) cryptographic permutation employ "round constants".  These constants are somehow mixed in the Keccak state.
The pseudocode document gives the round constants as a table:
RC[0]   0x0000000000000001  RC[12]  0x000000008000808B
RC[1]   0x0000000000008082  RC[13]  0x800000000000008B
RC[2]   0x800000000000808A  RC[14]  0x8000000000008089
RC[3]   0x8000000080008000  RC[15]  0x8000000000008003
RC[4]   0x000000000000808B  RC[16]  0x8000000000008002
RC[5]   0x0000000080000001  RC[17]  0x8000000000000080
RC[6]   0x8000000080008081  RC[18]  0x000000000000800A
RC[7]   0x8000000000008009  RC[19]  0x800000008000000A
RC[8]   0x000000000000008A  RC[20]  0x8000000080008081
RC[9]   0x0000000000000088  RC[21]  0x8000000000008080
RC[10]  0x0000000080008009  RC[22]  0x0000000080000001
RC[11]  0x000000008000000A  RC[23]  0x8000000080008008

and explains how they are used.  In the iota-step of the $n^\text{th}$ Keccak-p round, the $n^\text{th}$ round constant $RC[n]$ gets introduced and gets XOR'd into the first word, first lane.
Apart from the round constants, the Keccak permutation has a very good diffusion: a single bit somewhere in the initial state will contribute significantly to many output bits.
The combination of both means that your Keccak permutation looks very random.  It cannot, of course, turn zero entropy into random, since no finite algorithm can do that, but the goal of Keccak is to mix things about and make them appear random.