Multi-Party Encryption for a Shared Document

Is there an encryption algorithm/protocol where any of a pre-defined
  set of keys/passwords will succeed in decrypting a document?

Not exactly a protocol, but there are formats out there that will allow this sort of thing. An example system using a similar appraoch would be LUKS which offers "key-slots" doing exactly what you want - but targeted at full disk encryption.

  [C]an I append a (symmetrically) encrypted key
  to the document, where the password to decrypt this is a user's
  password?

Yes you can, although usually these information are put in front of the document so you don't have to start at the end to gather the key and then jump to the front again.

  I'm not sure what algorithm is appropriate here.

I'm quickly describing what each key slots needs to hold. The extrapolation to 20 slots is then trivial.

The slots may hold an identifier so each user can quickly discover his slots. This may be a hash (SHA-3-256 or SHA-256) of the the email, or other appropriate identifiers.
The slots may hold algorithm identifiers for key derivation, for encryption and for authentication in case you plan on changing the format in the future.
The slots should hold a unique, random 16 - 32 byte salt each.
The slots should hold derivation parameters for the key derivation.
The slots must hold a unique, random IV of length 12 - 16 bytes each.
The slots must hold the encrypted document key and the encrypted IV for the document.

As for the algorithms:

The key derivation algorithms (in order of preference):

Argon2, the winner of the password hashing competition (PHC), will need at least two parameters and a salt along with the password, you may lack an implementation of Argon2 because it is fairly new
any other PHC recommendation (except Makwa), they are all fairly new and you may you not have an implementation, they all will need a salt and at least two parameters
scrypt, will need three parameters and a salt and is more likely to be available than Argon2 and the PHC recommendations and uses large amounts of memory
bcrypt, will need only one parameter and a salt and is likely to be available
PBKDF2-SHA256, is 100% available or you can quite easily implement it yourself

Encryption algorithms for the document key, the document IV and the document (in order of preference):

AES-GCM / AES-OCB, use AES-OCB if available but chances are you can't because of the patent, if available AES-GCM is your best option then
AES-CCM / AES-EAX, use these modes if possible or if necessary implement them yourself if you have access to an AES primitive.
AES-CTR + HMAC-SHA-256, use this mode in an encrypt-then-authenticate manner and only use it if you have AES and HMAC at your disposal but can implement EAX or CCM.
3DES-EAX / 3DES-CCM, use this if you have access to an implementation of 3DES (or just DES) and implement EAX / CCM on top.
TEA-EAX / TEA-CCM, use this if you don't have access to any implementation of any block cipher (highly unlikely)


Have affine ciphers actually been used in practice?

While it's hard to prove that something has not been done, I'm fairly confident in asserting that affine ciphers (with $a \not\equiv \pm1$) are purely educational toys and have never been used for serious encryption (i.e. something not deliberately designed to be broken), except perhaps arguably as parts of a more complex cipher.
For one thing, affine ciphers of this type aren't really particularly good for anything in practice.  Their keyspace is not that much larger than that of simple Caesar shift ciphers, and in any case they are just as vulnerable to attacks via frequency analysis as any other simple monoalphabetic substitution cipher.
As hand ciphers, affine ciphers are too complex to be practically applied without the aid of an explicit lookup table.  And while one could indeed construct an encryption table using an affine map, doing so would not seem to offer any particular advantage over e.g. the various keyword-based methods actually used in practice.
Meanwhile, for a machine cipher, affine maps offer no obvious advantage over the combination of shifts and (fixed) non-linear permutations, as used e.g. famously by the Enigma machines, and they have the obvious disadvantage that modular multiplication is far harder to implement mechanically than simple shifting.
That's not to say that it could not be done, as exemplified e.g. by Weisner & Hill's patented mechanical implementation of the Hill cipher.  That said, it's worth keeping in mind that, although proposed as (a component of) a practical real-world cryptosystem, the Hill cipher was never really adopted as such, is large part due to its cumbersomeness.  Presumably, any attempts to employ affine ciphers via mechanical means would have encountered similar difficulties.

I tried to see if I could determine when and where the concept of affine ciphers was first introduced, but I'm not sure if I've really found it.  In any case, the earliest mention of the term "affine cipher" that I could find in the literature is from 1983, in a book chapter titled "Elements of Cryptology" by M. Davio and J.-M. Goethals, included in the book Secure Digital Communications by G. Longo (ed).
However, while the chapter indeed briefly discusses classical monoalphabetic substitution ciphers (of which affine ciphers as you define them are a subset) on page 3, the phrase "affine cipher" only occurs on page 14, in the context of block ciphers, and only as an example of an insecure class of ciphers to be avoided:

2.4 Combining building blocks.
Individually, each of the above building blocks [i.e. bit permutations, translations, linear transformations, addition mod $2^n$ and substitutions (S-boxes)] is a poor cipher. However, by combining them (as suggested by Shannon) in a product cipher, we may obtain much stronger ciphers.
Some of the combinations, however, are weak. For example, by combining translations and linear transformations we obtain an affine cipher: $$m \to Am + b$$ which can be broken in much the same way as a linear cipher. Thus affine substitutions should be avoided.

(emphasis original; [editorial note] mine)
In particular, in the context where the quote above appears, $m$ in fact denotes a block of $n$ bits, $A$ is an $n \times n$ matrix over GF(2), and the operator $+$ (which really should have been written as $\oplus$, to stay consistent with the usage on the previous page) clearly denotes bitwise XOR.  Thus, while the "affine cipher" described in this text is indeed clearly an affine transformation, the elements being transformed in this case are $n$-bit vectors over GF(2) rather than integers modulo 26 (or any other modulus).

Meanwhile, the earlier mention that I could find of the "educational" form of the affine cipher you describe above is from Douglas R. Stinson's book Cryptography: Theory and Practice, first published in 1995:

1.1.3 The Affine Cipher
The Shift Cipher is a special case of the Substitution Cipher which includes only 26 of the 26! possible permutations of 26 elements. Another special case of the Substitution Cipher is the Affine Cipher, which we describe now. In the Affine Cipher, we restrict the encryption functions to functions
of the form $$e(x) = ax + b \bmod 26,$$ $a, b \in \mathbb Z_{26}$. These functions are called affine functions, hence the name Affine Cipher. (Observe
that when $a = 1$, we have a Shift Cipher.)

