Is it more weak to encrypt with the private key RSA?

the "breaker" doesn't know any of the keys

That goes against the very name of the public key, and rationale for using RSA or any asymmetric cryptography. Let's assume it nevertheless in the first section of this answer.

  Is the only difference between the public and private (keys) that the private can generate public keys but the public key can not generate private?

No.

The two keys typically are not in the same format.
Further, in RSA

The exponent in the public key is customarily small.
The most common formats for private key include the factorization of the modulus, when the public key never does.
Depending on format of the private key and method of generation of the key pair, the private key allows to generate a matching public key, or not. Neither constitute a weakness of RSA.

The public key of any secure asymmetric cryptosystem never allows to generate a matching private key.

  (assume):

  RSA key generated with puttygen
  PGP encryption / decryption

PGP does not give any way to encrypt with a private key, nor decrypt with a public key. Neither does GPG, nor any reasonable OpenPGP implementation. The closest it allows is producing a signature, which leaves the message in clear or removes it. That's totally unsafe or dysfunctional from the perspective of confidential transmission of a message.
Note: When creating or importing a private key, PGP/GPG also generates or import the public key, and that what it uses to encrypt. Correspondingly, the passphrase normally required for private key use is not asked for encryption.

The closest feasible thing matching the question's description would be to swap the public and private key generated by puttygen, before somewhat feeding them to the encryption program. That's not quite trivial, because the two keys are not in the same format. But that's feasible: we change $e$ of the formerly public key to $d$ from the formerly private key, and change $d$, $d_p$ and $d_q$ of the formerly private key to the former $e$, that is $37$ as explained here.

If we do this, the newly made public key will look about normal, except for a large exponent instead of a customary short one ($37$ and $65537$ are common). Encryption will be possible (and measurably slower than usual). Decryption with the newly made private key will be possible (and measurably faster than usual). The question asks if that's less safe than normal encryption is.

Yes, that's less safe in the sense that now an adversary knows the normally secret $d$ in the private key (that's $37$). Thus if somewhat the normally public modulus $N$ gets public, it becomes trivial to decipher. Normally $N$ is in both keys, thus public; and further, encryption programs make no effort to keep $N$ secret: we can't rule out that with some encryption option, $N$ is sent in clear along the plaintext. Or that some attack allows the attacker to know $N$. For a start, PGP and GPG store $N$ in clear in the pubring file, not protected by a passphrase.

If we hypothesize that an attacker only has one ciphertext without $N$, I see no way to obtain $N$ or otherwise decipher or get any useful information about the plaintext.

This perhaps remains true if the attacker has multiple ciphertexts and knows some corresponding plaintexts, assuming hybrid encryption is used (as in OpenPGP). However, with textbook RSA encryption, $N$ can be recovered and security is lost.

[From this point onwards, we again assume the public key is public]

  Is it more weak to encrypt with the private key against the public key with RSA ?

Often that's impractical or/and unsafe (see above); but not necessarily. In fact, RSA as taught and practiced today reverses the public and private key compared to the key generation procedure of original RSA (Ronald L. Rivest, Adi Shamir, and Leonard  Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in Communications of the ACM, Feb. 1978). That reversal was originally made for performance reasons, and it turns out that it improves security compared to that in original RSA!

Original RSA has an almost unique characteristic among asymmetric cryptosystems: we indeed can exchange public and private key, and that does not compromise security (including when we reveal the key used for encryption, as designed, see final section). That's because original RSA

first selects the decryption exponent $d$ mostly randomly in a large set, then computes the encryption exponent $e$ from that, per the symmetric equation $e\,d\equiv1\pmod{\phi(N)}$
public and private keys are in the same format: the public modulus $N$ and an exponent.

It quickly became standard practice to first choose the encryption exponent $e$ (that is, reverse public and private key compared to key generation of original RSA): in Martin Gardner's A new kind of cipher that would take millions of years to break (in the Mathematical Games column of Scientific American, Aug. 1977), Rivest's MIT group used $e=9007$ in a then difficult challenge, implying that $e$ was chosen before $d$. Such small $e$ speeds computations involving that exponent (encryption and signature verification) by a large factor, broadening the practical uses of RSA; but it becomes unsafe to exchange public and private exponents.

It took some time to fully realize that original RSA's prescription "It is important that $d$ should be chosen from a large enough set so that a cryptanalyst cannot find it by direct search" is necessary, but insufficient for security. Selecting a random $d$ in $[2^{135},2^{136}]$ with $\gcd(d,p-1)=1=\gcd(d,q-1)$ blocks direct search of $d$, but would be unsafe for $p$ and $q$ 512-bit or larger primes (see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999).

In original RSA, decrypting is the same as signing, and both are encrypting with public key replaced by private key. However:

Original RSA's enciphering is insecure (among reasons: correct guess of the message can be verified with the public key, thus it is insecure to encipher a name on the class roll, a password, or a credit card number).
Original RSA's signing is insecure (for different reasons, including: an adversary can find signature of a message showing as any short desired text when printed as a C string; a few rightful signatures of some selected meaningful and sizable messages can be turned into forged signatures of other meaningful and sizable messages).

Weaknesses of original RSA have been fixed, but with modern RSA as practiced (or PGP/GPG and RSA keys), signing is markedly different from encrypting with public key replaced by private key. And many other common signature schemes have no encryption counterpart.

While modern RSA practice distinguish signing from encrypting with public key replaced by private key, it's possible to have the two use essentially the same padding. See Jean-Sébastien Coron, Marc Joye, David Naccache, Pascal Paillier, Universal Padding Schemes for RSA, in proceedings of Crypto 2002 (also there). Note: AFAIK it is not used in practice.

Glossary of things properly named:

In public-key cryptography, the public key is made public (the private key is kept secret).
In public-key encryption, encryption is with the public key (decryption is with the private key).
In public-key signature, signature verification is with the public key (signing was with the private key).


Given $$\alpha ^{k}\equiv \prod p_{i}^{a^{i}}  \mod p$$

take $\log$ of both sides to base $\alpha$

\begin{align}
\log_\alpha(\alpha ^{k}) &\equiv \log_\alpha(\prod p_{i}^{a^{i}})  \mod p\\
k &\equiv \sum \log_\alpha(p_{i}^{a^{i}})  \mod p-1 \quad\text{;by Little Fermat}\\
k &\equiv \sum a_i \log_\alpha(p_{i})  \mod p-1\\
\end{align}

Here $\log_{\alpha} = L_{\alpha}$.


Yes, there does happen to be such a scheme: the Lamport one-time digital signature.

The basic idea of a Lamport signature is that the private key consists of a large number (say, 256) of pairs of secret random numbers, while the public key consists of the cryptographic hashes of those numbers.  To sign a message, you first hash it down to 256 bits, and then, for each of those bits, reveal one of the secret numbers in each pair depending on the corresponding bit.  Thus, a Lamport signature is literally a (pseudo-randomly chosen) half of the private key.

Technically, publishing two Lamport signatures using the same key weakens the security of the scheme by half, such that the probability of an attacker being able to successfully forge a signature for a given message increases from, say, $1/2^{256}$ to $1/2^{128}$.  A third signature using the same key would increase the probability of a successful forgery to $1/2^{64}$, a fourth to $1/2^{32}$, and so on.

Generally, this one-time nature of Lamport signatures is seen as a problem, and there are various signature schemes, such as Merkle signatures, that extend the Lamport scheme to work around it.  If you wanted to make deliberate use of it, you'd have to deal with the fact that, as described above, the security collapse caused by a duplicate Lamport signature is not quite immediately, but somewhat gradual.

For example, if you wanted a duplicate signature to allow easy forgery with $2^{32}$ effort, you'd have to accept that even a single signature could be forged with $2^{64}$ effort, which might be a bit too low for comfort.

One possible solution to this problem would be to modify the Lamport scheme so that, instead of pairs of random numbers, your private key would consist of, say, groups of 16 random numbers, out of each of which you'd reveal all but one in the signature (with the one hidden number in each group chosen based on four bits of the message hash).  Thus, a duplicate signature would have a $15/16$ chance of fully revealing each group in your private key (and thus rendering it trivially forgeable), increasing the forgery probability from, say, a negligible $1/16^{64} = 1/2^{256}$ to an easy $1/16^\frac{64}{16} = 1/16^{4} = 1/2^{16}$.

Of course, you'd also need to deal with all the other inconvenient features of the Lamport signature scheme, like the enormous size of the public and private keys and the signatures themselves, or the fact that, as one would expect of a one-time signature scheme, each key can indeed only be safely used once.  As the Wikipedia articles I've linked to note, various tricks do exist to mitigate several of these issues (and sometimes even several of them at once), but turning the basic Lamport scheme into something practically usable is still not exactly a trivial task.


What is the difference between verifying the hash value (MAC) and security provided by authenticated encryption?

Authenticated encryption also keeps the message secret.

Often, though not necessarily, authenticated encryption is built out of a composition of a cipher and a MAC—which, if you have to do yourself out of parts like AES-CTR and HMAC-SHA256, you should do as encrypt-then-MAC.

P.S.  There is no substantive difference between authenticity and integrity.  They both answer the question: Was this message sent by the party I expected to send it?


No, plain RSA signatures are existentially forgeable under a key only attack. This is because of the following attack strategy:

Given a verification key $(e,N)$, set the message to $m=s^e \bmod{N}$ for an arbitrary $s$ in the message space and set the corresponding signature to $s$. Output the message signature pair $(m,s)$ as a forgery.

It is easy to verify that this pair passes the verification equation.


The number of cipher texts possible for each plaintext

What exactly is $N_c$?

It is a number that may depend on a given ciphertext and states how many keys exist for every message that produce this ciphertext. The statement here is that every ciphertext can be produced from every message with an equal number of keys, i.e. if you draw keys uniformly at random all messages had the same probability of being the source.
For perfectly secret schemes with $|K|=|M|$ this will always be either 1 or 0. It could be 0 e.g. if the ciphertext is longer than anything in the message space for a OTP.


Economically Rational as a security proof

The tricky part is what if the agents do not follow the protocol? It is often the case that by deviating from the protocol, an agent can gain a higher payoff than following the protocol. if this happens, then the agent may not follow the protocol. One party deviating from the protocol may cause other parties to change their strategy. Will they reach a stable state?

Therefore, to prove security, you would need to specify the following:

All the parties (players);
All actions can be performed by the parties (strategies);
Is there any sequence or order of parties have to act, or they move simultaneously;
What information do the parties have in the process? Do they know everything or only some information?
The utility functions of each party -- taking into account not just money, but others types of payoffs.
All assumptions

Putting those together, you can formally specify a game. Having the game formally specified, you will have all possible outcomes induced by all possible combination of parties' strategies, and payoffs for each party associated with the outcome. You can then analyse the game to see whether there exist an equilibrium (or more than one), which is a "solution" of the game. An equilibrium consists of a set of strategies for each party (and maybe probabilities). An equilibrium basically says if all parties choose the strategies in the equilibrium, they will not want to change their strategies because their utilities won't be better.

