Hardness of LPN problem with small secret

There is a simple trick (known in the LWE literature as the Hermite normal form of the problem) that takes an existing LPN problem and transforms it into a problem in which the secret has the same Bernoulli distribution as the error. This trick is proved in Lemma 2 of Applebaum et al. for a more general case, or on the (Ring-)LPN attacks of Kirchner (Section 4.3.2) or Bernstein and Lange (Section 3).

The idea is that you start with a number of $n$ samples $(\mathbf{a}_i, c_i)$, where $c_i = \mathbf{a}_i \cdot \mathbf{s}$. Suppose, now, that some subset of the $\mathbf{a}_i$ vectors is linearly independent (you do not need much more than $n$ randomly-sampled $\mathbf{a}_i$ for this to be the case), and let them form the matrix $M = \{ \mathbf{a}_{i_1}, \dots, \mathbf{a}_{i_k}\}$. Then we have $$\mathbf{c} = M^T\mathbf{s} + \mathbf{e},$$ where $\mathbf{c} = \{ c_{i_1}, \dots, c_{i_k}\}$ and $\mathbf{e} = \{ e_{i_1}, \dots, e_{i_k}\}$ are the corresponding vectors to the chosen $\mathbf{a}_i$. But we also have $$\mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e}).$$

Now that we have this matrix $M$, query the LPN oracle with a new sample $\mathbf{u}$, receiving $(\mathbf{u}, v = \mathbf{s}\cdot \mathbf{u} + e)$. But you can convert this into a  second oracle that returns $(M^{-1}\mathbf{u}, \mathbf{c}\cdot M^{-1}\mathbf{u} + v)$.
Obviously, $M(M^{-1}\mathbf{u}) = \mathbf{u}$. Further,
$$
\begin{align}
\phantom{=}  &\mathbf{e}\cdot M^{-1}\mathbf{u} + e \\
= &(M^T\mathbf{s} + \mathbf{c})\cdot(M^{-1}\mathbf{u}) + e  \\
= &M^T\cdot\mathbf{s}\cdot M^{-1}\mathbf{u} + \mathbf{c}\cdot  M^{-1}\mathbf{u} + e \\
= &\mathbf{s}\cdot M M^{-1}\cdot u + \mathbf{c}\cdot M^{-1}\mathbf{u} + e \\
= &\mathbf{c} \cdot M^{-1}\mathbf{u} + v.
\end{align}
$$ So this is now an instance of LPN with Bernoulli-distributed secret $\mathbf{e}$, from which you can extract the original secret as $\mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e})$.

In other words, given some algorithm that solves LPN with a Bernoulli-distributed secret, you can also solve regular LPN with the same error distribution.


Please explain me why we require $2^m$ & $2^{\frac{m}{2}}$ random messages

$2^m$ requirement is for the pre-image attack. You have to hash approximately  $2^m$ messages to find the message that has the same value you were looking for if the hash function has pre-image resistance.

In a collision attack, you are looking for two messages that have the same hash value.

If you look at Wikipedia Birthday Paradox at section Cast as a collision problem, it is also generalized for the arbitrary number of days not just for 365 days. The approximation is given by

$$n \approx \sqrt{2^m}$$ and we call it generic birthday attack.

Note that: if you find an attack which is faster than generic birthday attack like SHA-1 attack you will be famous.


I'll try to answer your questions. First I shall write  Coppersmith's Theorem.

Theorem.  Let $0<\varepsilon<1/d$ and $F(x)$ be a monic polynomial of degree $d$ with at least one root $x_0$ in  ${\mathbb{Z}}_N$ and $|x_0|<X =\lceil 0.5N^{1/d-\varepsilon}\rceil.$  Then, we can find $x_0$ in time $poly(d,1/\varepsilon,\ln{N}).$

First, notice that in your polynomial you know the factorization of the modulus. But, in Coppersmith method, you can find a solution $\mod{N},$ even if you don't know the factorization of $N$ (e.g. if $N$ is an RSA modulus).

should the coefficient of $^3$ be 1?

Yes, in the theorem of Coppersmith we deal with monic polynomials.

should the  of all the coefficients of $$ and $∗81$ be 1?

I did not understand what you mean. The gcd of the coefficients of the polynomial with $n?$

If we know the factorization of 81∗, can we benefit from it?

$81*P$ is your modulus. So, no. You can apply Coppersmith without knowing the factorization of the modulus.

What is the problem with using the Coppersmith method for
with 1000 digits?

No problem, if the assumption of the Theorem are satisfied.


How to decode a Playfair message with a partial key?

The quick and dirty way would be to write a computer program to try all the remaining possible key letters in the ? positions and print out the resulting plaintexts.  Hopefully, one of them will stand out as being obviously correct.  Remember that each letter can occur only once in a Playfair key, and that your key is already pretty long, so there aren't a lot of unused letters left in the alphabet for the unknown positions.

