Attack for RSA 1024 bit with Low Public Exponent

The original poster clarified that:

the application of RSA is signature (not encryption as originally stated);
at least one signature $s$, the value of $N$, and $e=3$ are given;
the signature is by signing an MD5 hash of a message, and a hash of the message matching the signature $s$ is also a given.

The first, low-effort thing to do with the givens is computing $r=s^e\bmod N$, which in most RSA signature schemes is the so-called message representative (single practical exception: in some schemes including some in ISO/IEC 9796:1991, ISO/IEC 9796-2, ISO/IEC 14888-2, the message representative could also be $N-r$).

The message representative $r$ that we now have was determined by the signer from the MD5 hash (that we know) of some message, using some in principle public process that we are not given. That process usually involves padding on the left or/and right with repetitive constant bytes, or randomness; perhaps hashing; and in modern schemes XORing some portions with the result of some public mask generating function of some other section of the message representative. Many paddings found in practice are easily recognizable by some prescribed constant byte at some prescribed location; all are bound to be unambiguously detectable if one has the specification and parameters necessary to check a signature.

Doing the above, the original poster reported that $r$ is exactly the hash (the tool computing $r=s^e\bmod N$ has output the 16-byte hash with a 00 on the left, perhaps because the hash starts with the byte B5 and that's in the range 80..FF of negative byte values for two's complement).

So we conclusively know that there is no padding; in other words, it is used textbook RSA signature, or equivalently the padding type 00 of section 8.1 of PKCS#1 Version 1.5 of 1993, also RFC2313 of 1998 (I find it unjustifiable that this non-padding is in these documents with so little warning).

We know the padding, and it is so lacking that we know the signature matching many hash values: for example the all-zero bitstring of 1024-bit ($s=0$) is the signature of the hash consisting of the all-zero 128-bit bitstring ($r=0=s^e$); the bitstring with only the $k^{th}$ bit set ($s=2^k$) and $k\le42=\lfloor{128\over e}\rfloor$ is the signature of the hash with only the $3k^{th}$ bit set ($r=2^{3k}=s^e$); more generally we know the signature for any hash which value is a cube in $\mathbb N$. However that is not solving the concrete problem of forging a message passing a signature check of its MD5 hash, thus does not answer the question. We have several options to proceed towards that goal:

