How does one design a traffic analysis resistant protocol?

The obvious way to thwart traffic analysis is to send fixed-size messages at a fixed rate, whether there's any actual information to transmit or not.

I've heard it claimed that such protocols have been used in the past for diplomatic communications: a fixed-length packet of encrypted data would be sent say, once a day to an embassy in a foreign country, and the embassy would reply with another fixed-length encrypted packet.

Of course, such protocols are on one hand wasteful of bandwidth, and on the other constrain the peak bandwidth of the encrypted channel, which is why they're not more often deployed in practice.

To apply this principle to an instant messaging protocol, let's assume that we have a trusted central server acting as a message relay.  Each user of the messaging service establishes a separate encrypted connection to the server.  (We can use existing off-the-shelf protocols like SSL/TLS for that.)  Over these encrypted connections, the clients send messages to the server, which relays them to other clients.  (Again, we can use a standard instant messaging protocol like IRC or XMPP for the client–server interaction.)

The only unusual thing we'll do is throttle the communications between the clients and the server so that each client sends the server a single block of $n_c$ bytes at time intervals of $t_c$, and the server sends a block of $n_s$ bytes to each client at time intervals of $t_s$.  These blocks might combine multiple messages, and a single message might be split over multiple blocks; also, if there isn't enough data to fill a block, it's padded with dummy data which is ignored by the receiver.

(Note that the blocks need not map to single packets in the underlying transport protocol; it's enough that each block is fully assembled before it's passed to the transport layer, so that one cannot tell how many messages a block might contain by timing the transmission layer.  In many cases, this could be easily achieved by inserting an extra "chunking" layer between the messaging protocol and the encryption layer, without either having to be aware of the chunking.)

The parameters $n_c$, $n_s$, $t_c$ and $t_s$ should be chosen to match the needs of the messaging protocol.  For simple text-based instant messaging, $t_c$ and $t_s$ might be from 0.1 to 0.5 seconds, and $n_c$ and $n_s$ might range from, say, 64 to 256 bytes.  (Even lower bandwidth might be usable if the messaging protocol was optimized for it.)  Voice messaging is likely to need somewhat more bandwidth, depending on the audio quality desired.

The reason for using a central server is that, in a typical conversation, only one participant (or at most a few) is likely to be talking at any given time; thus, the peak bandwidth requirements for the clients will probably be more or less independent of the number of participants, whereas in a naive distributed protocol they'd scale linearly with it.  (This could be avoided by using more advanced messaging protocols, but that would complicate the example.)  Of course, the server would still require bandwidth proportional to the number of clients, but that's generally the case with centralized instant messaging protocols anyway, and it could be mitigated by connecting multiple servers in a network (with fixed-bandwidth links, of course!).


What is the main difference between Anonymous HIBE and Anonymous Predicate Encryption?

Identity-based encryption (IBE) uses the receiver's identity as a public key. The sender specifies an identity that the receiver with a matching identity already has. An IBE scheme is anonymous if a ciphertext does not reveal the identity of the recipient.
"Hierarchical IBE (HIBE) is a generalization of IBE that mirrors an organizational hierarchy. An identity at level $k$ of the hierarchy tree can issue private keys to its descendant identities, but cannot decrypt messages intended for other identities."[1] (p.1; details are given in Section 2.1) (HIBE) is a scheme "in which an identity is a vector of strings $id= (id_1, \ldots,id_l)$ with the understanding that when $l = 0$ this is the empty vector $()$." See this paper, especially pp. 19 and 20, for the quote and more information. For more about IBE, see Adi Shamir's Identity-based cryptosystems and signature scheme (1984).
Anonymous IBE (A-IBE) aims to hide attributes. It is an early example of public key predicate encryption. Anonymous HIBE offers hierarchical key delegation and fully anonymous ciphertexts.[2] Anonymous HIBE is a form of IBE that does not leak the identity of the sender. D. Bonah et al. have characterized the security of HIBE as IND-ID-CCA and IND-ID-CPA (p.4; paper listed below).
In predicate encryption (PE), secret keys correspond to predicates. The master secret key owner can issue tokens that allow access to specific data. This scheme can be useful in controlling access to classified information--think of keywords associated with classified data. It is also used in biometric matching and secure cloud storage. Predicate encryption generalizes attribute-based encryption (ABE). ABE has to do with access that follows from the data's attributes, and is probably based on an access roster and policy. ABE treats a set of attributes as if it were an identity. Again, PE is useful for precise access control over encrypted data--namely, who gets to see what. Anonymous predicate encryption hides the users' identity; for example, from a server that controls users' access privileges.
The main difference between anonymous HIBE and anonymous PE is that the latter offers granular access control over encrypted data.
[1] D. Boneh, X. Boyen, and E. Goh. Hierarchical Identity Based Encryption with Constant Size Ciphertext.   In Advances in Cryptology—EURO-CRYPT 2005.
[2] X. Boyen and B. Waters. Anonymous hierarchical identity-based encryption (with-out random oracles). In Advances in Cryptology — Crypto 2006.