The slightly more clever method (which is probably what you're supposed to use) would be to first see if any of the ciphertext letter pairs can already be decoded without knowing the missing key letters (or any of the letters on the last row of the key matrix, since they obviously depend on the missing letters too).  You can do this by hand (again, presumably the intended method, since that's the way you'll actually learn how a Playfair cipher works), or you can cheat and use any standard Playfair decoder tool and just try a couple of different variations of the key and see which letters of the plaintext change.

For example, here are the results of trying to decode the message (using this online decoder) with a few different choices of missing letters, out of the eight letters not already present in the key (F, H, M, P, S, T, Y and Z):

Ciphertext:              LG OX MV YH IM IS YS SQ WM ZX
Decoded with ??? = FHM:  WE LC OF SK LW LT TP PH OW SU
Decoded with ??? = PST:  WE LC YN MF AI LR HK QB IZ HU
Decoded with ??? = TYZ:  WE LC PN EL AI WM BH FB IS LD

You could try a few more choices, but what should be apparent here is that decoding the first two letter pairs clearly isn't affected by the missing key letters, and thus, that the plaintext begins with the letters WELC.  Now, there aren't a lot of English words that begin with those letters — in fact, I can only think of a single really likely one.

Assuming that the plaintext begins with "Welcome", you can now rule out any choices of missing letters that would result in MV decrypting to anything other than OM.  Even if that's not enough to solve the problem completely, you should at least be able to lock in some more plaintext letters, and so hopefully guess more words in the plaintext, and so get more known plaintext letter pairs, and so on.

In fact, if you consider the way the Playfair cipher works, knowing that OM encrypts to MV would immediately tell you something useful: namely, that the letters V, M and O must all appear in the same row or in the same column, and that they must be adjacent and in that specific order.  In this case, looking at the key matrix:

? E N V G
Q ? R K B
D X A C U
? L I O W
? ? ? ? ?

this tells you that, for this plaintext / ciphertext pair to be correct, M would have to appear in the fourth column of the last row, below O and above V.  (Remember that the rows and the columns wrap around.)

Unfortunately, using the standard Playfair key matrix setup, where any letters left over from the key are simply appended in alphabetical order, there is no way to get M in that position simply by filling in the ? marks in the key!  So either:

my guess that the first plaintext word should be "welcome" is wrong,
the ciphertext contains an error (always possible, although hopefully rare in well designed crypto puzzles),
the key is actually longer than what we're given, and we're supposed to arbitrarily assign the remaining five letters for the last row too, or
there's something else funny going on, and this isn't a standard Playfair cipher after all.

If we assume #3 above, and start shuffling the letters in the last row, it is in fact possible to get a plaintext that begins with "welcome to" and where the rest looks at least vaguely like English (although not obviously enough so for me to declare it as clearly the correct solution without knowing where the puzzle came from and what other clues might be available).  So, alas, I have not been able to definitively confirm that these steps will yields a correct solution to your puzzle.  But at least they do illustrate the general method by which such problems can be attacked.


The difference is that when using ZKPP, the user's input is the password; while using public key on the server to authenticate, the user's input is her private key. There are two problems I can see:

When using the public key, the user have to copy the private key to the device she uses. This could be quite inconvenient.
The private key needs to be protected. If the private key is encrypted by a password, then an offline brute-force/dictionary attack is possible (by testing decryption with the public key). ZKPP should allow only on-line attacks.

In many systems that use public key for user authentication, the user's private key is often stored in a tamper-proof/evident device, e.g. smart card or hardware token. This can solve partially the problems mentioned above.


Why Nonces and timestamps are used in Public key authority?

To understand how nonces and timestamps are used to prevent a replay attack, you must understand generally what a replay attack is. A replay attack is a network attack in which a data transmission (that is valid) is repeated or delayed. An attack like this is usually done by an adversary who happens to intercept this data and re-transmits it.

If Alice (Initiator A) and Bob (Responder B) are conversing, Alice can send over a nonce with a MAC which can be checked by Bob to verify that it is Alice and not an adversary sending it.

Timestamping also is important because if Alice sends a message with one, Bob can choose to only accept messages with reasonable timestamps.

So for 'Certificate-Based Key exchanges', Alice provides nonce, or a timestamp along with her certificate. This will help preventing Replay Attacks!


How are the lower levels calculated using upper levels in an optimized Merkel Hash Tree?

The usual way to do this is by using a CSPRNG to generate the leaf values, such as AES in counter mode.  That way, once you have calculated the entire tree, you only need to store the upper layers, the secret AES key, and the initial counter value, and it is quite easy to recalculate very quickly any particular branch you need.

For example, let's say you generate a tree of depth 20 using AES in CTR mode to generate the values $v_0, v_1, v_2, ...v_n$ (in figure 1 on page 5 of the paper you linked), so there is a corresponding counter-value $c_i$ for each $v_i$, such that $v_i = E_K(c_i)$.  Let's also say you only store the AES key, the first counter value, and the top 9 layers of the hash tree (so you only need to keep 511 hashes, and can discard the remaining 1 million or so hashes in the tree).

To recalculate the path from any one particular leaf, $v_i$, back to the top-most node, all you need to do is re-generate the leaf value for $v_i$ using AES and the counter value $c_i$ (which is easy if you know the initial counter value and the index $i$), plus 2047 of its immediate neighboring values, and then use the hash function $H$ to re-generate the branch of the tree from those 2048 values up to one of the 256 stored values in layer 9 (which takes much less time to calculate than the initial set-up because you are only doing one 256th of the tree rather than the whole tree).


Generating dataset for LFSR stream cipher

Firstly using an LFSR output as a keystream generator is insecure, due to the Berlekamp-Massey attack which only needs $2m$ bits of known or guessed plaintext to break the stream with period $2^m-1.$

The coefficients  you are asking about, must define a polynomial $$c(x)=c_0+c_1 x +c_{m-1} x^{m-1}+x^m$$ with $c_0=1,$ and $c(x)$ must be primitive. See Wikipedia here.


Using multiple cryptographic keys for encryption?

A more standard way is not to make any of this yourself.  Use a proper database like Oracle 11g.  It's all built in.  And you can even use it for free in some circumstances.

You think that it's simple just to AES some records in, but there's a great deal more for a production system.  Oracle have spent millions developing all this functionality and vastly more like key and privileged user management and backup/restore whilst addressing all the performance issues.  How would you handle encrypted joins for example?  You won't do better building something yourself.

Have a look at their transparent data encryption FAQ.


RSA: Given two very large prime $p,q$ and $n=p\;q$, how to quickly find $e$ such that $\gcd(\varphi(n),e)=1$?

Normall practice is to pick public exponent as a small prime(preferably with few set bits in binary representstion). If the public exponent is prime we only need to verify it doesn't devide $\phi(n)$.


Prove that the $x^8+x^4+x^3+x+1$ is irreducible over $\mathbb{Z}_2[x]$

Definition: A non-constant polynomial is said to be irreducible if it is cannot be factored into a product of two non-constant polynomials. In other words; if $p(x) = q(x)t(x)$ and it is irreducible then either $q(x)$ or $t(x)$ is a constant polynomial.
One way to prove that is $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$ is checking the divisibility by the lower degree irreducible polynomials. First degree 1, then degree 2, then degree 3, and degree 4 will be enough to determine since a degree 8 can be factored into two polynomials with possible degrees as $1\cdot 7,2\cdot 6, 3\cdot 5$, and $4 \cdot 4$.
Below all the arithmetic is performed on $\operatorname{GF}(2)[x]$

degree polynomials are $x$ and $x+1$. We can check the divisibility by setting $p(0) \stackrel{?}{=} 0$ or $p(1) \stackrel{?}{=} 0$. $p(0) = 1 \neq 0$ and also $p(1) = 1 \neq 0$. Therefore degree one polynomials doesn't divide $p(x)$. This is by the factor theorem and here a nice proof in Math.SE.

degree polynomials, where we have four polynomials;

\begin{align}
 & x^2+x+1\\
 & x^2+x \\
 & x^2+1\\
 & x^2\\
 \end{align}
Let see why $x^2+1$ is not irreducible;
\begin{align}
(x+1)\,(x+1)&=x\,(x+1)+1\,(x+1)&&\text{by distributivity}\\
  &=x^2+1\,x+1\,x+1&&\text{.}\\
  &=x^2+(1+1)\,x+1&&\text{.}\\
  &=x^2+(0)\,x+1&&\text{since the coefficients are in }\operatorname{GF}(2)\\&=x^2+1
\end{align}
with a quick check that only $x^2+x+1$ is irreducible. To see that $p(x)$ is not divisible by $x^2+x+1$ perform division and look for the remainder. One can use this Sage script
R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
q = x^2 + x + 1
p.quo_rem(q)

the output is $(quo = x^6 + x^5 + x^3, rem = x + 1)$, . i.e cannot divide.

degree irreducible polynomials

\begin{align}
 & x^3 + x + 1 \\
 & x^3 + x^2 + 1
 \end{align}

degree irreducible polynomials

\begin{align}
 & x^4 + x + 1 \\
 & x^4 + x^3 + 1\\
 & x^4 + x^3 + x^2 + x + 1
 \end{align}
These polynomials are generated with SageMath
degree=4
R = GF(2)['x']
for p in R.polynomials(degree):
     if p.is_irreducible():
         print(p)

To test all the division use the below
R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
lst = [ x^2 + x + 1,  x^3 + x + 1,  x^3 + x^2 + 1,  x^4 + x + 1 , x^4 + x^3 + 1, x^4 + x^3 + x^2 + x + 1]

for t in lst:
    print(p.quo_rem(t))

The output is
(x^6 + x^5 + x^3, x + 1)
(x^5 + x^3 + x^2 + 1, x^2)
(x^5 + x^4 + x^3, x + 1)
(x^4 + x, x^3 + x^2 + 1)
(x^4 + x^3 + x^2 + x + 1, x^3 + x^2)
(x^4 + x^3 + 1, x^3 + x^2)

Therefore $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$

Note 1: low degree irreducible binary polynomials are important in Cryptography since they reduce the required arithmetic. Gadiel Seroussi, in 1998, made a huge list in Table of Low-Weight Binary Irreducible Polynomials. The list contains binary irreducible polynomials up to 10000 degrees.
Note 2:  A014580 from
The On-Line Encyclopedia of Integer Sequences contains a list of binary polynomials, encoded in binary, or evaluated when $x=2$. The $p(2)$ is 283.
2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375,...
The bolds irreducibles are listed in this answer.
Note 3:  A001037 keeps the number of degree-n irreducible polynomials over $\operatorname{GF}(2)$. There are 18 in degree 8 and $p(x)$ among the lowest possible weight.
degree 1  2  3  4  5  6  7   8
count  1, 2, 1, 2, 3, 6, 9, 18

and this can be counted by $$L_q(n) = \frac{1}{2} \sum_{d|n} \mu (\frac{n}{d})q^d$$


How can I decrypt this kind of variation of block cipher?

The question likely really is:

It is known $c$ with $c = E_{K_1}(m \oplus K_1 \oplus K_2)$, and a few distinct plaintext/ciphertext pairs $(m_i,c_i)$, that is with $c_i = E_{K_1}(m_i \oplus K_1 \oplus K_2)$. However, $c$ is not one of the $c_i$ (which would make finding $m$ trivial).

Define a strategy to find $m$, despite the terms $\oplus K_1 \oplus K_2$ in how the cipher operates. That should work whatever the internals of $E$ (which is assumed known per Kerckhoffs's principle, but not given). If necessary, assume that a lot of computing power is available, enough for about $2^\ell$ encryptions or decryptions using $E$ and whatever key, which would be enough to brute-force a normal use of $E$ as $m\mapsto E_K(m)$.

Hint 1: How would you confirm (with excellent confidence) or infirm (overwhelmingly often) an hypothetic guess of $K_1$, despite not knowing $K_2$?

Hint 2: Put yourself in the skin of an attacker. You have a black box implementing $E$, where you can enter key and data each as $\ell$ bits, press one of two buttons marked "encrypt" or "decrypt", and that applies $E$ or $E^{-1}$ as asked, data gets changed, and you see the new value thanks to $\ell$ LEDs wired on the data bits. In particular, if you press the other button, the data gets back to the previous value. That black box is an encryption/decryption oracle for $E$ (though one not knowing the key, as some oracles do; rather, it operates with any given key).

Assume that some fairy gave a tip that $K_1$ is that $\ell$-bit value. How do you put that box and what you know (stated in this answer) to use in order to confirm or infirm the tip, then (if confirmed) find $m$ ?

Next, replace the fairy (these are harder to implement with silicon chips than oracles are) by a lot of uses of the black box.

Further hints (hover mouse to see)

   3. You'll need at least two plaintext/ciphertext pairs to check the fairy's tip, and three to carry the attack.

   4. You'll need a mere two uses of the box to check that fairy's claim, and very little extra computations that one can carry with pencil and paper to note intermediary results. Addition seems complicated in comparison.

   5. You can achieve that with a single button of the black box, but not any button.

   6. If the fairy gave the right $K_1$, also putting the values of $m_0$ and $c_0$ to use, a single precise use of the black box plus a little extra allows to find $K_2$. The rest is easy.


What does the strict avalanche criterion mean?

As pointed out in the comment, SAC is just one criterion relevant to diffusion, useful in ciphers as well as hash functions but by no means enough to provide security under any reasonable definition.

Just a partial list of desiderata for Sbox function design, optimal nonlinearity, high degree, low differential probabilities, high degree as a univariate polynomial, algebraic immunity, correlation immunity, etc should be enough to convince one of this.


Can POS devices really generate random numbers?

Modern POS devices are designed to meet the strict security requirements of payments industry (search for PCI-DSS standards). They are typically based on a SoC designed specifically for secure payment applications. An example of such SoC:
https://www.broadcom.com/products/embedded-and-networking-processors/secure/bcm5892/#overview

From the datasheet:
"The random number generator (RNG) is a true random source. It utilizes free-running oscillators to capture thermal noise as the source of randomness. It has been used in numerous devices (such as BCM5820, BCM5821, BCM5841, or BCM5890) and been evaluated as a valid source for seeding FIPS approved pseudo-random number generators as the initial secret value"

If the POS in question runs Linux - it's fairly new, but if in doubt you can always query its vendor directly.


This is actually quite a common problem in cryptographic systems. This can be looked at as proving two different things:

Is the server currently storing all of the elements a specific client has given it before in order (is it honest with us)?
Is it giving us all of the other client's data (is it honest with others)?
Will it continue to act as an append-only log in the future (will it always be honest)?

Is it honest with us?
This is and easy to solve problem, solvable by a simple Merkle tree (also hyped as a "blockchain"). Publish a list of tuples <hash(previous_element), current_element> and the hash of the most recent one, known as the head. Now a verifier can update by looking at the head and downloading it, then looking at the previous hash and downloading that, and so on until it reaches the head it previously stored.
This only verifies that nothing before the previous head has been altered or removed: an omission or alteration before the previous head would change the head's hash, so the client would be able to detect it.
Of course, the client doesn't need to store the whole history; they just need to verify the hashes all the way down to their previous head, and then store the new head's hash, making this very space efficient.
If you want to restrict who can append, add a ring signature to the tuple, and give each validated client a key in the ring.
Is it honest with others?
The second one cannot be proven without some form of communication between the clients. This is a simple information-theoretical result: there is no evidence the server could provide that would convince you that a client had not added something to the database, as it could just present you with the state it had when you last appended to it. However, if two clients have diverging histories, you can prove that either the client is lying, or the server is. If there is a group of clients that all trust each other, then even an evil server would have to act honestly with all of them. Conversely, this could be turned into a peer-to-peer protocol, with clients acting as servers for others, making it harder for an adversary to compromise completely.
If you are going down the authenticated route, the server would be unable to successfully forge an entry in the log.
Will it always be honest?
The last one is impossible to prove. My evil server could be simulating an honest one, maybe even running the honest code, up until a point where I chose to change it for a different one. Someone could unplug the cable to my server and plug it into theirs. I could maintain two logs, an honest one I show to you, and a dishonest one I show to everyone else, or even just show each client only the results they themselves had appended. These are problems that would apply to any system, not just the one that I set out above.
In the real world
A real-life example of this is the "Certificate Transparency Logs". These are used to prove that a CA has issued a TLS certificate (used for securing websites). This means that an attacker cannot surreptitiously create a certificate and use it to impersonate a site: they must publish it's issuance for the world to see (allowing it to be revoked). This record is a kept as a Merkle tree (with each CA contributing a branch) and replicated by multiple different servers, who watch for alterations in the others history. If you want to read up on this similar system, their website is here.


Why can't decrypt with OpenSSL if salt changed (for CBC and ECB)

In your command:

openssl enc -aes-256-cbc -in texte -out encrypted_texte -k password

a password is supplied, which will be used to derive the key and IV for encryption. The salt stored in the file is used in conjunction with your password for this purpose. Therefore when you change the salt, you will get both a different IV and a different key in the decryption process, not just the IV. Then you will get problem decrypting in block modes such as CBC and ECB because the padding in the decrypted plaintext will not be correct (decrypted with a wrong key). While in stream modes like CFB, there is no padding, so modifying the salt won't cause a problem, but you will get wrong plaintext back.

Edit to add: the EVP_BytesToKey() function is used to turn the password and salt into the key and the IV.


Is This method of generating Initialisation Vector for Cipher Block Chaining secure?

I have not looked in detail at the standard you linked to, but in general, applying a PRF (such as HMAC) to the plaintext (plus associated data and/or a nonce, if any) to derive a message authentication tag, and then using the same authentication tag as the IV to a conventional IND\$-secure length-preserving IV-based encryption scheme, is an instance of the "SIV construction" (Rogaway & Shrimpton 2007, pp. 6–9).  Thus, if the assumptions of Rogaway & Shrimpton's proof are met, this construction yields a secure deterministic authenticated encryption scheme (if used without a nonce) or a misuse-resistant authenticated encryption scheme (if used with a nonce) in the sense defined in the paper.

However, a notable issue in applying the SIV proof to the BACnet scheme (as you describe it) is that basic CBC mode (without ciphertext stealing) is not length-preserving.  In particular, the scheme you describe appears potentially vulnerable to the CBC padding oracle attack if an attacker can distinguish a CBC padding error from an HMAC mismatch.  Even if the recipient is specified to return the exact same error in both cases, it might still be possible to distinguish the two cases by timing how long it takes the recipient to reject the message.

A simple solution to this issue would be to replace CBC with a length-preserving encryption mode, such as CTR, CFB or even CBC with ciphertext stealing.

Ps. I thought this question seems vaguely familiar, and while searching for references I stumbled across an earlier very similar question about HMAC + CBC in an SIV-like construction that I'd previously answered:

Is this method of deterministically using CBC secure?

Also, for general information about the security of the MAC-and-encrypt structure of SIV mode, see the following question:

Why is synthetic IV (SIV) mode considered deterministic authenticated encryption (DAE)?

as well as the paper "Reconsidering Generic Composition" by Namprempre, Rogaway and Shrimpton (Cryptology ePrint Archive, Report 2014/206, 2014) which I cite in my answer there.


Output a pad (un-keyed, variable length) from an input seed (fixed value for same seed)

It sounds like the SHAKE functions (there are two flavors, SHAKE-128 and SHAKE-256) are designed to do exactly what you're asking for.

SHAKE takes a value ($x$ in your case), and generates an arbitrarily long output from it.  You can take the first $len$ bytes from it, and that's your $y$

As for your requirements:

  For each same pair of $x$ and $len$, the value of $y$ is same.

For any input seed $x$, SHAKE always generates the same key stream.  This does mean that (for example) $\text{SHAKE}( \text{"abc"}, 128 )$ is a prefix of $\text{SHAKE}( \text{"abc"}, 256 )$.  Your requirements didn't mention that as a concern, but if it is, you can always use $x || len$ as the input to SHAKE

  seed should have a reasonable short length.

SHAKE can handle any seed length you want.

  4a. $y$'s length may support a certain range (*remark)

SHAKE can generate any length of output

  Every byte value of $y$ should be uniformly (or close to uniformly) distributed

As far as we know, the output of SHAKE is uniformly distributed.

And while it's not difficult at all to generate the same functionality from a fixed length hash function, the nice thing about SHAKE is that all the logic about generating multiple hashes and truncating the last one is already done for you.

Here is the standard implementation of SHAKE (as well as a number of related functions)


Why sorting is needed for Meet-in-the-middle attack

That's an optimization for the attack. It would work without it, but slower.

To do a Meet-in-the-middle attack, we need to encrypt a known plaintext with every possible key and save the resulting text (with the used key) in a list. Now we decrypt a known ciphertext with every possible key and look if we got the resulting text in our list.

We want to know the key for a specific ciphertext. Searching for a specific value in an unordered list is quite hard: We need to look at every single entry and see if it is what we search. That takes (on average) $\frac{n}{2}$ attempts (with $n$ = the key space of the algorithm, for DES it is $2^{56}$).

If we sort the resulting list before we do the decryption we can use the Binary Search. This reduces the search attempts to ca. $\log_2(n)$ (n = the keyspace). That's only 56 for DES, much less than with an unsorted list.

Small note: We sort the column with the key at the same time as we sort the column with the ciphertext. For example, the first key will be the key for the first ciphertext.


Algorithm Design for only Mutual Information Sharing

Aaron Roth on theoretical CS was kind enough to answer with the following answer for anyone out there who is interested.

What you want to do is called "Private Set Intersection". You can think of Alice and Bob as each holding sets (the indices for which their strings are "1"), and they want to compute the intersection (the bitwise AND) so that neither of them learns anything about the other's set except what is implied by the intersection itself.
This problem is well studied. See, for example, Freedman, Nissim, and Pinkas: http://www.pinkas.net/PAPERS/FNP04.pdf


Why is the security of block cipher not a function of key and tweak?

Generally speaking, in proofs of security for Feistel ciphers with various numbers of randomly selected round functions, the secret 'key' is the set of round functions.  Thus, when Patarin or whoever gives upper bounds on the Adversarial advantage for distinguishing a Feistel cipher with $k$ rounds from a random permutation, the key 'length' (i.e. the size of the key space) is implicit in $k$, the number of rounds.  Keep in mind that many of the bounds (e.g. of Patarin) are information theoretic, so brute force isn't really an option -- that is, even someone with an infinitely powerful computer would not be able to distinguish the Feistel cipher from a random permutation better than the relevant bound.

Tweaks are not commonly included mostly because tweakable block ciphers are a recent innovation.


Is there any digital watermark technology for raw text?

I assume the request for clarification of "Plain-Text" has to do with content, not that it's an ASCII or UTF string.

There is not a "Hello World!" string that I could make that you couldn't then copy and call your own, where I could 100% prove that it was mine to begin with. For example anyone can just delete a PGP signature wrapper.

However, if the content of your string is structured in a way that was uniquely identifiably yours then I would call that a watermark, as any change to the content of string would change its context. For example using a private RSA key to encrypt your string then coding it back into ASCII with Ascii85, or if your string contains obfuscated JavaScript, or even simply something you've published under a copy right

That should afford about the same level of watermark you'd see in the other media, but the thing is any media which can be displayed with out the watermark is by the reflexive property media that can be stripped of its watermark and not still remain self judicating. ie copy right it, or have context that's destroyed when changed.


This is called homophonic encryption, and has been around for a long time.

In terms of cryptanalysis of such ciphers, there is a nice thesis from SJSU on this topic which is available here. The attacks tested in that cipher were based on hill climbing and local optimization techniques. The conclusion states:

  We designed and implemented an efficient attack on the homophonic substitution ciphers.
  The attack is based on the hill-climbing heuristic technique. The proposed algorithm has
  a multi-layered architecture with three nested loops to solve the challenges imposed by
  the homophonic substitution ciphers and the hill-climbing technique. The algorithm was
  successfully tested on simple substitution ciphers and many instances of homophonic
  substitution ciphers with variable ciphertext sizes and cipher symbol sizes. [..] For the ciphertexts having minimum 3000 characters and
  maximum 75 cipher symbols, the algorithm was able to break at least 85% of cipher
  symbols.

So, homophonic substitution increases the required ciphertext length, as expected, for a high rate of success of correctly decrypting plaintext characters. If 55 ciphertext symbols are used (to flatten the frequency distribution) the success rate increases from about 10% for a ciphertext length of 300 characters to about 80% for a ciphertext length of 4000 characters.

If 95 ciphertext characters are used, at 4000 character ciphertext length, the success rate is around 50%.


Using Microsoft SIDH library for messages signing

SIDH is a key exchange algorithm, not a digital signature algorithm. The way SIDH works is each side generates a private, random value along with a corresponding public value. The public values are exchanged, and from this, a shared secret can be mutually calculated. No signing is involved.

If you need a post-quantum signature algorithm, you would want to look at something like SPHINCS. You can also use a classical, non-PQ signing algorithm if your threat model allows it.


Is it possible to create an asymmetric cryptosystem where the private keys are not easily verifiable as such?

A key pair (private key and corresponding public key) is always "verifiable" by simply trying to use it. E.g., if this is a key pair for a signature algorithm, then you can try to sign some data with the putative "private" part, and see if the signature can be verified with the "public" part. There is not much you can do about that.

"Hard to recognize plaintext" was thought as a line of defense in cryptosystems from, say, the 1930s. This was before the invention of the computer, hence algorithms had to be performed by hand or through relatively simple electro-mechanical apparatus. Invariably, they were quite weak and needed the extra safety of having a relatively uniform distribution of plaintext data elements. But we are now in 2011, and we have big computers and good algorithms. To state things plainly: if having a "hard to recognize plaintext" makes any difference, then your encryption algorithm sucks.

With a modern symmetric encryption systems (e.g. AES-128 with CBC mode), plaintext internal structure is not an issue.


Is it possible to find a Mersenne Twister seed given only the first output?

Is it impossible to go from the first output to the seed, or is there some trick that I’m missing?

Yes, it is impossible, but not because the algorithm could not be reversed. If you had the whole state, you could go back to find the seed, but you need at least 624 32-bit outputs before you can uniquely find the state of MT19937 (due to the $k$-distribution property).

As @yyyyyyy mentions in the comments, seeding with a timestamp cannot produce all the possible states. However, due to collisions there will not always be a single 32-bit state that produces a particular 32-bit value as the first output, so even if you could work through the math to invert to the seed, you might not find a unique timestamp that way.

Your spoilered approach is much better.


Encrypting a string as smaller pieces vs. encrypting it as a whole

(1) correct a mistake here:

  set S = {AA,AB,AC,BA,BB,BC,CA,CB,CC} = {0,1,2,3,4,5,6,7,8,9}

should be
set S = {AA,AB,AC,BA,BB,BC,CA,CB,CC} = {0,1,2,3,4,5,6,7,8}

(2) According to your example. I would say the "Usage 2" is better than the "Usage 1", since the "Usage 2" has more possible mappings than the "Usage 1" does.
Proof:
Usage 1:
1. E function works for both set S (size = 9) and set T (size = 5).
2. When E function's input is in the {0,1,2,3,4}, its output must also be in the {0,1,2,3,4}. Or, you cannot map "the set T = {0,1,2,3,4} = {0,1,2,3,4}" by the E function.
3. This leads to a problem: the first 5 elements in S ("AA,AB,AC,BA,BB") can only be mapped to a subset of S ("AA,AB,AC,BA,BB"). For example, you will never map "AA0" to "BCX", "CAX", "CBX" or "CCX", where X is in the {0,1,2,3,4}.

"Usage 2":
All possible mappings are here.

(3) According to your two comments:

  @D.W.the string is only 3 bytes composed of characters only from the sets above. The output scope should be the same as the input - the function E puts you back into the same set from which the value came from – erotavlas 8 hours ago

  In Usage 1, I could encrypt them as separate entities (pass them to an integer FPE with different max value for each) – erotavlas 8 hours ago

I would also say that the "Usage 2" is better than the "Usage 1".
Proof:
A1. the E function now maps S(9) to S(9), T(5) to T(5), S'(45) to S'(45), where S' is the S of your Usage 2 example;
A2. "Usage 1": I will feed your E function 9 inputs to get all possible mappings(S=>S, T=>T). That is, {AA0, AB1, AC2, BA3, BB4, BCx, CAx, CBx, CBx}, where x is a number in the T set.
A3. "Usage 2": I will feed your E function 45 inputs to get all possible mappings(S'=>S'). That is, the whole S' set as specified in A1.
A4. The difference is that by dividing the string into small pieces, the spaces of clear text and cipher text are changed.


How to calculate the entropy of passwords?

First of all: Entropy is a property of the process generating a password, not a property of an individual password.

Random passwords

Apart from that, the basic idea is the following: Say you have the password aeLuboo0 that contains lower-case chars, upper-case chars and numbers. Then under the assumption that you have choosen every character uniformely from all possible characters, there are in total

$$(26 + 26 + 10)^8 = 218340105584896$$

many passwords that can be generated in the same way as your concrete password has been generated. The entropy in bits is now the number of bits you need to have approximately the same number of possible bit-combinations. That is:

$$\log_2((26 + 26 +10)^8) = 47.633570483095$$

Hence the assumed process that generated your password aeLuboo0 can generated as many different equal likely passwords, as different numbers can be represented by $47.63$ bits. The entropy of the password can be assumed to be at $48$ bits.

Non random passwords

The cartoon has the example of a word, that has been taken from a dictionary and then mutated to get the actual password. The idea of entropy is the same again (heavily simplified): Guess the number of different words your theoretical source dictionary and multiply it by the number of possible mutations the get a total count of passwords that can be generated in this way. Now find the $\log_2$ of this count to approximate the entropy.


Upper bound for the length of non-interactive zero-knowledge proofs of knowledge

As Natanael pointed out, if you are willing to make very strong assumptions, SNARGs can be used to give proofs of constant size, independent of the size of the statement to be proven. However, these proof systems are in general not UC-compatible (see e.g. this paper). You have two natural alternatives:

1) use NIZKs with "almost optimal size", i.e., of size $w + \mathsf{poly}(k)$, where $w$ is the witness size, and $\mathsf{poly}(k)$ is a fixed polynomial in the security parameter. Such NIZKs exist from the LWE assumption (by combining this recent breakthrough and this paper), or from more exotic assumption. This is the generic, "heavy hammer" approach, if you really want to avoid thinking about how to concretely implement your NIZK.

2) Alternatively, you can use the right approach: look at the concrete statement you want to prove, write a NIZK for this statement, and look at its size.