In the simplest case, if you have one equilibrium and it entails your security goal, then you can say you have proved security in the presence of rational parties. But the situation can be much more complicated.


Does having a known plaintext prefix weaken AES256?

AES-256 has sustained 15 years of cryptanalysis, and it can be stated that no knowledge of some plaintext bytes would help to reveal the other bytes no matter what mode of operation (CBC, CTR, etc.) is used.

AES-GCM is an authenticated encryption scheme that allows a key holder to detect any modification that has been done to the ciphertext. If you do not care about such modifications (which are easy in the Counter mode), then you do not have to use GCM. However, if you can use it, I would definitely recommend doing so.


Distinguishing generators of RSA primes and moduli

This has been examined before, for example in Fouque and Tibouchi (2001).  It's been brought up in a number of places in online forums as well, though not with any sort of resolution.

I agree with this statement from F/T: "Moreover, even for more common uses of prime number generation, like RSA key generation, it seems preferable to generate primes that are almost uniform, so as to avoid biases in the RSA moduli themselves, even if it is not immediately clear how such biases can help an adversary trying to factor the moduli."

It is very easy for people to fall into the "proof by failure of imagination" trap.  Well I can't think of any way to do it, so it's good.  There are a lot of areas in life where this is an efficient strategy, but cryptography should avoid this compromise where possible.  Just because we can't think of a way to exploit it now, why should we leave this very large bias when we know how to do much better with almost no loss of efficiency?

It's easy to implement PRIMEINC, and while just as easy to implement, TRIVIAL without optimizations is slower.  Effective optimizations of the latter require some thought, coding, and testing.  Most consumers honestly do not care (edit: they should, but evidence is that quality isn't a big priority until something obviously breaks).  Also I see most packages like the OP's referenced pycrypto are really simple -- finding a hundred lines of optimized random prime generation would be out of place there.  This does have the advantage of readability and debugging.  But we can do this both better (more uniformly) and faster if we want.

The provable prime generators don't have this same issue, but they do generate only a subset of the primes in the range.  Both Shawe-Taylor and Maurer spend a large portion of their papers going over the distribution and implications.


Is there a number of tries after which Hashcash is guaranted to be solved?

The probability of finding an acceptable number is
$$Pr(\mbox{accept})=2^{-20}.$$
Thus the probability not to find an acceptable number is
$$Pr(\mbox{reject})=1-Pr(\mbox{accept})=1-2^{-20}.$$
Assuming independent events, the probability not to find an acceptable number in $k$ attempts is given by
$$Pr(\mbox{$k$ rejects})=(1-2^{-20})^k.$$
Thus, the probability to find at least one acceptable number in $k$ attempts is given by
$$Pr(\mbox{not $k$ rejects})=1-Pr(\mbox{$k$ rejects})=1-(1-2^{-20})^k.$$

This means that if you want to find an acceptable number with a probability $P$, you chose $k$ such that
$$1-(1-2^{-20})^k>P$$

$$\Leftrightarrow k>\frac{\log (1-P)}{\log(1-2^{-20})}.$$

Example

To find an acceptable number with a probability of P=99%, you have to make
$$k>\frac{\log (1-P)}{\log(1-2^{-20})}=\frac{\log (0.01)}{\log(0.9999990463256836)}\approx 4828869$$
attempts.


The "base point" is conventional. When using El Gamal or similar algorithms with an elliptic curve, you want to work inside a group with a prime order (either the complete curve has a prime order, or you work in a subgroup of the curve). Within a group of prime order, any element (except the neutral element, which is the "point at infinity" for an elliptic curve) is a generator for the group, so any point will be appropriate. The only requirement here is that all parties agree on the point to use.

It can easily be shown that any base point is as good as any other with regards to resistance to discrete logarithm: if you can solve DL efficiently in base $G$, then you can solve it efficiently in any other base $G'$ by first solving $G'$ with regards to $G$: first, use your efficient DL solving algorithm to compute $k$ such that $G'$ = $kG$; then, given $xG'$, solve it in base $G$ to get $xG' = rG$, then the solution will be $x = r/k \pmod n$ (where $n$ is the group order).

In practice, the "base point" is considered to be part of the curve definition, along with the other curve parameters. For instance, FIPS 186-4 defines the "NIST curves" (in annex D); for each of them, it lists the field modulus ($p$), the curve order ($n$), the curve equation parameters (NIST curves in a prime field use $y^2 = x^3 -3x + b$, so the only equation parameter is $b$), and the two coordinates $G_x$ and $G_y$ of the conventional base point.


About the Rijndael/AES sbox polynomial (subBytes)

I'm not seeing any particularity between the two field that they build, but exists?

First off, one basic truth about finite fields is that there is at most one finite field of a given size.  Given that both $x^7 + x + 1$ and $x^7 + x^4 + x^3 + x^2 + 1$ are both irreducible, they both generate the same finite field.  Where they differ is the representation; how they represent specific GF(128) field members as bit patterns.  For example, the member 0x02 in the $x^7 + x + 1$ representation is the same abstract element as 0x1d in the $x^7 + x^4 + x^3 + x^2 + 1$ representation.

So, the question becomes "which representation would have an advantage within AES"?  The answer to that would be "both are equally good"; as I discuss in this answer, both representations are equivalent; the rest of the AES structure can be adjusted so that the AES cipher as a whole acts equivalently.

So, the reason that $x^8 + x^4 + x^3 + x + 1$ was chosen was because it was the lexically smallest; they had to pick one, and there was no reason one polynomial representation was better than any other; it was simply an arbitrary choice.


What was the NSA's reasoning for making their bitwise combination functions in SHA-1 the way they did?

What choice did they have?

F1 is a bitwise function with three inputs and one output. There are $2^8 = 256$ such functions. Only 70 of them are "unbiased" (i.e. have as many 0 and 1 outputs in their image). If you further require that each input, as well as the order of inputs, matters for the output, you are left with only 36.

However, those 36 are all basically equivalent. If you change the order of arguments for F1 and/or add some initial negations to any of the arguments, you will be able to construct them all. So they could have added some initial not-operations (making it more complex) or changed the argument order, but that's it.

The only other options they had were biased functions like the one in the question, ones where some input doesn't matter (so they are actually one or two input functions), and ones where the argument order doesn't matter, like B ^ C ^ D.


As for goals, there are typically two that you would look to when implementing something on an FPGA: first, minimizing latency; second, maximizing throughput.

To minimize latency, you would use the FPGA to perform a computation much faster than you could do on a CPU. An example here would be the DES cipher. DES is well suited for hardware and you can get significant reductions in latency using an FPGA.

The second goal to potentially look at is maximizing throughput. The idea here is that you could potentially use hardware to encrypt 100s of streams in parallel.

As to which algorithms are not suited for FPGA, Thomas pointed out scrypt. I'm guessing other KDFs are similar in that they try to make it extremely hard for an attacker to gain any advantage by using an FPGA. Of related interest might be this question on bcrypt using GPUs.


For the theoretic scenario of a brute force attack, how would you know if you succeeded?

If you managed to brute force an AES encrypted text , how would you know you cracked it ? After every attemt , you wold have to compare the text to an english dictionary right ? That would take ages .

Yes, thats why you could first check if most values are mapped to normal ASCII letters. If they do, then you could try that for more blocks, and when you got enough confidence you can check if those are most likely proper words, for example with dictionary. Since only marginal number of keys would result in such data, it wouldn't matter.

  In the scenario of an AES encrypted program , you would get hexadecimal code every time even if you succeeded right ?

Every program in virtually any OS has a structure to it. You would find static elements, which would make checking plaintext even simpler: try to read file header, to see if this is valid header.
Even if your specific code had no header, you could still easily predict that this code starts with 0x55 0x89 0xE5 (push ebp;mov ebp,esp), as thats typical procedure entry code (of course this is specific to architecture, example is given for x86).

Very same continues for virtually every data you can invent except for plain random data which is never reused anywhere.

  So i wanna know , how do the best AES cracking methods of today work .

There are no AES cracking methods that we know of. There are some theoretic attacks on AES which are nowhere near being applicable. Problem in cracking any modern cipher is cost of trying all keys, check if decryption is right can be easily checked on most data.


All is solved in the comments, but I thought this would be a good opportunity to tell a real story. I was once called urgently by a company that I consulted for due to a bug discovered by their QA department. When they encrypted and decrypted with plain RSA, they would sometimes not get the same input back. The problem was simple, they were using RSA1024 at the time (many years ago) and would take random 1024-bit strings as input. But as good QA people, they also tested the "edge cases", so they would encrypt the string of all zeroes and the string of all ones. Needless to say, the string of all ones would not decrypt correctly. This is exactly the case that $m \geq n$ and so "decryption" indeed doesn't work. It's a nice story and just goes to show that even QAing crypto requires some math understanding!


Proof of (in)distinguishability based on DDH/CDH/DL

The two given tuples are computationally indistinguishable. Here's a proof
Let tuples $T_1=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_1y})$ and $T_2=(g,  g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_2y})$
Lets take a tuple $T_3=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^r)$ where $r \overset{$}\leftarrow
 \mathcal{R}$. That is, for the purpose of the proof we generate a tuple with the last element being a random element of the group.
It's easy to see that $T_1 \approx T_3$ ($\approx$: notation for compuational indistinguishability) because of DDH assumption. Same way, $T_2 \approx T_3$ as well. Since we know that computational indistinguishability is transitive, that means $T_1 \approx T_2$.


The best algorithm for computing discrete logarithms are based on families and variations of methods known as "number field sieve" and "function field sieve". They all share a common structure. In particular, they are divided in several phases, only the last of which depends on the value whose discrete logarithm must be computed: all the previous steps require only the order of the field.

I did some research. I do not know about the computational complexity of each step, this would involve some more research but can probably be found in some of the articles and surveys of Antoine Joux. However, I'll focus on the case which seems to be your target: discrete logarithm in prime order field. For that case, the actual record is a discrete log in a field of order $p$, with $bitsize(p) = 530$. You'll find Here the report on this record. The computation is divided in five phases: polynomial selection, sieving, filtering, linear algebra, and actual computation of the discrete logarithm. Among them, the sieving is by far the dominant cost: the report indicates it took approximately 50 core-years on a 2-GHz Intel E5-2650. This phase depends only on the order $p$ of the field. The report mention that once the four first phases have been performed, "Computing one individual logarithm required a few hours". Therefore, Compared to the overall time, computing discrete logarithms is extremely fast once the precomputation has been made (with the order of the field only).

Although I do not know the theoretical complexity of this last step, I'm pretty sure that this is still not polynomial time (id est, $O(\log^c p)$ for some $c$), even if it is only a negligible cost in the total computation.


Number of rounds for constant header size in common hashes and XOFs