GPG doesn't use post-quantum signatures, so any current implementation of GPG would be unable to provide such security; regardless of the hashing algorithm used.
However, let's assume we have post-quantum signatures in our GPG implementation:
If the hash is sufficiently large, and the hash itself is secure, an attacker not knowing the HMAC key would be unable to forge a message. The issue is, for a quantum computer to be unable to do this, the hash must be at least 512 bits long.
For quantum computers a 512-bit hash behaves (approximately) like a 256-bit hash does on classical computers; while the birthday paradox states that even on classical computers a 256-bit hash ensures only 128 bits of security.
Note: for those who care, a 512-bit hash would behave with slightly more security than a 256-bit hash would for classical computers; the bits of security is relative to the cube-root of $2^k$ (where $k$ is the hash's bit length), not the square-root of the square-root.
Also, the HMAC key must be able to provide (ideally) 128 bits of security, in order to not be compromised by any attack; this applies to classical computers, as well. That means, the HMAC key must act as a 256-bit key to not be broken. This means you should choose a secure password, if you use a password for the HMAC key... But you already knew that.
Once the HMAC key is broken, the security of the hash reverts to the security of the underlying hashing algorithm.
The security of a signature depends only partly on the hash. The rest is up to the signature algorithm; since a weak signature scheme would allow me to sign whatever I want, anyway.
But my real question is "why do you think HMAC is a good idea for a signature scheme?" Doing this would allow only the people with knowledge of the HMAC key to verify signatures; and as such, anyone able to verify messages would be able to forge messages the same as a normal signature scheme.
Another note: You only HMAC the already-signed message. As such, the ability to forge signatures is unaffected; since forging a signature doesn't require the attacker to change the signature, just to collide the signature, which will inevitably lead to the same HMAC as well under your scheme, effectively removing the HMAC's security from the question.


Overview of relations between cryptographic primitives?

You'll find it in any textbook on basics of cryptography, for example Foundations of Cryptography by Goldreich. I have added a figure which sums up the relationship between the primitives: arrow represent reductions (i.e. $A\rightarrow B$ means that primitive $B$ can be constructed in a black-box manner from primitive $A$) and dashed arrows represent separations (i.e. $A$--$> B$ means that primitive $B$ cannot be constructed in a black-box manner from primitive $A$). The asterisk denotes folklore results (but feel free to correct me if it is wrong).

(1. I'll add other primitives (FHE, iO...) and assumptions (Factoring, DLP...) in due course.

Please correct any mistakes in implicaitons/separations or references.)

Abbreviations

C: Commitments
CFP: claw-free permutation
CRHF: collision-resistant hash function
DLP: discrete-logarithm problem
DS: digital signature
OWF: one-way function
OWP: one-way permutation
TDP: trapdoor permutation
OWF: one-way function
OWP: one-way permutation
OT: oblivious transfer
PKE: public-key encryption
PRG: pseudo-random generator
PRF: pseudo-random function
PRP: pseudo-random permutation
SKE: symmetric-key encryption
UOWHF: universal one-way hash function
ZKP: zero-knowledge proofs for NP

References.

[D]: Damgård. Collision Free Hash Functions and Public Key Signature. Eurocrypt’87.

[GGM] Goldreich, Goldwasser and Micali. How to Construct Random Functions. JACM’86.

[BM] Blum and Micali. How to Generate Cryptographically Strong Sequence of Pseudorandom Bits. SIAM JoC’82.

[EGL] Even, Goldreich and Lempel. A Randomized Protocol for Signing Contracts. CACM’85.

[GMR]: Goldwasser, Micali and Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM JoC’88.

[GMW1]: Goldreich, Micali and Wigderson. How to Play any Mental Game: A Completeness Theorem for Protocols with Honest Majority. STOC’87

[GMW2]: Goldreich, Micali and Wigderson. Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero Knowledge Proof. FOCS’86

[H+]: Håstad, Impagliazzo, Levin and Luby. A Pseudorandom Generator from Any One-Way Function. SIAM JoC’99.

[IR] Impagliazzo and Rudich. Limits on the Provable Consequences of One-Way Permutations. STOC’89.

[LR] Luby and Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM JoC’88.

[N] Naor. Bit Commitment using Pseudorandom Generator. JoC’91.

[NY] Naor and Yung. Universal One Way Hash Functions and their Cryptographic
Application. STOC’89.

[Rom] Rompel. One way Functions are Necessary and Sufficient for Secure Signatures. STOC’90.

[Rud] Rudich. PhD Thesis

[S] Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? Eurocrypt’98

[Y] Yao. Theory and Applications of Trapdoor Functions . FOCS’82


Is symmetric encryption with a key containing the userId passes as authentication?

First and foremost: Stop using JWT for sessions and why your cannot hack it into working.

  I do not have the knowledge to properly argue against this, apart from reciting things like "do not invent your own security", but this seems like a horrible disaster waiting to happen.

So your primary question is how to convince your coworkers that this is a bad scheme?

If telling them they shouldn't be writing their own cryptography isn't enough, tell them instead how their custom solution is more expensive, complex and less secure than the alternatives. See below for alternatives.

  What seems problematic to me is that the ciphertext is not signed so if the user can forge the request somehow he still has access to all other user data.

Signatures are asymmetric (expensive) and are (generally) larger than symmetric MACs. You'll be better off using symmetric solutions instead. Similarly encrypting is not authenticating and copy-pasting a ciphertext is not demonstrating an authority.

  Is it possible to somehow forge a request here? For example by messing around with the bits and see if the server throws an error (or what kind of error).

If these object IDs are encrypted using CTR mode, then incrementing the ciphertext still gives you the next ID. If instead the object ID is encrypted using a PRP, then you can guess a random ID in $2^{b/2}/n$ guesses assuming a $b$-bit block-size and $n$ valid IDs exist. If you have 1 billion IDs, then this is only $18446744 \approx 2^{24}$ attempts. (can someone verify?)

Cryptographically this is weak. In practice you should have rate limiting and should slow down users who make repeated attempts for invalid IDs so this might not be too bad, but with only $18$ million guesses for $1$ billion possibilities this really depends on how sensitive you think these apples are. If they have no value, no one will try. If they are sensitive, it'll be only a matter of time.

  I'm looking for easy-to-understand reasons on why it is a bad idea to do this to present a solid argument to my colleagues (or be convinced that it is not).

It is custom, slow, expensive, unverified and unnecessary!

Alternative 1: per-user isolated sets of apples

If apples cannot be shared between users then only display the ID relative to the user in question. I.e. If Alice has $3$ apples, they are $0$, $1$, and $2$. If Bob has $2$ apples, they are $0$, and $1$.

Additionally this can be bound to HTTP cookies such that malicious JavaScript cannot exfiltrate the JWT stored in LocalStorage. Better yet, this doesn't rely on JavaScript at all.

Alternative 2: capability-based sharing of apples

If apples can be shared between users, look into capabilities and macaroons.

A capability is an unforgeable, unguessable and communicable token of authority. You can only acquire a capability from someone who already holds it. Capabilities are stronger than cryptography, but they rely on trusted systems. Using keys-as-caps, cryptography can emulate a weaker form of capabilities based on knowledge (not possession). Macaroons are a cryptographic capability relying only on a secure keyed-hash (HMAC). No expensive asymmetric encryption or signatures.

Example macaroon (approximate example, see the paper for better definitions):

$$\begin{aligned}
s &= \text{new_macaroon}(\text{server_secret}, \text{nonce})\\
  &= (nonce, \text{HMAC}(\text{server_secret}, n))\\
a &= \text{add_caveat}(\text{authority}, \text{caveat})\\
  &= (\text{authority}_0, \text{authority}_{n-1}, \dots, 0 \| \text{caveat}, \text{HMAC}(\text{authority}_n, 0 \| \text{caveat})\\
i &= \text{invoke}(\text{authority}, \text{message})\\
  &= (\text{authority}_0, \text{authority}_{n-1}, \dots, 1 \| \text{message},\text{HMAC}(\text{authority}_n, 1 \| \text{message})
\end{aligned}$$

$s$ is an unrestricted credential. It is always valid. Technically the server could revoke it by the $nonce$, but this is not assumed. $a$ has additional caveats added. I.e. To expire the credential after some time, or to limit the objects or functions that may be reached or called. And finally $i$ invokes the authority to send some message to the server. If all caveats evaluate without failure, then the message is approved and evaluated.

Any time the un-invoked authority is shared we must use a secure transport to prevent a MiTM from learning the secret key. When invoking we reveal only public information and a proof binding the authority to the message. Conveniently this also makes CSRF tokens obsolete, but it does not prevent replays as-is.

Notice that macaroons do not assume the system has "users" or that revocation or expiration are required. The server is responsible to selecting the initial caveats, and the user may add any caveats they want when they share the credential. If Alice shares her credential with Bob to access an $\text{apple}_5$, then Bob can access only this apple and not any of Alice' other apples. Nor does this credential assume signatures.

Signatures only make sense when a large (or unknown) audience needs to verify the integrity offline. Your server is the only one producing and verifying these credentials correct? If your users need to authorize a third party service to perform some actions on their behalf, they share a provisioned credential with any caveats they want. Additionally, the user can include a special kind of caveat that pings back to their own server to ask for permission to perform some action. This enables the user to revoke the capabilities.

The users can add caveats and distribute them offline without interacting with your servers.


Homomorphic Encryption and Semantic Security using Lattices?

The LWE assumption

I think we should start from the LWE assumption.
Let $n$ and $q$ be integers and let $\chi$ be a distribution over $\mathbb{Z}_q$. We often take $\chi$ as a Gaussian with small variance. (We take an error $e$ from this distribution $\chi$ and assume that $|e| \ll q$.)

The LWE assumption states that any efficient adversary cannot distinguish two oracles if a vector $\mathbf{s} \in \mathbb{Z}_q^n$ is chosen uniformly at random;

one is the random oracle that returns $(\mathbf{a},b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ chosen uniformly at random
the other is the LWE oracle that returns $(\mathbf{a},b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$, where $\mathbf{a} \gets \mathbb{Z}_q^n$, $e \gets \chi$, and $b = \langle \mathbf{a},\mathbf{s} \rangle + 2e$.
(Note: I replace $e$ with $2e$ from the correct definition. This is a minor problem.)

The LWE-based Symmetric-key Encryption

Keeping the assumption in mind, we next review the symmetric-key encryption scheme appeared in your quotation.

$\mathsf{Gen}(n,q)$: Choose $\mathbf{s} \in \mathbb{Z}_q^n$ uniformly at random. The secret key is $\mathbf{s}$.
$\mathsf{Enc}(\mathbf{s},m \in \{0,1\})$:

Choose $\mathbf{a} \in \mathbb{Z}_q^n$ uniformly at random.
Take a sample $e$ from $\chi$.
Compute $b = \langle \mathbf{a},\mathbf{s} \rangle + 2e + m \in \mathbb{Z}_q$.
Output a ciphertext $c = (\mathbf{a},b)$.

This encryption scheme is apparently IND-CPA.
In the IND-CPA game, denoted by $G$, the adversary has an encryption oracle which has a secret key $\mathbf{s}$.
Let us replace the encryption oracle with the random oracle and call this game as $G'$.
It is easy to show that $G$ and $G'$ are indistinguishable under the LWE assumption.

Answer

  How can this be semantically secure if the same mask $\langle \mathbf{a},\mathbf{s} \rangle$ is being used on messages? That is, two different encryptions of the same value (say "10") would produce the same cipher texts.
  If I added two numbers (say "10" and "100"), wouldn't they need to be masked with the same $\langle \mathbf{a},\mathbf{s} \rangle$?
  Or does this scheme require additional accounting somewhere to allow for different $\langle \mathbf{a},\mathbf{s} \rangle$ masks?

By this definition, two ciphertexts $c_1, c_2$ of plaintexts $m_1, m_2 \in \{0,1\}$ under the secret key $\mathbf{s}$ are written as

$c_1 = (\mathbf{a}_1, b_1) = (\mathbf{a}_1,\langle \mathbf{a}_1,\mathbf{s} \rangle + 2e_1 + m_1)$ and
$c_2 = (\mathbf{a}_2, b_2) = (\mathbf{a}_2, \langle \mathbf{a}_2,\mathbf{s} \rangle + 2e_2 + m_2)$.

If we can obtain two ciphertexts with the same mask, that is, two ciphertexts with the same randomness $\mathbf{a}$, they are not IND-CPA secure.
We have

$c_1 = (\mathbf{a}, b_1) = (\mathbf{a},\langle \mathbf{a},\mathbf{s} \rangle + 2e_1 + m_1)$ and
$c_2 = (\mathbf{a}, b_2) = (\mathbf{a}, \langle \mathbf{a},\mathbf{s} \rangle + 2e_2 + m_2)$.

It is easy to check the relation $m_1 - m_2 \bmod{2}$ by
the relation $b_1 - b_2 \equiv 2e_1 + m_1 - (2e_2 + m_2) \bmod{q}$.
Since $e_1, e_2, m_1, m_2$ is "small", $b_1 - b_2 \bmod{q} = 2(e_1 - e_2) + m_1 - m_2 \in [-q/2,q/2]$. Therefore, the difference $b_1 - b_2 \bmod{q}$ reveals the relation $m_1 - m_2 \bmod{2}$.

Finally, I mention that the scheme is additively homomorphic.
Suppose that we have two ciphertexts

$c_1 = (\mathbf{a}_1, b_1) = (\mathbf{a}_1,\langle \mathbf{a}_1,\mathbf{s} \rangle + 2e_1 + m_1)$
$c_2 = (\mathbf{a}_2, b_2) = (\mathbf{a}_2, \langle \mathbf{a}_2,\mathbf{s} \rangle + 2e_2 + m_2)$.

Consider $c_1 + c_2 \in \mathbb{Z}_q^n \times \mathbb{Z}_q$.

$c_1 + c_2 = (\mathbf{a}',b')$
$ = (\mathbf{a}_1 + \mathbf{a}_2, \langle \mathbf{a}_1 + \mathbf{a}_2, \mathbf{s} \rangle + 2(e_1 + e_2 + (m_1 + m_2 \mathbin{\mathrm{div}} 2)) + (m_1 + m_2 \bmod{2}))$.

Multiplication is tricky. I recommend to read the BGV paper, which employs "tensor" to make notation simpler than the BV paper.


Using chi square for distinguishing between compressed and random data

The NIST tools are a good starting point.

There is no general-purpose algorithm that will always distinguish compressed from random data

However, if you want to try the chi-squared test, you can compute a histogram of the frequency of all byte values (how many 0 bytes you saw in the data, how many 1 bytes you saw, etc.), and then use the chi-squared test to test whether this appears to deviate from what you'd expect for uniform-random data.


As pointed out by Chris Peikert in his comment, the actual definition must be

$f_\mathbf{B}(\mathbf{x}) = \mathbf{x} \mod \mathbf{B} = \mathbf{x} - \mathbf{B} \lfloor\mathbf{B}^{-1} \mathbf{x} \rfloor$.

we can see that the codomain of such $f_\mathbf{B}$ is the fundamental region $\mathcal{P}(\mathbf{B})$ as follows:

Write any given $\mathbf{x}$ as a linear combination of the columns $\mathbf{b}_1$, ..., $\mathbf{b}_n$ of $\mathbf{B}$, that is:

Let $\mathbf{x} = \mathbf{B}\mathbf{z}$ for some $\mathbf{z} \in \mathbb{R}^n$ (it's possible because $\mathbf{B}$ is fullrank, so its columns  span $\mathbb{R}^{n}$).

Let $\mathbf{t} = \mathbf{z} - \lfloor \mathbf{z} \rfloor$, so $\mathbf{t} \in [-1, 1)^n$ and $\mathbf{x} = \mathbf{B}(\mathbf{t} + \lfloor\mathbf{z} \rfloor)$.

Thus,

$f_\mathbf{B}(\mathbf{x}) = \mathbf{x} - \mathbf{B} \lfloor\mathbf{B}^{-1} \mathbf{B}(\mathbf{t} + \lfloor\mathbf{z} \rfloor) \rfloor = \mathbf{x} - \mathbf{B} \lfloor \mathbf{t} + \lfloor  \mathbf{z} \rfloor \rfloor = \mathbf{x} - \mathbf{B} \lfloor  \mathbf{z} \rfloor = \mathbf{B}\mathbf{t}$

and $\mathbf{B}\mathbf{t} \in \mathcal{P}(\mathbf{B})$ by definition of $\mathcal{P}(\mathbf{B})$.


What algorithm does PGP use to encrypt email?

According to How PGP Works it uses a hybrid approach that generates a secret key for symmetric encryption.  The wikipedia page for GPG then indicates that CAST5, Camellia, Triple DES, AES, Blowfish, and Twofish are the supported ciphers.


Verification of NIZK proof with algebraic MACs

Yes, you are correct that this is an error. I discovered the same thing myself a couple of months ago and emailed the authors. Greg Zaverucha responded and agreed with me. More specifically, this was what he agreed with:
"
Hi,
I've been studying https://eprint.iacr.org/2013/516.pdf and in Appendix E.2 part 3(b) in the verification algorithm, there appears to be an error, wanted to check it with you:
In order for the verifier to reconstruct the challenge hash $c$, you concatenate items in the preimage, the 4th item (or set of items) is given as:
$$C_{m_{i}} . g^{s_{m_i}} . h^ {s_{z_i}} \quad \forall i$$
but this does not appear to be the correct way to construct the items $C_{m_i}$~ that were in the prover's challenge hash preimage. As far as I know the correct way to reconstruct the $C_{m_i}$~ terms would be:
$$(C_{m_i})^c . u^{s_{m_i}} . h^{s_{z_i}} \quad \forall i$$
(where $c$ lower case is of course the challenge hash provided by the prover).
"
I figured out what it should be based on analogy with sigma protocols in general, but it's been a little while; hopefully you can see that this version makes sense.
Additional edit: today I have been studying this again, and realised that you were also stating that the final element of the hash preimage construction also does not validate. Looking at it carefully I can see there is a very similar issue: $V$ should be replaced with $V^c$.


HD (Hierarchical Deterministic) Keys using Safe Curves?

Jason Law and Dmitry Khovratovich published a paper on how to do this with the Ed25519 curve.
http://ieeexplore.ieee.org/document/7966967/?reload=true

I don't know for sure if this exact method can be applied to curve 41417 but I bet with further research it probably could.


Why develop new stream ciphers when block ciphers can be trivally made into streams?

The biggest reason is performance. Stream ciphers are generally faster than block ciphers and perform fewer operations. Stream ciphers only need to generate a pseudorandom output while block ciphers need to be pseudorandom permutations. So when you create a steam cipher out of a block cipher, you are doing a lot more work to get the same effect. To get an idea, look at how much more work is required to encrypt 16 bytes with AES than RC4.


DSA, RSA, ECDSA etc - which one is cheapest for signing?

From these three, ECDSA is faster - it does arithmetic with smaller numbers, and is thus faster. (RSA verification is faster than ECDSA, even though it uses larger numbers, because it computes a exponentiation by a small number.)

Still, elliptic curve Schnorr signature should be around 5-10% faster than ECDSA (or even more in a side-channel resistant implementation) since it does not require an inversion modulo the curve order. And as mentioned, there is also Ed25519, which uses a special, non-standard curve in order to be more efficient.


Known-plaintext attack on Blowfish in ECB mode

If there was a full 64-bit block of known plaintext, there would be a very fast attack using precomputation.  You can build a precomputed table of all $2^{40}$ ciphertexts.  Once you've got the precomputed table, recovering a key (given a ciphertext) would require just a single lookup in the table, so recovering a key would be extremely fast.  Storing that table would require something like 5 Terabytes of storage, which isn't too bad: it might cost you \$300 or so to buy 5 TB of storage.  The precomputation takes $2^{40}$ trial encryptions (key schedule + a single block encryption using Blowfish), e.g., 64 days for your implementation.  Once you've built the precomputed table, cracking each file/ciphertext could be done almost instantaneously.

If 5 TB of storage feels like too much, a variant of this would be to use the Hellman time-space tradeoff (or, if you prefer the "hyped" version, "rainbow tables").  That attack also requires a precomputation that takes about the same amount of time: $2^{40}$ trial encryptions.  However, its storage costs are much lower: storage for a table containing about $2^{27}$ entries (instead of $2^{40}$ entries), which corresponds to about 700 MB of storage.  The trade-off is that cracking each file/ciphertext takes a bit longer: about $2^{27}$ Blowfish trial encryptions, or about 700 seconds.  So, once you've built the precomputed table, cracking each file/ciphertext can be done very quickly: not instantaneously, but much faster than exploring the entire space of all $2^{40}$ keys.

These precomputation attacks are not of any benefit if you only have a single file to crack, but if you expect that you'll want to crack multiple files/ciphertexts, then the precomputation attacks can be beneficial: they allow you to amortize the cost of the precomputation across many different files/ciphertexts.

However, you say that you only have 32 bits of known plaintext, not a full 64-bit block of known plaintext, so these precomputation attacks are presumably not applicable to your particular setting.

FYI, the Isobe-Shibutani paper is not going to be helpful to you.  Their basic attack on reduced-round Blowfish takes at least $2^{160}$ steps of computation and thus is completely impractical -- not to mention that it only attacks a reduced-round variant of Blowfish with 8 rounds, whereas the real Blowfish uses 16 rounds.  Their attack on the full 16-round Blowfish takes $2^{288}$ steps of computation, so is ridiculously impractical.  In short: that paper is completely irrelevant to any real-world attempt to mount key-recovery attacks on Blowfish.


Here's an approach that corrects some errors:

Alice has a bitstring S that is indistinguishable from random that she wants Trent to know. (Perhaps it's actually a ciphertext that only Bob knows how to decrypt).
Alice generates 5 fresh new random bit-strings pM, pN, pP, pQ, and pR just as long as the original random bitstring S.
For each bit of S, Alice checks the the corresponding 5 bits of the random strings pM, pN, pP, pQ, and pR. If the majority of those 5 bits is the same as S, Alice keeps that bit the same, otherwise Alice flips all 5 bits, generating 5 modified versions of those random strings M, N, P, Q, and R.
Alice sends M, N, P, Q, and R to Trent.
For each bit of the messages M, N, P, Q, and R, Trent uses 5-modular redundancy -- the majority of the 5 bits -- to attempt to recover the string S.

Because pM, pN, pP, pQ, and pR are completely randomly generated, and S is indistinguishable from random, Trent is still unable to distinguish M, N, P, Q, and R from random bit-strings.

For any one bit-position, the 5 bits can be in any one of 32 possible patterns with equal probability.
If there is no bit error in some particular position, Trent always recovers the correct bit of S at that position.
Trent can usually correct any single-bit-flip error across a row of 5 bits.
(Given any 1 of the 5 bit positions ahead of time that will suffer a single-bit-flip error, 20 of the 32 possible patterns result in Trent recovering the correct bit of S, but the remaining 12 possible patterns would result in Trent decoding an erroneous bit).

I suspect there is a better encoding that allows Trent to always correct any single-bit-flip error.
Perhaps somehow forbidding the 12 vulnerable patterns, even though that allows statistical tests to conclude the collection of strings M, N, P, Q, and R are not completely random?


Digital signature that is only verifiable by one specific person

What you seem to be looking for is deniable authentication.

This is actually a somewhat stronger property than what you're asking for: it guarantees that the recipient (let's call him Bob) cannot cryptographically convince anyone else that the sender (let's call her Alice) signed the message, even if he discloses all his private keys, simply because the protocol guarantees that knowing Bob's (and/or Alice's) private key is both necessary to verify the signature and sufficient to forge it.  So Bob, seeing a message with a valid signature and knowing that he didn't create it himself, can be confident that Alice must have sent it — but he cannot use the signature to convince anyone else of that, since he could've just as well created the signature himself.

The simplest way to achieve this kind of authenticated but repudiable communication between two parties is to use a symmetric-key authenticated encryption scheme (or, if message privacy is for some reason not required or desired, just a plain MAC).  With these schemes, Alice and Bob know the same secret key that is used both to authenticate the messages and to verify their authenticity.  Thus, trivially, anything Alice can do (such as to create a valid authenticated message claiming to be from Alice to Bob) Bob — or anyone else who knows the secret key — can do as well.

The main drawbacks of such symmetric-key schemes are that they require a separate secret key for each pair of communicating parties (which could become cumbersome if there are potentially many such parties) and that the secret keys must somehow be securely shared between each pair of parties.  This would be easy if we had an encrypted and authenticated secure channel between each pair of parties, but since that's exactly what we're trying to set up here, that creates a kind of a chicken-and-egg problem.

One way around these issues is to use public-key encryption to share the secret keys.  In particular, we can use the Diffie–Hellman key exchange to establish a shared secret between any two parties, as long as they know each other's public keys (and, of course, their own corresponding private keys).

The Diffie–Hellman key exchange is often illustrated as an interactive protocol, but actually the only interaction it needs is for each party to send their public key to the other (which they may do in advance, e.g. by publishing them on some semi-trusted central key server).  After that, any time one party (say, again, Alice) wants to send a message to another party (say, Bob), she can just combine her private key with Bob's public key to obtain a secret value known only to her and Bob, and then use this secret (possibly after feeding it through a suitable KDF) as the symmetric secret key for an authenticated encryption scheme as described above.

Anyway, for practical use, you don't actually need to implement any of this yourself, since there are plenty of existing implementations of such schemes.  For example, the NaCl library (and its various derivatives, such as libsodium) provides the crypto_secretbox function for symmetric-key authenticated encryption and the crypto_box function for repudiable authenticated public-key encryption.  If you don't particularly need to roll your own encryption scheme, I would encourage you to use those, or some other similar established and well studied implementation.

(One possible reason why you might want to do that is for nonce misuse resistance.  The NaCl functions described above require you to assign each message a unique nonce, and its security can be badly compromised if you ever reuse the same nonce for two distinct messages encrypted with the same secret key.  There are authenticated encryption schemes based on the SIV construction that are much more resistant to such nonce misuse, such as AES-SIV, AES-GCM-SIV or even HS1-SIV, but NaCl crypto_box does not currently support them.  If you wanted, you could reimplement the "hashed Diffie–Hellman" part of crypto_box using crypto_scalarmult and use the resulting key with some SIV-style symmetric encryption scheme, but that requires a lot more effort and care than just using crypto_box as it is.)

Ps. On a slight tangent, note that Diffie–Hellman alone doesn't entirely solve the key distribution problem, since it still relies on the parties being able to share their public keys without anyone tampering with them.  In particular, if Alice and Bob are trying to exchange public keys over a channel controlled by a middle-man Mallory, he can just replace Alice's and Bob's public keys with his own, and thereafter intercept any messages encrypted with those keys, decrypting and re-encrypting each message before passing it on.

(Of course, if Mallory ever stops doing that, Alice and Bob will find themselves unable to communicate until and unless they re-exchange public keys.  But to Alice and Bob, that just looks as if someone just started attacking their communications by intercepting their messages and replacing them with invalid forgeries.  Without some alternative communications channel, there's no way for Alice or Bob to know whether an attack just started or whether one just stopped.  And even if they do somehow figure it out, it may be too late.)

One way to try to solve this problem is to set up some kind of a public key infrastructure where third parties can sign Alice and Bob's public keys in order to vouch for their correctness.  But setting up a reliable PKI is far from a trivial task, since at some point you still need to trust someone.


What if the hash code of the genesis block (first block in the block chain) is changed?

The genesis block is embedded in the chainblock (the hash of all the transactions since the bitcoin network was powered on).
Now, from your question I deduce that you know little about cryptography and in particular hash functions and the blockchain protocol so I will try to explain myself in the simplest (and obviously incomplete) way possible:

Blockchain can be corrupted only if the majority of the network work to corrupt it, this is the (in)famous 51% attack.
If I modify the hash on my client, this change does not involve anything on the network as 99.999% of clients have a different version of the hash (the correct one) and the majority is the authentic. This is one of the main strenghts of the blockchain: the fact that it is decentralized and that transactions must necessarily be accepted and registered by multiple clients (at least 51%) to be verified. Very democratic isn't it?

In any case, I believe it is a good thing that you want to inform yourself about how the protocol works before throwing into trading. Many (too many) people invest in bitcoins or other crypto without even knowing what they are ... after all, when you invest in a cryptocurrency, you should do it because you believe in the potential of the protocol that supports it and not just for fashion or to make (or lose) money.

If you want to know more about bitcoin, the starting point could be to learn some basic cryptography, especially Hash: Section 8 for Hashing functions.
         Once you have become familiar with these concepts, I suggest you read the original publication in which Satoshi Nakamoto (we dont know who he/she/them is/are) illustrates the bitcoin protocol:
a milestone of our time.


DES f function injective for no fixed subkey?

First thing to observe is that a DES-like confusion function can be a permutation, depending on the contents of the S-boxes. DES S-boxes are formally defined as $6\rightarrow 4$ functions, with the leftmost and rightmost bits selecting a row, which itself defines a $4\rightarrow 4$ function applied on the four central bits of the input. This last function is, in DES, a permutation (over the space of 4-bit strings). If we change S-boxes such that all these $4\rightarrow 4$ permutations are the identity function, then, for subkey $0$, the whole confusion function is the identity, which is bijective. Therefore, we must take into account the exact definition of the S-boxes in DES, since the answer will depend on that.

Some notations:

We number bits from left to right, starting at 1 on the left (this is the notation used in the DES specification).
Subkey is $K$ and has length 48 bits.
We consider the function $f(K,R)$ for a 48-bit subkey $K$ and 32-bit input $R$. This is the DES confusion function, with the expansion step, but without the permutation $P$.

We can observe that changing bits 3 of the subkey does not change the injectivity status of the function: if there are two inputs $R$ and $R'$ such that $R \neq R'$ and $f(K, R) = f(K, R')$, then $f(K \oplus M_1, R \oplus M_2) = f(K \oplus M_1, R' \oplus M_2)$ for masks $M_1 = 2^{45}$ (i.e. bit 3 is set, all other bits are cleared) and $M_2 = 2^{30}$ (i.e. bit 2 is set, all other bits cleared). This applies to all bits $6j+3$ and $6j+4$, for $0 \leq j \leq 7$.

Similarly, if we flip both bit 5 and 7 of $K$, the injectivity status of the function is not changed: the assertion above stands for $M_1 = 2^{43}+2^{41}$ and $M_2 = 2^{28}$. This applies to all pairs of bits $6j+b \bmod 48$ and $6j+b+2 \bmod 48$ for $0 \leq j \leq 7$ and $b \in \{5,6\}$.

Using these two facts, we can say that $f$ is be injective for a subkey $K$ if and only if it is injective for subkey $K'$ such that:

$k'_i = k_i$ if $i \bmod 6 = 1$ or $2$;
$k'_i = 0$ otherwise.

Thus, if we want to check things exhaustively, we only have $2^{16}$ possible subkeys $K'$ to investigate.

At that point, I made a small program which tries all subkeys $K'$, using Floyd's cycle detection algorithm to find a collision. The program is written in C and can be found there. On my laptop, this program takes on 66 seconds to go through all possible $K'$, and finds a collision for each one.

Therefore, assuming that this program is correct (you can check the collisions, there are "only" 65536 of them), and modulo the epistemological reservations that some mathematicians have about computer-assisted proofs, one can say that it is proven that the DES confusion function is never a permutation, for any possible subkey $K$.


How can I decode a substitution cipher in the form of pictures?

There is little difference with regards to any attack method that is already available for substitution ciphers. You can do frequency analysis, for instance. If a single symbol is used for the letter e or for space then it should be easy to find.

It's easy to see that there is no fundamental difference: just replace each symbol with a character and you're back to a normal substitution cipher.

If there are symbols that represent sets of characters or if there are more symbols for the same character then the cipher will of course be harder to crack.


No. For any key $k$ your ciphertext $c$ has a corresponding plaintext $p$ (since block ciphers are families of bijections). Hence, since you can't (in)validate plaintexts, you can't discard any possible key.

Or, in other words: If someone claimed the right key was a certain $k$, you had absolutely no way to ever prove them wrong.


With Encrypt-then-MAC, and flexible protocols, do I need to authenticate the authentication?

Though a full analysis would require some details and, presumably, a lot of work, guidance can be obtained from what is done in SSL: at the end of the handshake, a verification step occurs with the Finished messages. These messages are protected with the negotiated algorithms and keys (both encryption and MAC) and, crucially, the contents of a Finished message are a one-way hash of all the previously exchanged handshake messages, thus including the cipher negotiation, the server's public key, the key exchange messages... For instance, see this article for some discussion on the subject. The security of the SSL handshake against various types of active attacks relies heavily on the contents of these Finished messages, and (this must not be forgotten) on their mandatory aspect (client and server ought to refuse to send or receive application data until they have sent/received appropriate Finished messages).

With such a verification, a client (or server) implementing SSL will ensure some security level against active attacks on the handshake which should be at least as great as the weakest of the MAC algorithms that the client (or server) accepts to use. Getting beyond that level (i.e. showing a posteriori that a given connection was protected with the strength of the MAC algorithm which was apparently used, regardless of whether some system would have accepted a weaker MAC) can get tricky.


note: I am unsure that you can get an answer for your question as there's not enough technical information in the paper to reproduce (for me anyway) the results.  However, you could work through it in the following method for any ring oscillator.

A ring oscillator is comprised of a ring built of an odd number of inverters. The simplest model of this oscillator can be represented with a single inverting transfer function $f(\cdot)$, a delay of $\tau$ and a feedback loop that meet the Barkhausen criteria. The $f(\cdot)$ function can be approximated with a hyperbolic tangent. However, an electrical model must involve additional lumped components (low pass filter) namely the input capacitance $C$ and the output resistance R that represent inverter's active region behavior.  The $RC$ is particularly pertinent due to the FPGA architecture in this case.  The noise processes of the circuit are represented in the model by $N(t)$.

The purpose of the "PUF" in this case is to have unique delay, which is the $N(t)$.  The momentary $N(t)$) value results from the sum of Gaussian noise and two-way shot noise sources (it's not thermal noise, which is actually shot noise in a semiconductor and every textbook that says otherwise is incorrect.  You can derive it from 1st principles) with a zero mean value and ${\sigma^2_N}$ variance.

The ring oscillator manifests oscillations due to the propagation delay $\tau$ in delay in the feedback loop.  In the image, $\Sigma$ is the contributions of $N(t)$  You then look at this behavior as non-linear delay such that

$$ \widetilde{\dot{\mathbf{U}}}_i = \frac{f(\widetilde{U},t-\tau)-\widetilde{{\mathbf{U}}}_i+N(t)}{RC},$$

where $f(\cdot)$ is the transfer function.  The transfer function in this case is the PUF behavior, which the authors did not model.  Also, it would be dependent on not only the semiconductor fab mismatch, but the router.  The question is "does the RC of the routing contribute more than the PUF circuit variance".  There's no way to know.

What they should have done is the following:
Let's assume that randomness is a function of the nondeterministic contribution of N(t) and a derivative of the random variable $\widetilde{{\mathbf{U}}}_i$.  The behavior of the circuit can be explained when the random part in the above equation is omitted and a we can linearize it with a small signal model.  In this case, the linearized $f(\cdot)$ function brings an amplification coefficient g, therefore, the circuit can be described with a linear differential equation as

$$\frac{d u_i}{dt} = \frac{-g u_i(t-\tau)-u_i}{RC} $$

You can then take the above and put it through a Laplace transform and find the zeros resulting in

$$ s+ \frac{1+g e^{-\tau s}}{RC}=0$$

The solution can then represented as a Fourier series with periodic responses from the time domain.  You can then use these modeled for each oscillator in the chain to understand the contribution of each oscillator.   For this reason, I do not believe that their analysis is adequate enough to make assumptions about the hamming distance in any method that is qualitative.  It is a quantitate measurement, and I am not convinced by that paper that the authors know how their system works.

I have no idea why this paper is so highly cited.  I would not pass muster in a circuits journal, and honestly, it just complicates things.  You can already consider an inverter to have a unique transfer function due to surface roughness and manufacturing defects.  I do not know either of the original authors, but I would love to know why this was thought to be a good idea.


Any stream cipher with avalanche effect?

A stream cipher, by definition, acts on individual bits at a time. This effectively means that bits later in the plaintext cannot affect bits around the beginning of the ciphertext. It can, however, feed the ciphertext back into the state of the PRNG to affect all future bits. This can be seen in the CFB (Cipher Feedback) block cipher mode. It acts similarly to a stream cipher, in that each ciphertext bit can be drawn one at a time, but they feed back into the system to affect all future bits.


How does Feistel cipher create diffusion between blocks?

If a message is longer than the block length, how would changing one
  part of the message affect the encryption of other parts of the
  message?

That really doesn't depend on the block cipher in use, which may be a feistel cipher like DES or a SP network like AES, but on the mode of operation.

Now the answer to this really depends on the actual mode chosen. Note anyways: The encryption process is never message dependent, only the encryption result shows observable differences between the modes.

If you use CTR or OFB, then any change in the message bits will only affect the corresponding ciphertext bits and no other. The same applies for all modes using CTR internally (e.g. nearly all authenticated encryption modes).
For CBC, this will scramble the current block and thus also scramble the "encoded message" for the next block and thus a message change is fully propagating until the last block in a randomized fashion starting at the block of change (this also makes CBC somewhat suitable as a message authentication code aka CBC-MAC).
As for CFB, it's similar to CBC. A change in the plaintext will propagate infinitely, as this will change the current ciphertext block and thus the "xor-pad" for the next block.
ECB (which you really shouldn't use) behaves much like CTR and OFB in this regard, with a change in the plaintext influencing the ciphertext at block-level granularity instead of bit-level.

  If L1 and R1 are considered one block, how would they affect the next
  blocks or the previous blocks of the message?

This is not well-known or -defined usage of feistel networks. However, you either create a larger block cipher this way and thus "moving" the problem of the mode to a higher granularity or you're defining some sort of mode operating on two blocks of data at once, like $C_1||C_2=E_K(P_0,P_1)||E_K(P_1,P_2)$ which would suffer from similar problems as ECB but at a higher granularity level (e.g. you can detect when a pattern of three blocks repeats).


Definitions / Introduction

We define (this is solely for our example):

$enc()$ and $dec()$ as the encryption and decryption function using CBC mode, with a constant key. any block cipher will do
$\oplus$ is the XOR operation.
$n$ the amount of plain text blocks.
the length of a block in bytes is $16$ (i.e. 128 bit).
$m_1$ through $m_n$ the plain text blocks.
$c_0$ through $c_n$ the cipher text blocks, whereas
$c_0$ is the Initialization Vector (i.e. we have one more block here!).
for each block, a second index points to the byte, i.e. $m_{1,0}$ is the very first byte of our plain text.
$x_1$ through $x_n$ are the intermediate decryption values, after $dec()$ and before XOR.
the single equal sign $=$ is used for assignments, the double equal sign $==$ for comparisons.

To explain what $x$ means, here's the CBC decryption formula again. For each encrypted block $c_i$, we determine $m_i$ by:

$m_i$ = $x_{i} \oplus c_{i-1}$,(and the value $dec(c_0)$ is also named $x_0$)

For the very first block, we use the IV as follows:

$m_0$ = $dec(c_0) \oplus iv$

I recommend taking a quick glance at these images for decryption and encryption (It's not gonna hurt to read the whole Wikipedia Article too).

Scenario

For this attack we need a so called padding oracle, e.g. a web application.
This padding oracle accepts arbitrary cipher texts and gives different messages about whether the plain text is invalid or the decryption has failed.

Let's imagine this padding:

For all plain texts the last block is padded to a length of 16 bytes as follows, the end.\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x08.
If the last block is 15 bytes long, the padding is simply \x01.
If the last block is 16 bytes long, that is if the length of the message is a multiple of 16, then a block of 15 arbitrary values followed by \x10 is appended.
This means, the last block is always filled with zero to fifteen \xFF bytes up to the last one, which gives the length of our padding.

After decryption, one might now read the very last byte and cut off the given amount of bytes at the end. A value equals 0 and above 16 is invalid and returns a padding error.

We define the Oracle as follows:

$$
  O(c) = \left\{
  \begin{array}{l l}
    0 & \quad \text{if $c$ has a valid padding and }\\
      & \quad \text{decryption yields a well-formed plain text} \\
    1 & \quad \text{if the padding was valid, but the plain text}\\
      & \quad \text{was not well-formed (contained \xFF)} \\
    2 & \quad \text{if $c$ has an invalid padding}\\
  \end{array} \right.
$$

The web application expects plaintext as XML (or JSON or whatever) and will report a different error, when parsing fails. For our simplified scenario, let's just say there exists an evil character the plain text (after removing the padding) must not contain, e.g. \xFF

The attack

For this attack to work you need a valid ciphertext $c$, it is not required to know the correct plaintext value $m$.

We will start decrypting block by block, byte by byte. We start with the very first block and it's last byte.

Let's take the very first two cipher text blocks
$c_0c_1$, and send them to the oracle. Since $c_0$ is just the IV, the oracle  gets the first block (16 bytes) of plain text. Now, this depends on the value but it's pretty likely that the padding will be wrong, so you'll get a padding error.

Now by XORing the value $j$ from \x00 through \xFF to the very last byte of your $c_0c_1$ block you will get a total set of 256 different results. These results, let's call them $\tilde{C}_j$, make up cipher texts with the last byte in all possible values from \x00to \xFF - randomly distributed though.
Sending all of them to the oracle will yield 16 for which $O(\tilde{C}_j) < 2$. This means, that the last byte decrypted to valid bytes like \x01 through \x10. Of these 16 values for $j$, one must correspond to the plain text byte \x10. Bitwise comparison will help you notice, that they all have the very same fifth bit (counting from the right, where the rightmost is 1), except one. The exception results to the one that corresponds to 0x10. Let's memorize this $j$-value as $s$.

Whatever value $s$ has, we can XOR it with \x11, which will then result to the plain text \x01. We now have a block with a valid \x01 padding. (Oh, btw. $s \oplus j$ is the last plain text byte for $c_1$)

Now that we have a block with a valid \x01 padding, we have 15 more bytes to find.
We know that whenever we have an invalid byte \xFF in the plain text, the web application will stop and say so.
So for now, we can go through each byte and find the plain text as following:

  let $c$ be the current block and $p$ the plain text result
  for $i$ from 1 to 8 (each byte in the block):
  $\quad$ for $j$ from 0 to 255 (all ascii values):
  $\quad$ $\quad$ $\hat{c}_{i,j} = c_0c_1...(c_i \oplus j)...c_n$
  $\quad$ $\quad$ if $O(\hat{c}_{i,j}) == 1$:
  $\quad$ $\quad$ $\quad$ $p_i = j \oplus 0xFF$

Repeat this procedure with block pairs $c_1c_2$, $c_2c_3$, ...

Disclaimer

This is a simplified example and I tried to highlight all simplifications where made. I am by no means a crypto expert and my knowledge is limited. If you find any unmentioned simplifications or plain mistakes, please comment/edit :)
I can highly recommend reading a good explanation of the XML Encryption padding oracle in this blog. The paper about the attack is a pretty good read too: Breaking XML Encryption

TODO: This post is lacking a good explanation on why the CBC scheme is malleable and I wouldn't mind if there was a good graph to include.


So your protocol goes like this:

Alice generates a key pair $(a_{priv}, a_{pub})$ and sends $a_{pub}$ to Bob.
Bob generates a key pair $(b_{priv}, b_{pub})$ and sends $b_{pub}$ to Alice.
Alice generates a message $m$ and sends $Enc(Sign(m, a_{priv}), b_{pub})$ (or $Sign(Enc(m, b_{pub}), a_{priv})$, I'm not sure which of both is usually used by PGP) to Bob.
Bob decrypts and checks the signature to get a message $m'$.
By a video call both verify that $m' = m$.

Your key verification scheme is based on two ideas:

If Bob did succeed to decrypt some message encrypted by Alice using $b_{pub}$, then Bob must be in possession of the corresponding private key $b_{priv}$.
If Alice knows the content of a signed message which could be verified using $a_{pub}$, then Alice must have been the signer and be in possession of $a_{priv}$.

But this doesn't work in presence of a man-in-the-middle attack for the previous key exchange and the exchanged message.

Assume Eve is able to intercept all messages between Alice and Bob.

Then the attack goes this:

A → E: $a_{pub}$
Eve generates a new key pair $(a'_{priv}, a'_{pub})$.
E → B: $a'_{pub}$
B → E: $b_{pub}$
Eve generates a new key pair $(b'_{priv}, b'_{pub})$.
E → A: $b'_{pub}$
A → E: $Enc(Sign(m, a_{priv}), b'_{pub})$
Eve decrypts the message, strips the signature and re-signs and re-encrypts.
E → B: $Enc(Sign(m, a'_{priv}), b_{pub})$
Bob checks signature and decrypts, and gets the same $m$ as sent by Alice.
Video call verification shows that "everything is okay".

If the message also contains parts of the key to be used, that would have to be changed by Eve as well, of course.

So no, you can't get around checking the actual finger print of the keys (or something derived from it).


Implementing RSA with small integers in CUDA

It is of course possible to combine multiple operations on 64 bit or 128 bit to operations modulo $N$ where $N$ is a value up to $2^{1024}$, where 1024 bits is about the absolute minimum size for an RSA key (2048 bit is now being more common, at least 3072 bits is recommended).

For example, take a look at my 32 bit JCInteger class that I created for the 16 bit Java Card platform. Processors even only handle operations on single bits and combine them into 64 or 128 bit instructions resulting in operations in your GPU.

One problem is that modular exponentiation - the most inefficient part of RSA operations - can only be parallelized to a small extend, leading to speed ups of about 2 times single core operation. This is because the multiplications required to perform the exponentiation generally require the outcome of previous multiplications.

So what you will probably see is that 1-4 GPU threads (1 probably most common) will be used to implement modular exponentiation. The rest of the speedup must come from executing a lot of RSA calculations in parallel. This would be useful for instance when a lot of server authentications are required for parallel TLS handshakes.

Parallel operation could be very efficient for creating RSA keys as well. Looking for primes is embarrassingly parallel, and creating RSA keys of 8Ki size and over takes plenty of time even on the fastest CPU's. Unfortunately that doesn't mean much in the end; generally RSA keys are long term keys so there are few use cases where the - possibly huge - speedup would be useful.

Note that I found quite a few CUDA related RSA papers that simply implement RSA for very small sizes of $N$. These should be thought of as exercises rather than real implementations of RSA. This is not always clearly mentioned in the readme files or papers.


Comparing Shanks' Algorithm to Brute Force

Shanks' algorithm—also known as baby-step, giant-step, or BSGS, and known well before Shanks (English translation)—does not solve the discrete log problem faster than a brute force search, because it is an example of a generic or brute force search algorithm.  Actually it's costlier than other generic algorithms like Pollard's $\rho$, in the standard area*time cost metric that serves as a good proxy for number of joules or number of rubles you would have to spend on the computation.

Fix a group $G$ and an element $g \in G$ of prime order $\ell$.  Suppose you can compute the functions $(a, b) \mapsto a \cdot b$, $a \mapsto a^{-1}$, and $(a, b) \mapsto [a = b]$ on elements of $G$; that is, you can compute the group operation and inverse, and you can test elements for equality.  If $h = g^x$ for a uniform random exponent $x$, how can we find $x$?

This setting—where you can compute products and test equality but you know nothing else about $G$—is the generic setting; attacks in this setting are sometimes called generic attacks or brute force attacks.  If we had specific knowledge about $G$, like we do when $G = (\mathbb Z/p\mathbb Z)^\times$ for prime $p$, we might have better attacks, like index calculus with the NFS.  But we are in the generic setting.

Naive approach.
One option is to try $x = 0$ and check whether $h$ is $1$, then try $x = 1$ and check whether $g$ is $h$, then try $x = 2$ and check whether $g^2$ gives $h$, then try $x = 3$ and check whether $g^3$ gives $h$, etc.  If $x$ is uniformly distributed, the expected number of trials is $\ell/2 = O(\ell)$.  To save effort in each trial, rather than computing $g^k$ afresh each time, we can store state $s_k = g^k$ and update it by $s_{k + 1} = s_k \cdot g$ with a single multiplication.  This is the naivest approach.  Can we do a better brute force attack?

Pairwise grouping.
Consider grouping the trials into pairs:

Is $h$ either $1$ or $g$?
Is $h$ either $g^2$ or $g^3$?
Is $h$ either $g^4$ or $g^5$?
Is $h$ either $g^6$ or $g^7$?

⋮

If we succeed on the $k^{\mathit{th}}$ trial, we need only determine whether $x = 2k$ or $x = 2k + 1$.  The expected number of trials is $\ell/4$, plus a little extra work at the end.  Of course, each trial costs twice as much as before, so this doesn't win anything yet.

Common criterion.
Rather than compare $h$ to $g^{2k}$ and $g^{2k + 1}$, we can compare $h g^{-2k}$ to $g^0 = 1$ and $g^1 = g$, so that each trial performs the same test.

Is $h$ either $1$ or $g$?
Is $h g^{-2}$ either $1$ or $g$?
Is $h g^{-4}$ either $1$ or $g$?
Is $h g^{-6}$ either $1$ or $g$?

⋮

Once we have found $k$ and $\alpha$ so that $h g^{-2k} = g^{x - 2k} = g^\alpha$ and thus $x - 2 k \equiv \alpha \pmod \ell$, we can solve for $x$ as before.  The expected number of trials is still $\ell/4$, but we can precompute $g^{-2}$, and then keep a running state $s_k = h g^{-2k}$ which we can update to $s_{k + 1} = s_k \cdot g^{-2}$ by a single multiplication.  The expected number of trials is about half the naive algorithm, and the number of multiplications per trial is the same, so the expected number of multiplications is $\ell/4$, half that for the naive algorithm.  Of course, we have to do two equality comparisons for each trial, but an equality comparison is probably cheaper than a multiplication.

Wider grouping.
If a table lookup had the same cost as an equality comparison, we could make a table of $m$ different entries by precomputing $1, g, g^2, g^3, \dots, g^{m - 1}$, precomputing $g^{-m}$, and then searching as before:

Is $h$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
Is $h g^{-m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
Is $h g^{-2m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
Is $h g^{-3m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?

⋮

Once we have found $k$ and $\alpha$ so that $h g^{-k m} = g^{x - k m} = g^\alpha$ and thus $x - k m \equiv \alpha \pmod \ell$, then we can solve for $x$ as before.  Also as before, we can update the state $s_k = h g^{-km}$ with one multiplication $s_{k + 1} = s_k \cdot g^{-m}$.  The expected number of trials is $\ell/(2m)$ and the cost of each trial is (a) one multiplication and (b) one table lookup.  Thus the expected number of multiplications and table operations is $O(m + \ell/m)$, which is optimized by $m = \sqrt\ell$.

Caveat.
In real computers, storing tables costs energy and table lookups cost more time and energy than equality comparisons.  So BSGS's apparent ‘cost’ of $O(\sqrt\ell)$ multiplications, which seems to be an improvement on the naive algorithm's $O(\ell)$, is misleading in practical terms because it uses an unrealistic cost model where storage is free and an equality test costs the same as a table lookup.  Pollard's $\rho$ is a generic brute force algorithm that actually improves the cost in realistic cost models to $O(\sqrt\ell)$: it too runs in $O(\sqrt\ell)$ computation time, but it has constant space requirements and no table lookups, and as a bonus it can be parallelized to take advantage of extra die area to speed it up without changing the net cost.


Is there (this) a case in which salting is dispensable?

Passwords should use a password hashing function. Password hashing functions are different from basic cryptographic hashes, though they use cryptographic hashes as part of their construction. Password hashing functions must use salt. (Password hashing functions can also tune their time and/or memory usage, cryptographic hashes generally can't.)

So for your case, you probably don't strictly need a password hashing function. More importantly you probably want to not store the nonce in the database at all.


Constructing public key encryption schemes with desired ciphertext expansion

From your expanded comments, it appears that you hope to use encryption to do data compression; that is, you have an $N$ Megabyte input, and hope to store it in a 1 Megabyte storage, and later recover it in toto.

Sorry, but that's (probably) impossible.  If there are $2^n$ possible largeInstance's, then you cannot store them in less than $n$ bits, and be able to recover it later.

The only case where it might be achievable is if the largeInstance's have a great deal of redundancy (and so that even though they are $n \times N$ bits long, only $2^n$ values are actually possible); if so, you'd be better off looking at a data compression method, rather than an encryption method.


What is the branch number of this matrix?

The matrix is not MDS over $GF(2)$; No binary MDS codes exist and non nonbinary (over $GF(2^n)$ MDS codes would have this generator whose scalar entries are in the field $GF(2)$). Over $GF(2^n)$ The branch number, which is the minimum weight of the corresponding linear code is 4, in $GF(2^n)$ for all $n$. This covers all possible fields of interest for crypto.

Note that you just need to take the given matrix, call it $A,$ form $G=[I | A]$ over the relevant field and determine the minimum weight of the resulting code. Magma (and GAP, Pari, Python) can do this for you easily. This code turns out to be a quasi-cyclic code over the fields $GF(2^n)$ with minimum distance 4.

Edit: It seems that 4 is the limit for the minimum distance of this type of code. In particular a $16\times16$ version, still has minimum distance only 4, for the fields $GF(2^n)$ where $n=1,2,\ldots,8.$ I assume $n=8$ is of interest to the OP, since it corresponds to having bytes as code symbols, as in AES.

This was checked on Magma as well.


I'm using AES encryption in CTR mode that takes a key generated by a KDF (script).

You should use authenticated encryption unless you have a strong reason not to.  For example, AES-GCM, or AES-CTR with HMAC-SHA256 in encrypt-then-MAC composition like the scrypt(1) utility uses.  If you're not sure, use authenticated encryption.

If you are sure you have a strong reason not to use authenticated encryption, you should have a design document articulating (a) what you're trying to accomplish with what resources, (b) what powers the adversary has to subvert those resources, and (c) what security properties you want to provide to the legitimate users in spite of that—and a clear justification that the adversary's powers enumerated in (b) exclude the ability to modify ciphertext.

Actually, you should write that design document anyway!  But the use of unauthenticated encryption will definitely raise a lot of eyebrows if you don't have a clear justification for it.

  For key derivation I generate a random salt for every file. Do I need a different salt for every chunk or for every file it's enough?

As long as you generate each key independently for each file (which you do already, if you derive it from a password using a random salt generated independently for each file) and never reuse it outside the file, you can safely reuse the key for all the chunks in the file as long as you use a distinct nonce for each chunk.

  To encrypt the file I divide it in chunks and I encrypt them with AES generating a random nonce for every chunk.

Random nonces with AES-CTR (or AES-GCM) are generally unsafe because for plausibly large volumes of data the collision probabilities are uncomfortably high, and nonce reuse is catastrophic.

In this case it may be that you won't ever have a file with more than a few million chunks, which is safe for 64-bit nonces, but I don't know that and I wouldn't rely on it.  Even if you choose 96-bit nonces, which you can safely use if your chunks are never more than a gigabyte, a few billion chunks may be a plausibly large volume of data.

If you used NaCl crypto_secretbox_xsalsa20poly1305, random nonces have negligible collision probability because they're 192 bits long, longer than AES can support directly or efficiently.

Even with authenticated encryption, an adversary may be able to cut and paste chunks to put them out of order or delete them or duplicate them.

You can kill two birds with one stone by using sequential nonces: use the chunk's sequence number in the file as a nonce.  Even with 64-bit nonces, you won't ever get a collision sequentially (you'll hit birthday bounds on the 128-bit block cipher first, and it will take centuries unless you parallelize the computation), and if you demand that the nonce match the chunk's sequence number in the file then even an adversary who can modify the file can't put the chunks out of order.

  Do I need a padding with CTR mode?

CTR mode does not require padding.  CTR mode is just a way to use a block cipher with a key and a per-message nonce to generate a one-time pad in any bit length you want.

All that said: Consider using an existing construction for many-chunk files?


Choosing primes in the Paillier cryptosystem

Since $p$ and $q$ are primes, the only factors you need to rule out are those two numbers.

Suppose $p$ divides $(p-1)(q-1)$. Then it divides either $p-1$ (clearly not true) or $q-1$. The latter means $q-1 = p \cdot x$, for some $x \ge 2$ (if $x = 1$ either $p$ or $q$ is even, which is only possible if the numbers are 2 and 3). However, then $q \ge 2p+1$, so its binary representation is longer.

A similar argument proves $q$ can't be a factor. Thus, the GCD must be $1$.
If you just pick a random $g$ modulo $n^2$ the odds that it is a good choice are high (for large primes), so you usually only have to verify once. However, like your Wikipedia link states, you can just choose $g=n+1$ (when your primes are as long).

For $r$ you are also likely to get a good number randomly, but there you do have to check that neither $p$ nor $q$ divides it.

  We know that product of two $s$-bit numbers gives a number whose number of bits is between $s+1$ to 2$s$ , Suppose we are taking the equal length primes to ensure the property $\operatorname{gcd}(pq,(p-1)(q-1))=1$, then it is necessary to take $k$-bit primes  since $m<n$ .

If you multiply two $s$-bit numbers the product is always either a $2s-1$-bit number or a $2s$-bit number. (Here an $s$-bit number means one which has its $s$th bit set.)

To allow any $k$-bit messages, it is necessary that $2s-1>k$, so $s=k/2+1$ is enough.


"Order" in cryptographic terms for generators

You probably know that cyclic groups of any order exist, so it is perfectly possible to have a cyclic group of order $pq$, and to consider a generator thereof.


Secure multiparty sum computation corruption bound

For just computing a sum, the information-theoretic bound (assuming semihonest) is $t<n-1$.

Why $n-1$ and not $n$?
In the case of $t<n$, we can allegedly tolerate up to $n-1$ corrupt parties. If we are computing a sum, and the $n-1$ parties know the sum $S$ and their own inputs ($x_i$), they can simply compute the sum of their inputs and subtract that from $S$ to learn the private input of the single honest party. Therefore, there must be at least two honest parties if we are computing the sum.


ECCS: Elliptic Curve Cryptography Cramer Shoup

How to convert Cramer-Shoup into ECC?

Because Cramer-Shoup restricts itself to using only group operations (and never using a single value as both a scalar and a group member), it can translate directly into elliptic curve group operations.  What you quoted are the operations listed in multiplicative form, and so:

When the protocol says to select a cyclic group $G$ of order $q$, you'd pick an elliptic curve, with $q$ being the order of the large prime subgroup.
When the protocol specifies $g^x$, this is the point multiplication of $g$ times the scalar $x$, that is, what is more typically written as $x \cdot g = \underbrace{g+g+...+g}_{x\text{ times}}$
When the protocol specifies $gh$, this is point addition of $g$ and $h$, which is more typically written as $g+h$
When the protocol specifies $g/h$, this is point subtraction of $g$ and $h$, which is more typically written as $g-h$

For example, the original has $c = g_1^{x_1} g_2^{x_2}$; this would be understood as (written in additive notation) $c = x_1\cdot g_1 + x_2 \cdot g_2$.  That is, you perform the point multiplication of the scalar $x_1$ with the point $g_1$, and you perform the point multiplication of $x_2$ with the point $g_2$, and then you add the two resulting points.

The hardest part would be the conversion of $m$ into an elliptic curve point.  Of course, you can avoid the issue entirely if you're doing hybrid crypto (just pick a valid point $m$ randomly, and then use $KDF(m)$ as the transmitted symmetric key).  If that doesn't work for your scenario, one alternative method is to encode the value $m$ into some of the bits of the $x$ coordinate, and they try random settings of the remaining bits until you get a valid $x$ coordinate (e.g. if you're using a Weierstrass curve with $p>3$, then $x^3 + ax + b$ is a quadratic residue); then, select the $y$ coordinate from the two possibilities randomly.

  How do I prove the security of ECC Cramer-Shoup?

The proof in the original Cramer-Shoup paper assumed that the Decisional Diffie-Hellman problem was hard in the group; as long as you select a curve where that is also hard (pairing friendly curves are not an option), the original proof would apply.


Can the premaster secret generated by SRP be used as a secure private key?

From the RFC:

  SRP also supplies a shared secret at the end of the authentication sequence that can be used to generate encryption keys.

It seems from my quick look over the RFC that that shared secret is the premaster secret, so you are correct.


Is there a well known way of splitting a piece of information so that the information is only recoverable if all the pieces are together?

What you are describing is called secret sharing schemes.

The scheme you outline is sometime called XOR-sharing (or additive secret sharing more generally). It is a very used scheme as a sub protocol in more advanced cryptographic protocols (such as secure computation protocols). This scheme has perfect security. It is also very fast because it only requires XOR. So from those perspectives it is a good secret sharing scheme.

However, secret sharing schemes comes in many flavors with different properties, so it's not possible to say if there are better schemes. There certainly are more advanced schemes. But whether they are better depends entirely on the application.

For example, a weakness of XOR-sharing is that you need all the pieces of the secret in order to reconstruct the secret. Schemes exists where you can pick a parameter $t$, called the threshold, so that any group of size $t + 1$ pieces is enough to reconstruct the secret. These types of secret sharing are called threshold secret sharing schemes. The most well known scheme of this type is called Shamir secret sharing, which is based on polynomials over finite fields.


How to transform a text into numbers in the shortest way possible?

The best approach is to compress the text, then encode the output as decimal digits.

For the compression, the state of the art is complex; it was/is PAQ8 (used by the current holder of the Hutter Prize); PPM* is also quite good. In the realm of common, there's bzip2 and other methods based on the Burrows-Wheeler transform. In the realm of easily done, there's zlib, which is built in java.util.zip

Encoding the output in decimal is the easy part. A trivial method is to consider the bit string or octet string output by compression as an integer in a prescribed endianness, and convert that into decimal. The method is well known (basically: divide by 10, use the remainder as an output digit, and repeat dividing the quotient until that's 0). That's even built in Java's java.math.BigInteger (for big-endian). The only caveats are that with the big-endian convention, removing leading zeroes will be a disaster; the original length might be needed to allow decompression (depending on the compression method); and (with the standard algorithm outlined) execution time grows with the square of the size. If the later becomes a problem, one can subdivide the binary output into fixed-size blocks (except for an agreed-upon one, e.g. last), efficiently converted to a fixed size decimal output with a small size overhead. For example, 22 octets can be converted to 53 digits with less than 0.036% overhead, noticing that 25622 is just shy of 1053.

The reverse operation is trivial: convert from decimal digits to bitstring or octet string, then decompress. One caveat is that erroneous input might trigger strange bugs in the decompressor.

Note: The compression will make the output a lot shorter for real text, but in the worst case can cause a slight expansion (that can be limited to 1 bit). If the worst case size is what matters, remove compression.

Note: This is only tangentially on-topic, unless it is added encryption between compression and encoding as digits. In this case, the compression can have undesirable effect (like, ciphertext size leaking information on plaintext nature for one knowing plaintext length).


Why would anyone use an elliptic curve with a cofactor > 1?

Montgomery and twisted Edwards curves have even order, but the group law can be implemented using fewer multiplications than Weierstrass models.  So that is why these curves are popular and we have to live with cofactors $> 1$.

There are other reasons to prefer to use prime-order elliptic curves (e.g., small subgroup attacks).  So you are right that in an ideal world one would used prime order curves.  But sometimes it is worth the trouble to use a more efficient curve model.


Counter Mode: how to choose the nonce part of the counter?

The once part inside of the nonce in CTR mode means effectively "once for this particular key".

If you use a fresh key for each message (e.g. by encrypting it using public-key crypto or similar), you can use the same nonce for all the messages (or a size-zero nonce).

The important part is that the combination of nonce and ctr-value (i.e. what is input into the block cipher) is not repeated while using the same key.


What's the fundamental difference between Diffie-Hellman and RSA?

The difference is subtle.
DH is used to generate a shared secret in public for later symmetric ("private-key") encryption:

  Diffie-Hellman:

  Creates a shared secret between two (or more) parties, for symmetric cryptography
  Key identity: (gens1)s2 = (gens2)s1 = shared secret    (mod prime)
  Where:

  gen is an integer whose powers generate all integer in [1, prime)    (mod prime)
  s1 and s2 are the individuals' "secrets", only used to generate the symmetric key

RSA is used to come up with a public/private key pair for asymmetric ("public-key") encryption:

  RSA:

  Used to perform "true" public-key cryptography
  Key identity: (me)d = m    (mod n)    (lets you recover the encrypted message)
  Where:

  n = prime1 × prime2     (n is publicly used for encryption)
  φ = (prime1 - 1) × (prime2 - 1)     (Euler's totient function)
  e is such that 1 < e < φ, and (e, φ) are coprime     (e is publicly used for encryption)
  d × e = 1    (mod φ)     (the modular inverse d is privately used for decryption)

It just so happens that -- in practice -- RSA's results are subsequently used to generate a symmetric key.
Furthermore, it also happens that you can also modify DH to be used for public-key encryption.
But they are fundamentally different, even though both of them have "public" and "private" components.


Compute statistical distance between two distributions over tuples

No, you cannot prove that, since it is not generally true. Consider the following counter example.
Let $X$ be a distribution over $\{0,1\}$ with $$\Pr_{b\gets X}[b=0] = \Pr_{b\gets X}[b=1]=\frac{1}{2}.$$
Let $f,g,h : \{0,1\} \to \{0,1\}$ be defined as $$f : b \mapsto b,\quad g : b \mapsto b, \quad \text{and} \quad h : b \mapsto b\oplus 1.$$
The statistical distance between the distributions $g(X)$ and $h(X)$ is zero and thereby negligible.
\begin{align}&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[g(b')=b] - \Pr_{b'\gets X}[h(b')=b]\right|\\
=&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[b'=b] - \Pr_{b'\gets X}[b'\oplus 1=b]\right|\\
=&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\frac{1}{2} - \frac{1}{2}\right| = 0
\end{align}
However, the support of the two distributions $$(f(X),g(X)) \in \{(0,0),(1,1)\}\quad \text{and} \quad (f(X),h(X)) \in \{(0,1),(1,0)\}$$ are completely disjoint and their statistical distance is thus $1$ which is non-negligible.


Why should a distribution being pseudorandom strictly be a sequence of distributions being pseudorandom

A sequence of distributions is a definition of a distribution for each $n$. For example, consider the distribution $Dist_n$ to be a string of length $l(n)$ generated using some pseudorandom generator with a seed of length $n$. Then, for each $n$, the distribution is actually different. The reason why technically you need this is because the notion of negligible is asymptotic - it needs to be a function so that for every polynomial, the function is smaller than it for some large enough $n$.


Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes?

A collision is between two values. If you take a random pair of values you get a 1/2n chance of having a collision.

With 2n/2 values you have about 2n-1 pairs, so you could expect about 1/2 chance of collision.

(That's just the "intuitive way" of thinking about it; in practice, there are mathematical details.)


Modification of block cipher in CBC mode

If you flip bits in cipher text block $E_K(M_i)$ then you flip the same bits in $M_{i+1}$. If you know or guess the value of the last plaintext block then XOR the second to last ciphertext block with the guessed plaintext value. That makes it zero because $v \oplus v = 0$ for all v. It's not so easy to manipulate otherwise.

Edit: I misread encrypted "0" as set plaintext to zero

If $M_i$ is known to be zero then XORing $M_{i-1}$ with $v$ causes block i to decrypt to $v$ instead.


How do you test the security of your cipher?

This somewhat reminds me of “How do I test my encryption?” but that question was more specific than this one, which seems to be too broad in it’s current state.

Nevertheless, there’s an easy answer to your question:

Check and verify all the security aspects you target with your cipher.
When done, simply respect Kerckhoffs' principle and make your cipher public… that way, others can check on the security of your cipher and either confirm it’s security (which builds public trust) or they can show you what’s wrong with it.

If you need any help or have any questions while checking and verifying your cipher algorithm, please feel invited to ask more specific questions that can be answered more on-point.


If a connection polynomial of degree $d$ is primitive, i.e., it is irreducible and has a root of order $2^d-1,$ then the period is $2^d-1,$ for any nonzero loading.

There is more information in answer


Problem in understanding Blakley's Secret Sharing Scheme

An easier way of explaining it is here: http://www.demoivre.org/courses/CIS628/chapter15.pdf

So for a point $(x_0,y_0,z_0)$ we set $x_0$ as the secret and then randomly choose $y_0$ and $z_0\pmod{P}$.

Now we  generate our plane to distribute to the participants:
we pick two random integers $a$ and $b$, then we set

$$C = z_0 - ax_0 -by_0 \pmod{P}$$

we now have our equation for the plane, such that:

$$z = ax + by + c$$

to reassemble the secret we use matrix manipulation and it is simply:

$$a_i x + b_i y - z \equiv -c_i \pmod{P} $$

scroll down to page 12 on that link for a really good example


This is due to the modelling approach called Markov Ciphers, by Jim Massey (I think).

Basically the hypothesis is that round by round independence applies and correlations can be concatenated by using conditional probabilities and multiplying the probabilities. Since you must have the previous and current round correlations to build up a trail step by step, you apply conditional probability.

Daemen and Rijmen (designers of AES) state:

The Markov cipher theory [18] has inspired many research on iterative block ciphers, including ours. It can be considered as the first approach to design block ciphers resistant against differential cryptanalysis. A Markov cipher is an (iterative) cipher for which the average difference propagation probability over one round is independent of the round’s text input. For such ciphers, the assumption of independent round keys allows to compute the average DP of a characteristic as the product of the probabilities of the individual round. Here the average is taken over all the round keys, considered as independent variables. The average DP of a differential can be computed —in principle— as the sum of the probabilities of all characteristics with input difference a in the first round, and output difference b in the last round. Estimating the average probability of a differential to be equal to the fixedkey probability for almost all keys, is called making the hypothesis of stochastic equivalence. After the publication of linear cryptanalysis, Markov cipher theory has been extended to the resistance against linear cryptanalysis (e.g. see [26, 30]), leading to analogous conclusions for the LP of linear approximations (hulls) over the cipher. In [27] Markov theory was used to show that the average DP values in a Markov cipher employing differentially 2-uniform mappings converges exponentially fast to a flat distribution with high probability.

The quote above is from  their paper https://eprint.iacr.org/2005/212.pdf


Does password length affect AES encrypt/decrypt velocity?

No, password length does not perceptibly change encryption throughput. That's valid for overwhelmingly most password-based encryption schemes using AES-256, especially the secure ones.

More precisely,

The time it will take to encipher an extra kilobyte of data is fully independent of the password length. That's because the password is first transformed into a 256-bit key, and then this key is used for encryption/decryption/authentication, and the throughput of that later step does not depend at all on the value of the AES key (that would be a weakness of the AES implementation).
Even the time it takes to encipher/decipher/authenticate the first kilobyte does not perceptibly depend on the password length, for reasonable size thereof (say, up to 55-byte password, often much more). That's because the code that transforms the password into key falls into one of two categories:

Slow: for these, up to said limit at least, execution time depends almost only on parameters adjusted to slow things in order to make password search suitably difficult.
Fast, thus of negligible cost w.r.t. the rest. CAUTION: these are extremely vulnerable to password search.

Note: 55 bytes is a limit above which some common hash algorithms (SHA-256..) see their computation time abruptly increase, because they process their input data split into 64-byte blocks, and there's an overhead of 9 bytes.

Note: this answer is independent of the nodejs context. The linked page gives zero clue about how the password is changed to key, and this site is not about language-specific questions.


Would XOR'ing two Argon2 keys add extra security?

That sounds convoluted.

The server-generated passphrase is essentially an extension to the client password. So you may just concatenate both (with a proper delimiter, or with their respective sizes being included) and hash the whole thing.

Also, from a usability perspective, the passphrase is inconvenient (and useless when using a password manager). You may use the user's email address as an extension instead.


Functional signatures vs homomorphic signatures

The difference is that in homomorphic signatures anyone can compute on the signatures, whereas in functional signatures only the party holding the functional secret key $sk_f$ can compute $f$ on signatures (signed by master secret key corresponding to $sk_f$)


Does any operating system offer full system encryption, including RAM and SWAP?

Yes and no.

Let's go through the requirements you have step-by-step:

  So if anyone steals the hard disk [...] he cannot decrypt the data.

That is widely supported in modern operating systems and called full-disk-encryption (FDE). On Windows you'd use something like Bitlocker for this task and on Linux something like dm-crypt should do the trick. Note however that this would require entering a passphrase every, single time you boot the server up.

  I mean all it's encrypted, also [...] the swap

Any decent full-disk encryption system hooks itself into the driver stack and encrypts everything going through this stack shortly before the drive is actually invoked to write, thus, as the swap is a normally written onto the drive, it will be encrypted as well by most full-disk-encryption programs.

  I mean all it's encrypted, also the RAM [...]

This is where things get tricky and the answer becomes "no".
You can encrypt data in RAM, as it's just data and the algorithms don't care where the data resides. However this would also mean leaving the key in RAM, which makes this kinda pointless. BUT, there's Intel SGX and AMD's upcoming memory encryption techniques (PDF whitepaper). They both consider the OS an adversary and thus offer protection against him, even in RAM. So with a combination of standard encryption and SGX based encryption, you could get large parts of the RAM only holding encrypted content, but SGX also needs external management and because of that you can't encrypt everything in RAM (for now), as long as you don't put an encryption chip in between your CPU and the RAM. Also note: As these technologies are very recent, there isn't many products that use them right now, especially since Intel requires a business contract with SGX production-users.

"Encrypt everything" sounds nice in theory, but isn't practicable. There are trade-offs to be made. Full-disk-encryption will protect you against attackers stealing your physical disks and reading their contents and RAM-protection can at most defend against attackers who get root access and / or physically steal and try to read-out the RAM (note that RAM doesn't hold data for a long time), but the technology isn't there (yet).


How to find a primitive cube root of unity

Show the following.

For any prime $p \ne 3$, we have $p^2 \equiv 1 \pmod 3$, and thus a primitive $3$rd root of unity exists in $\mathbf F_{p^2}$.
Assuming $p^2 \equiv 1 \pmod 3$, for any $x \in \mathbf F_{p^2}^*$, $x^\frac{p^2-1}3$ is a $3$rd root of unity, and moreover, all $3$rd roots of unity can be obtained in this manner.
Given a $3$rd root of unity, it is easy to check whether it is primitive.
If $x$ is chosen uniformly from $\mathbf F_{p^2}^*$, $x^\frac{p^2-1}3$ is a primitive $3$rd root of unity with probability $2/3$.


Why do we use prime numbers apart from hard factorization?

Any finite setting with addition that distributes over multiplication where neither operation loses information—except multiplying by zero—necessarily has a prime characteristic, which is the number of times you can add 1 to itself before you get back 0.  Further, the size of any finite field is some power of its characteristic, so the size of any finite field is always a prime power (proof).

Finite fields are useful for polynomial evaluation authenticators like Poly1305 and GHASH—their security as a message authentication code follows from the fact that a polynomial of degree $d$ over a finite field has at most $d$ distinct roots.  You could use a ring instead of a field, but then you would need a larger ring to attain the same security because multiplication even by a nonzero value may lose information.

The multiplicative group of certain finite fields—specifically prime fields $\mathbb Z/p\mathbb Z$ when $p$ is large, subject to certain other criteria—seems to be hard to compute discrete logs in.  If we used a ring instead like $\mathbb Z/p_1^{e_1} p_2^{e_2} \dotsm p_k^{e_k}\mathbb Z$ for $\gcd\{p_1,p_2,\dotsc,p_k\}=1$, then we could compute discrete logs independently in the $\mathbb Z/p_i\mathbb Z$ and then lift the solutions to the whole ring using a combination of the Chinese remainder theorem and a magic trick called Hensel lifting in an algorithm chronicled by Eric Bach.  So the DLOG security of $(\mathbb Z/m\mathbb Z)^\times$ depends on the size of the largest factor of the modulus $m$, and there's no reason to use a modulus with more than one factor.  (In principle we could also use finite extension fields like $\operatorname{GF}(2^t)$, but the DLOG security story is pretty well demolished there these days.)

Finite fields also are needed to construct elliptic curves, which provide groups with much better DLOG security than the multiplicative groups of finite fields directly.  (‘Elliptic curves’ over composite moduli lead to arithmetic errors eventually (attempts at division by noninvertible elements), an observation which turned out to inspire a state-of-the-art method of factoring, ECM!)  Either way you get a group $G$ of size $n$, and as you observed, when $n$ is composite, the cost of Pohlig–Hellman—and also of Lim–Lee active small-subgroup attacks on Diffie–Hellman protocols—is determined by the size of the largest prime factor of $n$.

Generally, in any setting where you have a finite group $G$, the group $G$ decomposes into subgroups of $d$ elements apiece where $d$ divides $n$.  And any setting of invertible transformations on a finite set leads to a finite group under composition, so there will necessarily be primes involved in the algebraic structure of the group.

All that said, not all cryptography involves large primes.  For example, the polynomial evaluation hash GHASH—used in AES-GCM for message authentication—is defined over $\operatorname{GF}(2^{128})$, but the group structure of $\operatorname{GF}(2^{128})^\times$ is not relevant to its security so the only prime that's ‘really’ involved (whatever that might mean in math!) is 2.  Code-based cryptosystems like McEliece public-key encryption and CFS public-key signature don't involve any group structures and are usually defined over binary Goppa codes, so, again, the prime 2 is involved, but other primes, maybe not so much.


Where can I find information on the speed of basic hand-operated ciphers?

You’ll likely have to do your own analysis.
First of all, most of existing literature focuses either on asymptotic speed or specific implementations (such as in the case of hardware based encryption). Neither of which will be very useful to your pen-and-paper scenario.
Second of all, coming up with your own “similar system” implies it is a “new” system and no existing analysis would’ve been done on it.
I recommend that you create a set of “basic operations”, such as lookups in a table, arithmetic operations, copying intermediate result to another piece of paper, etc. This way you can estimate the number of operations the original decipher takes and compare it with that of your new algorithm.
(As this is for a science fair project, I'm leaving out any considerations for the actual security implications.)


Verifiable Encryption of a Pedersen Commitment

Yes. Say the message is $m$ and the commitment is $C$ such that $C = g^mh^r$. Since you can use verifiable encryption to prove that a given ciphertext encrypts $m$ in relation $g^m = y$ where $g$ and $y$ are also public knowledge, using the Schnorr protocol you can prove that the $m$ in relation $g^m = y$ is same as the $m$ in $C$


DSA: How to calculate 224-bit $q$ for 2048-bit $p$

I can calculate 2048 bit prime $p$, but how to find $q$ efficiently?

You're doing things in the wrong order.

Instead, you pick a 224 bit $q$, and then such for a 2048 bit prime of the form $p = kq + 1$ (for some integer $k$).

This can be done with essentially the same amount of effort as finding a 2048 bit prime (without constraints), and directly answers the problem, as such a $p, q$ pair guarantees that $p \equiv kq + 1 \equiv 1 \pmod q$


Can an U2F public/private key-pair for signatures be used for encryption?

No.

It is possible to derive keys from deterministic signatures (or non-deterministic signatures that can be converted into a deterministic value), for example Android uses Trusted Execution Environment's RSA signing plus scrypt to bind Full Disk Encryption keys to a specific device.

However, ECDSA signatures are not deterministic (there's RFC6979, which specifies deterministic use, but U2F doesn't use it), so each generated signature will be different for the same message and key, thus you cannot derive the same key from multiple signings.


Creating a random password based off of a prime number

If you just need random numbers, there's no point in generating random primes.  Just make sure that you're using a cryptographically secure random number generator, properly seeded from a secure entropy source.

Also, passwords made up of random letters and numbers are very hard to remember (and type).  For a password meant to be memorized by a human, it's much more efficient (in terms of security vs. effort) to generate a passphrase made out of random words instead.  See diceware and this xkcd strip for some well known examples.

Also, 100 random base-32 characters equals 500 bits of entropy.  That's ridiculous for a password; 128 bits of entropy is plenty for anything, and you're probably OK with 80 bits or even less, depending on what kind of threats you're expecting.  If your key derivation function does proper key stretching, that'll add some 10 to 30 bits of effective strength to your password (depending on the iteration count), allowing you to reduce its length even further.

A typical randomly chosen word has about 10 to 14 bits of entropy, depending on the size of the word list (a diceware passphrase has just under 13 bits of entropy per word), so generating a passphrase of five or six random words and using a key-stretching KDF should be safe  enough.