How does the zuc algorithm complete the synchronization?

frame counter (32 bit)

you find it in  last paragraph of page 14 in Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 4: Design and Evaluation Report.


AES-128. Do there exist two different keys for a pair (text, encrypted text)?

$\newcommand{\given}{\mathrel{|}}$Answer 1.

Let $\pi_0, \pi_1$ be independent uniform random permutations of $\{0,1\}^{128}$.  What is the probability that for any fixed string $x \in \{0,1\}^{128}$, $\pi_0(x) = \pi_1(x)$?

For any fixed string $x$ and each $i$, the variable $\pi_i(x)$ is a uniform random element of $\{0,1\}^{128}$.  (Only if we consider multiple distinct inputs $x_0 \ne x_1$ does the fact that $\pi_i$ is a uniform random permutation rather than a uniform random function come into play, when we consider whether repeated elements are possible in $\pi_i(x_0), \pi_i(x_1)$.)  Since $\pi_0$ and $\pi_1$ are independent, so are $\pi_0(x)$ and $\pi_1(x)$.

Thus
\begin{align*}
  \Pr[\pi_0(x) = \pi_1(x)]
    &= \sum_y \Pr[\pi_0(x) = y \given \pi_1(x) = y]\cdot\Pr[\pi_1(x) = y] \\
    &= \sum_y \Pr[\pi_0(x) = y]\cdot\Pr[\pi_1(x) = y] \\
    &= \sum_y 2^{-128} \cdot 2^{-128}
     = 2^{128} \cdot 2^{-128} \cdot 2^{-128}
     = 2^{-128}.