Trying to find $d$ (or more precisely, one of several working private exponents $d$), which would trivially allow to sign any message. In RSA, example cryptograms (if valid) are of no help towards that (we do not know how to prove it, but if such a mean was found after 38 years of public research, it would make the headlines). The only practical way we could find such $d$ is by factoring $N$. Factoring a properly generated 1024-bit RSA modulus is currently well beyond the possibility of anything but deep-pocketed organizations like the NSA, which would not claim that capability if they had it (a plausible but unproven conjecture). Thus if we try factoring $N$, it will only succeed if $N$ was poorly chosen. If the teacher mentioned some factoring method (like Fermat's, or Pollard's $p-1$), it might be worth trying that.
Trying to find a message that matches the existing signature. That's a preimage attack on MD5 (first preimage since we do not have a message), and although the collision-resistance of MD5 is now broken, its preimage resistance stands valiantly; so that won't work. We are not in a position to obtain the signature of a chosen message, thus we can't make use of MD5 collisions.
Trying to find a message and a new matching signature going with that. If we had many signatures, that would be feasible by a transposition to signature of the attack on textbook RSA encryption of Y. Desmedt and  A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (in proceedings of Crypto 1985). It is re-explained in the context of signature by Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann in section 3 of Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (extended abstract in proceedings of Crypto 2009). But unless we have many valid signatures, that can't work.
[Late addition, independently found by Poncho] Another method to try to find a message and a new matching signature going with that, but without requiring extra valid signature, would be hashing messages with a random ending until their hash happens to be a cube (it is then trivial to find their signature). This is expected to require about $2^{{e-1\over e}128}=2^{85.3\dots}$ hashes, which would require the resources devoted to bitcoin mining in like a year (and can't be done with exactly that hardware: it seems to consist of ASICs hard-wired for SHA-256 rather than MD5, and no way to stop hashing on cubeness, or likelihood of that).
[Credit goes to Poncho in this comment] Trying to find a message and some value that the verifier will accept as a valid signature, even though it is not the normal signature. That might be possible in particular if the verifier checks a signature $s$ by computing $s^e\bmod N$ and checking that the rightmost 16 bytes match the MD5 hash of the alleged message $M$, but fails to fully check the rest of the padding (something similar was a formerly common goof).
Assuming checks are made on at most the $w\le\lfloor{\log_2(N)\over e}\rfloor$ rightmost bits of $s^e\bmod N$ (here $w$ can be up to $341$, much more than the hash width), we can pick messages $M$ (e.g. at random within messages that it is useful to get signed) until $r=\operatorname{MD5}(M)$ is odd (or more generally $r=u\cdot2^{e\cdot v}$ with odd $u$, which gives a little extra freedom in the choice of $M$); and then find a $w$-bit number $s$ with $s^e\equiv r\pmod{2^w}$, which will exist. $s$ can be found in $w$ steps each finding an additional bit for $s$ starting from the right, with $s^e\equiv r\pmod{2^k}$ for $k$ increasing from $0$.
Then $s$ (zero-padded on the left to the width of a signature) will be accepted as a signature for message $M$ !! Notice that $s^e<N$, thus $(s^e\bmod N)=s^e$, and we know that the rightmost $w$ bits of $s^e$ (which we assumed are the only ones checked) match the true message representative $r$ for our message $M$. We don't need any signature to carry that attack, which fits the problem statement; but since we do not have the code of the verifier, we will only know if it works by trying.

If Poncho and I missed any other avenue for attack that might fit the question, I want to know!

Attack 5 assumes an hypothetical verifier goof. Attacks 3, 4 and 5 depend entirely on the disastrous/absent padding. Attacks 4, 5, and to a lesser degree 3, also depends on $e$ being very small, with the common $e=65537$ enough to block 4 and 5, and appreciably slow 3. The lesson about RSA signature should be to

Ensure that verifier code is correct in how it checks padding, which is done with best confidence by a combination of scrutinizing the source code and testing; the most critical being that what's been reviewed is what's actually used (including but not limited to that the compiler did not goof, and that an adversary can't zap some of the checks by altering what's run, which could be at any point from the developer's penetrated development machine, to the internals of the target CPU in a fault attack).
Use a proper padding for RSA signature, with the bare minimum PKCS#1 V1.5 type 01 (now officially named EMSA-PKCS1-V1_5), and EMSA-PSS preferable (specially in circumstances where the attacker might obtain the signature of even partially chosen messages).
Use $e=65537$ (or more, but that's technically unjustified) unless it is used a padding with a strong security argument (including EMSA-PSS). There might be additional reasons to stick to $e=65537$, see this.


There are a number of multiplicative subgroups in the ring of divisor classes modulo $n^2$. One particular subgroup (with easy logarithm) is generated by $(n+1)$. You would not want to use it for ElGamal. Other subgroup (of large enough order) are fine.


Why is the rand() function in C not a cryptographic pseudo-random generator?

This is a Pseudo Random Number Generator, but not a Cryptographically Secure PRNG, which requires that the output is undistinguishable from random for one not knowing the initial *seed.

One problem is, the effective state is very small: 27 bits at most (or less, limited by the size of int), because only the 27 low-order bits of the input *seed ever have a chance to influence either result or the low-order 27 bits of the output *seed. That alone limits the generator to 27-bit security, which is not enough (40-bit was already low security down in the 1980's). Also, this small effective state limits the period to $2^{27}$ (about 134 million), which is not enough even for simulation purposes.

Worse, one 31 bit output result is (at least, most likely) enough to easily reconstruct the full state *seed on output and then trivially predict future output, a total disaster for a CSPRNG. One simple method for that is: enumerate the $2^{16}$ possible values of the low 16 bits of next in the line result = (unsigned int) (next / 65536) % 2048;, and deduce the other 11 meaningful bits of next as result>>20; then check that guess of next against the 20 lower bits of result by replicating what the code does. We are down to 16-bit security, and that could be brought further down.

Walking back and computing previous output is trivial, too. The low 27 bits of *seed are transformed by three iterations of the linear $x\mapsto a\;x+b\bmod2^{27}$ with $a=1103515245$ and $b=12345$, giving $x\mapsto y=c\;x+d\bmod2^{27}$ with $c=a^3\bmod2^{27}=8240309$ and $d=117712863$ determined from $x=0$. And that is inverted as $x=e\;y+f$ with $e=c^{-1}\bmod2^{27}=70668701$ and $f=80477501$ determined from $x=0$.


Algorithm to generate ECDSA keys with random number generator

Many libraries allow you to specify your own random number generator. In BouncyCastle, for example, you can specify a SecureRandom in the initialize method of the KeyPairGenerator class; while in Go you can specify a io.Reader to the GenerateKey function.

Therefore, you would need to write a class that implements SecureRandom or io.Reader and reads the specified number of bytes from your TRNG, assuming your TRNG actually produces uniformly distributed random output.  Be careful though, if you mess it up, the whole security of your system is compromised.

(A safer approach would be to make a program that reads from the TRNG and writes to /dev/random, mixing up the system PRNG, assuming it's Linux)


General
The existence of a "perfect" one-way function is not proven. Such a function would prove that P $\ne$ NP, which is still an unsolved problem in mathematics / computer science.
One-way functions are per definition hard to invert, but easy to check. One example, that are assumed that they are one-way, are hash-functions:
You can easily create a hash of a given input, but you can't get the input from a given hash in a reasonable amount of time, assuming the input is long enough.
Some properties of a one-way function:

Easy to compute, but infeasible to compute the inverse of the function in the average case
Preimage resistant

Hashes
We assume that there exists a perfect one-way hash function: Hash functions are a special kind of one-way functions, since they reduce a possible large input to a fixed length smaller hash value, the term is a one-way compression function. This means that there is a data-loss and also means that mulitple different inputs can have the same hash value (pigeonhole principle). Data-loss here means, that it's impossible to retrieve the unknown original input from a given hash-value.


Two or more initialization vectors with the same key

It seems that because it uses a initialization vector of 24 bits, which is relatively short, is easy to determine which key was used to encrypt the data.

Actually, it's not the shortness of the IV that does cause the key leakage (although it does cause other problems).

Instead, it's due to how WEP combines the IV and the key, and then how the RC4 key initialization algorithm takes the combination, and generates a biased permutation.  Depending on the IV, this permutation may make the first byte of the RC4 keystream (and, it turns out, later bytes as well) to be correlated to bytes within the key; this allows someone listening in (who knows the first byte of the plaintext; with WEP, that's constant) to deduce the key.

The bias isn't extremely strong, and so we do need multiple IVs to fully leak the key.

To go into more details than that fairly high level description, you need to start looking into the RC4 KSA and keystream generation; that's where the weaknesses lie.


Why am I getting a wrong output when implementing Feige-Fiat-Shamir ID protocol?

The first problem is, that you calculated $v_i$ wrong right at the start.
$$v_i = s_i^2 \mod n$$
This means:
$$v_1 = 5^2 = 25 \mod 77$$
$$v_2 = 12^2 = 67 \mod 77$$
$$v_3 = 37^2 = 60 \mod 77$$

Then at the end you have:
$$(x \cdot \prod_i v_i^{a_i})  = 67 \cdot 25 \cdot 1 \cdot 1 = 58 \mod 77$$


The paper's tables in Appendix A are wrong.

For the entries in the first line of Table A1(a) I independently get:

0A 15 3F 2C 90 3B 19 51 FD EF 28 8C 83 A0 A7 36

and the fourth value (for input 03h) matches the OP's computation.

Note: there are fixed points (including 23h), invalidating the list of the valid additive constants, which is about the only attempt at an addition to self-citation [15] (at least, Appendix 1 table 2b appears correct and is available for free there).

Recommendation: if working on that paper is an assignment in a crypto course, question the competence or/and honesty of the assigner.


..then the verifier can't extract any knowledge besides the statement
  being challenged.

Please let me amend it to, since a proper transcript (an indistinguishable one) can be generated by a simulator having no secret input at all, then transcript value is questionable for any reasoning about secrets (an easy, non-formal wording). In particular, a Prover can claim did not run (was not a party to) a protocol.

  Now, this doesn't prove that the verifier is not extracting knowledge
  from the transcript.

Knowledge extractor algorithm is a requirement for another property, proof of knowledge.

  Thinking it differently, if a monkey randomly type a Calculus book...
  yes, the monkey knows nothing about calculus, but a reading verifier
  would get real knowledge by reading his work.

Simulator is required to be efficient (expected polynomial running time), and calculus book is too complex to fit that. I'd suggest a weather forecast instead, like yes/no for rain tomorrow.

Back to book, a fast (efficient) reader would get garbage most of the times, with no chance to distinguish the correct case (proper textbook) better than guess.


Partial-Message Collisions on Iterated Hash Functions

If you go through what Ferguson said, I'm sure he'll include a condition that $m$ and $m'$ are the same length, which is also a multiple of the hash block size. In this case, $m||X$ and $m'||X$ will not be preprocessed into single blocks; instead, they'll be processed as (at least) two blocks; one being $m$ (or $m'$), and the rest consisting only of $X$.

What's crucial is that the state of the hash function after processing $m$ and $m'$ are the same.  Because the state is the only way the hash function 'remembers' what came before, it'll do the same thing in both cases when processing $X$; hence $h(m || X) = h(m' || X)$


Why "encipher" instead of "encrypt" and "decipher" instead of "decrypt"?

I've seen encipher, encrypt, and encode for encryption. Encode is the worst since we have text encoding. The below definitions from Google dictionary that uses  Oxford Languages.

encipher: convert (a message or piece of text) into a coded form; encrypt.
Merriam Webster gives the date of the first usage of encipher as 1577.

encrypt: convert (information or data) into a cipher or code, especially to prevent unauthorized access.
Encrypt formed from English en + Greek kruptos is originally from the USA around 1950s.
Merriam Webster gives the date of the first usage of encrypt as 1944.

The above chart doesn't compare the actual values, Google's ngram can handle this

Encode: convert into a coded form. ( Please don't use this for encryption)

Is there concrete evidence that in cryptography the standard words to use are "encipher" and "decipher" and that we do not use "encrypt" or "decrypt" because they are offensive words?

I've searched and I couldn't find, however, if you consider usage statistics, the encipher should be increasing over time instead of decreasing. The academicians visit various countries around the world and meeting in the conferences, and if it is an offensive word in some language we have already heard about that a lot from them. For example, take Eve, although it is an abbreviation for an eavesdropper, it is used for a bad actor can be considered an offensive usage since the religious Adam and Eve but still in use. I know some people don't use Eve anymore.
Personally, I read a lot of text using encipher, however, that usage is decreasing. And I've seen some texts that use encoding for encryption, I hope that will fade away.
And the Google fight Encipher vs Encrypt : Encipher 1 : Encrypt 200

Is there concrete evidence that in cryptography the standard words to use are "encipher" and "decipher" and that we do not use "encrypt" or "decrypt" because they are offensive words?

Actually, I have seen the reverse of this. There is a website named word safety ( Warning no https) show some -not exact- potential unwanted meaning for the word encipher in Russian, I would not list here.


SHA algorithim with different hash value

I'll assume that you are thinking this way:

I am hashing a series of values that share the same prefix $X$ (which is a multiple of 64 bytes in length), that is, you are computing:

\begin{gather*}
\operatorname{SHA256}(X \mathbin\Vert A) \\
\operatorname{SHA256}(X \mathbin\Vert B) \\
\vdots \\
\operatorname{SHA256}(X \mathbin\Vert B)
\end{gather*}

and you are wondering "can I just compute the internal SHA256 state immediately after X, and then just use that as the "initial SHA256 state" when I process the strings $A, B, \dots, Z$?

Answer: yes, absolutely.  In fact, this is fairly common practice when these sorts of hashes are needed (which happens more than you'd expect; for example, when computing HMAC's).

  What problem I would get?

One thing you need to be careful is in the length field in the SHA-256 padding at the end; it needs to include the length of the entire message (including $X$), not just the message you just processed.


Complexity of Discrete Logarithms in binary fields without special exponents or special structure

Edit: My hunch that the best complexity is exponential was incorrect. It is actually quasi-polynomial (thanks to Samuel Neves for his comment).

Recall that  Coppersmith's algorithm has complexity
$$
L_{2^n}(1/3,c)
$$
for a small constant $c,$ while even for $n$ prime, which is the hardest case,  discrete logarithms over $GF(2^n)$ using Barbulescu et. al.'s method   have quasi polynomial complexity
$$
O(2^{c(\log n)^2})\asymp c' n^{c \log n}.
$$

Note that the authors state "The crossing point between the (best knoen before) L(1/4) algorithm and our quasi-polynomial one is not determined yet".


Is it possible to have perfectly secure public-key cryptography with oracles?

What you're saying is unclear... If you have uncountably many possible keys, if the scheme is computationally secure in the normal case (you're using an already-secure algorithm), your algorithm would fit your definition of being perfectly secure - the computation required to break it goes up with the key size, effectively creating an infinite search time for the key. The issue is, this basically equates to having a key of infinite size which is just as impossible to use for encryption, since the time to encrypt increases as well - just not as fast as the time to break it.
However, if we assume your oracles $A$ and $B$ operate in a finite amount of time (somehow you manage to encrypt using an infinitely large key) you would have a perfectly secure scheme, as you describe.


HMAC and assumptions on the cryptographic hash

Before we jump into this question, you first need to know a bit about the internals of hash functions with the Merkle-Dåmgard construction. Here's a pretty picture from Wikipedia:

In this diagram, you see the compression function $f$ being fed the message blocks along with the output of the state of the previous compression block (or the IV). The final output is the result of the last compression function. (You can ignore the finalization step for our purposes.)

Now, let's focus on the original NMAC/HMAC paper. In it, the authors state:

  In the rest of this paper we will concentrate on iterated hash
  functions, except if stated otherwise.

This should be the first clue that your scheme is not one that will work with NMAC/HMAC: it's not iterated! Not all of it, at least. The fact that the first $n$ bytes are concatenated (leaked, what have you) means that your hash function's output is no longer solely the result from the compression function evaluated on the last block. This changes the construction of the scheme drastically.

In regular circumstances, the (almost implicit) assumption that the underlying hash function is iterated is not an unreasonable one at all: all of the popular hash functions of today are. (SHA3/Keccak is a bit of a special case. It's not clear one even needs the HMAC construction for it. But that's a topic for another question.)

For example, what do you do with the IV (initialization vector, or as Bellare et al call it, "initial variable")? Do you simply pass it along to the $H$ in $H'$? If so, then your scheme doesn't actually leak the key with NMAC, although it does leak $k \oplus \mathtt{opad}$ in HMAC. In case you're unfamiliar with NMAC, the basic idea of the scheme is replace the IVs of the regular hash functions with the keys $k = (k_1, k_2)$. In the case of HMAC, the "new IVs" are (where $f$ is the compression function for the hash in question) $k_1 = f(k \oplus \mathtt{opad})$ and $k_2 = f(k \oplus \mathtt{ipad})$. But note that this, too, carries with it the implicit assumption that the starting state of the next $f$ in the chain is the previous evaluation of $f$.

Trying to discuss $H'$ in the context of HMAC is difficult, though. The primary issue is that your $H'$ doesn't have a clearly available compression function. Sure, $H$ (probably) has a compression function, but for $H'$, things are much less certain. Even if you attempted to define a compression function for $H'$, in order to be an iterated hash function, it would somehow have to leak the first $n$ bytes of the original message while simultaneously evaluating $H$ for the rest of the message.

Here is the problem, though: even if you created such a compression function, it would be insecure, naturally. Namely, it no longer would act as a pseudorandom function (PRF) (or for Wikipedia's less thorough, but perhaps easier, explanation, see here). In this relatively new paper, Bellare proves that HMAC is a PRF itself if the compression function of the underlying hash is a PRF. If $H'$ had a compression function, then it definitely would not be a PRF, since it (quite literally) leaks part of the input.

The prerequisite that the compression function is a PRF is quite a weak requirement, too. Given that $H'$ (even if you did somehow come up with a compression function for it) simply fails this requirement, the security proofs for HMAC do not cover it. Further, pretty much all of the security proofs given in favor of HMAC assume that the attacker doesn't know the key. Those proofs are possibly invalid if this assumption is invalid.

So, to answer your question directly, HMAC requires an iterated hash scheme whose compression function is, as best as we can tell, a PRF. A generic cryptographic hash function, at least using the definition Wikipedia gives, is not strong enough to guarantee a solid MAC. But the PRF requirement is relatively weak, as even MD5 (which is completely broken as far as collisions go) still appears to satisfy it.


How would low-precision Gaussian sampling impact the security of BLISS?

The purpose of Gaussian sampling is to prevent the signature from leaking information about the product of the secret key and the callange, and the better quality the samples, the better security.

As we know, the reason NTRUSign is broken is because it's not zero-knowledge. When you sign about 400 messages with the same key-pair, the distribution of the signatures roughly makes up a (high-dimension) cube whose edges follows that of the secret key vectors.

The same would apply to BLISS if attacker would be able to statistically distinguish bad signatures from good discrete Gaussian. The attacker would then draw a rough picture of Sc - challenge multiplied by secret vectors, then take challenge out of the equation there by recovering the secret private key.

This is why we need to calculate some transcendent functions to high precisions to perform Gaussian and rejection sampling.

I'll soon update this answer once I've learned more from references such as this about how much precision is needed to achieve full and/or practical zero-knowledge.

Also, the distribution of signature polynomials z1 and z2 are Gaussian after rejection sampling, where as I generated Huffman coding table for the pre-rejection distribution as of the 2016-09-15 release. Obviously I did not fully understand the rejection sampling process.

Based on this, I did the following calculation:

$ awk "BEGIN { s = sqrt(2*${pi})*215 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
538.925079, 29.944378,
39.452107
$ awk "BEGIN { s = sqrt(2*${pi})*107 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
268.209225, 26.924290,
39.375418
$ awk "BEGIN { s = sqrt(2*${pi})*250 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
626.657069, 30.597140,
39.467662
$ awk "BEGIN { s = sqrt(2*${pi})*271 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
679.296262, 30.946228,
39.475846
$

Looks like 40-bit precision might do for now.


Does encrypting data multiple times using different passwords increase security?

There is a terminology gap in your question. Lets assume that you want to encrypt message $m$, and for that purpose you'll be using the encryption function $E$ such that the encrypted message will be $E(m)$. Now you ask whether your message will be more secure if you encrypt it for example as $E(E(E(m)))$. Well if this encryption is stronger than $E(m)$, then you might as well have selected in advance the algorithm $E'$ such that $E'(m)=E(E(E(m)))$. Does $E'(m)$ mean that you encrypt something 3 times? Well according to the custom terminology the answer is no, $E'(m)$ is a single iteration of the algorithm $E'$ which happens to consist of three iterations of $E$. If those three iterations were not to yield the optimal result then no one would bother to invent such algorithm $E'$. You may argue that the number of iterations represents some cost/performance tradeoff, but in this case the algorithm $E'$ would have been defined as $E'(m,n)=E^n(m)$ where $n$ is the number of iterations to employ (you'll find a similar concept in KDFs such as bscypt, scrypt, Argon2, etc. EDIT: But then a KDF is of course a one-way transformation as @tylo mentioned below, where multiple iterations do make sense). So the bottom line is that there is no such thing as "encrypting something multiple times", you'll always be just encrypting something, and this encryption may employ under the hood multiple iterations of one or more steps in the encrypting process.

Now to the point of your question, if you have multiple passwords then the strongest security you'll get is by concatenating these passwords together, pass them through a KDF, and use the resulting key for encryption. Your entropy for the entire process is the same, but if the encryption process is broken into iterations each one using only part of the entropy gives the attacker the luxury of keeping interim results and thus speeding up the cracking. So encrypting with a single iteration using a single password yields stronger encryption then multiple encryption iterations with multiple passwords which sum up to the same entropy as the password in the first option.

Concerning your idea of using different algorithms depending on password, well in that case you may leak information about your password if the attacker can guess the algorithm. So, you'll get better security by using an algorithm which is independent of message content or password.


Does the following Diffie-Hellman problem hold in bilinear groups $G\times G \rightarrow G_T$

Hint: suppose we modify the problem so that $r, a, b, z$ are selected uniformly randomly from the interval $[1, p-1]$; how do the probability distributions of $(g^{ra}, g^{rb}, g^{rab})$ and $(g^{ra}, g^{rb}, g^{rz})$ compare?

Hint: if we actually select $r, a, b, z$ from $\mathbb{Z}_p$, what is the probability that at least one of them are selected outside the interval $[1, p-1]$?  Can you show that this probability is negligible?


How do public key rings work in cryptographic applications?

It's shockingly simple. It's a file. It has public keys in it.

The traditional PGP Key Ring is a sequential file with a sequential list of keys in it. It's not even a database.

Slightly more advanced key rings, such as those used in Key Servers actually use a database.


What is the use of encoding a hash output?

What is the need for further encoding the hash value?

Representing the hash as a string of characters, without increasing the size too much. This is known as Binary-to-text encoding. It is commonly used for cryptographic data (hashes, ciphertexts..), because that can contain arbitrary sequences of bits (or arbitrary sequences of arbitrary bytes), and some data communication, storage or display means can only handle characters in some alphabet.This is not to be confused with encoding characters into bytes, as needed to hash or encipher text.

I will make the explanations and examples with the MD5 hash of a 26-ASCII-character message given in example in RFC 1321 appendix A.5:

  MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b

The hash is not c3fcd3d76192e4007dfb496cca67e13b. It really is a 128-bit sequence (or bitstring) which representation with 0 (resp. 1) for a bit clear (resp. set) is:

11000011111111001101001111010111011000011001001011100100000000000111110111111011010010010110110011001010011001111110000100111011

The 32-character sequence c3fcd3d76192e4007dfb496cca67e13b is a representation of the hash per lowercase big-endian hexadecimal. That was obtained from a representation of that hash as 16 bytes (or equivalently 16 octets) per this code C code (from the RFC):

/* Prints a message digest in hexadecimal.
 */
static void MDPrint (digest)
unsigned char digest[16];
{
  unsigned int i;
  for (i = 0; i < 16; i++)
    printf ("%02x", digest[i]);
}

Note: In the above, unsigned char is a byte representing an integer in range [0…255] that encodes 8 bits of the hash. Conversion to characters is in the printf function, with "%02x" specifying at least 2 lowercase hexadecimal characters.
Note: Each group of 4 bytes is the little-endian representation of a computer word, but that's a consideration internal to MD5.

Beside the aforementioned representations as 16 bytes, and 32 lowercase (big-endian) hexadecimal characters, there are other common representations, including

C3FCD3D76192E4007DFB496CCA67E13B : 32-characters, uppercase (big-endian) hexadecimal
w/zT12GS5AB9+0lsymfhOw== : 24 characters, Base64 per RFC 4648
w_zT12GS5AB9-0lsymfhOw== : 24 characters, Base64 with Filename Safe Alphabet
w/zT12GS5AB9+0lsymfhOw : 22 characters, Base64 with pad suppressed

If is possible to convert from a text (equivalently, character) encoding back to the hash. The same hexadecimal decoding method can handle uppercase and lowercase. The same Base64 decoding method can handle common alphabets and make pad optional.

There are other, more seldom-used, sometime more compact Binary-to-text encodings. See this for why Base64 is most popular.

  When we encode (a 16-byte MD5 hash) using the base64 scheme and produce 8 char long string, it will be 8 bytes.

No. Each Base64 character encodes 6 bits (except the last non-pad character which can encode 2, 4 or 6 bits; and final pad characters, if any). Therefore, per Base64 encoding, a 128-bit hash requires at least ⌈128/6⌉ = 22 characters, plus pad if any.

Depending on computer language and options, each character may in turn use several bytes. For example, each character in a C string is represented by 1 byte, in a Java String 2 bytes. Also, there is size overhead for each object, which may not be negligible.In a Python string, starting with version 3.3 or so of Python, each character in the above encodings by default uses 1 byte. In previous versions it used 2 or 4, depending on Python environment; refer to PEP 393.


If DDH is hard then CCA-secure PKES exist?

The answer is

  Because Cramer-Shoup encryption exists.

The construction of Cramer-Shoup is essentially a modification of ElGamal encryption with an added checksum, that allows to detect tampering of ciphertexts.

The construction assumes a cyclic group $\mathbb{G}$ of order $q$ with two generators $g_1,g_2$ in which the DDH problem is hard, as well as a collision resistant hash function $H : \mathbb{G}^3 \to \mathbb{Z}_q$.

Collision resistant hash functions can be constructed based on the discrete logarithm assumption (See, e.g., Section 121 in these lecture notes by Rafael Pass. There's a bit more work involved in encoding inputs and outputs to match the required domain and range, but it's possible to do.) Since the discrete logarithm problem is hard if the DDH problem is hard, it thus follows that if DDH is hard, then CCA secure PKE exists.


Collecting entropy from a stream to a file

Partition the file into blocks of almost-equal size, and let $B$ denote the maximum block size (in bits). $\:$ Choose a randomness extractor whose outputs are long enough to

sample from the blocks and still have $B$ bits of the output left over.

Choose a seed for the extractor (unless you choose an extractor that doesn't actually use one).

For each [extractor's source's size] bits from the stream, apply the extractor to those bits,

use the output to sample a block as described before, let $s$ be the number of bits in that block,

set that block equal to its old value plus the left-most $s$ bits of the remaining extractor output

(both interpreted as unsigned integers) mod 2$^s$, then if any of the extractor's

output is still unused, continue as if those were the next bits from the stream.


Different ways/algorithms for implementing AES

To my knowledge there are at least 4 ways to implement AES.

I. lookup tables

For simple blocs, lookup tables are fast but they are sensible to timings
attacks.

Here is an example of lookup table implementation:

b0 = T0[ a0 >> 24 ] ^ T1[(a1 >> 16) & 0xff] ^ T2[(a2 >>  8) & 0xff] ^ T3[ a3 & 0xff] ^ rk[4];
b1 = T0[ a1 >> 24 ] ^ T1[(a2 >> 16) & 0xff] ^ T2[(a3 >>  8) & 0xff] ^ T3[ a0 & 0xff] ^ rk[5];
b2 = T0[ a2 >> 24 ] ^ T1[(a3 >> 16) & 0xff] ^ T2[(a0 >>  8) & 0xff] ^ T3[ a1 & 0xff] ^ rk[6];
b3 = T0[ a3 >> 24 ] ^ T1[(a0 >> 16) & 0xff] ^ T2[(a1 >>  8) & 0xff] ^ T3[ a2 & 0xff] ^ rk[7];

II. With Inversion in $GF(2)[X]$

One can represent a polynomial of degree 7 in $GF(2)[X]$ by a number in $GF(2^8)$. (2.1.4 Polynomials over a Field, p. 13, The Design of Rinjdael) or in other word a byte.

By going back to the initial definition, one can implement subBytes is such way and have it potentially protected against timing attacks.

III. Bit sliced

Wait! This is slow as hell!

In order to gain speed, we can have a look at a bit sliced version. Bit slicing is basically writing an hardware implementation in software, considering that each bit is a different input and operations as gates applied at the same time.

In 2007 Matsui and Nakajima propose a bit-sliced implementation of AES-CTR, about 30% faster than the table lookup version. It uses 128 bits vector registers and computes 128 blocs of AES at the same time.
The only draw back is that you need 2kB of data to encrypt to benefit from the speed up. But that is still useful in the case of HDD encryption ...

Two years later P. Schwabe and E. Käsper implement another version 20% faster and that does not have this 2kB requirement.

IV. But I need more SPEED !

In 2010, Intel provides a hardware AES instruction.

aesenc xmm1, xmm3   % xmm1 - data, xmm3 - key

Which leads to:

# Encrypt the block.
pxor       %xmm5,  %xmm0
aesenc     %xmm6,  %xmm0
aesenc     %xmm7,  %xmm0
aesenc     %xmm8,  %xmm0
aesenc     %xmm9,  %xmm0
aesenc     %xmm10, %xmm0
aesenc     %xmm11, %xmm0
aesenc     %xmm12, %xmm0
aesenc     %xmm13, %xmm0
aesenc     %xmm14, %xmm0
aesenclast %xmm15, %xmm0

source

V. More readings:

Implementing AES 2000-2010: performance and security challenges by Emilia Käsper

How can bit slicing be constant time, when Mix Columns is in the cipher


Is any decent RNG acceptable as a stream cipher?

The property desired of stream ciphers, just like for any random number generators, is indistinguishability from true randomness — and indeed, any RNG that fails a statistical test suite is obviously not a good stream cipher.

However, to be considered secure, a stream cipher must not only withstand a generic battery of statistical tests; its output needs to be indistinguishable from a truly random bitstream even for an attacker who knows exactly how the cipher works (but doesn't know the key), allowing them to devise specific tests just for that algorithm.

This is the point where most non-crypto RNGs fail: there are various cryptanalytic techniques than can be used to devise specific tests to tell the output of a given algorithm from random data, and RNGs which are not specifically designed to withstand them will usually succumb to them.

Of course, as the state of the art advances, sometimes that can happen even for ciphers that were previously thought to be secure, but any cipher generally accepted as secure must at least have withstood a considerable amount of attention from the cryptanalytic community without being broken.


Incorrect solution for Discrete Log Problem when using the Index Calculus algorithm

Did it a quick sanity check, and indeed your relations hold in $\mathbb{F}_p$. I cannot judge where you went wrong of course, but my guess is that you are dividing at points where you can't. The Gaussian elimination is done $\bmod{2002}$, hence dividing with any positive integer which has $\gcd$ unequal to 1 with 2002 is off-limits. Below I show how you can get some solutions from your system of equations.

Note that you can trivially cancel out 5's on the right side of your equation, to get the system of equations
\begin{align*}
5^{790} &= 3^2\cdot11^2\\
5^{728} &= 2^5\cdot 11\\
5^{1161} &= 3^3\cdot7\\
5^{918} &= 2^2\cdot 7^2\\
5^{150} &= 2\cdot 3^2\cdot7\\
5^{952} &= 2\cdot7\cdot13\\
\end{align*}
This does not affect the solutions of course. Instead we get the matrix
$$\begin{pmatrix}
0 & 2 & 0 & 2 & 0 & 790\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
1 & 2 & 1 & 0 & 0 & 150\\
1 & 0 & 1 & 0 & 1 & 952
\end{pmatrix}$$
Using Gaussian elimination (for the full computation check below) we obtain the relations
\begin{align*}
2^{20} &= 5^{714} \\
3^4 &= 5^{1384} \\
3^{60} &= 5^{740} \\
7^{20} &= 5^{458} \\
11^4 &= 5^{196} \\
13^2 &= 5^{986}
\end{align*}
Of course $3^4=5^{1384}\implies3^{60}=5^{740}$, hence we get solutions
\begin{align*}
2^{20} &= 5^{714} \\
3^4 &= 5^{1384} \\
7^{20} &= 5^{458} \\
11^4 &= 5^{196} \\
13^2 &= 5^{986}
\end{align*}
Now note that $801\equiv5^{-1}\bmod{2002}$, hence $$2^{20} = 5^{714}\implies (2^{20})^{801} = (5^{714})^{801}\implies 2^4=5^{1344}.$$
Similarly $7^4=5^{492}$, and we have
\begin{align*}
2^4 &= 5^{1344} \\
3^4 &= 5^{1384} \\
7^4 &= 5^{492} \\
11^4 &= 5^{196} \\
13^2 &= 5^{968}
\end{align*}
Now we get into some trouble, since $\gcd(2,2002)=2$, hence we cannot simply eliminate 2. However we can conclude that $\pm 13\equiv5^{493}\bmod{p}$. Simply trying both gives that $\log_5(-13)=493$. Moreover $\mathbb{F}_p^*$ is cyclic of order 2002, and since 2002 is not divisible by 4, it does not contain any element of order 4. So the only elements $x\in\mathbb{F}_p^*$ that satisfy $x^4=1$ are $\pm1$. Hence
\begin{align*}
\pm2 &= 5^{336} \\
\pm3 &= 5^{346} \\
\pm7 &= 5^{123} \\
\pm11 &= 5^{49} \\
-13 &= 5^{493}
\end{align*}
Simply trying the two options leads to the solutions
\begin{align*}
-2 &= 5^{336} \\
3 &= 5^{346} \\
7 &= 5^{123} \\
11 &= 5^{49} \\
-13 &= 5^{493}
\end{align*}

Gaussian elimination:

Multiply the bottom row by 2 (the 6th row, starting the count at 1), and then subtract the 4th row from the bottom row. This leaves
$$\begin{pmatrix}
0 & 2 & 0 & 2 & 0 & 790\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
1 & 2 & 1 & 0 & 0 & 150\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiplying the 5th column by 2, and subtracting the fourth gives
$$\begin{pmatrix}
0 & 2 & 0 & 2 & 0 & 790\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiplying the first row by 2 and subtracting the 5th leaves
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiply the second row by 4 and subtract the first to get
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
20 & 0 & 0 & 0 & 0 & 714\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiply the 4th row by 10 and subtract the 2nd to get
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
20 & 0 & 0 & 0 & 0 & 714\\
0 & 3 & 1 & 0 & 0 & 1161\\
0 & 0 & 20 & 0 & 0 & 458\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Finally multiply the 3rd by 20 and subtract the 4th to obtain
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
20 & 0 & 0 & 0 & 0 & 714\\
0 & 60 & 0 & 0 & 0 & 740\\
0 & 0 & 20 & 0 & 0 & 458\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$


What was the BassOmatic cipher, and what made it so weak?

Phil Zimmermann did not use DES or the RSA-owned RC-2 as models for the Bass-O-Matic cipher.
For the basis of that symmetric cipher, he used the work of a man named Charlie Merritt. Zimmermann's strong suit was not mathematics but programming in C, so he needed help. Merritt had called Zimmermann by phone (at Metamorphic Systems, a 1980 startup by Zimmermann), and after that fortunate call, they talked more than once a week for several years.
Merritt, a computer programmer from Arkansas,

specialized in writing public-key cryptography implementations. Merritt wrote the
first commercially successful implementation of RSA for a personal
computer and taught Phil Zimmermann how to do arithmetic with
hundred-digit numbers on a personal computer. [1]

Merritt was an expert in assembly language. He had developed an implementation of RSA that was running on Z-80 computers with the CP/M operating system. It took, by the way, ten minutes to generate a 256-bit key. In 1980, Merritt's success in doing this inspired Zimmermann. They talked about Zimmermann putting crypto on his 8088 card for the Apple II, and everything else having to do with cryptography.
Merritt and Zimmermann, "PRZ," got along over the phone. Merritt said,

He began talking about protocols, in great detail. For hours, on the
phone. I hate protocols, that's for the Phone Company. But he needed a
brick wall. Then he began asking exactly how math was implemented on a
Z80. I mean detailed stuff about memory allocation, and adding two
giant numbers and what about the carry bit. We were back in my
territory. [2]

They finally met face-to-face in the summer of 1986.
Zimmermann labored in the wilderness for years. In November 1986, Merritt was working on a conventional cipher for the U.S. Navy, and this cipher was the basis for the Bass-O-Matic. Zimmermann then made it stronger by adding several rounds of substitution.
Time for the character in black to enter the stage: the NSA periodically threatened Merritt at this time. "They always travel in pairs," Merritt said. Unworried, Merritt started selling his encryption system, the DEDICATE/32, which used 256-bit keys.
Merritt's DEDICATE/32 was slow, and this convinced Zimmermann to create a hybrid system: slow RSA to exchange keys and something quicker for the bulk encryption.
The plot thickens: in 1991, a U.S. Senator sneaked this into a draft bill (S.266):

It is the sense of Congress that providers of electronic
communications services and manufacturers of electronic communications
service equipment shall ensure that communications systems permit the
government to obtain the plaintext contents of voice, data, and other
communications when appropriately authorized by law. [3]

Thank you, Senator Joe Biden.
Interestingly, Biden's clause in the draft bill got removed because of the outrage it caused. The furor pushed Zimmermann to release PGP 1.0. PRZ was angry.
Zimmermann let PGP 1.0 loose upon the word, but he said, "the Bass-O-Matic has not yet (in 89) been through a formal security review and has had only limited peer review."
Zimmermann needed to get an expert opinion on the Bass-O-Matic, so he attended Crypto '91 in Santa Barbara, California, in August. He and Eli Biham sat down in the UCSB cafeteria, and Biham told him that the Bass-O-Matic was vulnerable to differential cryptanalysis attack (Biham's specialty). Additionally, the most embarrassing error "prevented the last bit of each byte from being properly encrypted." So, the Bass-O-Matic was unceremoniously thrown into the trash.
Biham had destroyed the Bass-O-Matic in ten minutes over lunch.
Zimmermann then took up IDEA, added key certification, and PGP 2.0 was born.
[1] Garfinkel, Simson (December 1, 1994). PGP: Pretty Good Privacy. O'Reilly Media. p. 372, ISBN 978-1-56592-098-9.
[2] Ibid., 90.
[3] Ibid., 97.


In most PRNGs, this leads to a total disaster, in particular when the generator's state is bigger than the result returned as pseudo-random (call to rand()).

If you take Mersenne Twister with its big period guaranteed and apply the construction you expose, as it returns 32-bit integers, eventually you will get a repeated value that was used to seed previously, so it turns into a loop. You'll get an about $2^{16}$ repeating sequence of pseudo randoms, according to the birthday probability, and not the guaranteed generator's period length. This same issue applies to all other generators if it's seeding is deterministic and guarantees that a given seed always generates the same sequence of pseudo randoms.

On the other hand, if you do some steps of autoseeding first and then you use the PRNG without seeding it anymore then it shouldn't affect its properties.


Key length and message length in AES and perfect secrecy if plaintext length <= key length

Block ciphers, AES is a block cipher, encryption $Enc$ can be formalized as

$$Enc:\mathcal{P} \times \mathcal{K} \to \mathcal{C}$$ where $\mathcal{P}$ is the plaintext space, $\mathcal{K}$ is the keyspace, and $\mathcal{C}$ is the ciphertext space. Similarly the decryption; $$Dec :\mathcal{C} \times \mathcal{K} \to \mathcal{P}.$$ For a block cipher the $\mathcal{P} = \mathcal{C}$. The number of elements of this space is determined by the bits, for $\mathcal{P}$ it is determined by the block size. AES has 128-bit block size and it has $2^{128}$ message space for a single block. For DES it is $2^{64}$. AES has variable key sizes like 128,192, and 256, therefore, the keyspace $\mathcal{K}$ is $2^{128},2^{192},\text{ and } 2^{256}$, respectively.

We require the operation of a block cipher invertible[*] so that we can decrypt. Therefore the block ciphers are permutations. Each key from the keyspace selects a permutation for all possible permutations. The number of permutations of the message space is $2^b!$ where $b$ is the block size and for AES this is $2^{128}!$. With the Stirling's approximation $$2^{128}! \approx \sqrt{2\pi 2^{128}}(\frac{2^{128}}{e})^{2^{128}}.$$ That cannot be covered by the tiny keyspace  $2^{128}$, tiny according to comparison, but huge for any classical computational power.

We expect that a block cipher behaves like a Pseudo-Random Permutation that is a function that cannot be distinguished from a random permutation and AES has believed to be one.

Back to your questions;

  What is the concrete step(s) of AES (or a similar popular symmetric key encryption algorithm) that makes encrypting an n-byte plaintext with an n-byte key not the same as a One Time Pad?

Block ciphers use the confusion diffusion paradigm, Shannon 1945. Here, what related to your approximation is, changing one bit of the key will affect all ciphertext bits. If the cipher achieves the avalanche effect property then it will randomly flip half of the bits. Therefore all of the bits of the block are affected  (affected doesn't mean changed) whereas in OPT changing one bit only affects one plaintext bit.

  It feels intuitive that if the key is shorter than the plaintext, then all plaintexts cannot be possible regardless of the algorithm. The other way around (key longer than the plaintext) is not intuitive.

It is not all of the plaintexts, it is all of the permutations. In AES. all of the 128 bits are valid plaintext and plaintext space contains all. But block ciphers randomly select permutations from all possible permutations space. With the keyspace, we cannot cover all of the permutations. They are limited to keyspace.

This the distinction between the OTP and AES or any block cipher. In block ciphers, the key size is fixed no matter the length of the plaintext. In block ciphers, We use computational security since we cannot achieve informational security without key bits equal to message bits.

  If the question is if the key is as large or larger than the plaintext, then why can AES be distinguished from a perfect cipher?

There is no guarantee that given a ciphertext $c$ decrypted under all possible keys $c=AES_k(x)$ gives all possible plaintexts or gives all but they are equally distributed. This is contradicting to perfect secrecy that OTP has.

To prove that AES has perfect secrecy in this sense, we need to fully analyze the AES. This is beyond our computation point. If possible, it may lead to a known-plaintext attack.

While it is reasonable property of a block cipher that reaches all possible plaintext, equally, most block ciphers try to approximate random permutation where each key is independent of the others. This means that we may not reach all plaintext with decryption of $c=AES_k(x)$ under all keys. Or similarly, possibly there are plaintexts where $E_{k_1}(c)=E_{k_2}(c)$.

[*] Block cipher need modes of operation, and not all modes require decryption, like CTR mode. In CTR mode, one can use Hash functions that are not permutations.


Are developers expected to implement Diffie-Hellman key exchange themselves?

Look for a 'Key Agreement' functionality (see https://golang.org/src/crypto/tls/key_agreement.go), as many comments above suggested - if you're trying to establish a secure communication channel, the default TLS (SSL) would be good way to go.


How to construct a yes/no election protocol, such that only the result is revealed?

A threshold, additively homomorphic cryptosystems (such as the threshold variant of paillier) would work just fine for this sort of system. Each voter would need to prove that their vote was in the set $\{-1,0,1\}$ instead of the typical $\{0,1\}$. All of this could be done using the thep library. There is a page on dealing with negative numbers.

An alternative to this would be secure multiparty computation. At its core, MPC has the disadvantage that all parties must be online at the same time. This can be mitigated by say designating a few (e.g., 5) servers that perform all the computation. When a person votes, they use secret sharing to split their vote into 5 different shares and send a share to each server.


How to test the robustness of the cipher image against chosen and known plaintext attacks?

If you wish to construct a system which is resilient to Chosen Plaintext Attacks and Known Plaintext Attacks, the method to do so is through provable security, not empirical tests. If you're attacking an existing scheme which has not been proven secure, typically you would perform a variant of one of the methods that have been used for cryptanalysis in the past. For instance, you can try differential cryptanalysis or linear cryptanalysis.


how to solve discrete logarithm problem information requested

Let $f(x,y) = -y^2 + x^3+17230x+22699$ over $\Bbb F_p$ with $p=23981$. A point on the curve is a singular point if and only if the partial derivatives are vanishes at that point. The partial derivatives are;

$\frac{\partial f}{\partial x} = 3x^2 + 17230 =0 \pmod p$ and vanishes at $x=\{185,23796\}$ found by WolframAlpha or it can be found by Tonelli-Shanks.
$\frac{\partial f}{\partial y} = -2y = 0 \pmod p$ and vanishes at $y=0$

The vanishing point $(185,0)$ is not on the curve, however, $(23796,0)$ is.

Therefore $(23796,0)$ is a singular point for the Curve.

Then we then translate the origin to this singular point $(23796,0)$, that is replace $(x,y)$ by $(x+23796,y+0$) in the equation of $E$, yielding the equation of the curve in the shifted referential:
$$y^2 = x^3 + 23426x^2$$
The rest is in the answer which the OP had trouble with.

Note: credit goes to @kelalaka for the better of the present answer, in particular introducing $f(x,y)$ and its partial derivatives.


Key derivation functions (KDF): What are? Main purposes? How can they be used?

The HKDF paper provides as good a summary as any:

  A Key derivation function (KDF) is a basic and essential component of cryptographic systems: Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys.

Here it's important that you understand how the term "random" is used in probability theory vs. how it's (ab)used by computer people.  Very informally:

When us computer folks say "random" we more often that not implicitly assume that we're talking about a discrete, finite, uniform and independent random variable—one that takes on any value drawn from a finite set with equal probability as all the others, and earlier outcomes do not influence later ones, the way coin flips or dice rolls behave.
When statisticians say random, they aren't assuming as much.  For a statistician, for example, a stereotypical random variable has a normal distribution ("bell curve"), where values cluster around a mean and disperse according to a standard deviation—the way, for example, that inexact physical measurements have random errors that cluster around the true value.

So reading the quote with that in mind, a KDF is a cryptographically strong function that takes input that is random in the statistician's sense and produces output that is pseudorandom in the cryptographer's (preferred) sense.  This is useful in various contexts:

Diffie-Hellman key exchange with randomly selected keys produces a shared secret that is random in the statistician's sense, but its output is not uniformly distributed.  So to use this secret as a symmetric key you pass it through some KDF.
Cryptographic random number generators refresh themselves periodically from the values obtained by measuring random events like network packet timing, mouse movements or key presses.  These are also not uniform, so a KDF can be used to fix that.
Passwords are also not uniform, so to turn passwords into keys we use KDFs.  But in that case we use specialized password-based KDFs that also add a work factor to slow down brute force guesses.


Digital Signature Algorithm for large files - bottle-necked by hash function?

It is potentially a bottleneck, but will it be a problem in practice?  My phone doesn't have 10TB of storage, and if the files are remote the network speed will be the limiting factor.  There are other strategies possible, like computing hashes as the data is transferred to the device, or hash trees for updating a hash without re-computing the whole thing (for e.g. a small edit to a file).


The standard discrete logarithm assumption asks, given a group $\mathbb{G}$ of order $p$ with generator $G$, to compute $x$ given $xG$, where $x$ is a random. This means that $\{xG : x \gets \mathbb{Z}_p\}$ spans the entire group, so $xG$ is exactly a uniformly random group element. You cannot possibly hope to distinguish it from random, since it's perfectly distributed as a random group element.

That being said, there are "decisional variants" of the discrete logarithm problem:

distinguish $xG$ for a random even $x \gets \mathbb{Z}_p$ and $xG$ for a random odd $x \gets \mathbb{Z}_p$ (even and odd are defined by viewing $x$ as an integer between $0$ and $p-1$). This decision problem is equivalent to the computational discrete logarithm (the proof is a standard exercise, at least when the success probability is assumed to be 1 - it's harder in the general case).
distinguish $xG$ from a random group element, when $x$ is a random short element (e.g. between $0$ and $2^k$ for some $k$ related to the security parameter, such that $2^k$ is much smaller than $p$). This problem actually reduces to the computational "short-exponent discrete logarithm assumption", which asks to find $x$ given $xG$ for a random short $x$ (proof here).


The existence of two-round zero-knowledge proofs

Under the following assumptions there does not even exist three-round private-coin zero-knowledge proofs for languages outside BPP. See here.

The theorem holds assuming:

Sub-exponentially secure one-way functions.
Sub-exponentially secure indistinguishability obfuscation for circuits.
Exponentially secure input-hiding obfuscation for multi-bit point functions


modular exponentiation as a one-way-hash

It's a fine one-way function, based (as you noted) on the computational difficulty of the discrete logarithm problem. As far as its relation with modern-day cryptographic hash functions, however, it lacks two quite important properties.

Here's an okay definition: a function $H$ is called a cryptographic hash function if it possesses the following three properties:

Preimage resistance: Given $H(x)$, it's hard to find $x$
Second preimage resistance: Given $m_1$, it's hard to find another $m_2$ such that $H(m_1) = H(m_2)$
Collision resistance: It's hard to find any two distinct messages $m_1$, $m_2$ such that $H(m_1) = H(m_2)$.

Note that a general one-way function possesses only property 1. Unfortunately, your $h(x) = g^x \bmod p$ fails property 2. Suppose you had a fixed message $m$ that the adversary knows. Notice that

$$h(m + p - 1) \equiv g^{m + p-1} \equiv g^m \cdot g^{p-1} \equiv g^m \pmod{p}$$

by Fermat's little theorem. By extension, you find that $h(m + k(p-1))$ collides with $h(m)$ for any $k \in \mathbb{Z}^{+}$. So, you can in fact efficiently find infinitely many collisions with any $m_1$, which is relatively exciting, I suppose. And since $h(x)$ doesn't have property 2, it can't possibly have property 3. On the other hand, SHA2 and SHA3 (as two example candidates of modern-day hash functions) are strongly suspected to satisfy even property 3.

Also, even if we wanted a one-way function, modular exponentiation is dreadfully slow. Even with the repeated-squaring method, it's still painful. Some researchers at Intel did a benchmark with a modular exponentiation implementation and found that their implementation took nearly 450,000 cycles (!) for a 512-bit modular exponentiation. On the other hand, the Crypto++ Benchmarks report a figure of 17.7 cycles per byte for SHA-512. Now, I do admit that these were ran on different processors, but the difference is pretty spectacular.

So, in sum, there are essentially two reasons we use hash functions like SHA2: (1) they offer two extra properties, both of which are quite essential for many purposes and (2) modular exponentation is so very painfully slow. I'm sure there are more to be found, but I think these two are the most compelling.


For the hash computation of SHA-256, is it computed in parallel or series?

SHA-256 has a basic building block which is not easily paralalized. Between blocks SHA-256 follows a Merkle-Damgard construction and needs to be computed sequentially.
You could build a tree-hash using the same compression function, and this will be secure and allow parallel computing but results would not be consistent with the SHA-256 standard.

https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction
https://en.wikipedia.org/wiki/Merkle_tree


Exponentiation Problem of G2 in MNT curve

Here's a guess: when you ask to compute h ** (a * b), it actually computes h ** (a * b mod q), where $q$ is the order of $g$ in $G1$.
If that is the case, well, a random element from $G2$ is not going to be a divisor of $q$ - any element that is the result of a pairing operation will be; however most elements of $G2$ cannot be the result of a pairing operation.
And, if the order of $h$ is not a divisor of $q$, then $h^{a \cdot b} \ne h^{a \cdot b \bmod q}$
The above would give the expected result if you set $h$ to be the result of a pairing operation, possibly with two random $G1$ elements...
(This is labeled a guess because I'm not familiar with the Charm framework, so I'm guessing about its behavior)


Can the lengths of HTTPS requests be used to deduce which public pages on a site are visited?

Yes, you can often learn a lot just from the length of encrypted data (more generally the segmentation pattern of an encrypted stream). All the attacks that I know about leverage the data-dependent effects of compression.
It sounds like your question covers both HTTP requests and responses. There are indeed attacks that target exactly this side-channel. See the discussion here:

CRIME attack: if the user's HTTP requests support compression (which is possible as a TLS option) then private cookie data can be stolen by causing the victim to make many HTTP requests that include attacker-controlled content, and then measuring the size of the resulting (compressed) requests.

BREACH attack: Similar but works on the HTTP response.

Regarding the length of HTTP responses, here is a proof of concept showing how the length of different images from Google Maps can be used as a "fingerprint" of what area you are browsing.
This one is probably the simplest example of this kind of attack, and closest to the simple fingerprinting thing you describe:

Vincent Berg: I can still see your actions on Google Maps over SSL

The same concepts generalize to encrypted streams. When the compression uses variable-bitrate encoding, it leads to different segmentation/burst timing patterns.

You can recover actual spoken text from an encrypted VoIP audio stream:

Andrew M. White, Austin R. Matthews, Kevin Z. Snow, Fabian Monrose: Phonotactic Reconstruction of Encrypted VoIP Conversations:
Hookt on fon-iks. IEEE S&P 2011

You can identify the movie being watched (e.g., over Netflix, Youtube, etc):

Roei Schuster, Vitaly Shmatikov, Eran Tromer: Beauty and the Burst: Remote Identification of Encrypted Video Streams. USENIX 2017
Andrew Reed, Michael Kranch: Identifying HTTPS-Protected Netflix Videos in Real-Time. CODASPY 2017


In cryptography, forward secrecy = perfect forward secrecy, backward secrecy = future secrecy.

First, recall some background. The above terms are often discussed in the setting of secure channel establishment protocols, e.g., TLS, Signal, etc. In such a protocol, consider two parties, a client and a server, try to communicate with each other securely. The server (and the client if client-authentication is needed) is granted a certificate that shows its public key, and the server (and the client) itself knows the corresponding private key (a.k.a. the long-term secret). They essentially use the long-term secret and some randomness to compute and share a secret session key (only used within a session) and establish a secure communication channel based on the session key, e.g., using an authenticated encryption (with associated data) scheme.

Forward secrecy means if the long-term secret (together with the party's current session key and all other secret states) is corrupted (i.e., revealed), then the past sessions are still secure, i.e., the confidentiality of the previous messages exchanged between the client and the server is not compromised. I think people call this forward secrecy because they want the encrypted messages in a session to be secure even if "forward" long-term key corruption occurs. TLS is an example that achieves forward secrecy with Diffie-Hellman key exchange.

Then, as you may guess, backward secrecy guarantees the "opposite direction" of forward secrecy. In other words, this security guarantees that the encrypted messages in a session should remain secure even if "backward" long-term key corruption occurs. People more often call this future secrecy perhaps because they want to emphasize that even if at some point the long-term secret (together with the party's current session key and all other secret states) is corrupted the future messages can still be secure (if the previously corrupted party somehow becomes "clean" again). (I agree that the terms are a mess because "future secrecy" looks and sounds almost the same as "forward secrecy".) Signal is an example that achieves backward secrecy with the Double Ratchet Algorithm which can self-heal itself soon after corruption.


So, you are dealing with CBC decryption:

(image from Wikipedia)

What you want to do, is firstly to compute the key $K$ used by the block cipher at hand, since yours is a plain XOR, you can compute the key by XORing the ciphertext, the IV and the plaintext:
$$K=C_0\oplus M_0 \oplus IV$$

Next, once you've got your key, you can apply the CBC decryption, by XORing the key with the ciphertext block at hand and XORing the result with the previous ciphertext block to get the current plaintext:
$$M_i=C_{i}\oplus K \oplus C_{i-1}$$

Now, I do not see the whole code, but it seems strange that the IV is given as the first plaintext block.

If you were given: 1 block of known plaintext, 1 block of IV and 2 blocks of ciphertext, then you would be able to decrypt the second block of the ciphertext using the method I described above...

But there is something strange with your statement:

  "first_block" is a byte-array holding the decrypted first block (which is the IV)

So, the decryption of the first block is the IV? Are you sure? Because this amount to having a all 0s first plaintext block then you have that:
$$C_2 = (K\oplus IV) \oplus (M_2 \oplus K) = IV \oplus M_2$$
and so have a second block which is just an XOR of the IV and the second block plaintext, which defeats the purpose of CBC mode.

Which means you could simply decrypt your second block by XORing the second ciphertext block with the IV, since the key already canceled out, and the "chaining" doesn't apply because the first message is all 0s.

Notice that anyway, doing CBC mode with an XOR with a fixed key $K$ as an block cipher actually cancels the key $K$ for all  odd blocks:
$$\begin{aligned}
C_0 &= K \oplus M_0 \oplus IV  \\
C_1 &= K \oplus M_1 \oplus C_0 = K \oplus M_1 \oplus K \oplus M_0 \oplus IV =   M_1 \oplus M_0 \oplus IV   \\
C_2 &= K \oplus M_2 \oplus C_1 =K \oplus M_2 \oplus M_1 \oplus M_0 \oplus IV \\
C_3 &= K \oplus M_3 \oplus C_2 = M_3 \oplus M_2 \oplus M_1 \oplus M_0 \oplus IV \\ \cdots
\end{aligned}$$

This can also help you.


Why is OTP not vulnerable to brute-force attacks?

Brute force on OTP will give you all sorts of messages which are meaningful and not meaningful.

For example, you have a 4-character encrypted text: weaw. Now brute-forcing will give you all sorts of meaningful and not meaningful messages like:

erwe
hell
road
....

Now, which one was the real message? That would be difficult, rather impossible to guess.


The problem is that two partial evaluations of same length $\ell$ will have the form
$R_0 B_1 R_\ell^{-1}$
and
$R_0 B_2 R_\ell^{-1}$.
Thus, because the attacker possible knows $B_1$ and $B_2$, they can learn something
about the branching program that is obfuscated.
Encoding these randomized matrices with the multilinear map hides (or at least tries to hide) these relations.
Consider the security definition of iO.
It says that an attacker chooses two equivalent branching programs $P_1$ and $P_2$, sends them to an obfuscator, and then receives an obfuscated program $P$. The goal is to guess if $P$ corresponds to $P_1$ or $P_2$.
Now, if the obfuscation is done without the multilinear map, an attacker can break the security definition as follows:

Choose two different matrices $A$ and $B$;

Choose a length-2 branching program $P_1$ with a single input bit as follows:
$$\text{bit 0:} ~ ~ ~ ~ I  ~ ~ ~ ~ A$$
$$\text{bit 1:} ~ ~ ~ ~ I  ~ ~ ~ ~ B$$
$$\text{inp}(1) = \text{inp}(2) = 1$$

Choose a length-2 branching program $P_2$ with a single input bit as follows:
$$\text{bit 0:} ~ ~ ~ ~ A  ~ ~ ~ ~ I$$
$$\text{bit 1:} ~ ~ ~ ~ B  ~ ~ ~ ~ I$$
$$\text{inp}(1) = \text{inp}(2) = 1$$

Notice that $P_1(0) = P_2(0) = A$ and $P_1(1) = P_2(1) = B$, thus, they are equivalent programs.
Now, if $P$ obfuscates $P_1$, it is of the form
$$\text{bit 0:} ~ ~ ~ ~ R_1 \cdot R_2^{-1} ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot A \cdot R_3^{-1}$$
$$\text{bit 1:} ~ ~ ~ ~ R_1 \cdot R_2^{-1}  ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot B \cdot R_3^{-1}$$
Thus, we can distinguish the obfuscated programs by checking if the matrices
corresponding to the first step are equal.


Your design seems to be a byte-wise generalization of Jennings' multiplexed generator rather than the alternating step generator.

S. M. Jennings, “Multiplexed Sequences: Some Properties of the Minimum Polynomial,” Lecture Notes in Computer Science, vol. 149, 1983.

I believe designs like hers [may even be byte based for efficiency] have been used in satellite TV encryption in the 1980s-1990s, but can't find the reference now.

There has been cryptanalysis showing such schemes may not be as strong as first thought.

Jovan Dj. Goliv, Mahmoud Salmasizadeh, Ed Dawson: Statistical Weakness of Multiplexed Sequences, Finite Fields and Their Applications 8(4):420-433, 2002.


How to sign a large file for random-access reading?

Is there a RSA scheme which produces fixed size signatures?

Normally RSA signatures are fixed size. Depending on encoding and the details included, the length may vary by at least a few bytes, though. There is usually a known maximum at least.

  The last block can be as small as 1 byte. Is there any cryptographical risk doing this?

No. As long as a good signature scheme (including a secure hash and proper padding in the case of RSA) is used the length of the data signed does not matter.

  Is this globally a good idea?

Firstly, signing each block individually does not allow verifying that their order is correct – an attacker could reorder the blocks and the corresponding signatures. You would need to add at least an index of the block to the signed data to verify that. (You likely also need to sign the file identity and length to prevent moving blocks between files or leaving data off the end.)

It also seems somewhat inefficient — RSA signatures are quite long and computing them is relatively time-consuming. But you know best whether the performance is sufficient or the space usage a problem in your use case.

Signing a hash list or hash tree of the data would allow storing a shorter signature and verifying blocks faster — you only need to verify a signature of the hashes once, then it suffices to check that each block hashes to the correct value. It would also take care of verifying the ordering. However, it would require reading and verifying a length-dependent list/tree of hashes before reading the actual data, which may be a problem.


Birthday Attack Probability of Collision in Introduction to Modern Cryptography

We say $f(n)=\theta(g(n))$ if
$$
cg(n)\leq f(n)\leq Cf(n),\quad 0<c\leq C<\infty
$$
as $n\rightarrow \infty.$

Apply the $\ell-$bit hash function to $k$ randomly chosen inputs. Let $n=2^{\ell}.$

The chance of two values picked being unique is $n- 1 \over n$ because when picking the second value you only have $n-1$ unique values left in the range. Repeating this argument,
the chance of picking $t$ unique values is:

$${n - 1 \over n} \times {n- 2 \over n} \times \cdots \times {n- (k- 1) \over n}.$$

This is exactly the same as the limit for the birthday paradox.

Now $1-x \leq e^{-x}$ and hence
$1-(v/n) \leq e^{-v/n}$ for $1\leq v\leq n,$ and thus the probability of no collisions is at most
$$e^{-{1 \over n}} \times e^{-{2 \over n}} \times \cdots \times e^{-{k - 1 \over n}} =\exp\left\{-{1 + 2 + \cdots + (k-1) \over n}\right\}$$
which equals
$$e^{-{k(k-1)/2 \over t}} = e^{-{k(k-1) \over 2n}} $$

The chance of a collision is 1 minus this quantity. Plugging in $k=\sqrt{n}=\sqrt{2^{\ell}}$ yields a value not too far from $1/2.$


Which block cipher parameters should be kept secret?

In you opinion which of the parameters of a block cipher (e.g., algorithm name, mode of operation, IV (if any), key length) are essential to keep secret?

I believe that it is essential that you keep the key secret.

If there is any other aspect of the cipher that you must keep secret (that is, you become insecure if it is revealed), then your cipher is 'broken'.

We can assume that the attacker can learn any long term aspect of your cipher implementation, such as the cipher name, mode of operation, key length.  There are a number of possible ways they might learn it, such as an employee accidentally (or deliberately) leaking it, or if the attacker just obtains your implementation and dissects it.  Hence, for security, we want to depend solely on something that we update routinely (such as the key).  If the attacker learns the key, that limits the damage (as they can decrypt the traffic encrypted with that key, but nothing after we update the key).  This idea is referred to as Kerckhoff's principle.

Now, you list the IV; that is typically updated constantly.  On the other hand, we generally use it to refer to information that need not be secret.  If it does have to be secret, then it really is part of the key, and should be considered that way.


advances in usability for cryptography/authentication

This is an active area of research. There have been attempts at creating usable security tools and lots of user studies of existing tools (typically with critical results).

A good anthology for work in this area (a few years old now) is Security and Usability edited by Lorrie Cranor and Simson Garfinkel.

There is also a workshop every year called Symposium on Usable Privacy and Security (SOUPS) with lots of papers. However the best usable security papers tend to appear at the top security conferences (Oakland, Usenix Security, and CCS).


Is there any way to test how secure is a new cryptosystem?

The general answer given to all budding cryptographers is "don't."  Your system is not secure and will be trivially broken if anyone starts using it.

This advice is given out in general because it handles the 99% case.  99% of the time, people who think they have a good algorithm are simply wrong.

Now the cases that remain are the individuals with enough drive to actually learn cryptography.  There's still a very good chance that the first system these people put together has major holes, but there's a big difference between them and the 99%: they're willing to take the time to be objective and learn how to do it properly.

For those, I refer to a famous quote: "Any idiot can design a cryptographic system that they themselves cannot break."  Your system will not be considered secure until others have beaten on it.  Ideally, big names need to beat on it.  However, therein lies a conundrum.  It is far easier to develop a bad cryptographic system than to prove that it's bad.  The big names in the business don't have time to spend on your algorithm until they have a reason to believe it isn't trivially weak.

This is a chicken and the egg problem.  You can't get your algorithm accepted without the big names agreeing it's secure, and the big names wont look at it until your algorithm has seen some acceptance.  What are you to do?

The standard accepted answer in the industry is that, while it means little if someone says "hey, I think I have a good cryptographic algorithm," it means far more if someone with a name for themselves says it.  The community has an accepted way to build a name for yourself: breaking the algorithms of others.  If you want your algorithm to be taken seriously, you first prove that you're the kind of person who knows how to brutally attack their algorithm by showing how well you can break others.

Bruce Schneier, one of those "big names," put together an online self-paced course on this topic.  It's titled A Self-Study Course in Block-Cypher Cryptanalysis.  It consists of several dozen broken algorithms which he has carefully arranged in what he perceives to be an order of difficulty.  In the case of most of them, the task is simple:

Become familiar with a particular (broken) algorithm.
Read a paper about how that algorithm was broken.
Break the algorithm yourself, following the general path laid out by the paper

It's a sort of "following in the footsteps of giants" approach.  It introduces you to a wide array of attacks and encourages you to not only know they exist, but have experience working them.  This way, you are in a good position to try to apply those attacks to your own algorithms.

Once you go through the course, try to find publications of algorithms which have not been broken yet, but do not have the notoriety needed for the big names to go after them.  Break those, publish your results.  This will begin building up your name, and eventually you will be taken seriously when you put forth your own algorithms.

The path to a secure algorithm is long an arduous.  Consider the path undertaken by SHA-3:

Submissions for the NIST hash competition were accepted in 2008.  The total number of submissions is not known because some were rejected before they were even let into the first round.  There were 57 publicly known submissions, 6 of which were rejected outright with no further explanation.
The first round, with 51 submissions were officially announced on December 9, 2008.  There was a conference in February where the algorithms were presented and NIST's criteria for acceptance to round 2 was publicized.  The round ended on July 24, 2009 when NIST published the list of algorithms which made the cut:

10 algorithms were officially withdrawn from the competition after their authors conceded substantial weaknesses.  NIST considers all of these algorithms "broken in round 1"
16 algorithms were not officially conceded, but significant cryptographic weaknesses were found.  NIST considers all of these algorithms "broken in round 1"
11 algorithms were not accepted into round 2.  These were not conceded, and there were no glaring weaknesses.  However, in the name of efficiency of the competition, they were rejected.  Some were rejected because they appeared to be weaker than the others (yet not broken). Some were rejected due to performance issues.  NIST does not consider these algorithms "broken."

14 algorithms were accepted into round 2, down from 53.

Round 2 was a lot more demanding.  Now these algorithms had substantially more attention put on them.  The community was given a year and a half to attack these algorithms, publicizing the final round of advancements on December 10, 2010

9 algorithms were rejected, though NIST points out that none of them were considered "broken" during that period.  They just didn't make the cut.
5 algorithms were accepted into the final around.

The final round lasted almost 2 years, with the winner announced on October 2, 2012.  The entire cryptographic community was paying attention to this, with big names trying to break every one of these 5 algorithms.  In the end, Keccak was chosen as the victor, and is now known as SHA-3

So when you compare the security of your system to a "big name" cryptographic algorithm like RSA, be aware.  This is the kind of scrutiny that the algorithms go under.  If you enjoy that kind of thrill, I highly recommend going through Schneier's self-taught course.  And who knows.  Maybe your algorithm will be the one in a million that is truly secure!  You never know unless you try.

As an aside, you mentioned that you are using Elliptic Curves.  In that particular field, make sure you pay attention to the backdoor issues brought up by Dual EC DRBG.  Those algorithms in particular will be given extra scrutiny for backdoors because of how public the issues of Dual EC were.  You will want to take extra care to make sure the public is aware that your numbers were chosen in an acceptable quasi-random manner (taking digits of pi or e are popular)


NIST FIPS 180-4 on page 13 defines the padding scheme for SHA-512 as;

  Suppose that the length of the message, $M$, is $\ell$
  bits.  Append the bit 1 to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation
  $$\ell + 1 + k \equiv  896 \bmod 1024$$

So you first append 1, then calculate the number of the zeroes by the formula, append the zeroes, then append the 128-bit binary-encoded length.

For example: If your message size is $\ell =49$ than

$$49 + 1 + k \equiv  896 \bmod 1024$$ solving for minimal $k = 896-49-1 = 846$. Therefore the padded message is

$$ \text{padded message } = \overbrace{M}^{49-bit} \mathbin\| \overbrace{1}^{1-bit} \mathbin\| \overbrace{000\cdots 000}^{846-bit\; 0s} \mathbin\| \overbrace{00000000\cdots00110001}^{128-\text{bit binary encoded length } \ell} $$

Like all uniquely removable padding schemes this padding scheme also uniquely removable, usually called unpad. Get the last 128-bit, then remove all trailing zeros and the first 1 from the end. The rest will be the message and check the message size to ensure that it matches.

The length encoding in the NIST standard sets an upper limit for the size of the message to be hashed. One can hash at most $2^{128}$-bit-sized input messages. Before the upper limit, one has limited by the current technology.

SHA512, like all Merkle–Damgård constructions SHA512 has also vulnerable to length extension attack. Instead of SHA512 using SHA3 or Blake2 series are preferable. After SHA3, the stripped versions SHA512-384 and SHA512-256 are designed to have resistance to length extension attack. They have also different initial values that provide the domain separation from SHA512.


Is it safe to use RSA as a proof-of-work system?

Is this usable? Or does the generation of the modulus outweigh any
  gains in the difference in signing time?

No, it does not work. The generation cost itself isn't too important, because signing any one nonce doesn't help the client sign any other nonce, so you can just use a single key all the time (if you had to create a new keypair for every puzzle, this would be very impractical and nobody would use it).

But the problem is that the advantage of the server on the client is asymptotically more or less zero, so this is quite useless as a proof of work scheme. See D.W.'s answer for one way of breaking the scheme.

Another way similar to D.W.'s is to realize that your scheme requires the client to compute, given a random  nonce $a$ and a work factor $k$, modulus $n$ and private exponent $d$:

$$\text{proof} = ((a^d)^d)^{\cdots ~ k ~ \text{times}} ~ \text{mod} ~ n$$

And this is equal to:

$$\text{proof} = a^{d^k} ~ \text{mod} ~ n$$

But because the client knows $d$ (you gave it to him!) he can factorize $n$ in constant time and compute $\varphi{(n)} = (p - 1)(q - 1)$, which gives him the ability to reduce the inner exponent:

$$\text{proof} = a^{d^k ~ \text{mod} ~ \varphi{(n)} } ~ \text{mod} ~ n$$

The client can calculate this in $\log{k}$ modular multiplications or squarings by $d$, and $\log{n}$ (on average) modular multiplications or squarings by $a$. But the server has to do pretty much the same amount of work - the only difference is it saves some time because $e$ is smaller than $d$. The gain is minimal and very difficult to control, since there's a point where you just can't make $e$ any smaller and need to increase $n$ to compensate.

In conclusion, this is not a good proof-of-work scheme, as it provides basically no control over the work factor desired and the server will need to work about just as much as the client for realistic values of $n$ and $k$.

  If so, how could I make it usable, if at all?

However, it's possible to take your scheme a step further to make it cleaner (and not depend on RSA). The idea is to choose a "difficulty factor" $t$, a random number $a$, a large $n = pq$, and ask the client to compute:

$$\text{proof} = a^{2^t} ~ \text{mod} ~ n$$

The client will require $t$ squarings to achieve this (there is no known way to do better, and it cannot be parallelized to any significant degree), while the server, knowing the factorization of $n$ (since it generated it) can just compute:

$$e = 2^t ~ \text{mod} ~ \varphi{(n)}$$

And hence, from Euler's Theorem:

$$\text{proof} = a^e ~ \text{mod} ~ n$$

Which the server can then compute in logarithmic time. In effect, the server only needs $O(\log{nt})$ time, but the client needs $O(t)$ time. By making $t$ arbitrarily large, you can fine-tune the amount of work you want the client to do, linearly, but the work stays logarithmic for the server, which is practical.

The generation cost is also irrelevant, because the server can generate it once and reuse it all the time with different values of $a$ (that's not always true, but in this case it is - the attacker can't use the results of a previous proof of work to quickly solve another assuming $a$ is random and $n$ is large).

Note your scheme doesn't care if the client can factorize $n$ since you are basically giving away $d$, but in this scheme it is imperative that $n$ be large enough so that factorization is not possible. But this is easy to address, just create a 2048-bit modulus (or 4096-bit if you are paranoid) and be done with it.

For more details and supporting theory on this method, see:

Time-lock puzzles and timed-release Crypto, Ron Rivest, Adi Shamir, David Wagner.

Puzzle description for the MIT time capsule.


Rigorous practical pseudorandom generators

It is worth mentioning that there is a connection in complexity theory often called "Hardness v Pseudorandomness" that makes this question somewhat difficult.
It may not be surprising that given a strong enough PRG, one can derandomize certain randomized algorithms, i.e. trying to prove $P = BPP$ can be done by giving a provably strong enough pseudorandom generator.
What is perhaps surprising is that this is intimately connected to the existence of hard problems in $NP$.
Specifically, if there is a problem in $NP$ that requires exponentially sized circuits, I believe it implies that $P = BPP$ via the construction of an explicit pseudorandom generator.
Moreover, some form of the reverse holds --- being able to derandomize $P$ (via the construction of a provably good PRG of good enough parameters) leads to circuit lower bounds, which is a notoriously hard subject.
Keywords for this are things like "Nisan-Wigderson PRG", or you can look at these notes for some pointers.
I think (but am fuzzy on the details) that one can generalize the above to other circuit classes as well, i.e. the existence of explicit provably secure PRGs against some circuit class is intimately related to circuit lower bounds against some related circuit class.
As in general most circuit lower bounds we can prove are against fairly restricted models of computation, I would expect that the literature on "rigorous PRGs" is restricted to PRGs that are secure against relatively weak forms of computation.
I don't know a great place that summarizes this all --- I do not myself work in the area, but heard about it from someone who does. Perhaps their thesis would be a good reference, but I'll admit that I have not personally read it.


Could someone please elaborate on how $(c^d \bmod n) \bmod p = c^d \bmod p$, given that $n = pq$, where $p$ and $q$ are prime numbers?

Well, lets see if we can go through it from the basics.
$x \bmod y$ is the unique integer $x + \ell y$ that satisfies $0 \le x + \ell y < y$, for some integer $\ell$ (which might be positive, negative or zero)  I will skip the parts that prove that, if $x, y$ are both integers and $y > 0$, then there exists such an $\ell$ and it is, in fact, unique.
Now, when we have $(x \bmod pq) \bmod p$, we can replace the inner $(x \bmod pq)$ with $x + \ell_1 pq$, we get $x + \ell_1 pq \bmod p$.  This in turn becomes $x + \ell_1 pq + \ell_2 p$.  We further note that $\ell_4 = \ell_1 q + \ell_2$ is an integer (which we will denote at $\ell_4$) [1], and so we have:
$$(x \bmod pq) \bmod p = x + \ell_4 p$$
On the other side, $x \bmod p$ is the same as $x + \ell_3 p$, that is,
$$x \bmod p = x + \ell_3 p$$
So, on one side, we have $x + \ell_4 p$, which is a value between 0 and $p-1$.
On the other side, we have $x + \ell_3 p$, which is also a value between 0 and $p-1$.
Since both $\ell_3$ and $\ell_4$ are integers, these must be the same, and hence the original values $(x \bmod pq) \bmod p$ and $x \bmod p$ must also be the same.
Then, replace $x$ with $c^d$ and $pq$ with $n$, and there you go...
[1]: BTW: this is the step where we assume that $p$ is a factor of $n$ if that is not true, then relation will not hold in general.


Why did they choose $x^4+1$ for the MixColumns step in Rijndael/AES?

The idea is that when you're multiplying two four-term (four-byte) polynomials together, you could wind up with a seven-byte polynomial, but you need to reduce it to another four-byte polynomial. They chose $x^4 + 1$ because

$x^i \mod (x^4 + 1) = x^{i \mod 4}$

See this for an example.


Why does Hasse's theorem sometimes seem to be invalid?

The order of a point on $E(\mathbb F_p)$ merely divides the cardinality $\#E(\mathbb F_p)$ (or $|E(\mathbb F_p)|$) of the group.  If $\#E(\mathbb F_p)$ has composite order, it may have small prime factors and therefore there may be low-order points that don't generate all of $E(\mathbb F_p)$.  For example, on any Montgomery curve $y^2 = x^3 + A x^2 + x$, the point $(0, 0)$ always has order 2, even if the curve has large order like Curve25519, where $p = 2^{255} - 19$ and $A = 486662$, whose order is $8\ell$ for $\ell$ near $2^{252}$.  But the standard base point $(9, \cdots)$ on Curve25519 has order $\ell$, and $(8, \cdots)$ has order $8\ell$.


DSA: Authentication and assurance of authorized parties

If I'm understanding things correctly, you want to make sure that the public key you receive actually belongs to the person you want to communicate with.

Thus you want to avoid MITM attacks, which is non-easy.
Standard (TLS/S/MIME/...) solution would be to create a certificate signed by someone you trust to assure you that the particular public key belongs to the entity you expect.

Another solution would be to exchange some data over a second (trusted) channel containing a hash of the public key assuring you that the key belongs to this person. It is sufficient to do this once for the life-time of a key.

The last method of defense I'm aware of is identity-based systems or implicitly-signed systems. This is highly complex and I'd rather go with certificates in large scale and with second channel in smale-scale.


Chosen Ciphertext Attack with a theoretical decryption machine

Well, one obvious way he can decrypt ANY cipher block is just give it to his Decryption machine; that machine will give him the matching plaintext block, which is precisely what he is looking for.

Now, normally when we give an attacker a decryption oracle, and give him a challenge "decrypt this specific message", we put a limitation on the oracle that it won't decrypt that specific message; let us assume that there is such a limitation (even though it was not specifically listed).

So, we know that the encryption algorithm obeys $E(P_1 \oplus P_2) = E(P_1) \oplus E(P_2)$.

First question: does this imply that $D(C_1 \oplus C_2) = D(C_1) \oplus D(C_2)$ (where $D$ is the inverse of $E$)?  How would you show that?

Next question: if $D(C_1 \oplus C_2) = D(C_1) \oplus D(C_2)$, how would you select a set of ciphertexts $\{C_1, C_2, ..., C_n\}$ such that any ciphertext can be expressed as the exclusive-or of some subset of $C_i$?  How can you use this observation to decrypt this arbitrary ciphertext?

Bonus question (which goes beyond what they asked): how can you extend this observation if you were given a set of random plaintexts and their encryption?


The problem is proven unsolvable if the number $t$ of faulty machines of total $n$ machines have a ratio $t \geq \frac{n}{3}$. So for $t < \frac{n}{3}$ it can be solved. Or it can be solved if the result does not have to be certain agreement but allows some uncertainty (which should be small), which might allow a higher threshold.