There's no mention in the rest of Stinson's book of any historical usage of affine ciphers, and indeed the text seems to present them merely as a particular mathematically interesting class of simple ciphers.  If a historical source for affine ciphers existed, one would expect it to be mentioned in section 1.3 ("Notes"), which e.g. cites Lester S. Hill's original 1929 paper on his eponymous cipher, as well as David Kahn's The Codebreakers for general history of cryptography (with a special mention of the historical misattribution of what's nowadays known as the Vigenère cipher to Blaise de Vigenère rather than to its actual author, Giovan Battista Bellaso).  But no such reference is given there, or anywhere else as far as I can tell.
It thus seems possible that Stinson may have invented the affine cipher in its modern form, perhaps inspired by earlier uses of the term in contexts like Davio's & Goethal's mention of affine block ciphers.  However, without additional sources, I cannot be sure of this.  Perhaps someone ought to contact him and ask.


The 12 in BLS12-381 means that the embedding degree is 12 and the 381 means that the prime in the finite field $\mathbb{F}_p$ is of 381 bits.
Now talking about your bulletpoints:

The order is not $\approx 2^{381}$. The order is the number of points on the curve. A naive way is to find the coordinates $y$ in the equation $y^2=x^3+4$ for $x\in \{0, p-1\}$, or a better way you can run Schoof's algorithm.
The security level is around $128$ bits. In fact, you need a subgroup of order $r \approx 256$ bits to have this security level because Pollard's $\rho$ attack (the fastest known algorithm to find discrete logs on elliptic curves) has a complexity $\approx \mathcal{O}(\sqrt{r})$ and indeed for BLS12-381 $r \approx 2^{256}$.
The private key is a scalar in $\mathbb{F}_p$ which means $\in \{0, p-1\}$. So yes the size is $381$ bits.
The order of the curve is not prime. If it is prime all the generators will have the same order (and thus public keys of the same size) as all subgroups will have the same order as the curve. In fact, according to Lagrange theorem, the subgroups orders divide the group order so if it is a prime the subgroups orders will be equal to the group order. So, since in BLS12-381 it is not a prime, you have generators of different orders (which all divide the curve order). The reason behind this choice is that we can implement efficient pairings (https://eprint.iacr.org/2012/232.pdf).
see above.


Mathematically, this is expressed as H(P)=H(P|C), where H(P) is the entropy of the plaintext and H(P|C) is the conditional entropy of the plaintext given the ciphertext C. This implies that for every message P and corresponding ciphertext C, there must be at least one key K that binds them. Mathematically speaking, this means |K| >=|C| >= |P|. In other words, if I need to be able to go from any plaintext in message space P to any cipher in cipher-space C (encryption) and from any cipher in cipher-space C to a plain text in message space P (decryption), I need at least|P|=|C| keys (all keys used with equal probability of  1/|K|to ensure perfect secrecy).


ciphers depend on Elliptic curve cryptography

Yes. ElGamal encryption can be instantiated with Elliptic Curve Cryptography. That's essentially the asymmetric cryptography part of ECIES, which adds symmetric cryptography to become CCA-resistant. ECIES has wide endorsement, e.g. in SEC1 v2, ANSI X9.63, IEEE 1363a, ISO/IEC 18033-2.


Security of randomized data dependant key schedules?

Data-independent key schedules allow the round subkeys to be computed once in advance.  They can be reused for each subsequent block you encrypt.  This potentially allows significant performance speedups.

Data-dependent key schedules don't have that property.

Otherwise, there is no fundamental difference.

Normally, the key schedule is defined or understood to be the part of the cipher that depends only on the key and can be computed in advance (doesn't depend on the data).  So, "data-dependent key schedule" is somehow a contradiction in terms.


How should we interpret the cryptanalysis results of SIMON and SPECK?

Let's first get something out of the way. You say ".. key-recovery attack for SPECK32/64 ..". This is not true. The cryptanalysis you linked attacks SPECK32/64 with 10 rounds. This is less than half the amount of rounds used for SPECK32/64.

Then onto your actual question, is $2^{29}$ chosen plaintexts a good or a bad attack? I can't decide that for you, but I can give you an idea. SPECK32/64 uses a block size of 32 bits, or 4 bytes. This means that after encrypting 2.1 GB of plaintexts your key could be recovered.

Whether that is deadly for security or not is up to you to decide, not me.


How the message is decrypted in an RSA chosen ciphertext attack when it's a modulo?

In a chosen ciphertext attack, it is hypothesized that the adversary can obtain the decryption of cryptograms chosen by the adversary other than the targeted one(s), and in addition obtain the encryption of any message chosen by the adversary (which is free for asymmetric encryption).
The most general CCA experiment goes:

Key generation: the challenger secretly draws a key, and reveals the public key if any (that is for asymmetric encryption)
Message choice and encryption:

the adversary chooses messages $m_0$ and $m_1$ and submits both to the challenger
the challenger randomly draws $b\in\{0,1\}$
the challenger verify that both $m_0$ and $m_1$ are valid (could be encrypted), and if that holds encrypts $m_b$ yielding $c_b$, sets $c=c_b$, and reveals $c$ (unrelated to the question's $c\,$).

Interaction: the challenger accepts and answers both encryption and decryption queries, with the exception of decryption queries which ciphertext matches $c$.
Examination: the adversary makes a guess of $b$. The cryptosystem is broken under chosen ciphertext attack when the guess is correct for probability non-vanishingly better than $1/2$.

For asymmetric encryption, the challenger needs not answer encryption queries, for these can trivially be handled by the adversary using the public key.
No deterministic encryption can be CCA secure per this definition (argument: the adversary can get $c_0$ and $c_1$ and determine which matches $c$). For a weaker notion of CCA security applicable to deterministic encryption, another change is imperative. That can be:

The challenger does not answer decryption queries where the ciphertext submitted matches matches one of $c_0$ or $c_1$ (the challenger needs to compute both).
Alternatively, only the challenger is involved in the message choice, which becomes selecting $m$ such that encrypting it into $c$ succeeds. And in examination the adversary makes a guess of $m$, not $b$. And must guess correctly with non-vanishing probability.

The question is for textbook RSA, which is asymmetric and deterministic. With the second of the above options, and a single decryption query, the experiment goes:

Key generation: the challenger

draws a key pair
reveals the public key $(n,e)$
keeps secret the private exponent $d$
Note: $(n,e,d)$ is such that messages $m$ that can be encrypted are those integers with $0\le m<n$; their corresponding encryption is per $c\gets m^e\bmod n$, and decryption of $c$ with $0\le c<n$ is per $m\gets c^d\bmod n$ or equivalent.

Message choice and encryption: the challenger

randomly draws an integer $m\in[0,n)$
computes $c\gets m^e\bmod n$
reveals $c$ (unrelated to the question's $c\,$).

Interaction: the challenger accepts a chosen ciphertext query where it

receives $\tilde c$ (the chosen ciphertext) submitted by the adversary
checks $0\le \tilde c<n$ and $\tilde c\ne c$
checks and deciphers $\tilde c$, that is checks $0\le \tilde c<n$ then in the affirmative computes and reveals $\tilde m={\tilde c}^d\bmod n$ (this $\tilde m$ is the question's $c\,$).

Examination: the adversary makes a guess of $m$. The cryptosystem is broken under chosen ciphertext attack when the guess is correct for non-vanishing probability.

A standard way to carry this attack in textbook RSA is that the adversary

chooses some $t$ in $[2,n)$ with $\gcd(t,n)=1$, e.g. $t=2$ or $t=n-1$
computes $s=t^e\bmod n$
computes and submits $\tilde c=c\cdot s\bmod n$
obtains $\tilde m$ from the challenger
Note: from $\tilde c=c\cdot s\bmod n$ it follows ${\tilde c}^d\equiv(c\cdot s)^d\pmod n$ (obtained by raising to the exponent $d$), thus ${\tilde c}^d\equiv c^d\cdot s^d\pmod n$, thus $\tilde m\equiv m\cdot(t^e)^d\pmod n$ (since decryption works for $m$ and $\tilde m$), thus $\tilde m\equiv m\cdot t\pmod n$ (since decryption works for $t$).
solves for $m$ with $0\le m<n$ the equation $\tilde m\equiv m\cdot t\pmod n$ (which in the question is the equation $c = m \cdot t \pmod n\,$), and submits the result as the recovered $m$.

In that later step, the adversary computes a multiplicative inverse of $t$ modulo $n$, that is some integer $t'$ such that $t\cdot t'\equiv1\pmod n$. This is possible since $\gcd(t,n)=1$. One method uses the extended Euclidean algorithm. When $t=2$ (resp. $t=n-1\,$), we can use  $t'=(n+1)/2$ (resp. $t'=n-1\,$).
Then $\tilde m\equiv m\cdot t\pmod n$ becomes $\tilde m\cdot t'\equiv(m\cdot t)\cdot t'\pmod n$, thus $\tilde m\cdot t'\equiv m\cdot(t\cdot t')\pmod n$, thus $\tilde m\cdot t'\equiv m\cdot1\pmod n$, thus $\tilde m\cdot t'\equiv m\pmod n$.
Therefore, the adversary always finds $m$ by computing the uniquely defined $m=\tilde m\cdot t'\bmod n$ (see notation at end).

Critically w.r.t. to the question, there is no hesitation between several $m$ because

it is known that the challenger chose a valid message $m$, thus that $0\le m<n$
a solution $m$ to $\tilde m\equiv m\cdot t\pmod n$ exists and all are congruent modulo $n$, because a solution $t'$ to $t\cdot t'\equiv1\pmod n$ exists and all are congruent modulo $n$, because the adversary has chosen $t$ with $\gcd(t,n)=1$, thus $t\bmod n$ belongs to the multiplicative group of integers modulo $n$
when $y$ is congruent to $x$ modulo $n$, that is when $y\equiv x\pmod n$, the additional condition $0\le y<n$ makes $y$ uniquely defined by $(n,x)$.

Notation: for integer $n>0$ and integer $x$

$y\equiv x\pmod n$ means that $n$ divides $x-y$. This is best read as: $y$ is congruent to $x$ (short pause) modulo $n$. It can be written y = x (mod n).
$y=x\bmod n$ means that $n$ divides $x-y$, and $0\le y<n$. This can be read as: $y$ is $x$ modulo $n$. Such integer $y$ is uniquely defined for a given $(n,x)$. That $y$ is the remainder of the Euclidean division of $x$ by $n$ when $x\ge0$.


How to correctly evaluate the security of DH in TLS

With elliptic curves, the public certificate (?), used for DH, can be
  smaller than without elliptic curves and still be considered secure.

Yes, you can achieve the same level of security with shorter keys and thus shorter certificates with EC-based crypto and as an additional bonus: we tend to encode the full field (ie order, prime, generator) for standard DH but only a name (an OID to be precise) for elliptic curves.

  I have something in my mind like, non-elliptic-curve DH should have at
  least 2048 bit, to be considered secure.

  Is my information correct?

Yes, standard key size considerations (based on the GNFS) apply to finite-field DH.

  So in this case the DH key length/public certificate size would be
  4096, correct?

Yes, the size of the public key / the field prime is 4096 bit, the size of an actual DH certificate would be quite a bit larger though, due to the additional encoding of owner information, issuing CA information, field information, ...

Chances are that you are actually looking at your server's DH parameters that are used for the ephemeral key exchange.


How can I construct a proof that the decryption of a certain encrypted file matches a hash?

What you describe is very close to Zero Knowledge Contingent Payment (ZKCP) proposed for exchanging digital goods for bitcoins.

The setting is that Alice has a file $F$ and Bob would pay to have it. However they don't trust each other. So Alice generates a key $k$ and encrypts the file $E_f=E_{K}(F)$ using a cipher $E$, and hashes the key $y=H(K)$. Then she sends $(E_f,y)$ to Bob, along with a proof of knowledge $(F,k)$ such that $c$ is an encryption of $F$ under the key $K$ which satisfies $H(K) = y$. If Bob is satisfied with the proof, he will publish a transaction on the bitcoin network saying that there are some bitcoins locked in an account such that whoever can submit the pre-image of $H(K)$ to the account address can take the coins.

In your case, you have an additional hash value $z$ of the file published by Alice. It seems that you want Bob to also be able to verify the file matches $z$. In this case, Alice's proof would be a conjunction, i.e. $c$ is an encryption of $F$ under the key $K$ such that $H(K) = y$ AND $z=hash(F)$.

To do such proof, you would need SNARK (Succinct Non-Interactive Arguments of Knowledge). Conceptually it is simple, the prover shows that some secrets he knows, if computed correctly by some publicly known functions, will produce some values which the verifier knows. However the actual implementation can be quite complicated, and there are some caveats as well regarding the security properties.

A paper that contains more details and is worthy reading: Zero-Knowledge Contingent Payments Revisited: Attacks and Payments for Services by Campanelli et al, published in CCS 2017.


How many AES-operations have to be watched for key-exploit by side-channel attacks?

As pointed out by poncho, it is not possible to precisely answer your question since too many parameters are involved:

About the AES implementation: is it an unsecured implementation? Does it use masking? If yes, at which order? And so on...
The physical properties of the device also matter, does it leak a lot? Are there some hardware countermeasures such as a shield, a jitter, etc...
What equipment is used to measure leakages? Depending on the probe, the oscilloscope and its setup, the number of AES executions to achieve a 100% success rate may vary greatly.

To put it in a nutshell, you have to make practical experiments to answer your question.


Does a two-way fixed-length hash function exist?

What I understood from your question is that you want to map your data uniquely such that the output has less bits relative to the input. You can use data compression techniques to compress your data. Then, if you need the security, use cryptography. Although hash functions are able to compress your data, but they can't be reversed by everyone. This goal is opposite of their nature and their duties.


I believe that this is a poorly written question: such an $h$ obviously doesn't have either preimage resistance, second preimage resistance or collision resistance.

The inability to rederive the specific value of $m$ based on its hash is not an interesting property; it's pretty much true of any function which generates an output shorter than its input.

I don't know where you're getting these questions from; based on this question, I'd suggest you look elsewhere.


Oblivious Polynomial Evaluation and Encoding Payload

The bar is just concatenation of strings. As long as you are comfortable treating things both as bit strings and as group elements, there is nothing special about the encryption scheme being used here.

Without these payloads, the idea of the protocol is the following. Bob sends a set $Z$ of ciphertexts. Alice computers her output as $\{ \mathsf{Dec}(z) \mid z \in Z \} \cap X$. Items shared by Alice & Bob will be output by Alice in this way. Items not shared by Alice and Bob will result in a random value for  $\mathsf{Dec}(z)$, so they are negligibly likely to be output by Alice.

Now, with the payloads, suppose the parties are doing PSI on items that are $\ell$ bits long. Now Alice would compute her output as
$\{ \mbox{first $\ell$ bits of } \mathsf{Dec}(z) \mid z \in Z \} \cap X$. It is still the case that any item not shared by the parties is negligibly likely to be output by Alice (negligibly likely that its first $\ell$ bits match one of Alice's items). But you can use the remaining bits to encode a payload for each item.

This assumes is that the ElGamal/Paillier group is large enough to encode strings of this extra length. But without loss of generality you can always:

shorten the items: agree on a common hash function and do PSI on hashes of your items.
shorten the payloads: make $p_y$ a short key for a symmetric-key encryption, and send along an encryption of your actual (possibly huge) payload using this key.

edit: Oh, just saw that you're using exponential El-Gamal. You will have to alter things syntactically but not conceptually. As an example, let $V$ be the group element whose bitwise representation is the item+payload string $y | p_y$. Now $V$ has some discrete log (that exists but would be hard to compute) $V = g^v$. I claim that Bob should encrypt $rP(y) + v$ in the exponent. Fortunately you don't have to know $v$ to do it, just obtain an ElGamal encryption of $g^{rP(y)}$ in the way you already know, and use its homomorphic property to multiply by $V$, making a standard ElGamal encryption of $g^{rP(y)} \cdot V$. When Alice decrypts, she either sees a random thing, or else she gets group element $V$. Instead of trying to reason about $V$'s discrete log, Alice can just look at the bit-representation of $V$ and identify it by whether $y$ is a prefix.

The reason for all this is that the payload can't be conveyed in the exponent (Alice will never be able to get it back). Instead it must appear in the result of her standard ElGamal decryption. In exponential ElGamal, you can test whether decryption equals a value you already know (in the exponent), you can't decrypt to learn a value in the exponent that is new to you.


What's the odds of system generating same user ID for more than one users?

You need to have way more than $2^{100}$ key-pairs / users for a collision.

With Ed25519, the public key is $P=[a]G$ with $a$ being the private key and $G$ being the public generator point of the curve. Now because of the determinism of the scalar multiplication, if $P=P'$ then $a=a'$ and thus the users share the same private key. If both users are using a good random number generator, they never pick the same private key. More precisely: If you generate less than $2^{126}$ key pairs there shouldn't be any two key pairs with the same private key, because you would be looking for colliding random 256-bit strings.


Alice trusts Bob only when Bob trusts Alice

This sounds like a fair exchange protocol where what is exchanged is a digital signature.
Per this paper, these are impossible without trusted third parties.

With a trusted third party, they are possible. Indeed people have proposed schemes that do what you describe again relying on a third party in the case of failure.


Hash-based asymmetrical encryption (not digital signature) schemes?

It's impossible to construct a strong asymmetric encryption algorithm that relies only on the security of a hash function:

  We prove that every key exchange protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary making O(n^2) queries to the oracle.

Boaz Barak, Mohammad Mahmoody-Ghidary - Merkle Puzzles are Optimal

(The proof assumes the attacker is only limited by the number of hash computations and has unlimited computational power otherwise)

The quadratic advantage of Merkle Puzzles is not sufficient to achieve the security and performance levels expected of modern cryptography. For example at a security level of 80 bits (Breaking it is equivalent to about one day of bitcoin mining), the defenders would need to exchange terabytes of information and need an hour or so of computation.

And against quantum computers you don't even get that quadratic advantage.


If A and B are co-primes, does Ax mod B (where x, any positive int) gives {0,1,2,....,B-1}?

Claim: If $A$ and $B$ are coprime, the map
$$\begin{align*}
\{0,\dots,B-1\}\ &\to\ \{0,\dots,B-1\}
,\\
x \ &\mapsto\  A\cdot x\bmod B
\end{align*}$$
is a well-defined bijection.

It is clear directly from the definition of $\bmod$ that $A\cdot x\bmod B$ is indeed between $0$ and $B-1$.
Surjectivity follows, e.g., from Bézout's lemma.
Any surjection between finite sets of the same cardinality is automatically bijective.

In particular, this implies that the map
$$\begin{align*}
\mathbb Z\ &\to\ \{0,\dots,B-1\}
,\\
x \ &\mapsto\  A\cdot x\bmod B
\end{align*}$$
is also surjective.


Why is computational zero knowledge the most generic notion of zero knowledge?

Because being perfectly zero-knowledge is a more stringent security requirement.

For a language to have a perfect zero-knowledge proof, you need to exhibit a proof of membership to the language so that the proof can be simulated perfectly without knowing the witness; i.e., even an unbounded adversary should not be able to see any difference between the real proof and the simulated proof. Hence, you are requiring a very strong security notion: security against an adversary with unlimited computational power.

Computational zero-knowledge, on the other hand, only requires that the simulated proof cannot be distinguished from the real proof by a computationally bounded adversary. This is a weaker security notion, hence easier to achieve.

If a language has a perfect zero-knowledge proof, then it has a computational zero-knowledge proof (the same one: if it's secure against unbounded adversaries, it's in particular secure against bounded adversaries). We do not know about the converse, and we suspect that it is not true (i.e., some languages can have a computational zero knowledge proof, but no perfect zero-knowledge proof). Hence, computational zero-knowledge is more general, because more languages can have such proofs. Denoting CZK / SZK / PZK the class of languages with computational / statistical / perfect zero-knowledge proofs, we clearly have PZK $\subset$ SZK $\subset$ CZK. Furthermore, we also know that if one-way functions exist, CZK $=$ IP $=$ PSPACE, which is immensely powerful.


Signing a message using SPHINCS Hash-based Signature scheme

If I have to sign a message, M, do I randomly pick any of the HORST trees and sign my message?

With the original Sphincs, yeah, that's what you do.

(As an aside, the designers of Sphincs+ (and IIRC, Gravity-Sphincs) realized that this was a nonoptimal design; it allowed a forgery to select the HORST tree that gave him the best probability of success; that is, the one that was used the most).  Hence, what they did in Sphincs+ to do specify a mapping from the randomized message to both a FORS (used in replacement of HORST in Sphincs+) few-time-signature AND the combination of FORS leafs; that way, the attacker doesn't get such an advantage).

  The signature is going to be pretty huge to reach all the way up to the PK

Well, yes, yes it is.

  According to the example parameters mentioned of h=3 and d=3 which yields three layers of height 1 each. In layer 2, each node in the two WOTS+ trees can sign k roots of layer 1 WOTS+ trees? So when I reach layer 0, the total number of messages I can sign is (2*k)^3. Is this correct?

Well, no; in the notation they use in Sphincs, h is the total number of XMSS levels in the combined hypertree, and d is the number of levels of XMSS trees (that is, the number of one-time signatures).  With h=d=3, then each XMSS tree is of height h/d = 1; that is, each XMSS tree has two leaf nodes (and so can sign two messages).  In addition, if h=3, then there is a total of $2^h = 8$ HORST trees (as h is the total hypertree height); of course, each HORST tree can sign several messages (and the security of the HORST tree degrades as it signs more messages)


Symmetric encryption using RSA for random generated password

The concept of using an asymmetric key (RSA) to encrypt a symmetric key (AES) is not new.  This was first popularized by PGP, which is probably what I would encourage you to use to solve your problem.  SSH (well SFTP in particular) also uses a somewhat similar approach and could also be pressed into transmitting files securely.

Pretty much any approach you could dream up would suffer from the problem of the establishment of initial trust.  In general, you probably don't want to constantly regenerate the asymmetric keys as then you have to also regenerate the trust for them.

One of the simplest ways to handle initial trust for a program/automation is to establish it yourself by supplying the same PSK (pre-shared key) on both (or all) ends of a connection.  If you did that, then you have a different problem, of keeping the shared secret secure.  There are devices that can do that for you, such as HSM (hardware security module) but they are frequently expensive.  (The cheapest one that comes to mind is $500US from Yubico.)


Current situation of bilinear pairing protocols

That paper is misleading in several ways:

The DSA vs BB comparison: it is unfair because it compares DSA with the "full" BB scheme, which does not produce shorter signatures. The same BB paper describes a "basic" scheme that has a signature that is half the size of DSA. That's the whole point of short signature schemes (being shorter than ECDSA/DSA). This point is now moot, however, since a 2015 paper describing an attack that required pairing-based crypto to increase its parameter sizes, making short signatures not that short anymore (which does support the authors' claim, but that was not the justification they used).
They estimate that BB is 60 times slower than DSA but give no justification. While signature verification will indeed be slower, signing should be faster.
They raise the issue of the master key in PBC schemes. This is true, but only applies to ID-based crypto, and was known from the start.

Pairings are still relevant because some schemes can only be implemented efficiently using them. Zcash uses pairings to implement a zero-knowledge protocol; TPM chips use pairings to implement Direct Anonymous Attestation; for example.


What is the maximum number of shares in Shamir's Secret Sharing?

The maximum number of shares in Shamir's secret sharing is limited by the size of the underlying finite field.  In particular, the maximum is one less than the number of elements in the field, since each share must be associated with a distinct element of the field, and one of the elements (usually the zero element) must be reserved for the secret being shared.

A quick Google search indicates that the com.codahale.shamir implementation always uses GF(256).  Thus, it can support at most 255 shares.

If you switched to an implementation that used, say, GF(216), then the maximum number of shares would increase to 216 − 1 = 65,535.  That should be enough for your purposes.  If not, using GF(232) would let you have up to 232 − 1 = 4,294,967,295 possible shares.

The main disadvantage of using fields larger than GF(256) = GF(28) for Shamir's secret sharing is that you may need to pad your data up to a multiple of the field size.  (With GF(256), the field elements are single bytes, so that's rarely an issue.)  In your case, however, your secrets are always 32 bytes = 256 bits long, so you can safely use GF(216), GF(232), GF(264), GF(2128) or even GF(2256) without having to worry about that.


Extracting the hidden text off an image embedded with steganography

Yes, you can write a single application to reveal the hidden information as long as you know the method and they are not encrypting the messages they hide. The Wikipedia article in Steganography tools lists some information about availability as an opensource, their methods, and usege of encryption. And some information can be found on their website.

For example, QuickStego says that;

  The QuickCrypto steganography function allows carrier files to be photographs, drawings, images (.jpg, .gif, .bmp file types) and sounds (.wav and .mp3 file types). Any type of file can be hidden within these types of carrier files. Files and text to be hidden can easily be encrypted prior to hiding if required.

and SSuite Picsel

  SSuite Picsel secures all your text messages using Steganography encryption...

If encrypted you must know the encryption algorithm and the key to decrypt the message after you retrieve the hidden messages.

There may be also a patent problem since the SSuite Piscel is a company. They may have some patents on the steganographic methods. You may write your software by reverse engineering their products, but distributing it; may cause legal problems.


Which RSA keys are actually attacked In practice?

This question is based on a false premise, namely, that the difficulty of breaking cryptography (involving a given key type) depends only on the size of the key. This is not how cryptography is broken. The weak point in cryptography is usually flaws in the implementation.
For example, one way RSA can go wrong is if the key was not generated correctly. Cases of keys that were generated using a random generator that was not properly seeded are depressingly common. For example, Debian shipped a broken version of OpenSSL for two years which resulted in there being only a tiny number of possible SSH keys. Surveys of SSH and TLS public keys have shown that a small, but significant proportion of servers have keys that were generated with insufficient entropy or with a flawed process, resulting in keys that can be broken easily. (An RSA private key is determined by two (pseudo-)primes, and the public key is their product. If two private keys share a prime, it's trivial to spot this from the public keys $p \, q_1$ and $p \, q_2$.) Linux has had a steadfastly broken interface to random generation, historically giving the choice between an interface that blocks needlessly and one that is insecure in one specific but critical moment (just after the first boot of a system) (modern kernels have a good interface in the form of the getrandom system call, but because it's harder to use than the historical interfaces, a lot of software relies on the historical interfaces). In addition to the RNG problem, there is flawed key generation code out there, for example not using enough iterations when testing primality (which is a probabilistic test), or using computational shortcut that make the private key easier to calculate from the public key than brute force (such as generating primes that are close to each other, which can be faster, but is insecure).
A larger key size can help mitigate against a broken key generation process. For example, generating a larger key will request more material from the RNG and this can help if the RNG is not well-seeded at the beginning but receives additional entropy over time. Generating a larger key can also help if the code takes shortcuts, because it may compensate the loss of security from these shortcuts. But not all flaws can be mitigated that way. When the RNG is not seeded properly and only a small number of keys are possible at all (as in the Debian-OpenSSL case, or in the case of many embedded devices without a hardware RNG), no increase of the key size will help.
In addition to the key generation process, another source of weaknesses is the use of the key. Asymmetric (and symmetric) cryptography is prone to side channel attacks, where properties such as the timing of certain parts of the computation leaks information about the key, or about the data that the key is protecting. A larger key can help against some attacks, because many side channel attacks need to observe a large number of calculations in order to extract enough information to reveal the key or the data.
Asymmetric encryption is also prone to protocol attacks. Asymmetric decryption is tricky because it combines the private key with an input that cannot be trusted since it could have been produced by anyone. This can allow oracle attacks, where the attacker sends an invalid ciphertext, and based on the message or the timing of a decryption error, learns some information about the key. The general principle of this form of attack on RSA was published in 1998 by Bleichenbacher and was still a concrete problem 20 years later. Modern communication protocols avoid asymmetric decryption in favor of key establishment protocols where, rather than encrypting a session key with a symmetric key, both sides arrange to derive the same session key from different computations that give the same result. But RSA decryption is still used in the wild in TLS up to 1.2 (this is deprecated, but still used by “middleboxes” that intercept and filter TLS traffic in enterprise networks).

if a 2048 bit key is a square, would anyone actually bother checking this?

Well, yes, of course. It's very easy to check. It's also easy to factor the key if $p \approx q$, and it's one of the obvious things an attacker would try.

Where is the point where nobody will even try to crack it - with the result that some stupid mistake making a particular code insecure would never be detected, because nobody tries?

There is no such point. If you generate a key without a proper RNG, or if you store your key insecurely, or if you use an implementation that doesn't properly protect against applicable attacks such as side channel leaks and glitches, or if you use a flawed protocol, your key may be vulnerable no matter what its size is.
“Nobody will even try to crack it” is not a useful concept. It's based on the assumption that attackers are stupid and work in isolation. They aren't and they don't. Where there's a possible attack, all it takes is one expert to write a tool to perform a sophisticated attack, and sooner or later a conveniently packaged version of this tool will be available for free or for sale.


Proof one-time pad is perfectly secret with eavesdropping game definition

Might be too late.. but yes the approach is correct. As you said, since the one time pad is being used, Eve doesn't really need $c$(not even choosing the two messages) she could just use some simulator $\sigma$ and generate a random uniform $c' = \sigma((G, l))$ and run $r = E.r(c')$. So the distribution of $(m_0, m_1)$ doesn't matter, r and b are independent. Thus equal with probability at most $1/2$

Now, I'll try to  answer this more "formally".

Notation:  Let $(S, B)$ denote the system that emulates Alice, meaning a systems $S$  correlated with a uniformly distributed bit $B$. $S$ performs the $otp-enc(m_B)$. Let $S_0$ be Alice when the bit is zero(i.e sends $otp-enc(m_0)$, $S_1$ is defined similarly. Let $D$ be a distinguisher(Eve) characterized by a joint distribution $P^{M_0,M_1}[m_0, m_1]$ over the set of possible messages, and an algorithm $R: (G,l) \to \{0,1\}$. $R$ takes a cipher text and outputs a bit.

The setup: Eve is trying to win the bit guessing game wherein a distinguisher $D$ interacts with $(S, B)$ and outputs a bit $R$. The advantage of Eve is $\Delta^D((S, B)) =  2Pr^{D(S, B)}[R = B] - 1$. In other words by how much she performs better than when she just guess.

Now observe that what the question asks is to show that the advantage is 0 for any Eve.

Another type of game Eve could play is a distinction game where Eve is connected and interacts with either $S_0$ or $S_1$ and outputs a bit $R = 0$ if she thinks she is interacting with $S_0$ and outputs 1 otherwise. The advantage of Eve in this game is $\Delta^D(S_0, S_1) = Pr^{DS_1}[R = 1] - Pr^{DS_0}[R = 1]$. I introduce the following result without proof:

$\Delta^D((S, B)) = \Delta^D(S_0, S_1)$., for a uniform $B$.

So we can instead find the advantage of the distinguishing problem, which seems easier. We have that $Pr^{DS_1}[R = 1] = Pr^{KM_0}[m_0 \oplus k = c]  = \frac{1}{|G|^l}$. This is the same for $Pr^{DS_1}[R = 0]$. So $\Delta^D(S_0, S_1) = 0$.

Therefore $\Delta^D((S, B)) = 0$, which is what we wanted to show.

Remark: if Eve were to be allowed to additionally ask for encryption of up to $t$ messages, that would somehow be a proof of information theoretic  ind-cpa security of the OTP. Although some could argue that this notion doesn't really fit with the OTP.


Multi-target attacks on AES-CTR with a random nonce

Some amount of known or controlled plaintext is clearly required for the attacker to get the block cipher output.

Actually, that's not much of an issue; we can often get a reasonable amount of known plaintext from real encrypted messages.  In fact, the known plaintext for each message doesn't have to be the same, and you don't have to have completely known plaintexts; a sufficient number of linear equations in the plaintext will work.

  More importantly, this attack depends on the block cipher being fed the same plaintext block across many keys.

Yes, that is key.  CTR encryption is:

$$C = AES_k(n) \oplus P$$

This multitarget attack works by evaluating (for a test $k$) $AES_k(n)$ once, and then using that to check all plaintext, ciphertext pairs in parallel (say, by comparing that value to the list of $C_i \oplus P_i$ values you have precompiled.

However, this works only if every plaintext/ciphertext pair had the same $n$.  If each one used a different $n$, then you'd have to evaluate $AES_k(n)$ separately for each plaintext/ciphertext pair; in that case, you're no better off than picking one message, and just bruteforcing that.

This protection isn't a novel idea; for both TLS and IPsec, the GCM RFC's ask that 32 bits of random (actually, KDF derived) salt is included in the nonce, specifically to frustrate this type of attack.


Using master password to encrypt and decrypt user credentials

It's true that anyone who learns the master key has enormous leverage.  Key management best practices are worth investigating.  I highly recommend that you consider using a key management service (KMS) that is backed by a hardware security module (HSM).

There are affordable offerings in cloud-based services, such as Amazon's Key Management Service, that allow you to retrieve a key from their service and use it locally.  Alternatively you can use a cloud-based KMS to encrypt by transmitting plaintext data to the service, and receiving a reply consisting of ciphertext and a reference to a key (decryption consists of sending the ciphertext back to the same service along with the key reference).

Of course using a cloud-based service requires that you authenticate with the service, and that means transmitting credentials to it at some point.  You can make this process more secure by configuring the KMS to accept communication from a limited set of IP addresses.  Also, your KMS authentication credentials could be encrypted and stored at rest in the form of ciphertext.  The unencrypted KMS credentials could exist in RAM for a duration that you determine (your original post said every 8 hours, which seems adequate).  The method for decrypting the KMS credentials could be that you supply a password which gets converted to a key that could then perform the decryption.  Then let the KMS do the rest of the encryption work.


Why would this algorithm be vulnerable to a preimage attack?

Firstly, remember what is the pre-image attack*;

The pre-image attack is that given a hash value $h$ one need to find an $x$ such that $h = \operatorname{Hash}(x)$. The founded value doesn't need to be the pre-image that is used for the given hash value rather it can be any input value that its hash matches the given hash value, i.e. $x' \neq x$ and $h = \operatorname{Hash}(x')$.

Let call $\operatorname{H}_\ell (M) = (\ldots(((m_1 \wedge m_2) \vee  m_3) \wedge m_4) \vee m_5) \ldots [\vee|\wedge]\, m_{n-2})$ i.e words just before the last two operation. And

$$\operatorname{H}(M) = \big(\operatorname{H}_\ell (M)  [\vee|\wedge]\, m_{n-1}\big) [\vee|\wedge]\, m_n$$

The number of the blocks determines the order of the last two operations, the $\vee$ is the last or $\wedge$.

Now the trick is that

by using  $\wedge$ you can make any bit zero  $x \wedge 0 =0$ and
by using $\vee$ you can make any bit one $x \vee 1 =1$.

Therefore only using the last two blocks - actually using only two blocks - the attacker can create any hash value.

There are much more simple attacks as a note by Fgriue:

$h = \operatorname{H}(h)$
$h = \operatorname{H}(h\mathbin\|h)$ since $h = h \wedge h $
$h = \operatorname{H}(1^n\mathbin\|h)$ since $h = 1^n \wedge h $
$h = \operatorname{H}(h\mathbin\|h\mathbin\|h)$ since $h = (h \wedge h) \vee h $
$h = \operatorname{H}(\bar h\mathbin\|h\mathbin\|h)$ since $h = (\bar h \wedge h) \vee h $

* The formal definition can be found in this seminal work Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton.


Does two-factor authentication require one time use of one of the factors?

No.

The factors are:

something you know (for instance a password);
something you have (for instance a device containing a key for TOTP generation)
something that you are (for instance a fingerprint).

TOTP is not a factor in itself, it is a scheme that can be used to prove that you have the key / device).

There are however other ways of testing that you have something. If you bring a special amulet as "something that you have" then I could simply have a look at it after all. One time use is therefore not required.


Maximum Number of Blocks to be Encrypted under One Key in CBC and CTR Mode?

CTR mode.
There's a generic birthday attack on CTR mode of a block cipher.

The idea of CTR mode is to use a PRF, or pseudorandom function family, $F_k\colon \{0,1\}^\iota \to \{0,1\}^n$ to approximate a one-time pad with a short key $k$: $$c = m \oplus (F_k(0) \mathbin\| F_k(1) \mathbin\| F_k(2) \mathbin\| \cdots \mathbin\| F_k(\ell - 1)),$$ where $\ell$ is the length in $n$-bit blocks of the message $m$ (ignoring details of partial blocks).

If instead of a PRF we have a PRP, a pseudorandom permutation family or $n$-bit block cipher, $E_k\colon \{0,1\}^n \to \{0,1\}^n$, we can use that to approximate a PRF.  But a PRP, being a family of permutations, has the property that in the sequence of blocks $E_k(0), E_k(1), \dots, E_k(\ell - 1)$, as long as $\ell < 2^n$, there are no repeated blocks.  In a uniform random sequence of blocks, we would expect to see a collision when $\ell \approx \sqrt{2^n} = 2^{n/2}$, by the birthday paradox.

When $n = 128$ as in AES, this procedure—check for a repeated block—enables an attacker to distinguish a very long but not unimaginably long CTR mode pad from a very long uniform random pad with nonnegligible probability.

CBC mode.
In CBC mode, the $i^\mathit{th}$ ciphertext block is $c_i = E_k(m_i \oplus c_{i-1})$, with $c_{-1}$ being the initialization vector.  If the adversary notices that $c_i = c_j$ then they can infer $$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$ from which they learn $$m_i \oplus m_j = c_{i-1} \oplus c_{j-1}.$$  Turning this into a distinguisher and calculating how the birthday bound is relevant here is left as an exercise for the reader who has had more breakfast so far this morning than I have.

Recommendations.
Because of these birthday attacks, cryptographers usually sternly advise against using AES-CTR or AES-CBC for more than a few exabytes of data, or, to be conservative, a few hundred terabytes.  (It doesn't matter whether that's for a lot of short messages or a few long messages.)  64-bit block ciphers like 3DES fare even worse, to the point that they can be broken in practice.

When $n = 256$ as in Threefish-256, these attacks are irrelevant: the birthday bound is around $2^{128}$ blocks of data, which you will never see.  When it's a PRF with $n = 512$, as in Salsa20 or ChaCha, it's even less relevant—although if you pick per-message nonces at random, the birthday bound once again becomes relevant because those nonces are only 64 bits and there is a nonnegligible chance of a security-destroying collision in the nonce, which is why the extended-nonce variants XSalsa20 and XChaCha exist and why some cryptographers and standardizers are considering nonce-misuse-resistant AEAD schemes.   In sum, the birthday paradox is a versatile tool!


This is not a limitation of the cryptographic functions, like SHA or PBKDF,  since the zero byte isn't processed any differently.

Since the purpose of a salt is generally to travel alongside a human password, libraries that handle the password as a zero-terminated string might also handle the salt as such a string. Obviously, a 0x00 in the salt would terminate the salt per-maturely when it is processed as a string. If you're interested, you may want to view the code to see where the salts you saw generated actually get used and whether those APIs treat the salt as a string.

In general, there is no universal standard for how to format salt, so the way a salt is processed is left up to the designers of a specification. If you don't know what APIs a salt you generate will be plugged into, the safest strategy is to make the contents all non-zero so it will work with any API that evaluates the salt as a string.

Another (less likely) explanation: In general, there are some standards that require random values that be non-zero. For example, PKCS v1.5 encryption scheme (section 7.2.1 step "a") calls for 8 bytes of random padding of nonzero values. In this example the padding value is not a salt, but the existence of such requirements for random data in some specifications may lead a developer to cautiously always generate non-zero random data just to be safe.


Why is Ring-LWE based homomorphic encryption secure with one sample?

The security proofs on the papers about (R)LWE use several samples (usually denoted by $m$) because then the results (and the security guarantees) are stronger. And, anyway, they usually give upper bounds to $m$ (as being at most polynomially big in $n$), but not lower bounds.

For both, the decisional and the search version of the problem, giving less samples can only make the problem harder.

To see that, notice that if an attacker can distinguish the two distributions given only one sample, than it can break (R)LWE with multiple samples by just ignoring $m-1$ samples and distinguishing in the way he/she knows with one sample. And this argument works for any number of samples smaller than $m$ (so, we have a reduction from the (R)LWE problem with $m$ samples to the (R)LWE problem with any $m' < m$ samples).

To be more confident about that, take a look at section 4.1.1 of A Decade of Lattice Cryptography, where Chris Peikert explains why we can ignore columns of the SIS problem. It is basically the same argument to your case.


Finding all polynomials up to a given degree to generate a bit sequence

Given any finite sequence $(a_0,a_1,\ldots,a_{N-1})$ we may be interested in generating exactly that sequence, or generating the minimal degree (periodic) sequence which has that sequence as its' starting bits.

Trivially, the circulating shift register of length $L$, initially loaded by $(a_0,\ldots,a_{L-1})$, will generate this sequence, by implementing the recurrence

$$x_{t}=x_{t-L},\quad t\geq L,$$

i.e., give the characteristic polynomial $X^L+1.$

The polynomial that Berlekamp Massey (BM) yields is the minimal degree polynomial which matches this initial segment. Your sequence $$(a_0,\ldots,a_{10})=(00100000110)$$ has length $N=11$ and BM gave you a  degree $6$ polynomial.

In general, there will be a set of polynomials that can generate an initial segment. If the minimal recurrence (i.e., the minimal degree polynomial generating your sequence) has degree $n$, $2n$ bits are required to uniquely determine it. So to get a unique polynomial of degree 8 which generates a sequence, 16 bits are needed.

If you specify less than 16 bits, you will in general get more than one generating polynomial. You have 5 bits "free" to go from 11 to 16 bits so you may get up to 32 different polynomials, corresponding to all these possibilities, barring any linear dependencies in the resulting polynomials.


Which is better: “serialize and then encrypt” or “encrypt and then serialize”?

If you serialize it, then you have one [likely binary] block of data that you would then need to encrypt.

If you encrypt the contents first (however you might achieve this) and then serialize it, it would presumably have to identify the things that are encrypted, and this could likely leak information about the object or its makeup.  Also, this would theoretically open the individual parts up to tampering, or replacement, or other specific attack.

Therefore, I assume the best answer is to serialize and then encrypt.


Motivation for the definition of statistical distance

Statistical indistinguishability (i.e., negligible statistical distance) implies computational indistinguishability, but is typically easier to prove since it does not require a computational argument with a reduction and all that stuff.

Of course, it is not always possible to prove computational indistinguishability in that way; statistical indistinguishability is a stronger, information-theoretic notion.


Can blocks in AES-CBC ciphertext be manipulated in such a way that plaintext becomes shuffled?

It does not seem like this is possible. Consider the simple case where a 2 block (32 byte) plaintext message has been encrypted using AES-CBC with key $k$ and initialization vector $IV$. Let the plaintext blocks be referenced as $P_1$ and $P_2$, and let the corresponding ciphertext blocks be referenced as $C_1$ and $C_2$. In this case, knowing that $\text{AES.encrypt}(k, P_1 || P_2) = C_1 || C_2$ and that $\text{AES.decrypt}(k, C_1 || C_2) = P_1 || P_2$, you are trying to find out whether $\text{AES.decrypt}(k, f(C_1) || f(C_2))$ can possibly equal $P_2 || P_1$, where $f$ is some manipulating function applied to the ciphertext.

From the regular CBC decryption of $(C_1 || C_2)$ into $(P_1 || P_2)$, we are guaranteed the following relationships:

$\text{AES.decrypt}(k, C_2) \oplus C_1 = P_2$

$\text{AES.decrypt}(k, C_1) \oplus IV = P_1$

In order for $(f(C_1) || f(C_2))$ to decrypt into $(P_2 || P_1)$, the following relationships must be true:

$\text{AES.decrypt}(k, f(C_2)) \oplus f(C_1) = P1$

$\text{AES.decrypt}(k, f(C_1)) \oplus IV = P_2$

And then, by substitution, the following must also be true:

$\text{AES.decrypt}(k, f(C_2)) \oplus f(C_1) = \text{AES.decrypt}(k, C_1) \oplus IV$

$\text{AES.decrypt}(k, f(C_1)) \oplus IV = \text{AES.decrypt}(k, C_2) \oplus C_1$

In order for the first equation to be true, $f(C_2)$ must equal $C_1$ and $f(C_1)$ must equal $IV$, and in order for the second to be true as well, $f(C_1)$ must equal $C_2$ and $IV$ must equal $C_1$, giving us the following:

$f(C_2) = C_1$

$f(C_1) = C_2$

$f(C_1) = IV$

$C_1 = IV$

$f(C_1) = C_1 \rightarrow C_1 = C_2$

So the only way that you can manipulate blocks in the 32-byte AES-CBC output to decrypt to rearranged blocks of the original plaintext is if the output blocks $C_1$ and $C_2$ are identical. Clearly if this was the case, the corresponding input blocks would also be identical, and there would be no point for a malicious actor to rearrange them in the first place.


The algorithm for generating EC curve is in appendix D.5 of NIST FIPS 186-4, and the verification algorithm is in D.6. They are taken from ANSI X9.62, which justified the rationale as the following:

  In order to verify that a given elliptic curve was indeed generated at
  random, the defining parameters of the elliptic curve are defined to
  be outputs of the hash function SHA-1 (as specified in ANSI X9.30 Part
  2 [4]). The input (SEED) to SHA-1 then serves as proof (under the
  assumption that SHA-1 cannot be inverted) that the parameters were
  indeed generated at random.

The curve generation algorithm requires $a,b$ to satisfy $b^2\cdot c \equiv a^3 \bmod p$, and it is not necessary that $a$ and $b$ be chosen at
random. In the case of NIST Prime curves, they all use fixed $a=-3$, so $b^2\cdot c \equiv -27 \bmod p$.

As to the question why $b$ cannot equal to $c$, note if $a$ is not fixed then it is actually valid to choose $a=b=c$. But  $a=-3$ is chosen by NIST, so this is not possible because the seed does not hash to $-3$.


Since you are talking about password-based encryption, the best practice is to use a slow password-based key derivation function to derive the encryption key and only store the salt (and parmeters used). You can verify the correctness of the password by using authenticated encryption, which you should most likely be doing in any case.

The password hash used could be scrypt, or I suppose argon2.

Since you are using this in a password manager -type situation, the encrypted data is passwords, which is fine. The above advice is only about the master password that is used to secure the database. That should not be stored in plaintext or encrypted form and even its hash does not need to be.


What are the weaknesses in a block cipher that uses modular addition, rotations with fixed amounts, and XOR? Can substitution boxes or permutation boxes be replicated with these three operations?

The obvious question to ask is "what permutations can you form using those three operations"?

The surprising answer is "you can implement any permutation using a sufficiently large pile of those three operations in the proper sequence"; that is, you can find a sequence of operations which swap two specific entries (and leave everything else alone); you can concatenate those together to form any arbitrary permutation.

Hence, there cannot be any generic weakness that would apply to sufficiently long ARX ciphers.  Of course, this doesn't address what "sufficiently long" means; it may be longer than what's in use in practice.

And, yes, there exists an ARX equivalent to any invertible sbox.

Exhaustive search on 3 bit blocks shows that you can reach every permutation with at most 9 operations, which isn't that bad.  However, doing a search on 4 bit blocks would require searching over $16! \approx 2^{44.25}$ distinct states; a bit more than I can handle with my current resources.


Reverse the order of encryption and decryption in CBC mode. Does this work?

Welcome randomjsmash!

Reversing encryption and decryption would give you a very weak encryption scheme.

First, it would make the initialization vector effectively useless. An attacker could simply unmask the first encrypted block and subsequent blocks do not depend on the initialization vector.

Second, guessing a single block correctly (e.g. assuming it contains only space characters used for indentation) would allow an attacker to unmask the following block. If the attacker were able to do this repeatedly, she would immediately see if blocks of plaintext repeat.

Being able to see repeating patterns will enable an attacker to perform statistical analyses and can quickly lead to a complete loss of confidentiality.


Cryptography systems based on NP complete problems

No, the problem is np-completeness or even np-hardness is a worst case thing. In crypto, we don't want our systems to be unbreakable only in the worst case. We want them to be unbreakable at least in the average case. It would be better if it were unbreakable in the best case (or all cases).

Another, related, issue we have is that of generating hard instances of the problem. NP-completeness does not guarantee that we can easily generate hard instances of the problem. Compare this with factoring where we can easily generate hard to factor numbers.

There have been a few other good, related questions on SE that you might find interesting:

Are there public key cryptography algorithms that are provably NP-hard to defeat?
Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

I won't summarize them here. They are definitely worth a read though.


Poly1305 itself has the requirement that its keys can only ever be used to generate a tag for a single message. That means that when Poly1305-AES (or another Poly1305-based authenticated encryption algorithm) is used as intended, the Poly1305 authentication key will be different for each message even if a key is reused.

However, the various Poly1305-based authenticated encryption algorithms (let's say Poly1305-*) support key reuse as long as the same nonce is not reused for a given key. The nonce is a non-secret (single use) value, so it can be sent alongside the ciphertext.

Poly1305-* generates a new Poly1305 (authentication) key for every new message. It does this by using the (authenticated encryption) key and the per-message nonce to derive the single use Poly1305 key. As long as both the sender and receiver use the same key and same nonce, it is possible for both people to derive an agreed-upon per-message Poly1305 (authentication) key.

In Poly1305-AES, that key is basically derived by extracting the first 16 bytes of an AES CTR-mode key stream. Subsequent keystream blocks are XORed with the plaintext. Note that bits used for the per-message Poly1305 (authentication) key and the bits used for message encryption are non-overlapping portions of the key stream. Because the keystream is pseudorandom, the per-message derived Poly1305 are expected to be unique.

Because this is a safe way for the sender and receiver to agree upon a per-message key, there is no need for an API to expose the per-message key to the programmer using the API. They just see parameters for one key and for the nonce.

(An API may even go further and abstract away the nonce, randomly generating one every time the encryption function is called and silently concatenating it with the ciphertext and MAC tag. The corresponding decryption function also could silently read the nonce from its expected location in the combined nonce/ciphertext/tag string, never exposing anything but the shared key, combined ciphertext, and plaintext to the programmer.)


Does TLS have to provide both confidentiality and authenticity?

TLS can provide only authenticity without confidentiality.
To do this you need to use the *_WITH_NULL_* cipher suites. They're disabled by default in most libraries.

However, I strongly recommend against using them.
You've really nothing to lose when using encryption and if you don't there may be privacy concerns.


Why are theoretical hash constructions based on the hardness of the discrete logarithm problem not really used in practice?

I would say it is largely due to

  the fact that discrete log functionalities tend to be computationally expensive and harder to implement on specific hardware (compared to constructions like SHA-2)

In many (perhaps most) use cases, hash functions are not primarily used for their cryptographic security properties, but for efficient and comfortable data management, e.g. in databases. So complexity of running the algorithm should be minimal.

In addition, good hash functions do provide strong security and have several advantages over applications of finite group schemes (where the discrete logarithm applies). In particular, they provide extremely little algebraic structure, meaning there is not much to attack in the first place. This is also the reason why many consider hash functions to be quantum computer resistant, while it is already known that Shor's algorithm can solve the DLP efficiently.

In short, I do not know of any advantage that a DLP-based hash function would bring about, while there certainly would be some shortcomings by comparison.


Can you tell if this ECB mode mitigation idea is "OK"?

As already mentioned, if you've got ECB you can certainly design other modes of operation. Probably the easiest one to implement is CTR mode: you simply line up a number of counters (each of the block size of the underlying cipher) and then encrypt them using ECB. You can XOR the result with the plaintext to encrypt or decrypt data.

You'd still have to use a nonce for the initial counter value of course, if you want to reuse the same key.

Limiting passwords to a certain size is a bad idea. So is storing an encrypted password instead of storing a hash of the password.

If you use CTR mode I'd say limit the password size to 64 bytes and pad the password to that size using zero padding - then encrypt the result. That way you'd allow longer passwords and you would not leak the password size right away.


Is there any advantage – other than potential memory or speed performance reasons – of picking a state size different from 512? If, what would the advantage(s) be?

Yes.

With 256-bit state, the main advantages are memory use and hardware implementation area.

With 1024-bit state, a hardware implementation can be faster, but there are also security advantages.

The paper (pdf) claims the following, given state size $n$, output length $l$ and $m = \min\{n, l\}$. I've included only the ones where a 512-bit hash with 1024-bit state has a higher security claim than a 512-bit hash with a 512-bit state:

$r$-multicollision resistance: $\min\{2^{n/2}, 2^{(r-1)m/r}\}$.
Key recovery, forgery and distinguishing resistance (as MAC, PRF or in HMAC): $\min\{2^{n/2}, 2^{m}\}$.

None of these are likely to matter in practice unless Skein is broken, which is why they recommended 512-bit state. However, it is potentially useful if collisions are eventually found after all, and as a security buffer (same paper):

  Even if one day finding collisions
  turns out to be somehow feasible—as for MD5—exploiting that weakness for creating either multi-
  collisions or meaningful collisions should remain infeasible. This requires us to increase the internal
  state size, which is the core idea for the failure friendly “wide-pipe” design [77]. Thus, if we want
  a 256-bit hash function to be failure friendly, we need 512 bits of internal state, and if we want a
  failure-friendly 512-bit hash function, we need 1024 bits of internal state.

Finally, the 1024-bit variant has been defined with eight more rounds to counteract slower diffusion (80 as opposed to 72 rounds). This has the effect of making some other attacks break a smaller percentage of total rounds: e.g. the attack mentioned on page 67 breaks 25/72 rounds with 512-bit state but only 26/80 rounds with 1024-bit state.

(You could define an 80-round 512-bit variant that shared the above advantage, but that would likely be slower than the 1024-bit variant even in software, at least on fast 64-bit CPUs.)


In a very simplistic and step by step example, how do I get the 'w' values for SHA256?

In SHA-256, $W$ is a vector of 64 values $W_i$ each 32-bit, collectively forming an expanded form of the input to a compression step. Said input is a 512-bit sub-block of the message to be hashed par SHA-256 after that message was padded. The $W_i$ depend only on said input.

$W_0$ to $W_{15}$ are said input, formatted as 32-bit words. $W_{16}$ to $W_{63}$ are computed from these by applying for $i$ from 16 to 63 the recurrence defined by FIPS 180-4 section 6.2.2 as (within a reordering of terms):
$$W_i\gets W_{i-16}\;\tilde+\;\sigma_0(W_{i-15})\;\tilde+\;W_{i-7}\;\tilde+\;\sigma_1(W_{i-2})$$
where $\;\tilde+\;$ is addition with truncation of the result to 32-bit.

In the above expression, $\sigma_0$ and $\sigma_1$ are 32-bit functions of a 32-bit argument defined by FIPS 180-4 section 4.1.2 as:
$$\begin{align}
\sigma_0(x)&\gets(x\ggg\,\,\,7)\oplus(x\ggg18)\oplus(x\gg\,\,\,3)\\
\sigma_1(x)&\gets(x\ggg17)\oplus(x\ggg19)\oplus(x\gg10)
\end{align}$$
where $\oplus$ is bitwise-XOR, $\ggg$ is right-rotation of a 32-bit word (also known as right-rotate-no-carry or right-circular-shift), $\gg$ is right-shift of a 32-bit word (also known as right-logical-shift).

For example, to compute $W_{16}$, we

apply the function $\sigma_0$ to $W_1$ (right-rotating that value by 7 and 18 bits, right-shifting it by 3 bits, then combining the resulting three 32-bit values by XOR);
apply the function $\sigma_1$ to $W_{14}$ (right-rotating that value by 17 and 19 bits, right-shifting it by 10 bits, then combining the resulting three 32-bit values by XOR);
add $W_0$, $W_9$, and the two above results, truncating the result to 32-bit.

Note: the reason for using shift rather than rotate for one of the terms of $\sigma_0$ and $\sigma_1$ is discussed here.

Note: often (including in almost any careful hardware implementation) it is kept only the chronologically last obtained 16 values of $W$, evolving as the compression rounds are performed per the transformation:
$$W_i\gets W_i\;\tilde+\;\sigma_0(W_{(i+1\bmod16)})\;\tilde+\;W_{(i+9\bmod16)}\;\tilde+\;\sigma_1(W_{(i+14\bmod16)})$$


Is there any cryptographic scheme with block size more than 128 bit

In the designs, smaller block size typically results in better implementations (though, the extent of this may vary on the paradigm and the instruction set, e.g. ARX ciphers). That is, encrypting two 64-bit blocks would be faster than encrypting one 128-bit block (with the same key size and estimated security). Roughly speaking, diffusion and confusion happen much faster.
However, 64-bit blocks have issues in modes which have birthday-bound attacks (see https://sweet32.info/ ). So 128-bit block size is the most "optimal" choice.


Composite vs Prime Order Groups in Attribute Based Encryption

Composite-order groups for pairings are sometimes a necessary tool provide a proof for adaptive security. Most schemes for prime-order groups only reach selective security in their respective security models.

While the security generally increases, the performance of composite-order group pairings decreases heavily. Compare prime-order pairings of Type A with composite-order pairings of Type A1 here. All operations for Type A1 take roughly 18 times as much time as operations for Type A (although, they have different Dlog security levels, but that doesn't influence as much).

Dual Pairing Vector Spaces (over prime-order groups) behave similar to composite-order pairings in that they enable more powerful security proofs, but perform roughly 10 times slower than basic prime-order pairings.


Do we consider RSA+OAEP secure because the number of possible padded representations of a message is some insanely large number, and thus not feasible to bruteforce with current hardware?

No. But a related proposition holds: we would consider RSA+OAEP insecure if the number of possible padded representations of a message was less than some large number, like $2^{80}$ at the very least (which is not "insanely large" by today's measure).

In many practical cases, textbook RSA encryption per $C=M^e\bmod N$ would be insecure if $M$ was directly the plaintext, without some random added in the padding process transforming plaintext to $M$. This is because the adversary is assumed to hold the public key $(N,e)$ and could trivially use it to verify a guess of the plaintext, which matters (e.g. when the goal is to mask from adversaries the result of a coin toss, the name of someone on the class roll, a PIN number..). To resist that, the randomness added by the encryption padding process needs to be kept secret from attackers, and have at least $b$-bit entropy for $b$-bit security. RSAES-OAEP does that (it injects $2b$-bit, typically 256 bits nowadays), as well as other RSA encryption padding schemes like RSAES-PKCS1-v1_5.

But there are other objectives met by OAEP:

Allowing a security reduction to the RSA problem (which is of finding $M$ from $M^e\bmod N$ for random $M$ with $0\le M<N$). In a nutshell, OAEP padding transforms the plaintext into an $M$ that covers a large fraction of the $[0,N)$ in a random-like way, and allows a strong argument that if we could break RSA+OAEP under CPA or CCA (by this account: CCA1, or CCA2 under the Random Oracle model), we could break RSA or the pseudo-random functions (hash or Mask Generation Function) used in OAEP.
Mitigating the risk of attacks using side channels in the decryption operation when fed malformed ciphertext (information leak by timing to get an error code, or value thereof). These have the potential to transform something performing the decryption into a decryption engine (see Bleichenbacher's attack on PKCS#1 v1.5 encryption). In a nutshell, OAEP is better protected because the comparison done to decide if a padded plaintext $M$ is valid involves comparing hashes (it also helps that it is CCA-secure).

Conclusion: we consider RSA+OAEP secure because OAEP provides a security reduction to the RSA problem under CPA and CCA, and it helps mitigate implementation attacks.


What hash functions can be (efficiently) computed over GF(2^m)?

Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be computed with this circuit?

Answer: all of them.  The combination of addition and multiplication in $GF(2^m)$ is complete.  That is, for any arbitrary function that takes $n$ inputs in $GF(2^m)$ and an output in $GF(2^m)$, there exists a polynomial in $n$ variables that produces that function.

Note that this polynomial need not be simple; however it will exist.


Is there really any way to nullify or avoid MITM attacks?

You can't get a man-in-the-middle (MitM) resistant channel out of a vacuum.

You need some common knowledge beforehand. Luckily all one needs is a shared trust relation.

Suppose the server Steve trusts Carol, suppose further the client Charlie trusts Carol aswell.

As an example I'll give a simplified TLS-RSA key exchange because it's particularly easy.

First Steve needs to submit his public RSA key to Carol for certification. Carol digitally signs Steve's key and embeds in an certificate tying his name ("Steve") to his public key. It is assumed that Charlie can verify Carol's signature. This only needs to be done once.

Charlie now initiates a connection to Steve containing the request for communication and specifying the available cipher suites Charlie supports. They contain informations on how to encrypt and authenticate the data after the key-exchange is finished. Further a random number will be sent in the initial message. Steve will answer with his selection of the cipher suite and his random number.

In the next step Steve will send his certificate. Charlie will verify the certificate by checking Carol's signature and if it's valid will accept the key to be from Steve. Now Charlie randomly chooses a random "pre-master secret" and encrypts it using Steve's public key. He sends this to Steve. Charlie now derives the master secret from his random number, the pre-master secret and Steve's random number.
Now Charlie sends a message indicating that from now on the selected encryption methods shall be used. He finishes this messages with a message authentication code (MAC) on all previous data using the master secret as key.

Only Steve will be able to decrypt this pre-master secret. He decrypts it and derives the master secret himself. Now he verifies the MAC he received. Next he sends the message indicating he's ready to use encryption. He finishes with the same MAC (on all previous data).

Charlie verifies it and can be assured that no MitM attack has taken place because only the holder of the private key could have sent the MAC and he knows that Steve is the holder of the key because Carol confirmed it via the certificate.

Now a standard pre-shared key data exchange protocol starts (a.k.a. "record layer" in TLS terms)

TL;DR: You use digital signatures to bind public keys to identities and use those keys to construct secure key-exchanges.


You can use DTLS here.  C# can call any C API via P/Invoke.  OpenSSL, BoringSSL, Network Security Services (NSS), and mbedtls all provide C interfaces to DTLS.

Unless there are existing bindings, you will need to implement at least some of the P/Invokes yourself, but this is much easier than writing your own cryptographic protocol.

It would be very nice if you could open-source these bindings, for the benefit of those who follow in your footsteps.

Also, note that AES-GCM is, in the absence of hardware support, very tricky to implement in a way that is immune to cache-timing side-channel attacks — so tricky, in fact, that many production implementations are not hardened against such attacks.  Implementations that are immune to cache-timing attacks deliver suboptimal performance.  ChaCha20-Poly1305 is an efficient, secure, and portable alternative.  It is several times faster than pure-software AES-GCM while being immune to many side-channel attacks.  Since you mention mobile devices, you probably will not have hardware support for AES, so ChaCha20 is both faster and easier to implement securely.


Encrypting/Decrypting sensitive information for storage purpose

First, you should carry out a threat analysis and determine the attack scenarios that the encryption is supposed to protect you against.  Without such an analysis, all you're doing is sprinkling magic crypto dust over your database and hoping that it will somehow protect you from any and all possible threats.  (Spoiler: It probably won't.)

For example, some more or less plausible threats might include:

a remote attacker gaining access to the database via SQL injection;
a remote attacker gaining access to an entire server, including all data and keys stored on it, via a remote code execution (and/or privilege escalation) vulnerability;
a remote attacker guessing the password to a privileged account;
an employee with physical access to the servers carelessly disposing of a disk that used to contain sensitive data;
a privileged employee carelessly copying sensitive data to an insecure or publicly accessible location;
a privileged employee maliciously accessing or modifying sensitive data; and/or
a privileged employee's workstation being infected with malware.

Encryption can protect against some of these threats, but not all of them, and the extent to which it can protect against some of those threats depends on the degree of compartmentalization (e.g. separating publicly accessible services onto dedicated servers, implementing strict firewall rules, requiring secure multi-factor authentication for all accounts, storing active encryption keys in a hardware security module, splitting inactive master keys into multiple shares and storing them in separate locations, etc.) that you're willing to implement and endure.

Of course, it's also possible that your sole proximate reason for encrypting your data is to pass a certification that requires it.  In that case, you may wish to review the certification standards and determine what they require of your encryption and what threats they expect it to counter.

Depending on your specific requirements and threat model, it's possible that your need for encryption of data at rest might be sufficiently served simply by activating built-in encryption features of your database software, or even just by storing the database on an encrypted disk.  If so, that's certainly the simplest option, even though it protects only against a limited set of attacks.

Database front-end such as CryptDB may also be useful, although again, you should carefully review their ability to protect you against the threats you've determined to be relevant while still providing the access to the data that you need.

If you must implement your own database column encryption, and if symmetric-key encryption is sufficient for your needs, I would strongly recommend using AES-SIV (or possibly AES-GCM-SIV).  If you don't need to do equality comparisons on the encrypted fields, use SIV with a unique random nonce for each field (and consider including the table and column names and the row's primary key as associated data).  If you do need the ability to compare encrypted fields for equality without decrypting them, use SIV without a nonce (but preferably still with the table and column names as associated data).

(If you find yourself wanting to do any kind of searching or comparisons on encrypted data besides simple equality comparison, I would strongly suggest reviewing your design and trying to find an alternative solution.  While there do exist various "order-preserving" and/or "searchable" encryption schemes that claim to provide this functionality, they do not — and fundamentally cannot — meet the level of security normally expected of a modern encryption scheme, as the ability to perform such comparisons unavoidably leaks information about the encrypted data.  Even nonceless SIV should be used with caution, since it leaks the equality of encrypted values.)

In some cases, e.g. if you want your server to be able to add new encrypted values to the database but not to be able to decrypt existing data once it has been added, you may want to use a public-key encryption scheme.  In particular, you will probably want a hybrid cryptosystem such as ECIES, where the public-key part of the system is used to generate and encrypt a random symmetric cipher key, and this random symmetric key is then used to encrypt the data itself.  The main disadvantages of such systems compared to AES-SIV are their extra complexity and their higher overhead costs (both in terms of processing time and storage requirements).  Their main advantage, of course, is that the confidentiality of the data is not compromised even if an attacker gains access to the public encryption key.


What's the algorithm behind MySQL's sha256_password hashing scheme?

According to the MySQL Server Blog, it is:

  The advantage of mysql_native_password is that it support challenge-response mechanism which is very quick and does not require encrypted connection. However, mysql_native_password relies on SHA1 algorithm and NIST has suggested to stop using it.

  caching_sha2_password tries to combine the best of both worlds.

XOR( SHA256(pwd),SHA256(SHA256SHA256(pwd)) , Nonce)

  \$A\$005\$wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3

From the source code sha2_password.cc

  Expected format

  DELIMITER[digest_type]DELIMITER[iterations]DELIMITER[salt][digest]

Where the delimiter is $

  digest_type:

  A => SHA256

  iterations:

  005 => 5*ITERATION_MULTIPLIER

  salt:

  Random string. Length SALT_LENGTH

  digest:

  SHA2 digest. Length STORED_SHA256_DIGEST_LENGTH

From file i_sha2_password.h

  #define CRYPT_SALT_LENGTH 20

  const unsigned int STORED_SHA256_DIGEST_LENGTH = 43;


Why is it important that phi(n) is kept a secret, in RSA?

From the definition of the totient function, we have the relation:

$$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$

It then easily follows that:

$$(n + 1) - \varphi{(n)} = p + q$$
$$(n + 1) - \varphi{(n)} - p = q$$

And you know from the definition of RSA that:

$$n = pq$$

Substituting one into the other, you can derive:

$$n = p \left ( n + 1 - \varphi{(n)} - p \right ) = -p^2 + (n + 1 - \varphi{(n)})p$$

With some rearranging, we obtain:

$$p^2 - (n + 1 - \varphi{(n)})p + n = 0$$

This is a quadratic equation in $p$, with:

$$\begin{align}a &= 1 \\ b &= -(n + 1 - \varphi{(n)}) \\ c &= n \end{align}$$

Which can be readily solved using the well-known quadratic formula:

$$p = \frac{-b \pm \sqrt{|b|^2 - 4ac}}{2a} = \frac{(n + 1 - \varphi{(n)}) \pm \sqrt{|n + 1 - \varphi{(n)}|^2 - 4n}}{2}$$

Because of symmetry, the two solutions for $p$ will in fact be the two prime factors of $n$.

Here is a short example, let $n = 13 \times 29 = 377$ and $\varphi{(n)} = (13 - 1) \times (29 - 1) = 12 \times 28 = 336$. Using the quadratic equation shown above, we need to use the following coefficients for the equation:

$$\begin{align}a &= 1 \\ b &= -(377 + 1 - 336) = -42 \\ c &= 377 \end{align}$$

Thus we have the following quadratic to solve:

$$p^2 - 42p + 377 = 0 ~ \implies ~ p = \frac{42 \pm \sqrt{|-42|^2 - 4 \times 377}}{2} = \frac{42 \pm 16}{2}$$

Finally, we calculate the two solutions, which are the two prime factors of $377$ as expected:

$$\frac{26}{2} = 13 ~ ~ ~ ~ ~ ~ ~ ~ \mathrm{and} ~ ~ ~ ~ ~ ~ ~ ~ \frac{58}{2} = 29$$

In conclusion, knowledge of $\varphi{(n)}$ allows one to factor $n$ in time $O(1)$. The other answers are equivalent, in that knowing $d$ achieves the same result (loss of any security properties of RSA), but just for completeness I thought it would be a good idea to show how $n$ can be factored with this information.


So, does this mean AES doesn't have nothing-up-my-sleeve property?

That is correct in a sense, the design of the s-box is formulaic. It is generated using finite field inversion, an affine transform, and xor of a constant (0x63). It can be described as a simple equation.

The other parts of round transformation also have a very simple description, the most complex being the MixColumns operation.

The key schedule adds a round constant which is generated simply by consecutive multiplication by 2 in a finite field.

Not using NUMS numbers allows the entire encryption operation to be described as an equation in a much more simple manner, and is easier to analyze. Rational is given for all choices of constants, although some seem.. incorrectly chosen, like the s-box constant, which causes a self-inverse mapping (see my comment on answer). A limited number of specifically chosen constants also prevents anything from being hidden in the same manner NUMS numbers do.


Bootstrapping is the procedure that refreshs a ciphertext by running the decryption function homomorphically. By refresh you should think in something like decrypting and encrypting again, so the resulting ciphertext has little noise on it. Therefore, the main goal of bootstrapping is to manage the noise and it is used to transform a somewhat homomorphic encryption scheme into a fully homomorphic one.

Relinearization is a technique to transform quadratic equations in linear ones (generally, on a different set of variables). It is used to

gain the ability of performing homomorphic multiplications over (algebraic) structures that would allow only homomorphic additions;
reduce the ciphertext's size after multiplication (for instance, in this scheme, the ciphertext's size grows from $n$ to $n^2$ elements after multiplication and relinearization is used to generate ciphertexts again with $n$ elements);
make a ciphertext decryptable under the original secret key: in some (RLWE based) schemes, when we multiply two ciphertexts encrypted under a secret key $s$, we obtain a ciphertext encrypted under $s^2$. Then, relinearization (which is usually called keySwitch in those works) is used to obtain a new ciphertext that encrypts the same product but under $s$. (See, for instance, this work).

  which is the more expensive (computationally) and why?

I think that it depends on the scheme, but, in general, bootstrapping is more expensive because it involves evaluating the decryption circuit homomorphically while relinearization is usually performed just by calculating a inner product. Furthermore, bootstrapping almost always requires squashing the decryption circuit so that it can be evaluated homomorphically, but such changes on the scheme generate a more complex scheme with bigger ciphertexts and keys (which makes everything more expensive).


Is the EdDSA signature scheme provable security?

EdDSA is Schnorr signatures over the Edwards curve, with an additional twist that it is made deterministic. The basic Schnorr scheme can be proven secure under the discrete log assumption in the random oracle model. Furthermore, any probabilistic signature scheme can be made deterministic by applying a PRF (with a key that is part of the private key) to the message in order to derive the randomness used. This is essentially what EdDSA does. Thus, yes, it is provably secure in the random oracle model, assuming that the discrete log problem is hard in that group.


How to compare between two cryptographic algorithms in terms of security?

TL;DR, you don't.

At this point, we have algorithms we believe are unbroken by current adversaries. For hashing, this includes the SHA-2 family of hashes, SHA-3, BLAKE2b and others. For authentication, we have the HMAC family of functions, the UMAC family of functions, Poly1305, and others. For symmetric encryption, we have AES, ChaCha20, and others. For asymmetric encryption, we have RSA, too many elliptic curves to name, and others. For digital signatures, we have RSA, ECDSA, and others.

When used correctly and with appropriate key sizes, all of these algorithms are considered secure. "More" secure without additional context is a mostly meaningless question: none of these algorithms will ever be brute-forced. Some or all of these algorithms may contain flaws in their design which could render them useless or weakened tomorrow, next year, or a century from now. Some or all of these algorithms may never be broken. But there's no way to know which ones will fall into which category until this happens.

In specific contexts, some algorithms may have desirable properties. The so-called safecurves, for example, are considered more resilient against poorly-written implementations. Block ciphers like AES in virtually all real-world scenarios must be used in a mode of operation that should be chosen based on  the (not necessarily security-based) requirements of your application.

When misused, any algorithm is typically susceptible to catastrophic failure. And unfortunately, virtually any implementation or composition of cryptographic primitives by amateurs (and even, frequently, professionals) is prone to mistakes.

The solution to this is to operate at the highest level of abstraction available to you which is provided by respected cryptographers and software developers. Typically, this means GPG for data at rest, TLS for data in motion. These projects have the benefit of many eyeballs, decades of fixing security issues, and reasonably general default choices for algorithms.

If you're not a seasoned cryptographer and you're making a decision about what cryptographic primitive to use, you have already lost.


For this answer I'll use the paper linked in the comments: "Relations Among Notions of Security for Public-Key Encryption Schemes" by Bellare, Desai, Pointcheval and Rogaway (PDF) which also contains this very nice overview graph on page 4 of the PDF:

  How do Indistinguishability(IND) and Non-Malleability(NM) differ?

Generally in the IND setup you try to infer some information (at least 1 bit) about a given plaintext using your given capabilities (encryption and decryption oracles at the various stages).

In the NM setting on the other hand you are given a ciphertext $y$ of a plaintext $x$ and now want to come up with some "meaningful" relation $R$ such that given $y$ you can find a vector $\bf y$ which when component-wise decrypted yields a vector of plaintexts $\bf x$ such that $R(x, {\bf x})$ holds.

In case you are asking yourself how the distinction between CCA1 and CCA2 is implemented for NM, in CCA1 you only get access to a decryption oracle before  seeing $y$.

  Which is the stronger notion of the two [...]?

As can be seen in the above graph, for a given attacker capability X, NM-X generally implies IND-X but the converse doesn't always hold.

  [In] which (if any) scenario are they equivalent?

As can be seen in the above graph, NM-X and IND-Y are equivalent only if X=Y is the CCA2 attacker model.


gcm-spec, this document has "AES Test Vectors" section in the end. There are a numerous test cases with all intermediate results for encryption and ghash. I found them a rather useful.


Encryption of a number with RSA bigger than $n$

I'm assuming that you mean "encrypt with a single encryption operation" (and not to split it up into consecutive blocks such that each fits into $Z_n$).

RSA with modulus $n$ works in the ring $Z_n$, i.e., the set of integers $\{0,\ldots,n-1\}$. So you are limited to working with messages in this set. If you want to encrypt a message $m\geq n$, you are essentially encrypting a message $m'$ in the set $\{0,\ldots,n-1\}$ such that  $m'\equiv m\pmod n$, i.e, the message $m$ is "implicitly" mapped to another message $m'$ in the set $\{0,\ldots,n-1\}$ which is the remainder of $m$ when divided by $n$ (the two messages $m$ and $m'$ can be considered identical when working modulo $n$ , i.e., in the residue class ring $Z_n$).

Now, the problem is that after encryption of $m\geq n$ with RSA and decryption thereof you get back $m'$ and you cannot figure out what your initial message $m$ was, since $m'$ is in the set $\{0,\ldots,n-1\}$ and every message that has the same remainder modulo $n$ as $m'$ will be a potential candidate for $m$ (and that are infinitely many ones). So you would be lost. Consequently, to make encryption and decryption of a message $m$ unambiguously, you need to limit the messages you encrypt to the set $\{0,\ldots,n-1\}$.

You may also look at this question and its answers for a more detailed discussion (on the residue class ring $Z_n$).


How to know the type of encryption method

Ciphertext should be indistinguishable from random. The same goes for hash functions such as MD5 and SHA1. But as you already found out, this is only for the given output domain: the set of all possible ciphertext or hashes. It depends on the algorithm how much variation there is in ouput domains:

for hash functions the output size is part of the definition of the hash function, e.g. 160 bits for SHA-1;
for RSA - an asymmetric cipher primitive - the ciphertext is within 0 and N, the public modulus of the key used;
for DES, triple DES and AES, which are block ciphers, the size of the output is exactly the block size.

Now if we focus on the block ciphers: block ciphers are used in a mode of operation. Without the mode of operation the output of AES is not secure; in other words, AES needs a mode of operation to be used as generic, secure cipher.

It depends on the mode of operation what the size of the ciphertext will be. For instance for CTR mode the output is the same size as the plaintext - it doesn't need to be padded. For CBC some kind of padding is required and the output will always be a multiple of the block size.

So where does that leave us? Well, basically we cannot tell all that much from the ciphertext itself. We can tell that ciphertext is certainly not the result of some kind of ciphers.

For instance a 6 byte ciphertext cannot be the output of a cryptographic hash function and is not the output of 3DES or AES in CBC mode. This means that the analyst can skip these algorithms when trying to find the right one from a particular set.

On the other hand the same 6 byte ciphertext can be the result of AES or triple DES in CTR mode. Which one cannot be determined by the ciphertext alone.

So the encryption mode can often not be determined that way. Note that the encryption method is generally considered known by the attacker. It is not considered a secret by the parties using the cryptography.

This is known as Kerckhoffs principle. This is basically because the method of cryptography is only one static known fact, part of the protocol description. Hiding the cipher only makes the life of an attacker slightly harder; relying on secret cipher algorithms has resulted in spectacular failures in the past.

Note that for your question base 64 encoding really doesn't matter. You simply reverse the encoding before analyzing the ciphertext.


Maybe there is an encryption scheme out there that can be 'broken' in polynomial time, but only with super-polynomial space.

That possibility can be excluded; if an algorithm uses $F(x)$ time (for any $F$), then that algorithm can be implemented using $O(F(x))$ space.  The reason is fairly obvious; in $F(x)$ steps, the algorithm can access at most $\ell F(x)$ memory locations (assuming a 'step' accesses at most $\ell$ memory locations, where $\ell$ is some constant).  So, by tracking which memory locations the algorithm actually touches, and just tracking those (which another constant multiplier in terms of overhead), and so this modified algorithm uses (at most) a constant factor more memory than the total number of steps.