\end{align*}

What if instead of uniform random $\pi_i$ we had $\pi_i = \operatorname{AES}_{k_i}$ for uniform random strings $k_i$?  If you could predict how that would affect the distribution nonnegligibly, you could distinguish AES from a uniform random permutation, violating the pseudorandom permutation family property that it is conjectured to exhibit, and there would be lots of cryptographers who would like to have a word with you.

So, for any fixed plaintext $x$, does there exist a pair of keys $k_0, k_1$ under which $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$?  Maybe, but you're not likely to find them—for each plaintext, only $1/2^{128}$ of the $2^{256}$ possible pairs $(k_0, k_1)$ of these keys is likely to work!  (It's not guaranteed that any of them will work, but it would be a remarkable publication if you could say one way or another about that guarantee.)

Does there exist any plaintext $x$ such that there exists a pair of keys $k_0, k_1$ under which $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$?  Note the order of quantifiers: We are not asking about some particular fixed $x$; we are asking whether there is any pair of keys that agrees on any plaintext.  This is a little trickier.  To approximate an answer, let's first try the uniform random function model.  A random function is not restricted to be a permutation, so its values at two distinct points are independent, which makes the analysis a little easier.

In the uniform random function model, what is the probability that there exists a plaintext $x$ on which two random functions $f_0$ and $f_1$ agree, $\Pr[\exists x. f_0(x) = f_1(x)]$?  We can answer this by answering it in the complement: what is the probability that for all plaintexts $x$, two random functions disagree on $x$?

\begin{align*}
  \Pr&[\exists x. f_0(x) = f_1(x)] \\
   &= 1 - \Pr[\neg\exists x. f_0(x) = f_1(x)] \\
   &= 1 - \Pr[\forall x. f_0(x) \ne f_1(x)] \\
   &= 1 - \prod_x \Pr[f_0(x) \ne f_1(x)] \\
   &= 1 - \prod_x \bigl(1 - \Pr[f_0(x) = f_1(x)]\bigr) \\
   &= 1 - \prod_x (1 - 1/2^{128})
    = 1 - (1 - 1/2^{128})^{2^{128}}.
\end{align*}

That may look painful to evaluate, but it's turns out to be approximately $1 - e^{-1} \approx 63\%$, since $(1 + x/n)^n \to e^x$ as $n \to \infty$.  (This is why you should pay attention in calculus, kids!)

That's the probability that there exists an input on which two uniform random functions agree.  Of course, AES isn't even conjectured to be a random function—it's designed to be a random permutation.  How does this answer change if we use random permutations $\pi_i$ instead of random functions $f_i$?  The crux is that $\pi_i(x)$ and $\pi_i(\xi)$ for $x \ne \xi$ are dependent—they cannot be equal—whereas $f_i(x)$ and $f_i(\xi)$ are independent.

So let's consider how that affects the expansion of $\Pr[\forall x. \pi_0(x) \ne \pi_1(x)]$, first by examining the case of two distinct inputs $x \ne \xi$, and expanding with the chain rule:

\begin{align*}
  \Pr&[\pi_0(x) \ne \pi_1(x), \pi_0(\xi) \ne \pi_1(\xi)] \\
   &= \Pr[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)]
      \cdot \Pr[\pi_0(\xi) \ne \pi_1(\xi)].
\end{align*}

For the case of $f_i$, by independence of $f_i(x)$ and $f_i(\xi)$ we reduced this to

\begin{align*}
  \Pr[f_0(x) \ne f_1(x)] \cdot \Pr[f_0(\xi) \ne f_1(\xi)]
  = (1 - 2^{-128}) \cdot (1 - 2^{-128}).
\end{align*}

How do the left-hand factors compare?  We can expand the permutation case by Bayes' rule:

\begin{align*}
  \Pr&[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] \\
   &= 1 - \Pr[\pi_0(x) = \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] \\
   &= 1 - \Pr[\pi_0(x) = \pi_1(x)]
        \frac{\Pr[\pi_0(\xi) \ne \pi_1(\xi) \given \pi_0(x) = \pi_1(x)]}
             {\Pr[\pi_0(\xi) \ne \pi_1(\xi)]} \\
   &= 1 - \Pr[\pi_0(x) = \pi_1(x)]
        \frac{1 - \Pr[\pi_0(\xi) = \pi_1(\xi) \given \pi_0(x) = \pi_1(x)]}
             {1 - \Pr[\pi_0(\xi) = \pi_1(\xi)]} \\
   &= 1 - 2^{-128} \frac{1 - 1/(2^{128} - 1)}{1 - 1/2^{128}}.
\end{align*}

The quantity $1/(2^{128} - 1)$ arises because if $\pi_0(x) = \pi_1(x)$, the common value is excluded from the possible values of $\pi_0(\xi)$ and $\pi_1(\xi)$.

Thus, $$\Pr[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] > \Pr[f_0(x) \ne f_1(x)],$$ from which we can conclude that $$\Pr[\forall x. \pi_0(x) \ne \pi_1(x)] > \Pr[\forall x. f_0(x) \ne f_1(x)].$$ This further means that $$\Pr[\exists x. \pi_0(x) = \pi_1(x)] < \Pr[\exists x. f_0(x) = f_1(x)],$$ so there's less than about a 63% chance that any pair of permutations chosen uniformly at random agree on any plaintext.

Turning back to AES, we might guess that for about 63% of the key pairs $(k_0, k_1)$ there is a plaintext $x$ with $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$.  Not bad odds for existence—but will you find them by flailing around randomly, which is about the only thing you can do until you're ready to publish a novel cryptanalysis of AES?  No—there's too much hay in that stack of $2^{128}$ possible plaintexts.

Answer 2.

Exercise for the reader.  If you followed Answer 1, you should have all the tools you need to answer this yourself.


Second Preimages on n-bit Hash Functions by John Kelsey and Bruce Schneier

Ok, i figured out. I thought "M" - original message, but it's random data necessary for generation "Expandable Messages". In this case, range [ 0, 2^(n/2) ] is right.


Yes, the length extension is identical for key sizes that are a multiple of 64 as SHA-1 has an input block size of 512 bits. So you would have to generate the exact same padding for the same message in that case. However, commonly this includes the encoding of the length of the input message of the hash in bits.

The output of a number of blocks of SHA-1 cannot be distinguished from random if the input is sufficiently randomized. This is definitely true if a fully randomized key is used at the start of the hash. So you cannot get any information out of it. This is also true for any MD5, SHA-2 or any other Merkle-Damgård hash without any pre/post-processing to avoid it.

The fact that you can test your attack successfully while the sizes are unknown  in advance must therefore mean that you have some kind of oracle to test against. And this oracle simply returns success if you guessed the total message input size correctly, which is the addition of the key size and message size of the keyed hash.

For most protocols you'd know the key size, or consider it known due to the Kerckhoff principle. This is just a configuration parameter after all, it is not part of the security delivered by the key. However, that doesn't mean that you can calculate it from just the output of the hash function.


Why the following attack in common modulus RSA works?

One correction to your question: it's not necessarily true that your procedure will give you $\alpha = d_b$; however, the $\alpha$ you do get will work as a private key corresponding to $e_b$, just not necessarily the exact value that the user $u_2$ has.

With that in mind, here's an outline of why that is so:

First of all, two keys $(e, d)$ will work as corresponding public/secret exponents with an RSA modulus $N$ if and only if $e \cdot d \equiv 1 \space ( \bmod \space\lambda(N) )$, where $\lambda(N) = lcm(p-1, q-1)$.