Heading
\begin{array}{l|rrrl|rrrl}
\text{hash} & d&r&\mu&\text{(bits)}&\tilde d&\tilde r&\tilde
 \mu&\text{(bytes)}\\
\hline
\operatorname{MD5}        & 128 &  512 &  65 && 16 &  64 &  9 \\
\operatorname{SHA-1}      & 160 &  512 &  65 && 20 &  64 &  9 \\
\operatorname{RIPEMD-160} & 160 &  512 &  65 && 20 &  64 &  9 \\
\operatorname{SHA-224}    & 224 &  512 &  65 && 28 &  64 &  9 \\
\operatorname{SHA-256}    & 256 &  512 &  65 && 32 &  64 &  9 \\
\hline
\operatorname{SHA-512/224}& 224 & 1024 & 129 && 28 & 128 & 17 \\
\operatorname{SHA-512/256}& 256 & 1024 & 129 && 32 & 128 & 17 \\
\operatorname{SHA-384}    & 384 & 1024 & 129 && 48 & 128 & 17 \\
\operatorname{SHA-512}    & 512 & 1024 & 129 && 64 & 128 & 17 \\
\hline
\operatorname{SHA3-224}  & 224 &  1152 &  4 && 28  & 144 &  1 \\
\operatorname{SHA3-256}  & 256 &  1088 &  4 && 32  & 136 &  1 \\
\operatorname{SHA3-384}  & 384 &   832 &  4 && 48  & 104 &  1 \\
\operatorname{SHA3-512}  & 512 &   576 &  4 && 54  & 72 &  1 \\
\hline
\operatorname{SHAKE-128} & d   &  1344 &  6 && \lceil d/8 \rceil & 168 &  1 \\
\operatorname{SHAKE-256} & d   &  1088 &  6 && \lceil d/8 \rceil & 136 &  1 \\
\hline
\operatorname{BLAKE2s-256}   & 256 &   512 & 0 && 32 & 64 &  0 \\
\operatorname{BLAKE2b-512}   & 512 &  1024 & 0 && 64 & 128 & 0  \\
\end{array}

SHA3-x
SHA3-x is defined with KECCAK as;

$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M \mathbin\| 01, 224)$
$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M \mathbin\| 01, 256)$
$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M \mathbin\| 01, 384)$
$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024](M \mathbin\| 01, 512)$

KECCAK
and KECCAK defined as

$\operatorname{KECCAK}[c] (N, d) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–c] (N, d)$

and note that $N = M\mathbin\|01$ and $d$ is the required output size, Now we have

$\operatorname{SHA3-224}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–448] (N, 224)$
$\operatorname{SHA3-256}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–512] (N, 256)$
$\operatorname{SHA3-384}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–768] (N, 384)$
$\operatorname{SHA3-512}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–1024] (N, 512)$

Padding

$\operatorname{pad10*1}(x, m)$  is not important since the message is not formed yet.

SPONGE

$\operatorname{SPONGE}[f, \operatorname{pad}, r](N, d)$

Let $P=N \mathbin\| \operatorname{pad}(r, \operatorname{len}(N))$.

Let $n=\lfloor\operatorname{len}(P)/r\rfloor$.

Let $c=\lfloor b/r\rfloor$.

Let $P_0, \ldots, P_{n-1}$ be the unique sequence of strings of length $r$ such that $P = P_0 \mathbin\| \ldots\mathbin\| P{n-1}$.

Let $S=0^b$

$\textbf{For } i \textbf{ from }0 \textbf{ to } n-1$
$\textbf{let } S=f (S \oplus (P_i\mathbin\| 0c))$.

...

As we can see, we can precompute a message $M$ up to the maximum multiple of $r$  that is smaller than $\operatorname{len}(M)$. More mathematically $$\operatorname{precomputableLen} = \lfloor(\operatorname{len}(M)/r)\rfloor \cdot r.$$ And the $r$ for

$\operatorname{SHA3-224}(M)$ is $r = 1152$
$\operatorname{SHA3-256}(M)$ is $r = 1088$
$\operatorname{SHA3-384}(M)$ is $r = 832$
$\operatorname{SHA3-512}(M)$ is $r = 576$

and the formula
$$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu }r\right\rceil$$
SHAKE128 and SHAKE256

$\operatorname{SHAKE128}(M, d) = \operatorname{KECCAK}[256] (M \mathbin\| 1111, d)$
$\operatorname{SHAKE256}(M, d) = \operatorname{KECCAK}[512] (M \mathbin\| 1111, d)$

As we can see the main difference is the capacity and extra two bits appended to have the domain separation.

$\operatorname{SHAKE128}(M, d)$ is $r =1344$
$\operatorname{SHAKE256}(M, d)$ is $r =1088$

and the formula
$$\text{rounds}= \underbrace{\left\lfloor\frac{m_0}{r}\right\rfloor + \nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu}r\right\rceil}_{\text{Absorbing part}} + \underbrace{\nu  \left\lceil \frac{d}{r} -1 \right\rceil  }_{\text{Squeezing part}}$$
BLAKE2b and BLAKE2s
BLAKE2 uses modified ChaCha as compression function with 16 words. BLAKE2s is the 32-bit version so  $r=512$ here, and for BLAKE2b $r = 1024$ ( $s$ for small, $b$ for big).
and the formula
$$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu } r\right\rceil$$
since BLAKE2 uses all-zero padding, they called it minimal padding.


FIPS 140-2 compliant algorithms in Enhanced RSA and AES Cryptographic Provider (Windows XP)

I can't help you with your Windows question, however I can chime in on FIPS:

  Is it going to be FIPS 140-2 compliant?

It might not be.  The problem is the "SHA1 for hashing"; SHA1 is no longer approved as a collision resistant hash function.  On the other hand, HMAC-SHA1 is still approved as a Message Authentication Code.

That is, if you are using SHA1 (within HMAC) to perform integrity checking, this is not an issue.  However, if you are using straight SHA1 as a part of (say) RSA signatures, this won't work; you'll need to switch to one of the SHA-2 algorithms (or SHA-3 when that is finalized).


What is the probability that $(m_1,m_2,m_3)$ is a "cover"-triple for random $m_1,m_2,m_3$?

Assume $H(m_k)_i$ is uniform over $\{0,1\}$ for all $i,k$ and independent of any other $H(m_k')_{i'}~$, since you have a random oracle.

Let $H(m_1)_i=0$ (the same argument would work for it being one) then $$\mathbb{P}[H(m_2)_i\neq 0~~and~~H(m_3)_i\neq 0]$$ is $(1/2)^2$ by independence.

This gives probability $3/4$ that the $i$ bit of $m_1$ is covered by either of  the $i$ bit of $m_2$ or the $i$ bit of $m_3$ .

This would give the answer $$\frac{3^n}{4^n}$$ which goes to zero exponentially with $n.$


Understanding the distinguisher for a PRG

As said before, the distinguisher D outputs a bit.

I would like to add that the advantage is a measurement for how good the distinguisher is doing. Say you have two distributions which are computationally indistinguishable, then $adv_D$ is negligigle close to 0. On the other hand, if the two distributions are easy to distinguish, then $adv_D$ would be close to 1.

On your formula, the advantage of D is:
$$adv_D = |Pr(D(X)=1) - Pr(D(Y)=1)|$$.

If the distributions are indistinguishable, a distinguisher cannot succeed on doing its job, i.e. distinguishing the two distributions. Then, the output of D is the same regardless of having distribution X or distribution Y as input.

If you need further reading I strongly recommend you having a look at the paper "On the Role of Definitions in and Beyond Cryptography", by Rogaway. There he explains clearly the concept of distinguisher.


Why is the NIST recommendation for the private key exponent so much smaller than the modulus?

Generic algorithms for solving the DLP, like Shanks baby step-giant step or pollard rho are of complexity of order $\mathcal{O}(|G|^{0.5})$. That is, for $|G|=2^{256}$ you get a complexity of $\mathcal{O}(2^{128})$. However, for the index calculus method, that is operated on the modulus, for complexity of $\mathcal{O}(2^{128})$ you would need a modulus of size 3072 bits. You may use larger exponent, but this will result in more complex calculations, while the security remains $\mathcal{O}(2^{128})$


Simplifying the description of the Keccak padding rules

According to Keccak submission 3rd document on page 10, the padding scheme changed from round 2 to round 3.

  We shortened and simplified the padding rule. The new padding rule is the pad10∗1
  rule

In the original specifications on page 3;

  $\texttt{pad}(M, n)$ returns a bit string obtained by appending to the bit string M a single 1 and
  the smallest number of zeroes such that the length is a multiple of n.

In Sponge Construction Functions, The Keccak team  proved that both satisfies

  the sponge construction offers protection against generic attacks if the
  padding rule is sponge-compliant, i.e., it is injective and ensures that the last block is different from the all-zero block

They changed it because of this rationale:

  pad10∗1 is simpler to describe and to implement than the rounds 1-2 padding rule

In Short, Keccak padding rule evolved during the submissions.


What does "congruent to 448, modulo 512" mean for padding in MD5 hash function?

When we talk about a number $x$ being "congruent to 448 modulo 512", what we mean is that $x$ modulo 512 and 448 modulo 512 is the same number; since 448 is less than 512, this is equivalent to $x \bmod 512 = 448$

So, how the padding in MD5 works is "first you append a 1 bit (this part isn't mentioned in the above quote, but it's a necessary step), and then you keep on appending 0 bits until the total length of the message (mod 512) is exactly 448 (and then you append the 64 bit length of the unpadded message, in little endian order).

And, if you are only in hashing messages that are integral number of bytes (e.g. you don't care about the hash of a 123 bit message), then the equivalent procedure is "append an 0x80 byte, then then keep on appending 0x00 bytes until the total length of the message in bytes mod 64) is exactly 56 (and then you append the 8 byte length of the unpadded message).

Note that, in both cases, if the message after appending the 1 bit/0x80 byte is exactly 448/56, then you don't append any 0 bits/bytes.

Also, the SHA-1 and SHA-256 hash both use the same padding method (except that the byte length is in bigendian order)


Any implication of a Yale result to security of quantum cryptology?

No.  The Yale result describes a method of partial measurement that is not completely destructive to the quantum system's coherence, which is tied to its physical representation.  It is not a refutation of quantum indeterminacy, which is the basis for (provably secure) quantum key exchange.  In other words, the Yale team measured a qubit in such a way that it doesn't "fall apart" (decohere) when it's measured - in the author's words, "the measurement record faithfully reports the perturbation of the system after the fact." However, the act of measurement still affects the qubit's information content in accordance with the mathematics of quantum mechanics.


Implement deniable encryption with AES/RSA

We need clear goals. The question asks for "plausible deniability" or "deniable encryption", and these terms needs a precise definition in a public-key context (implied by RSA). I assume that in addition to the IND-CPA and IND-CCA1 properties of a cipher, including hybrid (as implied by AES), it is desired that:

One without the private key can't distinguish ciphertext from random data of the same length (with the exception of data too small to be correct ciphertext considering the key size).
One trying to decipher ciphertext with the wrong private key get random-like output and no error message (with the exception of ciphertext too small to be correct ciphertext considering the key size).
Even one with the private key can not distinguish from random the ciphertext obtained by encryption with the corresponding public key of unknown random data.

I think these goals are orthogonal. (1) is most natural; (2) helps leaving interceptors clueless; (3) is useful in a context of layered encryption. The whole gives some useful level of deniability in societies where possessing random files and encryption programs designed for deniability is not objectionable.

I propose a simple scheme that I claim meet the above goals. It is close to the simplest possible form of hybrid RSA/AES encryption: use a random key to AES-encipher the bulk of the data, and use RSA to encipher that key. The only difficulty is making sure we do not leave a bias here or there. In particular, usual RSA primitives have their ciphertext with some bits biased, sometime constant, failing (1); and with the right private key, they often reveal more structure, failing (3).

The key setup is that of RSA. Users have private keys $(N,d)$, and all the corresponding public keys $(N,e)$ are made public. $n$ is the bit size of $N$, so that $2^{n-1}\le N<2^n$. I restrict to plaintext, ciphertext, and more generally data or files that are a contiguous collection of octets. Ciphertext always is exactly $\lceil(n-1)/8\rceil$ octets longer than the plaintext. Big-endian binary is used in all conversions between octets and integer.

Symmetric encryption is done using AES-128 for $128<n\le2049$, AES-192 for $2049<n\le4097$, AES-256 for $n>4097$.

The encryption procedure accepts a public key $(N,e)$ and plaintext:

repeat the following steps..

generate $M$ uniformly random in $\{0\dots N-1\}$;
compute $C=M^e\mod N$, which is textbook RSA encryption;

..until $C<2^{n-1}$ [notes: here $C$ is uniformly random in $\{0\dots2^{n-1}\}$; in the context, the end condition means that $C$ fits in $n-1$ bits; it will take on average less than two iterations to get there];
generate $a$ uniformly random in $\{0\dots2^{7-((n-2)\bmod8)}-1\}$ [note: in other words, generate $a$ of 7-((n-2)%8) random bits];
let $A=a\cdot 2^{n-1}+C$ [note: that concatenates $a$ and $C$ for a total of $8\cdot\lceil(n-1)/8\rceil$ bits, when considering $a$ and $C$ as bitstrings of fixed sizes $7-((n-2)\bmod8)$ and $n-1$ bits];
output $A$ as $\lceil(n-1)/8\rceil$ octets;
let the low-order bits of $M$ be the AES key of the size determined by $n$;
encipher the plaintext (if any) in AES-CTR mode with implicit zero IV, and output it.

The decryption procedure accepts a private key $(N,d)$ (possibly in another form) and data that is a putative ciphertext:

read the first $\lceil(n-1)/8\rceil$ octets of data, forming an integer $A$ of (at most) $8\cdot\lceil(n-1)/8\rceil$ bits; if there is not enough data, terminate with error or hang;
compute $C=A\bmod(2^{n-1})$ [note: that forms $C$ by ignoring the high-order $7-((n-2)\bmod8)$ bits of $A$, considered as a bitsring of $8\cdot\lceil(n-1)/8\rceil$ bits];
compute $M=C^d\mod N$, which is textbook RSA decryption;
let the low-order bits of $M$ be the AES key of the size determined by $n$;
decipher the rest of the data (if any) using AES-CTR mode with implicit zero IV, and output it.

I do not support encryption to multiple users (a common feature of hybrid encryption), or checking that the plaintext or ciphertext is unaltered, which are antagonist with the combination of the goals.

I make no attempt to hide the length of the original data (adding some level of this is simple: for example, before encryption, append 0 to 255 random octets, and a final octet coding the random number of random octets added, which will allow removing the appropriate number of octets on decryption; goals need minor refinements).

UPDATE: I have made IND-CPA and IND-CCA1 explicit goals. IND-CCA2 is not met. Worst problem is that the cipher is extremely malleable, including to one not knowing which public key was used, and that's a weakness: an adversary guessing the plaintext (e.g. from context and ciphertext length) can replace it with another ciphertext that will decipher to any plaintext of her choice that is not longer than the original, without knowing which key is used (with knowledge of the public key, anything can be enciphered, of course). Another weakness is that the size overhead depends on the key size, and is higher than strictly necessary. It seems all this can be fixed, but with two passes for decryption and added complexity.


We construct $OT^1$ from $RandOT^1$ as follows. Say, the Sender (S) has messages $m_0, m_1$ and the Receiver (R) has choice bit $c$. I.e., R needs to learn $m_c$. Now we first run the random OT. S now has random $x_0, x_1$ and R has $x_b,b$. The idea is now for S to somehow OTP $m_c$ with $x_b$ and $m_{c \oplus 1}$ with $x_{b \oplus 1}$ and send these values to R.

To do this R sends $d = b \oplus c$ to S (note this hides c as a OTP). S then sends $(y_0, y_1) = (x_{d} \oplus m_0, x_{d \oplus 1} \oplus m_1)$ to R. Note that we can write $y_i = x_{d \oplus i} \oplus m_i$. R then finds $m_c = y_c \oplus x_b$. Note, $y_c = y_{d \oplus b} = x_{d \oplus d \oplus b} \oplus m_c = x_b \oplus m_c$, thus we get the correct result. Also note, R does not learn $m_{c \oplus 1}$ as it is OTP'ed with $x_{b \oplus 1}$.


Distributing blocks with validation and non-dependant list generation

How about embedding each block's MAC to the next? So that $b'_0=b_0||MAC(b_1)$, with the last block having the MAC of $b_0$. To make it even easier to identify a corrupt block, $$b'_n=b_n||MAC(b_{n-1})||MAC(b_{n+1})$$

where $||$ denotes concatenation. To identify the order of the blocks, simply try to fit them together as they come, or embed each block's $n$ to it.


Is verification of ring signature always linear in the amount of members?

In the most common definition of ring signatures, the verification algorithm obtains the list of public keys (the ring) and thus already requires linear time to read this input.

However, there are constructions based on accumulators (Dodis et al. EUROCRYPT'04, Libert et al. EUROCRYPT 2016, Derler et al. PQCRYPTO'18) which allow amortized sublinear verification costs. In patricular, there is some constant size representation of the ring (the accumulator), where on the first verification one checks if it represents the correct ring (linear time) and after that, verifications with respect to the same ring can take the accumulator instead of the ring and the computation depends only on the complexity of membership proofs in the accumulator (constant for the RSA accumulator in the first link and logarithmic in the ring size for the latter two).


Timing attacks on homomorphic encryption

It is not possible since the IF condition with semantically secure FHE's can be implemented as

$$Q = (A * S) + (B * S'),$$ this circuit is the combinational logic of the if/else statement and we can construct this with FHE.

FHE encrypted $S$ is the input by the if statement ( the boolean expression part).
FHE encrypted $A$ is the input by the  then statement
FHE encrypted $B$ is the input by the  else statement
FHE encrypted $Q$ is the output of the expression.

This is for calculation of the ternary operator
Q = S ? A : B;

The IF condition must be implemented in this way. This is due to the semantical security that prevents the output of the comparison circuit to be known to the evaluator. The above circuit will reveal nothing to any observer. Actually, a similar calculation is also performed during normal programming to mitigate the side-channels.

Note that the == can be achieved with 2's complement and substruction. For a little detail see this answer : Representing a function as FHE circuit

One might also wonder that does the comparison circuits in FHE are constant timing, the answer yes since we don't have IF then return/break statements.


Can anyone tell me the name of this cipher please?

It's called a keyword cipher.  See this question for some ways to break it.


Discrete logarithm hash function Exercises

Yes, this logic works. You have shown that given the discrete log $x$ lets you easily find collisions. Now you need to show that any collision lets you extract the discrete log $x$ and then you are done (then you have shown the equivalence).


My question is: what does 'large' imply? How many digits - is there a
  'limit' to the amount of digits for an suitable prime?

A prime $p$ is called large in this case if factoring the multiplication $pq$ with a similar-sized prime $q$ prime is considered infeasible.  Usual sizes of the primes include $2^{1024}$ up until $2^{2048}$. For the recommended size of the modulus (which is roughly twice as long as the primes) refer to keylength.com.
There's no hard limit to the size of the RSA-primes, as there are infinitely many primes and any two will do.
The soft limit is the amount of computation you want to invest to use these parameters. The larger your primes, the longer you'll take to encrypt, decrypt, verify and sign data which is undesirable in many cases. Usually this makes people chose the lowest reasonably secure size (e.g. 1024-2048 bit primes).

  In some books they talk about 'bits' and 'strings': I still do not
  understand what they mean.

Computers represent numbers as a sequence of bits ($0$ or $1$). The bitlength of a number is said to be the amount of bits ($0$s and $1$s) required to represent said number or equivalently: The bitlength of $n$ is $\lfloor \log_2(n)\rfloor +1$.
A string is generally said to be an arbitrary sequence of bits without any interpretation of its contents (f.ex. as number).

  What does distinct mean?

It means what it says: Two primes $p,q$ are said to be distinct if and only if $p\neq q$. The reason for this requirement in RSA is obviously that $n=p^2$ is easy to factor.


In the SHA hash algorithm, why is the message always padded?

Well, the entire point of a cryptographical hash function is that no one can practically devise two messages that hash to the same value.

Now, the SHA family of hashes use the Merkle–Damgård construction; that is, they have an iterated hash function, and each invocation of the hash function takes as input a fixed block size (either 512 or 1024 bits in the case of the SHA family).

However, we're interested in hashing messages that don't happen to be an exact multiple of 512 or 1024 bits in length.  So, what we do is define a padding function that takes a message, and converts it into a form that's a multiple of the block size in length; we then run the hash compression function on this padded message.

Now, there are a couple of requirements on this padding function; one of the most critical that if we had two different messages, then they must still be different after padding; if not, then the hash compression functions will work identically, and so those two messages would hash to the same value.

That really is the answer to your question (a); if our padding function didn't modify (pad) messages that happened to be the correct length, then that would immediately lead to a collision.  For example, if we take any message $M$ that's not a multiple of the block size, we could compute $Pad(M)$.  Now, $Pad(M)$ will be a multiple of the block size, and so we'd know that $Hash(M) = Hash(Pad(M))$.

As for the answer to your question (b), well, if our padding function was simply adding zero bits until the padded message was of the correct length, well, that would lead to a collision of the form $Hash(M) = Hash(M || 0)$ (assuming postpending the 0 doesn't cause us to cross a block boundary).  On the other hand, the SHA padding function isn't just appending 0 and 1 bits; it also involves adding a bitlength of the entire message at the very end.  If the question is "why do they add a 100...000 pattern and add a message length', well, I rather suspect that's a belt-and-suspenders approach.  Either would be sufficient in itself (as either would prevent two messages from padding into a common value); both are cheap, and so the designers decided to do both.


You are confusing the concepts; the private key vs the public key. Your private key $k$ is an integer which is selected uniform randomly between $1$ to order of the base point $G$

Basepoint $G$ in compressed for
  0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

The order $n$ of $G$, i.e. $[n]G = \mathcal{O}$, where $\mathcal{O}$ is point at infinity, or the identity element in additive elliptic curve group.
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C

Your (or any) public key is $[k]G$, which is scalar multiplication and defined as.
$$[k]G = \overbrace{G+\cdots+G}^{{k\hbox{ - }times}}$$
With add double-and-add it can be calculated very efficiently.
Your failures are due to your python coding ( that is off-topic here) where you want to recover the $y$ value from a compressed public key, not the private key. Rasmus Faber's has an answer in StackOverflow. That is the way you need to find it wiht Python.
Note: All parameters of the curve can be found on Certicom's SEC 2: Recommended Elliptic Curve Domain Parameters


As defined e.g. in Stinson's Cryptography: Theory and Practice (1995, 1st ed.; the earliest source for the term I could find that has even excerpts online), the mutual index of coincidence of two strings of symbols (letters, numbers, whatever) is simply the probability that two symbols chosen at random from each of the strings will be the same.

The formula you've quoted for calculating it looks somewhat garbled, though.  The original(?) definition given in Stinson's book looks like this:

  DEFINITION 1.8   Suppose $\mathbf x = x_1 x_2 \dots x_n$ and $\mathbf y = y_1 y_2 \dots y_{n'}$ are strings of $n$ and $n'$ alphabetic characters, respectively. The mutual index of coincidence of $\mathbf x$ and $\mathbf y$, denoted $\textit{MI}_C(\mathbf x, \mathbf y)$, is defined to be the probability that a random element of $\mathbf x$ is identical to a random element of $\mathbf y$. If we denote the frequencies of $A, B, C, \dots, Z$ in $\mathbf x$ and $\mathbf y$ by $f_0, f_1, \dots, f_{25}$ and $f'_0, f'_1, \dots, f'_{25}$, respectively, then $\textit{MI}_C(\mathbf x, \mathbf y)$ is seen to be $$\textit{MI}_C(\mathbf x, \mathbf y) = \frac{\sum_{i=0}^{25} f_i f'_i}{n n'}.$$

For example, assuming that $\textbf x = \text{"ABACA"}$ and $\textbf y = \text{"BABAA"}$, then $n = 5$, $f_0 = 3$, $f_1 = 1$ and $f_2 = 1$ (since $\textbf x$ contains five letters: three $A$'s, one $B$ and one $C$) while $n' = 5$, $f'_0 = 3$, $f'_1 = 2$ and $f'_3 = 0$ (since $\textbf y$ contains three $A$'s, two $B$'s and no $C$'s), so the mutual index of coincidence of $\textbf x$ and $\textbf y$ is $$\textit{MI}_C(\mathbf x, \mathbf y) = \frac{f_0 f'_0 + f_1 f'_1 + f_2 f'_2}{n n'} = \frac{3\times3 + 1\times2 + 1\times0}{5\times5} = \frac{11}{25} = 0.44.$$

In particular, note that the "plain" index of coincidence of a string of symbols, i.e. the probability that two symbols chosen at random from the same string are equal, is very close to the mutual index of coincidence of the string with itself.  The only difference is that the single-string definition assumes that the two symbols are always chosen from different positions in the string (i.e. that we never just pick the same position twice and compare the symbol there with itself), which requires a small correction.  That is to say, $$I_C(\mathbf x) = \frac{\sum_{i=0}^{25} f_i(f_i-1)}{n(n-1)} \ne \textit{MI}_C(\mathbf x, \mathbf x) = \frac{\sum_{i=0}^{25} f_i^2}{n^2},$$ but the difference between the two formulas approaches zero as the length $n$ of the string $\mathbf x$ increases (and, in practice, is small enough to get lost in random sampling noise anyway).

(Also worth noting is that there are some minor variations between authors in the definitions of both the single-string index of coincidence and the mutual version.  For example, Wikipedia — which currently doesn't mention the mutual index of coincidence at all — uses a definition of $I_C$ that differs from Stinson's by being multiplied by the alphabet size $c = 26$, ostensibly to make it more comparable between texts written in alphabets of different sizes.  In any case, such minor differences in definitions have no real effect on cryptanalysis.)

Anyway, what's this whole "mutual index of coincidence" good for, then?  Well, for one, given two strings sampled from the same plaintext source but encrypted with possibly different shift ciphers — such as two columns from a Vigenère ciphertext, after determining the key length $\ell$ and splitting the ciphertext into rows of $\ell$ characters — we can use it to determine whether or not the strings have been encrypted with the same shift amount.

By further shifting the characters in one of the strings by successive amounts, and finding the shift that maximizes the mutual index of coincidence, we can quite reliably determine the difference between the two key letters used to encrypt those columns.  In this way, once we've guessed one letter of a Vigenère key, we can statistically determine the rest of them, effectively reducing the Vigenère cipher to a simple monoalphabetic Caesar shift cipher.


Permutation of first $k$ prime powers as a one-way function?

As this stands this is a hard to evaluate and inefficient proposal.

Firstly key size is effectively  $\log n\!=O(n (\log n-1))$ but the largest value (attained for the identity permutation) is $\sum_{i\leq k} p_i^{p_i}$
which is larger than

$$(n \log n)^{n \log n}=O(e^{n (\log n)^2}).$$

You would need to look at reduction modulo so elarge integer to make it efficient.

While it may be that the type of diophantine equation that needs to be solvable (for prime arguments) for the original function to have collisions is unsolvable, such things are almost impossible to prove. I am not an expert but I know of no such results even for few terms.

And once you do a modular reduction, all bets are off.

Computationally, you probably cannot check much beyond the first 20 or so primes for no collisions.

One idea is to check the differences of the values the set of functions for a fixed $k$ give, since there are quadratically many differences,  they’d be more likely to repeat. If this happens this means that you might be able to find a modular reduction that will yield a collision.


Is there benefit to signing unencrypted emails?

Yes, of course there is a benefit to signing unencrypted emails. The article you cite is solely about the combination of signature and encryption; it doesn't directly say anything about signing unencrypted emails.

There is an important concern raised by the article which does apply to unencrypted emails, but that's because that concern applies equally whether the email is encrypted or not. The problem is that only the body of the email is signed. So when you receive a signed email (whether it's encrypted or not), you need to be careful not to implicitly assume anything about the context of the email. For example, when Alice signs “I love you” and sends it to Bob, Eve can forward the message to Charlie; Charlie will then see a signed message, guaranteed to have been written by Alice, and saying “I love you”. Charlie might assume that because he received the email, the “you” in the email is him; but this association is not warranted. All that Charlie can know is that Alice declared her love to someone, but not who that someone is. If Alice had wanted to send an unambiguous message, she should have signed “Dear Bob, I love you”.


How does the order of Q affect the time it takes to solve ECDLP?

Here is what I believe Sagemath is doing:

Given the problem of finding $x$ s.t. $xP = Q$, one step is computing $x' = x \bmod 5888291787538299579505114081452341011$; it does this by computing $P' = (2\cdot 3 \cdot 5)P$, and $Q' = (2 \cdot 3 \cdot 5)Q$, and trying to solve $x'P' = Q'$
As the order of $P'$ is circa $2^{122}$, we would normally expect this computation to take circa $2^{61}$ time (quite a while).  However, in this case, $Q'$ is the neutral element.  I suspect that Sagemath notices this, and so immediately concludes that $x' = 0$
Every other computation involved in Pohlig-Hellman is relatively quick, and so it reports the answer ($3 \cdot 5 \cdot 5888291787538299579505114081452341011$) quickly.

The summary is: if your implementation special cases this $Q' = 0$ case, then we can skip any prime that does not appear in the order of $Q$; the time taken by Polhig-Hellman is dominated by the largest prime that appears both in the order of $P$ and the order of $Q$.


How to account for moore's law in estimating time-to-crack?

Moore's law has several variants. Gordon Moore himself first put it as a double of transistor density every year (i.e. you could put twice as many transistors on a given wafer surface, and production cost increases linearly with the wafer surface). In 1975, Moore altered his law to a double every two years. However, putting more transistors in a given surface also entails making them smaller and closer to each other, and this allows for clocking them at higher rates, too. So the "classical" version of Moore's law is "double performance every 18 months".

Performance depends on the kind of task you are trying to perform. For a general purpose computer, having more transistors does not makes things really better beyond a given point -- if you want to add "real-life" values which fit in 32 bits, then having 64-bit registers will not give you a boost. At some point, "many transistors" turns into "several cores", which helps a lot if (and only if) the task at hand is amenable to parallelism.

For symmetric cryptography, we usually worry about exhaustive search. The cost-effective attacker will use FPGA or ASIC. Parallelism is a given, so the attacker benefits from advances in both transistor density and clock rates. However, for the truly massive attack jobs, energy consumption (and its offspring heat dissipation) becomes a bottleneck, and higher clock rates do not help for that. So you can consider Moore's law to amount to about "1 bit per year" (a 100-bit key is as robust now as a 120-bit key will be in 20 years).

For elliptic curves, the most efficient attack is discrete logarithm using the "generic" algorithms, which work in $O(\sqrt{N})$ for a curve of size $N$. This means that a 256-bit curve fares about as well as a 128-bit symmetric key. Moore's law, then, yields "2 bits per year" of computing power to the attacker.

For integer factorization and classical discrete logarithm (i.e. RSA, DSA, Diffie-Hellman, ElGamal... but not the EC variants thereof), things are more complex. The best known algorithms are subexponential (that's the General Number Field Sieve); but their implementation requires large amounts of fast RAM. RAM size increases with transistor density as per Moore's law, but RAM latency does not get better as fast as that. In fact, base RAM latency is more or less stalled in recent computers. Therefore, it is difficult to give even a rough estimate of Moore's law effect on RSA security.

To account for Moore's law, several individuals and organizations have published estimates of key strength, as "recommendations" for minimal key length, now and in the next few decades. These recommendations vary quite widely from each other; there is a nice summary (with online calculators) on this site. The recommendations always use worst case estimates: they do not want to predict the actual attack cost, they aim at presenting key sizes which are "large enough" to thwart attacks. Therefore, each figure is a mixture of attack cost estimates, and a more or less generous amount of paranoia. For instance, NIST recommends not using 1024-bit RSA keys since last year, and yet the current RSA-breaking record is 768 bits, are it is known right now (2012) that existing academic resources are far from being sufficient to attack a 1024-bit RSA key.

As a very crude but effective estimate: 112-bit symmetric keys, 224-bit elliptic curves, and 2048-bit RSA/DSA/DH keys, ought to be enough for the next two decades (at least).


Is streaming API to ChaCha20-Poly1305 possible or recommended against?

This is not specific to this construction, but generally, you want to split the stream in smaller chunks, that are individually encrypted and authenticated.

If the encrypted stream doesn't have a valid authentication tag, this is not something you want to discover at the very end, after having decrypted terabytes of data.

Some precautions have to be taken when splitting a stream into chunks. Namely, you need to make sure that chunks haven't been reordered, removed, duplicated and you need a way to verify that the last chunk you read was meant to be the end of the stream.

The encrypting a sequence or a set of dependent messages page in the libsodium documentation provides some guidance for this, as well as a streaming API using Chacha20-Poly1305.


Why we cannot brute force Elliptic Curve private key?

The creator of the key pair can do it efficiently because he has to calculate $kG$ for only one value of $k$. The cost would be something like $\log(k)$ elliptic curve operations. It's very small.

What you propose is to compute $1G$, $2G$, until you reach $kG$. Since $k$ is a big number (something like $2^{256}$, it is very big), then you have to do $2^{256}$ times more operations than the creator. It is very big.


Adversary for attack on one variant of ElGamal

How should attacker choose $m_1$ to be able to calculate advantage of adversary exactly?

Well, for $p$ prime, then precisely $q$ of the values in $(1, p-1)$ will be Quadratic Residues and the precisely $q$ will not be; furthermore, there is one value ($0$) that resides outside the group (and hence is also an impossible value for $h^r$).  Hence, if he chooses $m_1$ uniformly from the range $(0, p-1)$ (and independently of the value $r$ the encryptor selects), then $h^r + m_1$ will be a random value uniformly from the range $(0, p-1)$, and hence will be either a quadratic nonresidue or 0 with probability $(q+1)/p > 0.5$.
You should be able to precisely compute the advantage from that.


Understanding how padding works when using Block Cipher

The padding scheme being used in your example for the block cipher is PKCS#7 Padding.

This scheme specifies that:

  The value of each added byte is the number of bytes that are added, i.e. N bytes, each of value N are added.

The thing is, if the plaintext is multiple of the block size, then a whole new padding block is added. In this case it will be a block of 16 bytes with value 16.

   This is necessary so the deciphering algorithm can determine with certainty whether the last byte of the last block is a pad byte indicating the number of padding bytes added or part of the plaintext message.

That's why your ciphertext has a size of 48 bytes when the plaintext is 32 bytes. That is one ciphertext byte for each plaintext plus a whole new block of padding


Restricting output of key derivation function

Modern cryptography operates mostly on binary values or big numbers. And generally cryptography that operates on numbers encodes / decodes those numbers to binary as well (RSA PKCS#1 specifies binary representations for the public key, private key and of course the ciphertext and signatures). If an API specifies text input / output it is generally provided as a convenience to the programmer rather than that it is part of the implemented algorithm specification.

To have printable ASCII it is easiest to convert the binary value generated by your KDF to base64 or base64url. In that case each character encodes 6 bits. It should be easy to calculate the output size of the KDF to give the precise amount of base 64 characters. Otherwise you could still cut of the left over base 64 characters, but remember that base 64 implementations may require you to input 4 characters at a time (including padding characters) making it impossible to decode your pruned base 64 encoding directly. It would make sense to use a multiple of 3 for the output of the KDF / multiple of 4 characters after encoding using base 64.

To have base 62 (as specified in your question) is much harder, as 62 is not a power of two. That means that you either need to perform base conversion using big integer calculations (divide-and-remainder) or you'll have to convert to base64 and escape out three characters (the +, the / and the escape character itself). Escaping will result in a variable length encoding though, maxing out on doubling the base64 string in size.

Notes:

Hexadecimals is even easier to work with: it takes 2 characters per byte, and that's it. It will expand the output some more, but that may be worth it for the convenience it offers;
Encoding keying material in a textual string is generally frowned upon. Strings are easy to find in application code and are generally hard to destroy (e.g. Java has immutable strings that may not be garbage collected either).


Yes, cryptosystems like ElGamal or Shnorr based on the intractability
of Dlog Problem are are indicated to be implemented on finite field,
which is not the case of the RSA for which a model was proposed in the
early $80^{ies}$, and immediatly broken. As you know, a finite field is denoted by $GF(q)$ where $q=p^m$ and p would be any Prime. But in the case there is no special advantage to use such q with $p\neq 2$, because the arithmetic on this field is a bit more complicated, and each party would beforehand agree on using the same irreducible polynomial for building the corresponding splitting field.

However, other applications could use these fields for specific attacks, as the MOV attack which was introduced to reduce the Dlog Problem on supersingular curves.


How to find irreducible polynomial for Barreto-Naehrig curves?

I am using  Pari/GP as a calculator.   In order to keep the presentation small, I will not use the $p$ you mentioned, but a toy value $p=31$, which fulfils all requirements from the paper.

First lets define p:

p= 31

Then we have to define the finite field $GF(p^2)$ via the defining (irreducible) polynomial $y^2- \beta$, i.e. $y^2+2$:

GFp2 = Mod (y^2+2, p)

Now we define $\xi$:

xi = -1 - y

( Please note that  $\sqrt \beta = y$ by the defining polynomial of $GF(p^2)$ )

Now let Pari check that $x^6- \xi$ is irreducible in $GF(p^2)$:

lift(factorff (x^6-xi, p, GFp2))

Pari responds as

[Mod(1, 31)*x^6 + (Mod(1, 31)*y + Mod(1, 31)) 1]

This says that the polynomial is irreducible.

(The "lift" call is only used to make the output more readable )

As a final test, show that $x^6 - \xi^2$ factors:

lift(factorff (x^6-(xi*xi), p, GFp2))

Pari responds as:

[  Mod(1, 31)*x^3 + (Mod(1, 31)*y + Mod(1, 31)) 1]

[Mod(1, 31)*x^3 + (Mod(30, 31)*y + Mod(30, 31)) 1]

Mathematically, this means:
$$x^6- \xi^2 = (x^3+ \sqrt \beta+1)(x^3-\sqrt\beta-1)$$


How many recursive md5 hashes are needed to always get same string

After about $2^{n/2}=2^{64}$ iterations an input will enter a cycle (of length approximately $2^{n/2}=2^{64}$). If inputs didn't collide by the time they enter a cycle, they never will.

If you have more than about $2^{n/4}=2^{32}$ inputs, you'll get collisions after $2^{n/2}=2^{64}$ iterations, as per birthday-problem. But of course you won't have the patience to wait that long.


In Fortuna, can I use ChaCha20 instead of a block cipher and Blake2b instead of iterated SHA256?

TL;DR: Fortuna is a CSPRNG so you can replace components pretty arbitrarily, because you're not bound by compatibility requirements and the modifications should work, although there are some points that are note-worthy.

In Fortuna (PDF), AES-256 is used in exactly one place: To generate the keystream based on the current counter (the function is even called GenerateBlocks())

However, there's one potentially difficult thing with the way AES-CTR is used by Fortuna: Counters aren't reset upon re-key. So if Fortuna re-keys, it generates two blocks of key material and uses them as the new keys, but the counter used for this just gets incremented by 1 again and continued to be used.

This can be overcome by appropriately using the seeking mechanism of ChaCha.

In the end, AES-CTR in Fortuna fulfills the role of a pseudo random generator and thus is arbitrarily exchangeable by any other PRG, which includes block ciphers in CTR mode and of course also ChaCha. Whether using a different cipher will actually increase security depends on the amount of cryptanalysis on the new cipher, as 256-bit AES is already physically unbreakable for humans.

SHA-256d is used in two places in Fortuna: As a KDF to derive the new key from the old key and a given random string and separately as standard hash function to collect the pool entropy.

For both usages, a replacement of SHA-256(d) by Blake-2b is functionally equivalent, even though one may want to consider using Blake-2b in MAC mode (for the KDF part) or with some (distinct) personalization string for both operations.


The first line in the quote now in the question defines a function $f$ of variable $n$. The last line is about how fast (the output of) that function grows when $n$ grows towards $+\infty$.
Both statements $f(n) = Ω(n^3 \log n)$ and $f(n) = ω(n^3 \log n)$ are about how fast $f(n)$ grows relative the function $g$ defined by $g(n)=n^3\log n$. The first statement roughly tells that $f(n)$ grows no slower than $g(n)$, while the second tells that $f(n)$ grows faster. Both statement are true, and easily shown so when we look at the definition of $f$ and $g$.
Update following comment:

The statement is strictly about the value taken by $f(n)$, not about the difficulty or cost to compute $f$. What that value represents is not stated by the notation. It's state by what defines what $f$ represents. That could be time, or effort, or memory, or the value of an integer, like an RSA public modulus; we can't tell.
"grows faster" is not really the same as "greater". Sorry, to be precise, we need the mathematical definition.

That's using a so-called (Bachmann-)Landau notation, which makes an unusual use of the $=$ sign: equality usually features transitivity. It takes some time to get used to it.
Anything more specific won't meet the "high level explanation" requirement in the question. But if we read a few lines above the question's quote in the book, or about (Bachmann-)Landau notation, the definitions are given.
It can be shown $f(n) = ω(g(n))\;\implies\;f(n) = Ω(g(n))$. That's why the sentence has $\text{in fact}$, often used to introduce a stronger or more precise statement, like: That's good. In fact, it's delicious.


No, not all encryption tools are made equal.

Even when using the same cryptosystem, say AES-256, a tool's choice of cipher mode, how to generate AAD if present, how to generate IV, how to generate key, and the quality of the random source all affect quality.  The quality of cryptography engineering is the major deciding factor at that point and it is tricky to get right.

To determine if you should use VeraCrypt or let Comodo Backup do the encryption you need to assess the effectiveness of their cryptography engineering.

The simplicity of using the built-in encryption supplied by Comodo Backup is a significant convenience advantage.  If their crypto eng is up to scratch I'd make that your choice.


Why does only length prepending improve the security of CBC-MAC

Well, let's try it, and see how hard it is to forge a message.

Let's say for illustrative purposes that each character is a block, and that numbers represent the length indicator section.  And let's start by putting the length indicator at the end.  So,

XXXXXXX7

represents a 7-block message, with the '7' indicator at the end.  Let's also say that,

$_{MAC}($XXXXXXX7$) = M_0$

represents the MACing of that 7-block message, with the resulting Tag $M_0$.

How hard is it to forge?  It is trivially easy.  All you need to do is request the MAC of three messages like so:

1) $_{MAC}($AAAAA5BBB9$) = M_1$

Note the '5' in the middle of the message.  For this first MAC, that is just part of the requested message -- only the '9' at the end has been added by the length-appending algorithm to indicate the total length of the message.

2) $_{MAC}($AAAAA5$) = M_2$

3) $_{MAC}($CCCCC5$) = M_3$

Then xor $M_2$ and $M_3$:

$M_2 \oplus M_3 = D$

And let $ E = B \oplus D$, and now you can trivially forge the Tag for a new message that you did not request from the MAC Oracle:

$_{MAC}($CCCCC5EBB9$) = M_1$

Note that the same logic applies if the length indicator is anywhere in the message except right at the beginning.


collision resistance of a composed hash function

Counterexample [from poncho in comments]: let $H_0\colon \{0,1\}^* \to \{0,1\}^{256}$; then $H(x) := p \cdot H_0(x)$, where $H_0(x)$ is interpreted as an integer in little-endian, is obviously collision-resistant but $H'(x) := \sum H(\cdots) \bmod p$ is identically zero and therefore very much not collision-resistant no matter what goes in the ellipsis.


Public-key cryptosystems without poly-time quantum attacks

McEliece

NTRU

Multivariate

If you mean "syntactically public key" instead of "implies the existence of secure key agreement",

then there is also hash-based signatures.


Can Shannon's entropy be used to determine if a file is encrypted?

You are likely going to have both false positives and false negatives if you try to use Shannon entropy for this.

Many compressed files would have close to 8 bits of entropy per byte, resulting in false positives.
Any encrypted file that has some non-binary encoding (like a file containing an ASCII-armored PGP message, or just a low entropy header) could have a lower entropy, resulting in false negatives.
If Format Preserving Encryption is used , this might result in false negatives too

It may work as a heuristic, but you should not rely on the results being correct.


Can I use a fixed IV with AES-GCM if I only encrypt unique plaintext values?

No, when an IV is repeated as in $C_1 = \textsf{GCM}(K,IV,M_1)$ and $C_2 = \textsf{GCM}(K,IV,M_2)$, the resulting ciphertexts leak $M_1 \oplus M_2$ to an eavesdropper. This is because GCM is based on CTR mode which has this property.

Authenticity also completely breaks in this scenario, although it's not a one-liner explanation.  An attacker who sees $M_1, M_2, C_1, C_2$ can forge arbitrary ciphertexts.


PBKDF1 as specified in PKCS#5 and RFC 2898 provides Key Derivation and Key Strengthening. The parameters of the function are a hash function (such as SHA-1), a password, a salt (sometimes called nonce, depending on context), an iteration count and the length of the derived key to be returned. The standard PBKDF1 will just calculate the hash of password concatenated with salt, and then hash the hash value that is returned by the previous step iteration count minus one times:

$$ K = H(H(...H(P||S)...))$$

If you only need key derivation but not key strengthening, use an iteration count of one. The purpose of the key strengthening is to increase the complexity of the key derivation, making certain attacks that exploit weak passwords more time consuming.

There are related key derivation functions that also provide Key Stretching, such as PBKDF2 and the .NET PasswordDeriveBytes function. Key Stretching is a feature that allows derived keys of any length to be returned, instead of being limited by the output length of the hash function.


Largest message size for XChaCha20-Poly1305

You should email the libsodium maintainers and the internet-draft author and ask them to talk to each other to work out what they mean, and to clearly document the limits in the internet-draft.  (They sometimes post here but not often.)

In principle, XChaCha provides $2^{256}$ 512-bit blocks of output under a single key, indexed by a 256-bit input.  The only question is how they are carved up for messages vs. blocks within a message.

For the XSalsa20 stream cipher, the message number is 192 bits, and the block number is the remaining 64 bits, so the theoretical limit on the number of blocks per message is $2^{64}$, or $2^{70}$ bytes.
For the Salsa20 stream cipher as in eSTREAM and as in NaCl, and for the related ChaCha stream cipher, the message number is 64 bits and the block number is the remaining 64 bits, so again the limit on blocks per message is $2^{64}$.
For the IETF ChaCha stream cipher of RFC 7539, the message number is 96 bits and the block number is 32 bits, so messages are limited to 256 GB.
The current XChaCha-Poly1305 internet-draft, draft-arciszewski-xchacha-03, is defined in terms of the IETF ChaCha-Poly1305 AEAD of RFC 7539 as a subroutine, in §2, p. 3, but it follows the XSalsa20 API, so the message number—which is a parameter to the API—is 192 bits, but the block number—which is managed internally by the API—is 32 bits; the remaining 32 bits of the internal ChaCha input are fixed to zero.
In what libsodium seems to implement for crypto_aead_xchacha20poly1305_ietf, according to the XChaCha20-Poly1305 construction page (archived 2019-05-30) and the AEAD limitations table (archived 2018-11-07), the message number is 192 bits and the block number is 64 bits, like XSalsa20.

If the byte order of the block number is chosen appropriately, this should be compatible with draft-arciszewski-xchacha-03 in the sense that it can correctly implement any protocol following the internet-draft, but it also allows much larger messages that are not allowed by the internet-draft.
It is also possible that the block number encoding is mismatched so that libsodium's crypto_aead_xchacha20poly1305_ietf is incompatible with draft-arciszewski-xchacha-03—I haven't checked.

All that said, the distinction between a 32-bit block number and a 64-bit block number is essentially academic: the largest message any implementation is willing to receive is the largest amount of memory that an adversary waste in a denial of service before you can drop the message on the floor.  It is hard to imagine applications for which this amount should reasonably be beyond a few megabytes, let alone 256 GB—larger messages can simply be broken up into smaller pieces at negligible additional cost since the per-piece overhead is at most a few dozen bytes, even if you include the 192-bit nonce and some formatting metadata.


No, these sorts of attacks are not of any use against RSA -- they are much harder to perform than other existing attacks (and in particular, attacks that factor an RSA modulus).

Here is how this precomputation attack works; you assume that someone generating the keys will always MAC (or sign) a specific message:

$$S_i = MAC_{K_i}( FixedMessage )$$

And so you treat this as a fixed function of key $K_i$ to tag $S_i$.

The legitimate key generator creates a long series of keys $K_1, K_2, ..., K_a$, and corresponding tags $S_1, S_2, ..., S_a$

The attacker generates a long series of random keys $K'_1, K'_2, ..., K'_b$, and corresponding tags $S'_1, S'_2, ..., S'_b$

Now, let us call the key space of the MAC in question $n$ bits.  If $a \times b \approx 2^n$, then there is a decent chance that one of the keys $K'_j$ will happen to be the same as one of the legitimate keys $K_i$, and this will be detectable because $S_i = S'_j$; this can be detected by (say) a rainbow table lookup.  Because of this, the attacker learns $K_i$.

With $n = 128$, e.g. AES-CMAC with 128 bit keys, this is just on the border of plausibility; if the legitimate generator creates $2^{50}$ keys (which is a huge, but not inherently implausible number), then the attacker would need to generate about $2^{78}$ keys; a huge but not inherently implausible number (and will perhaps be a bit more likely after a few more years of Moore's Law).

All that said, let us take a look at this attack in terms of RSA.  With RSA, we have much larger keys.  Currently, any key much smaller than 1k can be factored, so let us take a look at how this would apply to a set of 1k RSA keys.  An RSA modulus is a product of two primes; there are a bit over $2^{500}$ 512 bit primes, and so there are approximately $2^{1000}$ RSA modulii that are 1024 bits long.

Now, if we assume that our legitimate generator creates $2^{50}$ keys, that means that we'd need to create about $2^{950}$ keys to have a decent chance of creating a collision -- that amount of work is completely and utterly implausble.  In addition, if we were able to assemble anywhere close to that amount of computational power, factoring a 1k RSA key would be trivial.  Hence, factoring one of the RSA modulii would be far easier than the collision method.

So, why does the collision method have such a hard time with RSA?  Well, RSA keys need to be as big as they are to address attack methods that use the inherent mathematical structure within RSA.  This collision method ignores this mathematical structure, and by ignoring this structure, doesn't work nearly as well.


ElGamal and Paillier key sizes for short messages

You should not use keys smaller than 1024, and even 1024 is considered too small today. However, if you want additive homomorphism, then you can you encrypt with "ElGamal in the exponent" over Elliptic curves. To explain what I mean by this, let $G$ be the base point (generator) for the Elliptic curve group, let $x$ be the ElGamal private key, and let $P=x\cdot G$ be the ElGamal public key. Then, you can encrypt a value $m$ by computing $(r\cdot G,r\cdot P + m \cdot G)$, where $r$ is random.

Note that given $(U_1,V_1) = (r\cdot G, r\cdot P + a \cdot G)$ and $(U_2,V_2)=(s\cdot G, s\cdot P + b\cdot G)$, it follows that $(U_1+U_2,V_1+V_2) = ((r+s)\cdot G,(r+s)\cdot P + (a+b)\cdot G)$. Thus, this is additively homomorphic.

The only problem with this scheme is that you cannot efficiently decrypt, since this requires solving the DLOG problem over Elliptic curves. However, if you are only encrypting 4 byte integers, then you can brute force decryption using the private key as follows: given $(U,V)$, for every $a$ check if $V=x\cdot U + a\cdot G$. If yes, then you know that this is an encryption of $a$. Now, this will take $2^{32}$ time which is too long. However, you can use this idea and run a generic DLOG algorithm that takes square-root time (e.g., Pollard's rho algorithm) to do this in time $2^{16}$. It is still expensive, but may be OK for your application (depending on what you want to do).

Using Elliptic curves, the size of your ciphertext can be significantly reduced. E.g., with curve P256, you can hold a ciphertext in just over 512 bits.


This is homework, and so I won't give you the answer outright; I will give hints:

Hint 1: how could you efficiently generate a random pair $x_1, y_1$ with $x_1^e = y_1$, without resorting to the Oracle?

Hint 2: how could you use the above observation to accelerate your algorithm?


Is it safe to prefix the a key with a known value?

Generally, the actual key for most cryptographic algorithms is a fixed length bitstring (or something more complicated, like a tuple of appropriately chosen large numbers).  Thus, if you just take a valid key and add a prefix to it, it will no longer be a valid key at all.

(There are a few notable exceptions, such as HMAC, which can use any octet string as a key.  But those are definitely the exceptions to the norm.)

So what if your un-prefixed key was shorter than the algorithm needs (but still long enough to resist brute force guessing), and you choose the prefix so that it pads the key to the needed length?  Well, clearly you could do that, but depending on the specific algorithm you're using, it might not be a good idea, for several reasons:

Even if the algorithm is specified to just take a bitstring of a certain length as its key, that doesn't necessarily mean that every part of the key contributes equally to the security of the algorithm.  For example, some authenticated encryption schemes (such as, notably, SIV) take a key which is split into two halves, one of which is used to authenticate the message, and the other to encrypt it.

Thus, for instance, SIV-AES-128 takes a 256-bit key; if you were to construct one by padding a 128-bit key with a known 128-bit suffix, your messages would be perfectly well authenticated, but totally trivial to decrypt.  (Using a known prefix would compromise the authentication part instead, but due to details of the SIV design, that seems a bit trickier to exploit.  At least it would make it trivial for an attacker to verify if they guessed the plaintext of a message correctly.)
Even if all the key bits are supposed to contribute equally to the security of the algorithm, that's not guaranteed to hold in practice.  Many otherwise secure and well-regarded ciphers can be vulnerable to related-key attacks (including AES, although the published attacks against it are, so far, mostly of academic relevance).  Such attacks are outside the scope of many commonly used security definitions, and thus may receive less cryptanalytic attention than usual.

Instead, the proper way to expand a too short (or otherwise unsuitably formatted) secret value into a proper-sized key is to run it through a key-derivation function.  There are plenty such functions to choose from, but (for applications that do not require key stretching) I personally rather like HKDF (RFC 5896) for its flexibility.


How many encryptions are needed before OpenPGP key privacy is violated?

I'll leave alone the OpenPGP spec, and consider the problem of identifying among $k$ public keys $(n_i,e_i)$ the RSA public key $(n_j,e_j)$ used to encrypt $m$ messages per RSA with proper encryption padding. The only way is by examining the $m$ cryptograms $c_\ell$, which essentially are indistinguishable from uniformly random in $[0,n_j)$ (I assume the $c_\ell$ are computed with no countermeasure to foil identification attempts, except in last section).
An identification algorithm can use two facts:

If $n_i\le\max c_\ell$ , that rules out $i=j$.
The mean $x=\frac1m\sum c_\ell$ , which the attacker should compute, has Bates distribution, with mean $(n_j-1)/2$, standard deviation $(n_j-1)/\sqrt{12m}$. That distribution quickly becomes close to normal when $m$ increases, and the 68-95-99.7% rule quickly becomes applicable.

I think the optimum attacker's strategy in practice is to pick $j$ as $i$ with $n_i/2$ closest to $x$ among the $n_i$ surviving test 1. It's possible to estimate the confidence in a guess by computing $t_i=\lvert n_i/2-x\rvert\sqrt{12m}/n_i$ for the values of $i$ with $n_i/2$ the closest to $x$: the higher $t_i$, the less likely $i$ is (ignoring information obtained from other $n_i$): $t_i>1$ with 32% probability, $t_i>2$ with 5% probability, $t_i>3$ with 0.3% probability.

To go deeper in the analysis, we need an idea of the distribution of the $n_i$.
By making the say 256 high-order bits of the $n_i$ equal at generation time (fixed to some haphazard constant), which is easy and does not harm RSA security or interoperability, we could make identification hopeless.
For a common generation method with the prime factors $p_i$ and $q_i$ of $n_i$ independent and roughly uniform in $[2^{(b-1)/2},2^{b/2}]$ where $b$ is the bit size of $n_i$ (e.g. $b=3072$), I think an attacker would need $m$ in the order of a few times $k^2$ for a good success rate, and significantly more to conclude with good success rate and confidence for most users. Keys with the highest $n_j$ tend to be easier to guess correctly, because rule 1 prunes best, and there tends to be less other keys with nearby $n_i$. The second effect also makes keys with the lowest $n_j$ easier to guess than those in the center of the pack: those with the high byte in [0xB0,0xC1] (for $b$ multiple of 8) tend to be the most resistant to guessing, while giving no strong sign they have been chosen for this purpose.
All this is amenable to simulation and detailed analysis. I called for help. In the desert so far.
Update: this comment by Squeamish Ossifrage points a relevant paper: Jean Paul Degabriele, Victoria Fehr, Marc Fischlin, Tommaso Gagliardoni, Felix Günther, Giorgia Azzurra Marson, Arno Mittelbach and Kenneth G. Paterson: Unpicking PLAID - A Cryptographic Analysis of an ISO-standards-track Authentication Protocol, in proceedings of SSR 2014. Start with section 3.1 Tracing Cards via Shill-Key Ciphertexts.

I'm told a simple and clearly correct countermeasure to foul identification attempts even if we don't want to change pre-existing $n_i$ of the same bit size $b$: pick the first RSA cryptogram below $2^{b-1}$. Adversaries will be facing a uniformly random integer in $[0,2^{b-1})$.


Does size matter in case of attack on LUKS partition?

No, the size does not matter. No matter which algorithm you use, the attack with the best chance of success is to guess the passphrase, unless the passphrase is a long, random, unmemorizable one (i.e. a keyfile in practice).

Attacks against the passphrase are not helped by a larger amount of ciphertext. They work by generating the key corresponding to the passphrase, and then attempting to decrypt with the resulting key. A few bytes of ciphertext are enough to validate the guess.

If the algorithm is the limiting factor, then finding the 128-bit key using the fastest known techniques requires very close to $2^127$ attempts on average ($127$ and not $128$ because on average the key is found after exploring half the search space). Knowing a lot of plaintext-ciphertext pairs does not help to find the key or to decrypt other ciphertexts: cryptographic algorithms are designed to resist such attacks.


Question about using Montgomery form for elliptic curve operations on bls12-381

I figured this out, the best approach is to use either Montgomery or Barrets algorithm for modulo reduction, Barrets requires a slightly higher bit multiplication but not pre-transformation, while Montgomery has a pre-transformation but multiplications are slightly faster.

And if you use Montgomery you can do the entire point double/add in Montgomery form using jacobian coordinates and just convert back at the end.


After Google's breakthrough: When will quantum computers break today's encryption?

Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto algorithms used today and whether this breakthrough has significantly changed the predictions.

No, despite being on the front page of Nature, Google's result has no impact on cryptography for the foreseeable future.

The news about the (rather regrettable) term ‘quantum supremacy’ means that Google claims to have demonstrated ‘solving’ some problem on a quantum computer faster than anyone has been able to solve that problem on a classical computer.  In one sense, this is a remarkable achievement, because nobody had been able to do it before.  In another sense, it is the tiniest achievement imaginable: after decades of research, they found a problem, among all possible computational problems one might imagine whether or not solving it has any utility whatsoever, that they were able to demonstrate a quantum computer is better at than a classical computer.  (Maybe ‘quantum non-uselessness’ would be a better term than ‘quantum supremacy’, or perhaps ‘quantum non-futility’ since the problem they found is not terribly useful itself.)

The ‘problem’, in this case, is, given a random quantum circuit of about 50 qubits chosen by a challenger, to apply it on an all-zero initial state, and measure the result in the $\{0,1\}$ basis.  A choice of quantum circuit gives rise to a probability distribution on the outputs of this procedure—run the circuit on all zero inputs, measure the result in the $\{0,1\}$ basis—and nobody has shown a way to sample from this distribution as efficiently on a classical computer.  The results are then verified by statistical tests computed using classical simulation with about $2^{50}$ computations (which puts a bit of a damper on the prospect of verifying results like these on, say, 100-qubit circuits).

What Google has not demonstrated is anything that is useful for running quantum circuits like Grover's algorithm or Shor's algorithm, which requires substantially larger numbers of qubits and error correction at a scale we're nowhere near.  For more details, see Scott Aaronson's Supreme Quantum Supremacy FAQ.

To the best of my knowledge, no quantum computer has ever factored a number larger than 21 using Shor's algorithm, and there's no reason to suspect that other quantum factoring methods will meaningfully scale; see fgrieu's past answer on quantum factoring records (which I hope he will keep updated if the literature changes so I don't have to!).  Scott Aaronson estimates that if configured to run Shor's algorithm, Google's quantum computer could maybe manage factoring a number ‘up to the hundreds, depending on how much precompilation and other classical trickery was allowed’

  Also, when will good post-quantum crypto libraries be available so that programmers can slowly begin replacing currently used crypto with post-quantum cryptography or go with a hybrid solution?

Symmetric-key cryptography is not seriously threatened by quantum computers as long as you already meet a classical 128-bit security level by using ≫128-bit keys like 256-bit keys, which you're already doing, right?

There is an ongoing competition, NIST PQC, to settle on candidates for standardization of post-quantum public-key cryptography—encryption, key agreement, and signatures.  Aside from the NIST PQC candidates' reference implementations, available via the NIST PQC web site and in SUPERCOP, there are also some prototype libraries of post-quantum cryptography candidates, such as liboqs (open quantum safe), and experiments in deployment in protocols such as SSH and TLS.


I am not too familiar with this paper, but there is (at least) the following reason. They define $\Delta = l!$, then require (right after equation 6) that $1 = \mathsf{gcd}(e', e) = \mathsf{gcd}(4\Delta^2, e) = \mathsf{gcd}(4(l!)^2, e)$.
This is not possible if $e \leq l$ (as then the GCD is $e\neq 1$).


Given hash(x) and y, can I verify z = hash(x + y)?

The technical term for what you're looking for is "publicly verifiable proof of retrievability". Here is a question on crypto.SE that discusses existing implementations of PoRs.


Discrete log analog of ECM factoring algorithm?

Similar algorithms for factoring and discrete log are limited to pollard rho and sieve methods using a factor base. There are other factoring methods such as square forms, p+1 and ECM which as far as I know don't have logarithm-in-$F_p$-finding analogues. The factoring methods rely (explicitly for rho and implicitly for sieve methods) on treating a ring like a field, trying to measure the order of elements and waiting for the process to break down. Calculating a discrete log is a very similar process but it works correctly.
The other way to answer your question is yes there is a logarithm-finding analogue of ECM but it finds elliptic-curve logarithms. Similarly,the logarithm-finding analogue of Williams' p+1 method finds logarithms in a quadratic field. Not what you had in mind I guess.


MD5, like most cryptographical algorithms, takes inputs which are strings of bytes (actually, bits, however we rarely need to hash an arbitrary bitstring).  So, yes, to hash a string with MD5, you need to convert that string into a series of bytes somehow.

As for how you do that, well, for a string like 'amrasobalatel', the most common transform is to take the ASCII encoding of that string; however there's no reason you couldn't use UTF-16 or EBCDIC...


Could 64 bits be used instead?

Yes, but it reduces the security.

Assuming that the message length is $L$ blocks, then given a valid message, tag pair, the attacker can generate a second message/tag pair that would authenticate with probability $L/q$ (assuming, of course, that $L \le q$).  By reducing the value of $q$, you're increasing the probability that the attacker would succeed.

Now, you could run it several times in parallel (using distinct random values for $k_1, k_2$ for each instance; lets example how it works.

For example, if you use a single 128 bit $q$, and your message length is $\ell$ bytes (and hence we have $L = \ell/16$), that means that the attacker can succeed with probability $2^{-132} \ell$.

In contrast, if you have a 64 bit $q$, and run it twice in parallel, and your message length is $\ell$ bytes (and so $L = \ell/8$), this means that the attacker can succeed with probability $2^{-134} \ell^2$ (note, this is always larger, even with the smaller constant factor, as we assumed that $\ell$ is a multiple number of blocks, and so $\ell \ge 16$).

Because the second case reduced security as a square of the message length, it degrades significantly faster if long messages were possible.  Whether it degrades too fast would depend on a) how much forgery probability is tolerable, and b) how long your messages are anyways.

  Can this be scaled even further downwards to 32, 16, … bits? (block size and $q$)

Yes, but you run into even faster degradation based on message length.