So, we can restate the problem as: given values $(e_a, d_a)$ with $e_a \cdot d_a \equiv 1 \space ( \bmod \space\lambda(N) )$, and a value $e_b$, find a value $\alpha$ such that $e_b \cdot \alpha \equiv 1 \space ( \bmod \space\lambda(N) )$ (even if we don't know the value of $\lambda(N)$)

Now, the condition $e_a \cdot d_a \equiv 1 \space ( \bmod \space\lambda(N) )$ is precisely equivalent to the statement that there exists an integer $k$ such that $e_a \cdot d_a - 1 = k \cdot \lambda(N)$; let us call the value $k \cdot \lambda(N) = V$.  Note that, even though we don't know the values of either $k$ or $\lambda(N)$, we can compute $V$.

Now, given that we know the values $e_b, V$, we can certainly run the Extended Euclidean algorithm, and find values $\alpha, \beta$ with $\alpha \cdot e_b + \beta \cdot V = 1$.  Now, if reduce both sides modulo $\lambda(N)$, we find that $(\alpha \cdot e_b + \beta \cdot V) \bmod \lambda(N) = (\alpha \cdot e_b) \bmod \lambda(N) + 0 = 1$ (because $V$ is a multiple of $\lambda(N)$), and so $\alpha$ does meet the requirements of a private key corresponding to $e_b$.

Now, a few notes:

The above argument shows that the result is correct, however it doesn't say why someone would happen to stumble upon it in the first place.  Actually, it's not nearly as mysterious as it would seem; what we want is $e_b^{-1} \bmod V$, that is, the multiplicative inverse of $e_b$ modulo $V$, and the Extended Euclidean method is the standard way to compute that.
The algorithm you have divides $V$ by $W$.  It turns out that doesn't change anything; $W$ will be relatively prime to $\lambda(N)$; we know this because $W$ is a divisor of $e_b$, and $e_b$ must be relatively prime to $\lambda(N)$.  So, dividing $V$ by $W$ effectively makes $V = (k/W) \cdot \lambda(N)$; $(k/W)$ is an integer (which is all we cared about $k$ anyways), and so it doesn't change the above argument.
If someone does have a $(e,d)$ public/private key pair for a modulus $N$, it turns out that they can also efficiently factor $N$; however, the explination for how to do that would require a bit more work to explain.


How does the attacker include input before compression and encryption in CRIME?

Malicious JavaScript could trigger calls against any SSL server. Although this JavaScript is not able to actually read the cookie for that server directly, the browser will send that cookie through the SSL tunnel.

The JavaScript will then alter the URL, keeping the server but changing the path or request parameters. In that way it can inject data before compression and try to identify parts of the cookie.


What Are the Risks of AES-GCM [Key, Nonce, Message] where Nonce = Message

I think this is a bad idea for a few reasons:

In GCM mode, if you encrypt two messages with the same nonce, then the messages' plaintexts may be retrievable from the ciphertexts. So if you have two different messages about the same customer that both use the customer id as the nonce, then your encryption may be broken.
When a user retrieves a ciphertext, how will they know the customer ID to use as the nonce? Usually the nonce is included with the ciphertext so that the user can use it with the key to decrypt the ciphertext, but if you do this, then the customer ID will be in plaintext.

Is there some reason that you don't want to use a random nonce as is normally done? If there isn't a specific reason to go off the standard path, then you should avoid doing so.


Identify the cryptosystem where $\ m = c^2 \bmod n$?

I doubt this is an encryption scheme, except in the limited sense of that in code obfuscation. If indeed this is the decryption part of an encryption scheme, that's a very weak one: it is a symmetric encryption scheme which decryption key is $n$, and two distinct plaintext/ciphertext pairs are typically enough to recover that key. Often $n=\gcd({c_0}^2-m_0,{c_1}^2-m_1)$ (though sometime, pulling out small factors or a third pair is necessary).

This cryptosystem seems to be a simplified variant of Rabin signature. As any signature scheme, it aims at integrity and proof of origin of the message, not at protecting the confidentiality of the message.

Like in RSA, security relies on the difficulty of factoring $n$, which distinct prime factors $p$ and $q$ are the secret key. $m$ is the message to sign, assumed to have internal redundancy. Or better (true Rabin signature) $m$ is a full-domain hash of the message. Further, somewhat $m$ has to be made a square modulo $n$ (or equivalently, modulo $p$ and modulo $q$). $c$ is the signature. Schematically, verification is computing $c^2\bmod n$, and comparing it against $m$. Calling that decryption (as the question does) is an error in terminology.

There are several methods for generating $p$ and $q$; then for adjusting $m$, computing $c$ (which is signing, not encrypting), and checking $m$ against the result. One is described in algorithms 11.29 and 11.30 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography. Be sure to ignore the section 11.3.5 (which describes ISO/IEC 9796(-1) padding, dated and insecure).

If the rationale is that making a cryptogram $c$ leading to an $m$ that makes sense is hard without the factorization of $n$, again that's not a cipher or encryption, and $m\gets c^2\bmod n$ is not decryption. The proper name is Rabin signature with total message recovery, and $m\gets c^2\bmod n$ is signature verification and message recovery (and lacking validation of redundancy in $m$). This is standardized by ISO/IEC 9796-2 (with proper padding) including with exponent $2$.


What is a "constant time" work around when dealing with the point at infinity for prime curves?

Introduction
Dealing with the neutral element $\mathcal{O}$ of an elliptic curve in Weierstrass form is a major problem in implementations. This is due to the fact that this point has no affine representation on this form of elliptic curve and is called the infinity point.
This point can still be written using projective coordinates. Noting $x=X/Z$ and $y=Y/Z$, the equation of the elliptic curve defined by $y^2 = x^3 + ax + b$ becomes:
$$
Y^2Z = X^3 + aXZ^2 + bZ^3.
$$
An affine point $(x,y)$ has the representation $(X:Y:Z)$ where $Z \neq 0$ (and can have as many representation as there are possible values for $Z$). When $Z=0$, then $X=0$, so the point $(0:k:0)$ with $k \neq 0$ is the only point at infinity and is the neutral element $\mathcal{O}$.
Then it might be tempting to use this representation of $\mathcal{O}$ in the formulas. Unfortunately for most of them it doesn't work.
To make an implementation constant-time relatively to the infinity point, I see two general methods:

Manage the point addition in constant-time;
Use an algorithm that avoids the infinity point.

Solution 1: dummy point addition
The basic idea is to compute a point addition and ignore its result when the infinity point is one of the inputs.
This is what the double-and-add-always algorithm does, but can be extended to other regular algorithms.
This can be implemented using booleans based on the coordinates $Z$ of the points, then applying the point addition normally. Then the computation is ignored if one of the boolean indicates that one of the points is $\mathcal{O} by replacing the computed values by the other input point.
For example, this is exactly how it is done for several curves in OpenSSL with a conditional copy that erases the calculated values:
copy_conditional(x_out, x2, z1_is_zero);
copy_conditional(x_out, x1, z2_is_zero);
copy_conditional(y_out, y2, z1_is_zero);
copy_conditional(y_out, y1, z2_is_zero);
copy_conditional(z_out, z2, z1_is_zero);
copy_conditional(z_out, z1, z2_is_zero);

Source
Advantage:

can be used for any algorithm (double-and-add-always, fixed window based algorithms).

Drawbacks:

Useless computation;
Vulnerable to C safe-error attacks (an attacker inject a fault during the point addition and if no effect are observed on the output of the scalar multiplication, then the attacker knows the infinity point is involved and may decude information on the scalar).

Solution 2: Complete point addition
On the Edwards form of elliptic curves, the neutral element is an affine point, so it is possible have point addition formulas that are complete as was shown in this paper.
The authors of this paper proposed formulas for prime order elliptic curves that are complete using projective coordinates.
Advantage:

Unified and complete point addition (works for any inputs including the infinity point).

Drawbacks:

A little more costly than other formulas;
Still vulnerable to C safe-error attacks: if $P = (X_1:Y_1:Z_1)$ is the infinity point, then line 10 of algorithm 1 in the paper becomes a dummy operation, so a fault on this operation with no effects means that the entry $P$ is $\mathcal{O}$ (I didn't check the other algorithms on the paper).

Solution 3: Montgomery ladder with XZ formulas
Montgomery ladder is an algorithm where the point addition always occurs between a point $P_1$ and $P_2$ that satisfy the invariant $P_1 - P_2 = P$ where $P$ is the input of the scalar multiplication.
The formulas presented below are taken from the page XZ coordinates for short Weierstrass curves (given by the equation $y^2 = x^3 + ax + b$) in the Explicit-Formulas Database.
There are two types of mixed differential addition. Those do not make use of the protective coordinate $Y$ of the points.
I present the one from mdadd-2002-it-4 and make the assumption that the input $P$ of the scalar multiplication is a point of odd prime order $q$.
An affine point $(x,y)$ is represented as projective coordinates $(X:Z)$ that satisfy $x = X/Z$, and the infinity point $\mathcal{O}$ by $(1:0)$.
Differential addition
The inputs are $P_1$ and $P_2$ given by their XZ representation $(X_1:Z_1)$ and $(X_2:Z_2)$, and $x$ is the affine $x$-coordinate of $P_1 - P_2$. The computation of the addition is given by
$$
\left\{\begin{array}{rcl}
X_3 & = & 2(X_1Z_2 + X_2Z_1)(X_1X_2 + aZ_1Z_2) + 4bZ_1^2Z_2^2 - x(X_1Z_2 - X_2Z_1)^2 \\
Z_3 & = & (X_1Z_2 - X_2Z_1)^2
\end{array}\right.
$$
Now we need to look at the possible exceptions with these formulas:
Case 1: $P_1 = P_2$.
This case means that $P = P_1 - P_2 = \mathcal{O}$, but we assume that $P$ is not the infinity point so it is impossible.
Case 2: $P_1 = -P_2$ and $P_1\neq P_2$.
Then $P_1 + P_2 = \mathcal{O}$. We have $Z_3=0$ and
$$
\frac{X_3}{Z_1^2Z_2^2} = 4\left(\left(\frac{X_1}{Z_1}\right)^3 + a\frac{X_1}{Z_1} + b\right) \neq 0
$$
because $P_1$ is not a point of order $2$. So $P_1+P_2$ is correctly computed as a valid representation of the infinity point.
Case 3: $P_1 \neq \mathcal{O}$ and $P_2 = \mathcal{O}$.
We have $Z_1 \neq 0$, $X_2\neq 0$ and $Z_2=0$.
Then $X_3 = 2X_1Z_1X_2^2 - xX_2^2Z_1^2$, $Z_3 = X_2^2Z_1^2 \neq 0$ and
$$
\frac{X_3}{Z_3} = \frac{2X_1Z_1X_2^2}{X_2^2Z_1^2} - x\frac{X_2^2Z_1^2}{X_2^2Z_1^2} = 2x-x = x,
$$
so $(X_3:Z_3)$ is a correct representation of $P_1+P_2 = P_1 + \mathcal{O} = P_1$.
Other cases:
$Z_3\neq 0$ and $X_3/Z_3$ corresponds to the correct $x$-coordinate of $P_1 + P_2$.
Doubling
The input is $P_1$ given by its XZ representation $(X_1:Z_1)$.
Then $2P_1$ is given by the formulas
$$
\left\{\begin{array}{rcl}
X_3 & = & (X_1^2 - aZ_1^2)^2 - 8bX_1Z_1^3 \\
Z_3 & = & 4Z_1(X_1^3 + aX_1Z_1^2 + bZ_1^3)
\end{array}\right.
$$
Case 1:
$P_1 = \mathcal{O}$. We have $X_1\neq 0$ and $Z_1 = 0$.
Then $X_3 = X_1^4 \neq 0$ and $Z_3 = 0$, which gives a correct representation of the infinity point.
Other cases:
We have $Z_3 \neq 0$ and $X_3/Z_3$ corresponds to the correct $x$-coordinate of $2P_1$.
Recovery of coordinate $y$
At the end of the scalar multiplication, we can reconstruct the complete affine coordinates of the output thanks to the following formulas.
Given $P=(x,y)$, and $(X_1:Z_1)$ and $(X_2:Z_2)$ the XZ representations of $P_1$ and $P_2$ such that $P_2 - P_1 = P$, then the following formulas gives a complete representation of $P_1 = (X'_1 : Y'_1 : Z'_1)$:
$$
\left\{\begin{array}{rcl}
X'_1 & = & 2yX_1Z_1Z_2 \\
Y'_1 & = & 2bZ_1^2Z_2 + Z_2(AZ_1 + xX_1)(xZ_1 + X_1) - X_2(xZ_1 - X_1)^2 \\
Z'_1 & = & 2yZ_1^2Z_2
\end{array}\right.
$$
Case 1: $P_1 = \mathcal{O}$.
We have $X'_1 = Y'_1 = Z'_1 = 0$ which gives an incorrect representation of the infinity point. However, in the case of Montgomery ladder it means the scalar is a multiple of the order of the input so it has no cryptographic impact.
Case 2: $P_2 = \mathcal{O}$.
This case means that $P_1 = -P$.
We have $X'_1 = Y'_1 = Z'_1 = 0$ which does not correspond to $P_1$.
Case 3: $y=0$.
It means $P$ has order $2$, so it cannot happen.
Other cases:
We have $Z'_1 \neq 0$ and $(X'_1 : Y'_1 : Z'_1)$ is a correct representation of $P_1$.
Wrap-up
The only cases to manage are:

The input $P$ of the scalar multiplication is the infinity point;
The input scalar is a multiple of the order: the coordinate $Z$ at the end is $0$ then the output is $\mathcal{O}$;
The input scalar is a multiple of $q-1$: only a problem for the recovery of the missing coordinate.

Solution 4: Algorithms that avoid the infinity point
One possibility is to recode the scalar $k$ such that the point additions always occur between two points that can never be the infinity point.
A classic fixed window-based algorithm separate the scalar $k$ in windows of width $w$:
$$
k = \underbrace{k_0  + k_1 2 + \cdots + k_{w-1}2^{w-1}}_{K_0} + \underbrace{k_w 2^w + \cdots + k_{2w-1}2^{2w-1}}_{2^w K_1} + k_{2w}2^{2w} + \cdots
$$
so the scalar can be rewritten as
$$
k = K_0 + K_1 2^w + \ldots + K_{d-1}2^{dw-1}.
$$
where $d$ is the number of windows to cover the whole scalar.
Every $w$ doublings, a point addition with the precomputed point $[K_i]P$ is done. When the window $K_i$ is null, it means it is the infinity point.
To avoid that, several papers proposed to recode the scalar such that the windows are always nonzero. To cite a few:

https://eprint.iacr.org/2004/342
http://www.bmoeller.de/pdf/ecc-sca-isc2001.pdf
https://link.springer.com/chapter/10.1007/3-540-36563-X_23

Personnally, I like the way it is implemented in Mbed TLS. It is a variant of the technique proposed in the first paper above where the windows are in fact combs (the bits of the scalar in a comb are not taken consecutively but separated by a fixed distance).
Advantage:

No need to manage the infinity point in the point addition.

Drawbacks:

The scalar must be recoded, so it is a little bit more complicated;
While the infinity point is managed, does the case $P_1 = P_2$ can appear during the scalar multiplication? (The answer is maybe and depends on the method and other parameters.)


Chase et al.: Malleable Proof Systems and Applications. Eurocrypt 2012

This paper is the only one I know of that discuss a problem like this. They consider the problem of combining/modifying NIZK proofs -- for example, if I see a proof that $(A,B,C)=(g^a, g^b, g^c)$ is a DH-tuple ($c = ab$), then I can produce a proof that $(A^2, B^2, C^4)$ is a DH-tuple, even though I don't know their discrete logs.

Their focus is Groth-Sahai-style proofs in groups with bilinear pairings. I don't know how helpful the techniques will be for Schnorr-style proofs.


Advantage of AES(Rijndael) over Twofish and Serpent

During the final round of the AES contest, NIST issued a summary of the 5 finalists on the topics of security, speed, implementation, and such. That sounds like what you're looking for, see sections 3 and 5 of the paper.

General ideas from the paper:

Rijndael had a potentially lower security margin than Twofish and Serpent.
Rijndael had better performance than Twofish and Serpent.
The Rijndael construction was arguably simpler than Twofish and Serpent.

However, this was published in 2000, 12 whole years ago, so it won't have the latest security updates on the algorithms. Rijndael certainly has more attacks against it due to the focus on it. But presumably a lot less has been put into Twofish and Serpent, so we don't know how strong those algorithms would look if they had the same attention that Rijndael had.


Anonymous key exchange protocol not secure vs. computationally unbounded adversary

This is a homework, and my analysis is poor, but I try, this is what I answered:

In this case as is defined that our adversary is has no computationally limits, unlike real life, and it’s taken away most of the impediments that actually occurred. We can consider that the Key Generator algorithm, has an input a value R (it is conceptualized as a random  number generator), and produces a public key, PK, and a secret SK. A computationally unbounded adversary, possibly will consider all possible inputs of R, and eventually will find out which one generates the PK, so that’s the way for him knowing the SK, because if that R creates the PK therefore can creates the SK, and can be used for decrypting the message. Besides if the private Kay was generated correctly, it will be able to fulfill the next property:  DSK(EPK(M))=M Consequently, we can concluded that the Anonymous Key Exchanged cannot be secure against a computationally unbounded adversary.


What are the security risks in making a passphrase-encrypted private key public?

From the manual of GnuPG:

  To help safeguard your key, GnuPG does not store your raw private key on disk. Instead it encrypts it using a symmetric encryption algorithm. That is why you need a passphrase to access the key. Thus there are two barriers an attacker must cross to access your private key: (1) he must actually acquire the key, and (2) he must get past the encryption.

  [...]

  The motivation for trying passphrases is that most people choose a passphrase that is easier to guess than a random 128-bit key. If the passphrase is a word, it is much cheaper to try all the words in the dictionaries of the world's languages. Even if the word is permuted, e.g., k3wldood, it is still easier to try dictionary words with a catalog of permutations. The same problem applies to quotations. In general, passphrases based on natural-language utterances are poor passphrases since there is little randomness and lots of redundancy in natural language. You should avoid natural language passphrases if you can.

From here we have

  s2k-cipher-algo

  Name

  s2k-cipher-algo — use a specified algorithm as the symmetric cipher for encrypting private keys

s2k-cipher-algo name

  Description

  Use name as the symmetric cipher algorithm to protect private keys. Running the gpg with the command version yields a list of supported algorithms. The default cipher is Blowfish.

also

?> gpg2 --version
gpg (GnuPG) 2.1.11
libgcrypt 1.7.3-beta
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Home: ~/.gnupg
Supported algorithms:
Pubkey: RSA, ELG, DSA, ECDH, ECDSA, EDDSA
Cipher: IDEA, 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH,
        CAMELLIA128, CAMELLIA192, CAMELLIA256
Hash: SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224
Compression: Uncompressed, ZIP, ZLIB, BZIP2

TL;DR:

Sure, you can distribute your encrypted private key, but this defeat one of the two barriers mentioned in the manual (difficulty of access...)

The cipher used should be strong enough to guarantee the security of your key. However this will require you to use a really strong passphrase in order to avoid brute force and dictionary attacks.

Really TL;DR:

You can do it, but IT IS NOT ADVISED NOR RECOMMENDED. Your security will only rely on the strength of the passphrase that protect your secret key.


Is encrypting a secret key and being able to decrypt plain text with it possible?

In general, the answer is no.

An asymmetric cryptosystem is one which has the property where a public key and private key can be produced which satisfies:

The public key can encrypt messages, and the private key can decrypt messages.

The private key is computationally hard to recover from the public key.

Any particular message is difficult to recover from just the ciphertext and the public key.

We cannot go from these axioms to the property you have described. (These axioms don't tell you anything about how a given keypair interacts / works with other key pairs)

So now we would have to look at specific cryptosystems. Most cryptosystems have multiple variables in the public key. RSA-CRT has the private key mod each prime. Discrete log systems (typically, there are many exceptions) provide the generator, and the group parameters. So your suggested scheme must be encrypting the private keys element-wise, as you must be able to distinguish between the components.

Lets look at RSA. (not CRT)

Let Server one's original RSA private key (before encryption) be $<d_1>$, and Server two's original private key be $<d_2>$

Your question is then: is the following true $(m^{e_2} \mod n_2)^{d_2^{e_1} \mod n_1} = (m^{e_1} \mod n_1)$

I am stating this without proof (look into modular arithmetic for that), but this will not generally be true due to different modulus being used. To begin with, the former term is defined over n_2, and the latter is defined over n_1.  Then the property that $m^{e_2 * d_2} = m \mod n_2$ depends on the modulus being $n_2$. It is not true over other modulii. (Look into Lagrange's Theorem if your not convinced - https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory))  Your d_2 is taken to a power with an another modulus.

There may exist some cryptosystem where this is possible, but I am not hopeful of it working for any of the common cryptosystems.

To address your suggested use case for Tor, that is not viable. You are gaining no additional protection from a man in the middle, and a server can easily store their private key before encrypting it with another servers public exponent. The alternative would be having pre-encrypted private keys distributed from central authority, but that violates the goal of Tor, and alot of cryptography.


Analyzing ECB's and CBC's resistence to a known-plaintext attack

I understand that, for a block cipher that receives a key of k bits and processes blocks of n bits (n>k), on ECB mode, Oscar would find false keys and because of that he would need to check more than one pair (i.e. two or three for DES).

That doesn't sound right; if you are assuming that the attacker (Oscar) has a plaintext block $P$ and a ciphertext block $C$, and searches for all keys $K$ to find one that satisfies $C = E_K(P)$, well, if the size of the key space $k$ is smaller than the block size $n$, then one would expect that there would be at most one key $K$ that satifies this relationship.  That is, if we assume that $E$ acts independently with different keys, then $E_K(P)$ is effectively a set of independent variables based on the various values of $K$; since $K$ can take on $2^k$ different values, $E_K(P)$ can take on up to $2^n$ different values.  We're looking for a value $K$ for which $E_K(P)$ is a particular value (C); we know that there is one value $K$ (the correct one) for which this is true; the probability that there is a second (false) key for which this is true is at most $(2^k-1)/2^n$, which is fairly small if $k$ is larger than $n$.

However, on to your real question:

  But how would this attack work in a block cipher that uses CBC mode?

Pretty much the exact same way as it does in ECB; CBC mode is defined as:

$C_i = E_K( P_i \oplus C_{i-1} )$

(where $C_{-1}$ is taken to be the IV)

When the attacker has a known plaintext (that is, he has a plaintext message and its corresponding ciphertext), then the attacker knows the values $C_i$, $P_i$, and $C_{i-1}$, and he can look for a key $K$ that satisfies the value relation exactly as he would with ECB mode.  In addition, if he happens to find two keys $K^1$, $K^2$ that encrypts that block in the exact same way, then he can handle it just like in ECB mode, he steps to another block and does a test encryption (or decryption; whichever is most convienent) on that as well.

  I suppose Oscar still needs to deal with false keys, but now a encryption operation over block i needs the knowledge of block i−1 and possibly the knowledge of IV.

We always assume that the attacker sees the entire ciphertext; hence he sees ciphertext block $i-1$.  It's possible that he doesn't know the IV (we typically send the IV with the message, however that's not a requirement); if he doesn't, all the attacker does is not use the first block for his brute force attack.


It depends on which cipher suites and extensions the client and the server implement, enable and negotiate.

The default operation in TLS 1.2 and earlier, is MAC then Encrypt. This corresponds to alternative a in the question.
In TLS 1.2 it is possible to use AEAD cipher suites. Such cipher suites (e.g. AES-CCM but not AES-GCM) might correspond to alternative b in the question.
In all versions of TLS, the client and server might negotiate use of Encrypt then MAC with all non-AEAD cipher suites, provided that they both implement RFC 7366.


Cost of attacking Mobile OTP with a fake server

If  $\mathrm{MD5}$ had been computationally indistinguishable from a random oracle (for the fixed message size under consideration), there would demonstrably be no method better than brute force search of $K$ to recover $K$ or otherwise predict the next outputs of the function.

However, $\mathrm{MD5}$ is known to fall short of this goal. In particular, we know how to quickly make 1-block collisions, and there is a theoretical preimage attack slightly better than brute force.

Thus there is no insurance that the function described is secure, but I do not see that any current result on $\mathrm{MD5}$ endangers it. Perhaps there is a differential attack of some kind with enough $(\mathrm{T}, (\mathrm{MD5}(T_{\mathrm{dec}}||K_{\mathrm{hex}}))_{\mathrm{hex}}[0..5])$ pairs, but I do not see that as a practical threat even with thousands on pairs, in light of the short key $\mathrm{K}$.

On the other hand there are several truly worrying aspects of the scheme:

there is no salt (the same $\mathrm{K}$ and $\mathrm{T}$ yield the same cryptogram regardless of user or other parameter);
there is no other attempt to slow down brute force search;
the 74-bit key is short.

These three cardinal errors combined make the scheme quite vulnerable to a brute-force attack. Assuming $n$ users have used their authenticating device at the same known time $\mathrm{T}$ once, and have used it at three other known times (not necessarily the same among users), and the cryptograms have been gathered, the key of one user is recovered with better than 50% odds, and fair confidence against false positive, after an effort of $0.7 \cdot 2^{74}/n$ $\mathrm{MD5}$ rounds. That's simply by trying keys for the common $\mathrm{T}$ and, in the rare case that the result is a match for a user, further testing the key with other known data points for this user.

Also, the key generation is not specified here. If the key was not true random but, say, a password, or generated by a poorly seeded RNG, that would be a further weakness. Update: We learn that $K$ consists of 64 bits chosen at random, plus 10 bits from a 4-digit $\mathrm{PIN}$. If the users choose their $\mathrm{PIN}$, then $0000$, other $\mathrm{PIN}$s with 4 identical digits, and birth years, are going to be strongly overrepresented. That can be used to speed up a brute-force attack, significantly.

Rather than this scheme, it would be better to use industry standard primitives fit for the job, like $\mathrm{PBKDF2}$ or, better, $\mathrm{Scrypt}$. At the very least, the user ID or some form of salt should be part of the cryptogram's input.

Update: For example, with $\mathrm{PBKDF2}$ and keeping $\mathrm{MD5}$ as the underlying primitive, the function generating the one-time password could be replaced with $\mathrm{PBKDF2}(\mathrm{PRF}\leftarrow\mathrm{HMAC\_MD5}, \mathrm{Password}\leftarrow K||\mathrm{PIN}, \mathrm{Salt}\leftarrow\mathrm{UserID}, \mathrm{Count}\leftarrow 512, dkLen\leftarrow 3 \mathrm{bytes})$

Rationale: Using $\mathrm{Salt}$ (e.g. a User ID) insures that a brute force attack can not be leveraged against multiple users, avoiding the $/n$ factor above. The $\mathrm{Count}$ parameter is a compromise between increasing the effective key length (doubling $\mathrm{Count}$ has the same effect on a brute force attack as growing $K$ by one bit), and the computational cost of an authentication (growing linearly with $\mathrm{Count}$ on both the device and server side). With the given parameters, assuming 1000 users in the same 10 seconds, the scheme is about a million times harder to break than the original. Using $\mathrm{HMAC}$ increases assurance against theoretical attacks, even though $\mathrm{MD5}$ is less than perfect.


Performance bottlenecks in Paillier encryption

Recall that in Paillier encryption with public key $n$ of private factorization and $g=1+n$, encryption of plaintext $m$ reduces to:

choose random $r$, $0<r<n$
compute and output ciphertext $c=(1+n\cdot m)\cdot r^n\bmod n^2$.

Some ideas:

In some contexts, it is feasible to pre-compute $r^n\bmod n^2$ in masked time, before the encryption itself, meaning there is no modular exponentiation involved in encryption (only one multiplication and one modular multiplication); delay from plaintext-in to ciphertext-out is thus drastically reduced.
Using existing tightly optimized modular exponentiation code like in GMP might achieve 3, 4 and 5 below with little effort.
Tight coding (often, assembly) pays a lot for modular multiplication, and thus modular exponentiation (which is dominated by modular multiplication). Gaining a factor of 3 is common, 10 is not unseen if assembly coding allows to double the effective word width used for multiplication (e.g. C might not allows to use the full 128-bit result of a 64-bit times 64-bit multiplication available in hardware, or effective use of the carry bit).
Depending on hardware and size of $n$, it might pay to perform some optimizations that are not worthwhile for RSA and $n$ of comparable size, because the modulus width for modular multiplications is doubled in Paillier; even quadrupled (or more with multiprime-RSA) if the CRT is used and one compares the expensive operations, which are encryption in Paillier, and decryption in RSA. These optimizations include

sub-quadratic multiplication, like Karatsuba and friends;
modular reduction by multiplication with pre-computed inverse;
performing modular squaring by squaring with reuse of partial products (as in Algorithm 14.16 in the HAC) followed by modular reduction.

Sliding Window exponentiation (see Algorithm 14.85 in the HAC) will give some improvement (like -20%) over a standard exponent scanning, and slightly more so than in RSA.


Is it possible to encrypt data points but still be able to select the ones "near" a given value?

No, a cryptosystem can't do what's asked.

Proof: if one can precisely answer queries of the form "how many data points up to a distance of $3$ starting from an origin point = $n$" (a subset of what's wanted) for any value of $n$ with $|n|\le m+3$, and each point has integer value $v$ with $|v|\le m$, then one can find exactly the value of all the points in the set with at most $2m+1$ queries (with $n$ going from $m+3$ down to $-m+3$, each revealing if $v=n-3$ belongs to the set).

Thus in order to make the problem in the question tractable, one must use much larger integers (so that the necessary number of queries or work becomes infeasible), or/and heavily limit the number of queries an adversary can make, or/and introduce some fuzziness in the answers, or/and (as pointed by otus in comment) introduce the notion that some of the query is sent somewhat "enciphered" to the holder of the database. And it might well be that no practical system is possible.


Help with breaking AES reduced to 2 rounds

You may be overthinking this a bit.  Just pick any byte in the ciphertext, and for each possible value of the last RoundKey in that byte, do the following: decrypt just that single byte of the 256 ciphertexts  (i.e. compute $AR-SR^{-1}-BS^{-1}$ for that single selected byte using the candidate RoundKey byte in the $AR$ step), and then check to see if the corresponding byte in the State at the beginning of Round 2 all sum to zero.  For the correct RoundKey value, the byte will  sum to zero.  Incorrect RoundKey values will likely not sum to zero.  In that manner, you can sieve out most of the incorrect values for each of the RoundKey bytes for the last RoundKey, and can then exhaustively check the remaining possible Keys (i.e. all combinations of RoundKey byte values that were not sieved out) by using the Key Schedule in reverse and checking to see if a candidate Key correctly decrypts all 256 ciphertexts.

Edit to add: By the way, there are more efficient attacks on 2 round AES than the one you outline (which needs 256 chosen plaintexts).  For example, here is one that only needs a handful of chosen plaintexts:

Request $N$ chosen plaintexts that differ from each other only in four bytes, such that if any pair of plaintexts is xored together you get a result like so:
$$
\begin{matrix}
W & 0 & 0 & 0 \\
X & 0 & 0 & 0 \\
Y & 0 & 0 & 0 \\
Z & 0 & 0 & 0 \\
\end{matrix}
$$
Where $0$ denotes a zero byte, and $W, X, Y$ and $Z$ denote the 'active' bytes with some non-zero difference.  With $N$ such chosen plaintexts, there will be ${N \choose 2}$ pairs of plaintexts that have differentially 'active' bytes in the above pattern.  This efficient 'packing' of pairs will enable us to attack 2 round AES with only a handful of plaintexts (a dozen is likely to be more than enough).

Now observe from the difference distribution table of the AES S-box that for any given input difference, about half of the possible output differences have a probability of zero (they wont occur given that input difference).  This will enable us to sieve out the incorrect keys very efficiently using an impossible differential attack.

Pick a pair of plaintexts and focus on each active byte, one at a time. From the pair of plaintexts we are given an input difference for the focus active byte, and we can use the S-box difference distribution table to figure out the impossible outputs that cannot be attained from that input difference.

For each 'impossible' output difference $I$ for the focus byte after the first SubBytes step, apply ShiftRows and MixColumns to $I$ (notice that for any of the active bytes, after ShiftRows the active byte is mixed with inactive 'zero' bytes).  This will give us a set of impossible differences for four different bytes going into the second round (so from all four focus bytes we can derive a set of impossible differences for all 16 bytes of the State for our pair of plaintexts).

Now select any of the corresponding bytes of the ciphertext pair, and decipher that byte under all possible 256 values for the last RoundKey byte (i.e. given some guess for the last RoundKey byte, compute $AR-SR^{-1}-BS^{-1}$ for both ciphertext bytes).  For each guess of the RoundKey byte, we can xor the 'deciphered' byte together to get a difference in that byte just before the 2nd round.  We can then compare the 'deciphered' difference under that RoundKey guess against the 'impossible' differences that we computed from the plaintext side.  If a RoundKey byte guess leads to one of the impossible differences, then we can rule that guess out as not being correct.

We should be able to rule out about a quarter of the possible RoundKey values for any given byte with each plaintext pair, and for each subsequent pair that we test we can be more efficient in the key-guessing phase by not bothering to test the RoundKey values that we have already ruled out.  In this way, we can sieve out the incorrect RoundKeys very efficiently.


Simple homomorphic crypto for 32-bit integers

It depends on what you mean by "32-bit integer". If you want to add integers which will never exceed the range -231..231-1 (i.e. integers which fit in 32 bits), then Paillier cryptosystem will be fine. It uses mathematics which can be viewed as "slightly complex" so you could also rely on a simpler ElGamal encryption. With ElGamal, you do not add; you multiply. So you would have to represent integer value x with value gx, and, upon decryption, you would have to solve the discrete logarithm, which can be done with cost about 216 if you are sure that the exponent resides in a 32-bit range (232 is low enough that this can practically be sped up a lot with precomputed tables; e.g., store hashes of all gy where y is a multiple of 212: you only need to store a million hash values, and you do the discrete log step in an average of two thousands multiplications and hashing).

If by "32-bit integer" you mean modular integers, which "wrap around" at 32 bits, then things become much more complex. You could choose the group parameters for ElGamal such that the generator g has order 232 exactly, but security would have been quite nullified in the process. It would deter only low-grade attackers who indiscriminately balk at mathematics.


ECRYPT Salsa20 Test Vectors Interpretation

Your "different wrong result" (based on a littleendian counter) appears to be the correct second 64-byte sequence.  The test vector shows "stream[192..255] = ", which is the fourth 64-byte sequence.  The test vector is generated by calling "the Salsa20 encryption function" (Section 10 of the spec) on 512 zero bytes using the indicated key and IV.


How do I interpret the CADO-NFS output for discrete logarithm calculation in GF(p)?

ell is the largest factor of $p-1$, remember the Sophie Germain prime $p=2q+1$

All below from mail thread of [Cado-nfs-discuss] DLP and well explained with a sageMath code.

  cado-nfs is right, but maybe the printed info is scarce or misleading.

  Here's a verification script.

> sage: p=53236943330228380237618624445646085674945074907141464418703
> sage: ell=46188898894770668459
> sage: target=51415666321640196744601368459935322494639894379132878321944
> sage: logtarget=15315241815410699555
> sage: log2=39557689199984036821
> sage: redlog=ZZ(Integers(ell)(logtarget/log2))
> sage: (GF(p)(2)^redlog/target)^((p-1)//ell) 1
> sage: (GF(p)(2)^logtarget/GF(p)(target)^log2)^((p-1)//ell) 1

  cado-nfs only computes the discrete logarithm of elements of GF(p)^*
  modulo ell. And it won't tell you with respect to which base.

  So you first have to decide on which generator you want (e.g., 2),
  rescale logarithms so that this element has log 1, and then make sure
  that your target has the right log mod ell. Which is equivalent to
  saying that you have an equality in the subgroup of order ell, or in
  other words that when you take the ((p-1)/ell)-th power, you get 1.

  The last test of the script is the generic way to do pairwise
  verification of two (x,log(x)) pairs.


Symmetric-keys algorithms with different keys for encryption and decryption

A relevant example where you usually don't use the same key for encryption and decryption is actually AES (and any SPN-based cipher for that matter).
The simplest point here would be that for AES you'd normally store your expanded key in order of usage in memory (to help with things like prefetching). However this would mean that the e.g. 11 round keys are stored in reverse order for encryption and decryption!
Furthermore for actual AES-NI based implementations you'd go one step further and pre-process your decryption round keys due to the way the hardware decryption instructions work (see e.g. this Intel guide (PDF) on how to do that). Due to this your actual key schedule usually looks completely different for the encryption and decryption direction (though you can somewhat easily transform one into the other). But no one would argue that AES is not a symmetric cipher...
As for the more general angle on this question: If the transformation is a simple operation as suggested on Wikipedia, it would usually be "hidden" from the user. That is one would usually specify the faster expansion for encryption and then add a pre-processing step for the key-usage during decryption.


Cryptographically correct way to roll a giveaway winner

It looks mostly sound.
Why are you returning logs?
It is initialized to [] but never written to after that.
Are you aware of Crypto.Random.random.sample(population, k)?


The "obvious" (it really isn't that obvious) thing you are missing is: The same reasoning could be applied to literally any other private key! There is nothing special about $a=\lvert(\mathbb Z/p\mathbb Z)^\times\rvert=p-1$ (which would, by the way, more commonly be represented as $0$ modulo itself), except that checking for it is particularly easy. For instance, if an attacker suspects that your private key is $42$, they can simply compute $g^{42}\bmod p$ and compare it to the public key $g^a\bmod p$ you transmitted. Does this imply that $42$ is a weak private key?

The reason why Diffie-Hellman (and in fact, similar fallacies apply to any cryptosystem) can still be secure is that the probability of each single key occurring is negligible. An attacker can test whether your private key equals something, but it takes a certain amount of time (a bit less for $a=0$, but still). When the set of possible keys is reasonably large, the attacker can't search through a meaningful subset of in their lifetime, hence they will, with overwhelming probability, not be able to guess the correct private key.


Unforgeable CPA-secure private-key encryption scheme that is not CCA-secure

Take an authenticated (unforgeable and CCA-secure) encryption scheme, such as the one constructed in the book using encrypt-then-authenticate with a CPA-secure encryption and a strongly secure MAC.

Define a new scheme by appending to the ciphertext a random string.

This new scheme is still CPA secure and unforgeable. But it's not CCA secure because the adversary can change the random appendix and thus ask the oracle for decryption and win the CCA game.


Cryptography algorithms that take longer to solve on a GPU than a CPU

This specific situation is a central part of the analysis of password hashing functions. Indeed, for hashing a password, we want a function which is:

slow in a tunable way;
such that the most cost-effective hardware for evaluating many instances of the function is the hardware that the expected defender will use, i.e. a "normal PC".

"Cost" here means actual money. For the attacker, it does not matter whether he will need 10, 100 or 1000 units of whatever hardware he'll use; only the total cost will be necessary. It can be argued that with modern hardware, in particular GPU, the majority of the budget for crunching passwords will be spent on electrical power, not on purchasing the hardware. Therefore, it makes sense to define the cost of the function with regards to the energy consumed by its computation, on both general-purpose CPU, and various GPU.

The bcrypt password hashing function appears to be indeed such a function, that is more expensive (energy-wise) to compute on a GPU than on a CPU. The bcrypt feature that makes it so is that it is organized around an internal 4 kB array of data which is continuously read and modified in a way which is not amenable to shortcuts, and at pseudorandom addresses. GPU are not well-equipped for that; if you try to implement bcrypt on a GPU, you will experience considerable contention for data access, and most of the GPU cores will be stalled at any time (and such a stalled core still consumes power).

The Password Hashing Competition was organized to define new functions that fulfill a larger goal, namely to not only be more CPU-friendly than GPU-friendly, but also to "hold the line" to some extent when facing attackers with FPGA or custom ASIC. The main tool used by most candidates was again RAM, but more of it; the underlying assumption is that modern PC (servers, desktop systems...) contain a thoroughly optimized memory bus that cannot be operated at a substantially lower cost by custom hardware. It is unclear how far that assumption holds.

One of the PHC candidates, called Makwa (which I designed), did not use RAM but modular arithmetics. This is not expected to fare well against FPGA and ASIC, but, for GPU, it appears to behave well: according to my analysis, costs on CPU and GPU appear to be roughly on par for a 2048-bit modulus, and larger moduli benefit the CPU more than the GPU.

To sum up, both bcrypt and Makwa seem to be valid answers to your question, and they do so through quite different means.


Could using sequential plaintext uncover AES key?

Could the attacker figure out the AES key if the IV used to encrypt all the strings is the same?

No; the AES key is secure against such an attack.

  Could the attacker figure out the AES key if the IV used to encrypt all the strings is NOT the same (one IV per string), but known?

No, the AES key is secure against such an attack.

You say that you are having trouble wrapping your head around how strong AES actually is; it extends pretty far. In fact, AES is secure against a chosen plaintext attacker; that is, even if the attacker supplied Gigabytes of data for you to encrypt, and you encrypted them, we still don't know how an attacker would be able to use that to reconstruct the key.  This attack model is obviously much tougher on AES than your model (where the attacker just knows some information about the plaintext, but doesn't get to pick it).

  WITHOUT figuring out the full key, would it be possible for the attacker to compose their own string that allows them to set their own known value for bytes 18-34, and simply put garbage in the rest of the bytes?

Ah, that's a different question; that actually depends on the mode of operation that you use AES in.  The mode of operation is how you use AES (which just defines a transformation between 16 byte blocks to 16 byte blocks) to actually do something interesting, such as encrypting a long text.

What you are asking is 'suppose an attacker takes an encrypted message; could he modify that encrypted message, so that the modified message decrypts into something that the attacker wants (or, at least, parts of the decrypted message is what the attacker wants).  Now, there are multiple encrypting modes of operations defined for AES; they differ about how well they handle this.

If you are in a scenario where an attacker might be able to modify the ciphertext, you usually want to use something that detects such games; there are two standard ways of handling this:

You can encrypt the message (using any mode of operation that does encryption), and also apply a separate Message Authentication Code (such as HMAC or CMAC) on the ciphertext.  The MAC has the property that if anyone modifies it, the computed MAC and the MAC in the message will not agree, and so you know that someone modified the message.
You can use a mode of operation that does that inherently (such as GCM); these modes effectively both encrypt and perform a MAC on the message.


What size of initialization vector (IV) is needed for AES encryption?

For both CBC mode and CFB mode, the initialization vector is the size of a block, which for AES is 16 bytes = 128 bits.  For CFB mode, the IV must never be reused for different messages under the same key; for CBC mode, the IV must never be reused for different messages under the same key, and must be unpredictable in advance by an attacker.  Using successive integers as the IV is fine for CFB but not fine for CBC.

Beware: The Wikipedia articles are currently (2017-08-11) full of archaic drivel about self-synchronizing ciphers and error propagation and other fortunately forgotten relics of the dark ages of crypto engineering from a bygone century.  I cite them only for the easily accessible statements of equations relating plaintext and ciphertext and their associated diagrams.

All that said, could I interest you in an authenticated encryption scheme instead, such as NaCl crypto_secretbox_xsalsa20poly1305?  Or, if you find yourself reaching for the letters ‘AES’ and ‘CBC’, you're probably lost in a vat of acronym soup and you may need help navigating crypto protocols more than you need help picking the right parameter sizes for a confusing crypto API that asks you to choose mode and then specify IV.


This depends largely on the trustworthiness of Facebook and your assumptions about the model and attacker.

If Facebook is corrupted, they will just exchange your information to their address/public key and can still do a man-in-the-middle.
An external attacker could modify the profile pages while they are being transmitted to other users or in their browser, with the same result. In reality, this is easy when SSL is not used or when the person (viewing your profile) is infected by malware.
If your own computer/browser is compromised, the attacker will either know the according secret $a$ anyway or he can modify your profile update to a value of his choice.

In a more practical world, this could work... if people would use email encryption in general. There are mechanics like PGP or S/MIME, but they are not widely used due to not being comfortable. This is a general problem, but Facebook (or any other social media) would surely work as a place to publish your public key/certificate. But using such a public profile from Facebook from someone else requires a certain amount of trust in the plattform (that it is actually the information from the according user).

In your example you use an Diffie-Hellman key exchange with one fixed parameter, you might want to change that to an ElGamal encryption of a new random key for the symmetric encryption., as usual in hybrid encryption schemes.