We can get some clues from the various Internet RFCs defining or mentioning the three algorithms. There appear to have been two advantages of MD4, and subsequently MD5:

Performance
Licensing

It also appears that an attack on MD2 was expected long before one was found for MD5, even if none was actually found.

August 1989: RFC 1115 defines MD2. It is presented as part of a series of RFCs for Privacy Enhanced Mail. It states simply:

  It has been provided by Ron Rivest of RSA Data Security, Incorporated for use in
     support of privacy-enhanced electronic mail, free of licensing
     restrictions.

The "specification" is simply the source code of a reference implementation in C, dated "10/1/88" (presumably 1st October 1988)

October 1990: RFC 1186 defines MD4. Oddly, there is no mention of MD2 in the entire document.

Unlike RFC 1115, MD4 is presented as a general purpose algorithm, rather than as part of a particular framework:

  The MD4 algorithm is thus ideal for digital signature applications, where a large file
     must be "compressed" in a secure manner before being signed with the
     RSA public-key cryptosystem.

Intellectual property rights are also more clearly waived for any and all purposes:

  The MD4 algorithm is being placed in the public domain for review and
     possible adoption as a standard.

There is a clear emphasis on the algorithm's performance:

  The MD4 algorithm is designed to be quite fast on 32-bit machines.
     On a SUN Sparc station, MD4 runs at 1,450,000 bytes/second.  On a DEC
     MicroVax II, MD4 runs at approximately 70,000 bytes/second.  On a
     20MHz 80286, MD4 runs at approximately 32,000 bytes/second.  In
     addition, the MD4 algorithm does not require any large substitution
     tables; the algorithm can be coded quite compactly.

Buried in the summary is a disclaimer that this is a novel algorithm, and may need further scrutiny:

  The MD4 algorithm has been carefully scrutinized for weaknesses.  It is,
     however, a relatively new algorithm and further security analysis is
     of course justified, as is the case with any new proposal of this
     sort.

April 1992: RFCs 1319, 1320, and 1321 respectively re-define MD2 and MD4, and define MD5

Although clearly published as a series, there doesn't appear to be any comparison of MD2 against MD4 or MD5 in any of these three. All three RFCs include a reference implementation that actually implements all three algorithms.

RFC 1319's main purpose is to provide a textual description of the algorithm, and a more portable reference implementation. It also incorporates the purpose statement applied to MD4:

  The MD2 algorithm is intended for digital signature applications, where a
     large file must be "compressed" in a secure manner before being
     signed with a private (secret) key under a public-key cryptosystem
     such as RSA.

Although it goes on to say:

  License to use MD2 is granted for non-commerical Internet Privacy-Enhanced Mail

Which appears to be more restrictive than "placed in the public domain", and makes it ambiguous whether the algorithm could be used outside that realm, if it was protected by any intellectual property laws.

Under "Security Considerations", confidence in MD2's security is stated bluntly:

  The level of security discussed in this memo is considered to be
     sufficient for implementing very high security hybrid digital
     signature schemes based on MD2 and a public-key cryptosystem.

RFC 1320 is a minor revision of the previous MD4 description, with the new reference implementation.

The concerns previously mentioned in the Summary are now prominent in the Security Considerations section, with a mild recommendation to try MD5 instead:

  We do not know of any reason that MD4 would not be sufficient for
     implementing very high security digital-signature schemes, but
     because MD4 was designed to be exceptionally fast, it is "at the
     edge" in terms of risking successful cryptanalytic attack. After
     further critical review, it may be appropriate to consider MD4 for
     very high security applications. For very high security applications
     before the completion of that review, the MD5 algorithm [4] is
     recommended.

RFC 1321 is the first to define MD5. Its introduction includes most of the same claims of speed, compactness, and general applicability as MD4, along with an explanation for why a new algorithm was designed:

  The MD5 algorithm is an extension of the MD4 message-digest algorithm. MD5 is slightly slower than MD4, but is more "conservative" in
     design. MD5 was designed because it was felt that MD4 was perhaps
     being adopted for use more quickly than justified by the existing
     critical review; because MD4 was designed to be exceptionally fast,
     it is "at the edge" in terms of risking successful cryptanalytic
     attack. MD5 backs off a bit, giving up a little in speed for a much
     greater likelihood of ultimate security. It incorporates some
     suggestions made by various reviewers, and contains additional
     optimizations.

It also includes the same unambiguous licensing statement:

  The MD5 algorithm is being placed in the public domain
     for review and possible adoption as a standard.

March 1998: RFC 2313 references all three algorithms. After repeating that MD4 is "on the edge" because of its emphasis on speed, it compares MD2 and MD5:

  MD5, which has four rounds and is proportionally slower
               than MD4, is recommended until the completion of MD4's
               review. The reported "pseudocollisions" in MD5's internal
               compression function [dBB93] do not appear to have any
               practical impact on  MD5's security.

  MD2, the slowest of the three, has the most conservative
               design. No attacks on MD2 have been published.

April 2002: RFC 3279 references MD2. It includes this interesting note, which confirms my suspicion about licensing issues with MD2:

  MD2 was developed by Ron Rivest for RSA Security.  RSA Security has
     recently placed the MD2 algorithm in the public domain.  Previously,
     RSA Data Security had granted license for use of MD2 for non-
     commercial Internet Privacy-Enhanced Mail (PEM).

It doesn't give any reference for this release, so it's not clear how "recent" it was.

It also somewhat contradicts the assertion quoted above from RFC 2313, citing a partial attack on MD2 published in 1995:

  At the Selected Areas in Cryptography '95 conference in May 1995,
     Rogier and Chauvaud presented an attack on MD2 that can nearly find
     collisions.  Collisions occur when one can find two different
     messages that generate the same message digest.  A checksum operation
     in MD2 is the only remaining obstacle to the success of the attack.
     For this reason, the use of MD2 for new applications is discouraged.

March 2011: RFCs 6149, 6150, and 6151 retire or update the status of all three algorithms. 19 years after the previous series, we get some retrospective analysis.

RFC 6149 retires MD2, citing as rationale:

  MD2 was published in 1992 as an Informational RFC.  Since its
     publication, MD2 has been shown to not be collision-free [ROCH1995]
     [KNMA2005] [ROCH1997], albeit successful collision attacks for
     properly implemented MD2 are not that damaging.  Successful pre-image
     and second pre-image attacks against MD2 have been shown [KNMA2005]
     [MULL2004] [KMM2010].

It gives a list of RFCs which reference MD2; most appear to have offered it as an option alongside MD5.

More interestingly for our purposes, it notes that:

  MD2 has also fallen out of favor because it is slower than both MD4
     [MD4] and MD5 [MD5].  This is because MD2 was optimized for 8-bit
     machines, while MD4 and MD5 were optimized for 32-bit machines.  MD2
     is also slower than the Secure Hash Standard (SHS) [SHS] algorithms:
     SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512.

RFC 6150 retires MD4, with a similar, but stronger rationale. Amusingly, there are a number of accidental mentions of "MD2" instead of "MD4" in the RFC text, but there doesn't appear to be any explicit comparison.

Unlike MD2, the RFC includes extensive documentation on breaks in MD4; it seems Rivest was right to warn of its untested nature in 1992.

RFC 6151 doesn't go as far as retiring MD5, instead advising against some uses.

  Where the MD5 checksum is used inline with the protocol
     solely to protect against errors, an MD5 checksum is still an
     acceptable use.

but

  MD5 is no longer acceptable where collision resistance is required
     such as digital signatures.

It makes no mention of MD2 or MD4, other than referencing papers that covered both MD4 and MD5 in their cryptanalysis.


How to show something is not a one-way function?

Actually the proof that $h$ is one-way is not that trivial... First, a reminder on definitions. A function $f$ is (strongly) one-way if for all probabilistic polynomial-time adversaries $A$, all polynomials $p$ and all sufficiently large $n$, we have
$$\mathrm{Pr}[A(f(U_n),1^n) \in f^{-1}(U_n)] < \frac{1}{p(n)}$$
(where $U_n$ represents a random variable with uniform distribution over all strings of length $n$). Put in words, we choose uniformly a string $x$ of length $n$, we compute $y = f(x)$ and we run $A$ on input $(y,1^n)$, noting its output $x'$. Then the definition states that the probability that $f(x') = y$ is less than $1/p(n)$. We prove that $h$ is one-way by contradiction. That is, assuming that $h$ is not one-way, we show that $f$ is not one-way, contradicting our hypothesis.

So what does it mean to say that $h$ is not one-way. It is easily seen that "all sufficiently large" is equivalent to "all but a finite number", so we obtain the following. There is a probabilistic polynomial-time algorithm $A_h$ and a polynomial $p_h$ such that for infinitely many $n$ we have
$$\mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \ge \frac{1}{p_h(n)}.$$
We restrict out attention to such $n$. We will show that there is a probabilistic polynomial-time algorithm $A_f$ and a polynomial $p_f$ such that for all such (infinitely many) $n$, we have
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)] \ge \frac{1}{p_f(n)}.$$

$A_f$ works as follows, on input $(f(U_n), 1^n)$ (that is, on input $(y,1^n)$ where $y = f(x)$ for a uniformly chosen $x$ of length $n$).

Run $s \gets A_h(y||0,1^n)$. If $f(s) = y$, output $s$ and halt.
Run $t \gets A_h(y||1,1^n)$. If $f(t) = y$, output $t$ and halt.
Output $0^n$ and halt.

$A_f$ clearly runs in probabilistic polynomial-time, and we analyse its success probability. We observe that if the last bit of $U_n$ is $0$ and the call to $A_h$ in step 1 succeeds, then $A_f$ will succeed. Likewise, if the last bit of $U_n$ is $1$ and the call to $A_h$ in step 2 suceeds, $A_f$ succeeds. Hence (letting $\mathrm{last}(X)$ be the last bit of $X$)
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] $$
and
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1].$$

Now,
$$\begin{align*}
\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)]
  &= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \\
  &= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \\
  &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \\
  &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \\
  &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \\
  &\ge \frac{1}{p_h(n)}.
\end{align*}$$


yes, plain textbook RSA is only OW-CPA (not even IND-CPA).

You can construct an adversary $\mathcal{A}$ which wins in the IND-CCA2 game:

$\mathcal{A}$ sends $m_0=0$ and $m_1=1$ as challenge ciphertexts to be encrypted

$\mathcal{A}$ receives the ciphertext $c_b = Enc(pk, m_b) = (m_b) ^ e \mod N$ for some uniform random $b \in \{0,1\}$.

$\mathcal{A}$ uses the homomorphic property of RSA to obtain a ciphertext for $2\cdot m_b$:

$\mathcal{A}$ computes $c_b' = (2^e \cdot c_b) \mod N = (2 \cdot m_b) ^ e \mod N$

$\mathcal{A}$ sends $c_b'$ to the decryption oracle. and receives the decryption which is either 0 (then $b$ was 0) or 2 (then $b$ was 1).
$\mathcal{A}$ outputs $b$.

$\mathcal{A}$ can query the decryption oracle on the ciphertext $c_b'$ since this ciphertext wasn't received by
$\mathcal{A}$ from the encryption oracle.

The decryption oracle doesn't do any integrity checks, so it will successfully decrypt the ciphertext.

If I didn't miss anything, the probability of
$\mathcal{A}$ winning this game is 1.

You could also beak RSA IND-CPA security by testing which message was encrypted (by encrypting both messages yourself).
This works because textbook-RSA encryption is deterministic.
A scheme that isn't IND-CPA secure, can't be IND-CCA secure.

I hope I could help!


Turing's (still?) classified inference engine algorithm?

This doesn't answer your question, but you may find clues in two wartime papers of Alan Turing which were formerly classified were declassified and published in the UK National Archives in 2015, and are now available on the arXiv:

  Alan M. Turing, ‘The Applications of Probability to Cryptography’, UK National Archives HW 25/37, 1942, arXiv:1505.04714.

  Alan M. Turing, ‘Paper on Statistics of Repetitions’, UK National Archives HW 25/38, 1942, arXiv:1505.04715.

It may be possible to reconstruct, from the principles enumerated therein, what algorithm Turing would have implemented in the Colossus to perform the feats it is known to have been able to perform.


Privacy of randomness using extractors and PRGs

Yes, a true random number generator (TRNG) is only as secure as the privacy of the input randomness.  We call the input randomness entropy. You're conflating a TRNG and a pseudo random number generator (PRNG) with a randomness extractor.

A randomness extractor is simply a statistical combobulation and transmogrification of an arbitrary input distribution to a uniform distribution.  And to reduce inevitable correlation to negligible amounts. It's a component downstream of an entropy source or state. That's it. So an extractor might convert a correlated and normally distributed set of physical samples to an uncorrelated and uniformly distributed set.

There's no strict cryptographic security involved other than (input entropy) > (output). The security of the TRNG comes from the fact that since less entropy is output than input, it is mathematically impossible to discover  the original entropy.  Some people like to use cryptographic functions as the basis of randomness extractors, but that's not really necessary. However since this is a crypto forum...

Two examples:-

Have a 128 bit counter as a state. Repetitively increment that state.  Then encrypt that state with a keyed cipher like AES. You could argue that the encryption part forms a randomness extractor in a PRNG.  However, this is not a common paradigm.
Have some physical process generating a truly random digital signal with a wonky distribution.  Use some matrix multiplication or cryptographic hashing to produce a uniform distribution with an output bias < $2^{-64}$. This multiplication /hashing component is the randomness extractor part of a TRNG.

Now of course if someone knew the original state /entropy, the output sequence would be predictable. Unless you encrypted it with another cipher using a private key, or hashed it with a concatenated private IV. But what would the advantage be over a common PRNG in that case? It would be tantamount to example 1, but worse in that you'd have no idea of prejudice in the public sequence.


Research Guidance on Elliptic Curve Cryptography

Firstly, I am not sure about how I should narrow down the topic.

It is better to ask your advisor to help you for selecting a good research topic.

Secondly, which prerequisite knowledge do I need? Also, do you suggest any foundational books on the topic?

A roadmap for learning Elliptic Curve Cryptography:

Beginner: you can learn the basic of ECC by reading Chapter 9 of Understanding Cryptography book and/or some good online tutorials and/or by ECC workshop schools.
Intermediate: for a better understanding, you can read these three books: Elliptic Curves: Number Theory and Cryptography, Guide to elliptic curve cryptography and Handbook of elliptic and hyperelliptic curve cryptography.
Advanced: for a deep dive into the mathematics of elliptic curves, you can read Joseph H. Silverman's books.
Implementation: Implementing Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography by Martin Kleppmann.
Research: for selecting a research topic, you can read last research papers of the Workshops on Elliptic Curve Cryptography.


Read/Write speed of encrypted sparsebundle

It's recommended by Disk Utility to go with 128-bit AES because 256 is
  "slower"

Yes, AES-256 is 40% slower than AES-128, because it has 14 as opposed to 10 internal encryption rounds.

  This got me thinking, how slow is 128?

On a modern CPU, AES-256-CTR runs at about 1cpb (cycle per byte), meaning AES-128-CTR will roughly run at 0.75cpb (this assumes that the implementation is properly optimized). If you now have a CPU running at 3GHz you get about 4GB/s encryption throughput.

  Will the encryption slow me down?

That very much depends. It depends on the optimization quality of the AES implementation. It depends on the speed of your drive(s). It depends on the load on the CPU during the write / read operations except for the encryption. It depends on the specific CPU, ie whether it has ressources left for encryption.

Usual saying is that it will slow the PC down by a few per cent, so not much.

  Is this just while it's initially encrypting?

Initially it will encrypt the entire area you allocated so an attacker can't distinguish "empty space" from "meaningful data" when looking at it. During the normal usage, only the parts that need changing are changed, meaning you can use the actual size of the data you save / read for your timing calculations.


Verbatim of early work on public-key cryptography?

My wishes largely came true! The GCHQ (briefly) published scans of [1] and [2], and another 1970 document:

[1s]: James Ellis: The Possibility of Secure Non-Secret Digital Encryption
[1.5s]: James Ellis: The Possibility of Secure Non-Secret Analogue Encryption.
[2s]: Clifford Cocks: A Note on 'Non-secret Encryption'.

These scans are excellent, including [2s] which seems to be from a printout of an earlier scan (as visible on an apocryphal annotation on bottom of the second page). The typeset versions of [4] and [1] are very close to [1s] and [2s]; differences are in formatting, typography, and a few transcription typos, like [4] randomly uses MI or M1 where [1s] consistently uses M1.
[1.5s] studies an analog communication over metallic wires trying to resist eavesdropping. It is readily admitted the system is insecure. As apparent to an electronic engineer (even of the 1970s), if an eavesdropper is able to measure both voltage and current on the wire, s/he can break the system.
All in all: it is nice to have these verbatim, but I found nothing that was not essentially known before on the history of public-key cryptography as we know it.


Side-Channel attack on RSA decryption using comparison result with p,q?

Some hints:

You know $p\,q$.
First assume $q<p$ and find $q$ by dichotomic search.
Move to the slightly more difficult case $p<q$.

In dichotomic search, it is given an integer interval $\big[a,b\big]$ and a Boolean function $F$ defined on that interval such that $F(a)\ne F(b)$. Dichotomic search always find $c$ in $\big[a,b\big)$ with $F(c)=F(a)$ and $F(c+1)=F(b)$, using $\approx\log_2(b-a)$ evaluations of $F$. It proceeds by repeatedly computing $c=\lfloor(a+b)/2\rfloor$, stopping when $c=a$, otherwise replacing $a$ or $b$ by $c$ according to if $F(c)=F(a)$ holds or not.

Define $F(x)$ to be the result obtained by submitting $x$ to the side channel. That is $F(x)=\text{true}\iff(x\bmod p)>(x\bmod q)$.

By definition of the $\bmod$ operator in $x\bmod m$ (recognizable by neither having an opening parenthesis immediately on the left of $\bmod$, nor appearing on the right side of an expression with a matching $\equiv$ sign), for all $x$ and all $m>0$ it holds that $0\le(x\bmod m)<m$ and $m$ divides $x-(x\bmod m)$. It follows the properties
$$\begin{align}
x=(x\bmod m)&\iff 0\le x<m&&\text{and}\\
x>(x\bmod m)&\iff x\ge m
\end{align}$$

For the second bullet: When $0\le x<p$ and thanks to the above properties, $F(x)$ reduces to $x>(x\bmod q)$, then to $x\ge q$. Set $a=1$ and $b=\lfloor\sqrt{p\,q}\rfloor$, which we can compute. From the hypothesis $q<p$, we get $q\le b<p$. Therefore when $x\in\big[a,b\big]$ the function $F(x)$ tells whether $x\ge q$. It holds that $F(a)=\text{false}$ and $F(b)=\text{true}$. Thus dichotomic search yields $c$ in interval $\big[1,\lfloor\sqrt{p\,q}\rfloor\big)$ with $F(c)=\text{false}$ and $F(c+1)=\text{true}$, that is $c<q$ and $c+1\ge q$. That reveals $q=c+1$.


How difficult is it to find $b$?

If the matrices within $R$ are of dimension $n \times n$, then we can express the equation $u = a \cdot b + b \cdot a$ as $n^2$ linear equations over the finite field the matrices are over; a simple minded Gaussian Elimination would recover $b$ in $O(n^6)$ steps.

If $u$ is specified explicitly in the public key or the ciphertext or the signature, that'll take $O(n^2)$ space; in other words, to get $n$-bit security, you'll need to take $O(2^{n/3})$ space (field elements).

Currently, the lowest level of security we consider is $n=80$ bit (and that's for constrained devices that really can't do any more); even at that level, you'll end up with using multimegabyte public keys/ciphertext/signatures (at the very least, assuming that there's no better attack).

Now, if your cryptosystem has nice properties, for example, is at least partially homomorphic, it might be of some interest.  However, if it's just a simple public key encryption or signature system, well, something with a relatively low-exponent polytime solution doesn't look at all promising...


First, the expression "password" usually refers to "bad entropy, relatively easy to brute force". And basically the only way to deal with this is to use a decent key derivation function, which is designed especially for passwords. Examples are script, bcrypt or PBKDF2. The main difference to other key derivation functions is that you can tune up the process to actually take a long time - which is wanted in this case.

So, that leads to the first problem: What kind of key derivation do they have? I couldn't find it on their page. So probably, they don't have any.

Considering their "one time authentication", my guess is that they just offer the option to use MAcs. And they use HMAC-SHA1 for this, which is quite on the lower border of acceptable - for legacy systems but not for current development. SHA-1 should not be used today any more, but in HMAC it is not broken so far. But developing a new system should not actually involve such an outdated hash function.
And then: They use $(IV + KEY)$ as the key for the HMAC, which seems not that great either.

That last part actually leads me to believe they don't have session keys but just use that passwords (called $KEY$, I guess) directly, and maybe for both encryption and integrity check.

And then I stumbled over this discussion, which gave a little inside in their development of security features: github

Oh, and it seemds they are using libsodium as cryptographic library. And that one already gives you pretty much everything you would want: KDFs, key exchanges, state-of-the-art encryption and hashes, previously mentioned scrypt, etc. I don't know how good those implementations are, though.

Interestingly, there you can also find the term "onetime authentication" (link), which doesn't really make that much sense. But there you can find this:

  Finally, Poly1305 is not a replacement for a hash function.

Building an HMAC out of this sounds weird.

Overall, it doesn't look too good, and probably their security is lacking.

Coming back to yout questions:

Passwords should never be used as key directly, which might be what they do. And then it depends if your password actually has full entropy(uniformly chosen of all strings of length 28). In that case it should be fine. If it is words in language, that's entirely personal preferance.
AES 256 has a key size of 256 bit. The question is if they use actually the full size. If they use a password in base 64 encoding as key directly, that would be really, really terrible. Strength of security of AES is: Unbroken, don't worry about it. More of a problem could be their mode of operation, because you would actually want an authenticated one.
Well, using AES as standard is a really good thing. Supporting other ciphers is quite common. However, I doubt your statement, that we're heading into the direction of Bernstein's Chacha or Salsa ciphers. AES is the de-facto standard for state-of-the-art symmetric encryption.
It should, but I have doubts that this is done in Shadowsocks.
This isn't a consideration, because the encryption scheme is almost surely not the weakest part of their system. Security depends only on the weakest link of the system, and it is basically never the encryption scheme. One other possibility is wrong usage of an encryption scheme (e.g. hard coded key), maybe have a look here.
Well, that depends on how much you already know. For starters, Wikipedia has a really good quality for a lot of cryptographic topics. Then there are online courses for cryptography, books like Applied Cryptography by Bruce Schneier, etc. Most importantly, focus on scientific publications and try to spot and avoid amateur publications. Other than that, it mostly depends on the time and effort you are willing to invest.


What makes LSBit steganography detectable? And what would help in concealing it?

A general theoretical answer to the title's What makes LSBit steganography detectable? is that in normal images, the LSBit of a pixel in some channel is correlated to higher-order bits in the same pixel and channel, that pixel in other channels, and adjacent pixels, in ways that mere replacement of LSBit tends to strongly alter.

One simple way to improve that is adding noise or blurr to a degree such that the LSBit is nearly indistinguishable from random, in which case it can then be replaced by something equally indistinguishable from random (as resulting from good encryption) with little chance of detection versus an equally noisy/blurry image. Next step is changing only few bits at locations dependent on a key (towards that goal it is necessary to have a small payload, as previously pointed), and have the other pixels randomly noisy according to a good model of the natural image.

From a practical standpoint, sending uncompressed 24-bit bitmap images somewhat is a red flag that basic stego is in use. That would be somewhat less apparent with an additional step of JPEG lossless compression, or PNG or GIF conversion (lossy compression would destroy the hidden message given the LSBit encoding used; more sophisticated stenographic schemes survive that). Notice that sending noisy/blurry images without lossy compression is a waste of bandwidth, and could also raise alarm.

I suggest two "easy to detect" tests, to be applied comparatively on your image with stego (after decompression if a lossless compression step is added), and normal images that could be allegedly sent, at least including the one you start from.

Show as an 8-color image the 3 LSBits of each pixel; that can be done by changing each byte x in each RGB plane to ~((x&1)-1). It there something perceptibly remarkable for your image with stego? Update: a 64 or 512-color image using (x<<6)+32 or (x<<5)+16 might also be interesting. (note:  the three expressions are for C, and assume truncation to octet. ~((x&1)-1) yields 0x00 if the low bit of x is clear, 0xFF otherwise).
Is the compression ratio of PNG markedly lower for your image with stego than for normal images?

Note that these tests can only demonstrate failure to be undetectable.


What are the implications of an encrypted private key being released?

Since the encrypted key file is (potentially) leaked, and adversary is able to run an offline dictionary attack against your key. So you have to answer the question: Is the strength of the password used to encrypt the key, weaker than the strength of the key itself?

So what you should do, is calculate the strength (entropy) of your password (KeePass can do this, for instance) and compare it to current strength estimations for the itself (RSA 2048 has 112 bits, for example). If the password's result is weaker then the key, you should drop it and revoke the certificate.


Is there another group structure that is suitable for RSA other than $U_{pq}$?

The key point in RSA is the fact that inversion in modulo $|G|$ is hard, of course other groups are a priori okay to build a secure encryption scheme.

For example $U_{pqr}$, with $p, q, r$ large primes seems to be okay. But it will be probably less efficient (keys and ciphertexts will be probably larger for the same level of security).

Of course, it is not because the problem seems to be hard, that we can conclude with the same level of confidency that the RSA-problem-hardness. The RSA-problem has been particularly well-studied. And if you choose to change the group used, the risk to discover that "inversion in modulo $|G|$ is not so hard" is more important.


Block cipher to encrypt 8 bytes/64 bits - Use 64 or 128 bit cipher?

You can safely use ECB if all of the following conditions are met:

Your messages can be unambiguously encoded in a form with a fixed size which is equal to the cipher's block size. For example, your messages all have the same size which is smaller than the block size, or they're all smaller than the block size and they never have trailing null bytes.
You only need message confidentiality, not authenticity or integrity (i.e. you don't need to protect against an attacker who might modify the message in transit, possibly without knowing its content).
You don't mind that an observer can tell if you're sending the same message twice.

Even if you don't think you need authenticity or integrity checks, carefully consider the design of the whole system. What happens if an adversary submits fake messages (either made from whole cloth, or modifications of legitimate messages)? What happens if an adversary resubmits a previous message after having observed its effect?

If the messages are all produced and received by the same entity, and the sender and the receiver can agree on some kind of message identifier (e.g. a number that is incremented for each message), then there's a better mode: counter mode (CTR). CTR has several advantages:

By mixing the message number into the encryption, messages with identical content have distinct, unlinkable ciphertexts.
CTR turns a block cipher into a stream cipher, so you can send the exact number of bytes (of bits, even) that matches the length of the message.
CTR requires only encryption on both sides, never decryption, which can same a tiny bit of code size.

CTR only works if the sender and the receiver agree on the initial counter value for each message. Usually the initial counter value is sent as a prefix of the ciphertext, but if you already have a unique identifier for the message, you can repurpose it.

CTR requires distinct counter values for each block of all messages. For messages that are shorter than the block length, this requirement simplifies to not reusing a counter value for different messages.

Note that CTR does not help with message integrity. It even makes it trivial to make predictable changes to the ciphertext without deciphering it (flipping a bit in the ciphertext flips the corresponding bit in the plaintext).


Proving correctness of pseudorandom generator construction given existing pseudorandom generator

Call your original ($k$-to-$3k$ bit) PRG $G$ and your construction $G'$.

Let $\mathcal{U}_t$ denote the uniform distribution on $\{0,1\}^t$. Then $G'$ is a PRG as long as the distributions $\mathcal{U}_{3k}$ and $G'(\mathcal{U}_{2k})$ are indistinguishable with effort polynomial in $k$; see this reference.

Distribution $G'(\mathcal{U}_{2k})$ is just $G(\mathcal{U}_k) \oplus G(\mathcal{U}_k)$, where the two occurrences of $\mathcal{U}_k$ in the latter expression are independent. By the PRG property of $G$ applied to the first term, the distribution is indistinguishable from $\mathcal{U}_{3k} \oplus G(\mathcal{U}_k)$.

Since $\mathcal{U}_t \oplus \mathcal{D}$ is distributed identically to $\mathcal{U}_t$, for any independent distribution $\mathcal{D}$, we get the desired result.

I find this question a bit odd though. If all you want is a $2k$-to-$3k$ PRG constructed from a $k$-to-$3k$ PRG, then what about the following simpler construction: given $2k$ bits, throw away the first half and run the second half through the $k$-to-$3k$ PRG?


Why is a number of shares that is greater than a threshold required to construct secret?

To show that the adversary could not retrieve the secret, you can show that two different secrets will implies the same shares, and then an adversary that has access to these shares could not retrieve the secret.

To show that the adversary has no bit of information about the secret when he has $t'$ strictly less than $t$ shares, you can show that if you take two different $K_1$ and $K_2$, and compute the cardinality of $a$'s (for $k_1$ and for $K_2$) such that you obtain the $t'$ shares. Because they are the same, and because $a$ is uniformly picked at random, you deduce the perfect secrecy.
First I'm claiming that $a$ is chosen unifromly at random in $\{0, \dots, M-1 \}$ (I can give you more details, if you aren't not convinced.
Let $\left(y_1, \dots, y_{n-1}\right)$ a vector of shares.\newline
We call $\psi$ the isomorphism given by the chinese remainder theorem from $\mathbb{Z}_{m_1} \times \dots \times \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}$ to $\mathbb{Z}_{Mp}$, and $\phi$ the invert isomorphism.

$$Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in  \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}, \phi \left(K_1 + a*p\right) = \left(y_1, \dots, y_{n-1}, z, z'\right)\}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in  \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}, \phi \left(K_1\right) + \phi\left(a\right)*\phi\left(p\right) = \left(y_1, \dots, y_{n-1}, z, z'\right) \}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in  \mathbb{Z}_{m_n} \times \mathbb{Z}_{p},  \phi\left(a\right)*\phi\left(p\right) = \left(y_1 - \left(K_1 \mod m_{1} \right), \dots, y_{n-1} - \left(K_1 \mod m_{n-1}\right), z - \left(K_1 \mod m_{n}\right), z' - \left(K_1 \mod p\right) \right) \}$$

Because $p \mod p = 0$, we deduce, that necessarily  $z' = K_1 \mod p$ (and such $z'$ exists).

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists z \in  \mathbb{Z}_{m_n},  \phi\left(a\right) = \left(\frac{y_1 - \left(K_1 \mod m_{1} \right)}{p \mod m_{n-1}}, \dots, \frac{y_{n-1} - \left(K_1 \mod m_{n-1}\right)}{p \mod m_{n-1}}, \frac{\left(z - \left(K_1 \mod m_{n}\right)\right)}{p \mod m_n}, 0\right) \}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists z \in  \mathbb{Z}_{m_n},  a = \psi\left(\frac{y_1 - \left(K_1 \mod m_{1} \right)}{p \mod m_{n-1}}, \dots, \frac{y_{n-1} - \left(K_1 \mod m_{n-1}\right)}{p \mod m_{n-1}}, \frac{\left(z - \left(K_1 \mod m_{n}\right)\right)}{p \mod m_n}, 0\right) \}$$.

This cardinal doesn't depend of $K_1$ (it's equal to $m_n$).


Finding collisions for XOR of many hashes

This question is studied extensively in the paper

A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost by Bellare & Micciancio

In appendix A, they describe how to break the one-wayness of the function $H(x_1,\ldots, x_n) = h(x_1) \oplus h(x_2) \oplus \cdots \oplus h(x_n)$. The idea is as @SEJPM suggests in the comments above: XOR is the operation of a vector space over $\{0,1\}^\ell$ (where $\ell$ is the output length of $h$). Sufficienctly many $h(x_i)$'s form a basis for this vector space. Once you have a basis, you can easily solve for a subset of basis vectors that XOR to any desired value.


Distinguishing attack. How broken is it?  It is broken.  As fgrieu notes, the high bit is highly biased.  In other words, the high bit is fairly predictable.  This is enough to distinguish the output of this generator from a truly random bitstream.  That means the stream cipher is broken: that's the definition of what it means for a stream cipher to be broken.  The distinguishing attack requires observing a few outputs and requires very little computation, so it is much faster than brute force.

Of course, this is a distinguishing attack, not a state recovery attack.  Nonetheless, that's still a valid break.

State recovery attack.
There is also a state-recovery attack.  For instance, if you can observe $2^{30}$ outputs from the generator, then with about $2^{44}$ steps of computation you can recover the initial state of the stream cipher (and thus predict all of its outputs).  The running time of this attack is faster than brute force.

The attack chains together several observations:

Correlation to the MSB of a single LCG.  Notice that the most significant bit (MSB) of $z_i$ (the $i$th output from the stream cipher) is strongly correlated to the MSB of $x_i$ (the $i$th output from the first LCG).  In other words, $\Pr[z_i=x_i]$ is quite a bit larger than $1/2$: for instance, with your parameters for the 64-bit generator, $\Pr[z_i=x_i]\approx 0.8$.  This happens because the MSB of $y_i$ is more likely to be 0 than to be 1.

The consequence is that, if we can observe $2^{30}$ outputs from the stream cipher, then we observe a sequence that is highly correlated to the MSBs of $2^{30}$ outputs from the first LCG.
Outputs from the LCG are a linear function of the initial state. Notice that $x_i$, the $i$th output from the first LCG, is related to the initial state $x_0$ of that LCG by a simple linear relationship:

$$x_i = c_i x_0 + d_i \bmod p,$$

where $c_i,d_i$ are some known constants that depends only upon the (public) parameters of the LCG but not on the key or state.  (In particular, $c_i=\alpha^i \bmod p$ and $d_i = \beta (\alpha^i-1)/(\alpha-1) \bmod p$.)

This means that the state of the first LCG at any point in time can be related to its initial state through a simple linear relationship.  This will be useful in the remainder of the attack.
Sometimes, the MSB of the output of the 1st LCG can be predicted given only partial knowledge of the initial state.  Suppose we know the top 44 bits of the initial state $x_0$ (i.e., we know all but the bottom 20 bits of $x_0$).  Then there are some time steps where we can predict the MSB of the output completely, given this information, even though we don't know the bottom 20 bits of the initial state.

In particular, consider any time step $i$ where $c_i$ satisfies $c_i < p/2^{22}$.  Then we can predict the MSB of $c_i x_0 + d_i \bmod p$ given knowledge the top 44 bits of $x_0$, and our prediction will be right most of the time (about $7/8$ of the time).  This means we can predict the MSB of $x_i$ (the MSB of the $i$th output) and we'll be right about $7/8$ of the time.

It is easy to predict which time steps satisfy this condition: since all of the $c_i$'s are publicly known, we can easily enumerate which values of $i$ satisfy the condition $c_i < p/2^{22}$.  Among the first $2^{30}$ time steps, we expect to find about $2^8$ good time steps that satisfy the condition, i.e., about $2^8$ time steps where we can predict the MSB of the output of the first LCG, given a guess at the top 44 bits of $x_0$.
We can verify a partial guess at the initial state of the 1st LCG.  Suppose we have a guess at the top 44 bits of $x_0$ (at the top 44 bits of the initial state of the 1st LCG).  Then the above observations give us a way to verify whether this guess is correct.  We focus on the $2^8$ good time steps where $c_i$ is small; we'll analyze the outputs from the stream cipher at those $2^8$ offsets (the rest of the outputs from the stream cipher are simply ignored in this analysis).  Notice that the MSB of each of those outputs from the stream cipher are highly correlated with the MSB of the corresponding output from the first LCG (the MSB of $x_i$).  Now given our guess at the top 44 bits of $x_0$, we can produce excellent predictions for the MSB of $x_i$ at each of those $2^8$ time steps.  So, we can check whether the MSB of the outputs from the stream cipher appears to be well-correlated to the predictions for the MSB of the corresponding $x_i$'s.  If there is a good correlation, then we infer that this partial guess at $x_0$ is (probably) correct.  If there is no apparent correlation, then we can conclude that this guess is probably wrong.

This yields an attack on the stream cipher that is faster than brute force.  We identify the $2^8$ "good" time steps (where $c_i$ is small) in advance, and focus on analyzing those outputs from the stream cipher.  We enumerate all $2^{44}$ guesses for the top 44 bits of $x_0$, and use the observation above to verify which of those guesses appear to be correct.  For each guess that passes the above filter, we then exhaustively enumerate all possibilities for the remaining 20 bits of $x_0$ and then infer $y_0$.  The test described above should eliminate almost all of the incorrect guesses at the top 44 bits of $x_0$, so I expect the total running time to be approximately $2^{44}$ steps of computation.

I have not tried to finely optimize the running time of this attack, and my running time estimates are pretty crude, so a more careful analysis would probably give a better estimate (I would not be surprised if my estimates are off by an order of magnitude).  Nonetheless, it seems quite clear that this will be significantly faster than the brute-force attack you described; that attack requires $2^{64}$ steps of computation, and this is significantly faster.

Related literature. You might enjoy reading about the "Hidden Number Problem", which is the following: given $\text{MSB}(x_i k \bmod p)$ for many random, known values of $x_i$, find $k$.  That's closely related to a key step of my attack above, though my attack above has to work even in the presence of noise (on the other hand, my attack above is not polynomial-time; it is merely better than brute-force).  Past work on the Hidden Number Problem has been used, for instance, to attack certain implementations of DSA.

Performance. It occurs to me that, implicit in your question, is the follow-up question: "If this can't be broken, why isn't it used?"  The answer to that is: this cipher is going to offer poor performance.

Let's break it down.  If we want 128-bit security (which is the standard of comparison right now), we're going to need to use two 128-bit primes.  If we want to eliminate the distinguishing attack, we're going to need to discard some of the most significant bits; so we might get 80-100 bits of pseudorandom output per iteration of the stream cipher.

Now let's look at how long each iteration of the stream cipher will take, with these parameters.  Well, we have to do two 128x128->256 multiply operations, and two 256->128 modular reductions.  No computer chip offers a "multiply two 128-bit numbers" instruction; if you build it out of 32x32->64 multiplies, you're going to need to do 16 of those per 128x128->256 multiply, or 32 of the 32x32->64 multiply instructions per iteration.  The modular reduction is even worse; I'm guessing that might take something like 100 instructions per reduction.  So we're looking at maybe 250 instructions per iteration of the generator, or maybe 25-30 instructions per byte of output.  This is a very rough estimate, and I haven't benchmarked it, but I think this is enough to make clear that this generator is not going to be competitive with state-of-the-art stream ciphers, even if there are no clever shortcut attacks.


Is there a way to do anonymous encryption to a recipient?

You can write one very easily, but luckily there are libraries for these like Sealed boxes
From the site;

Sealed boxes are designed to anonymously send messages to a recipient given its public key.
Only the recipient can decrypt these messages, using its private key. While the recipient can verify the integrity of the message, it cannot verify the identity of the sender.
A message is encrypted using an ephemeral key pair, whose secret part is destroyed right after the encryption process.
Without knowing the secret key used for a given message, the sender cannot decrypt its own message later. And without additional data, a message cannot be correlated with the identity of its sender.
Note: the emphasis is mine.

The sealed boxes based on Crypto boxes that uses

Key exchange: X25519
Encryption: XSalsa20 stream cipher
Authentication: Poly1305 MAC

Keep in mind that the additional data can be, your IP address, your MAC address, your writing style, etc. This may leak your identity or location. You may need some protections/countermeasures like TOR network against the identification of the sender.


Are you sure?

Float operations are very hard to reproduce in diverse environments.

Do you round towards positive, negative or zero? Do you handle denormals or just treat them as zero? What about dividing by zero?

I'm sure we would love to have that problem with every cipher we implement.

  Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU or FPGA to beat.

To beat FPGA... don't do anything. There are problems that are slow on CPUs & GPUs, but otherwise you won't have as big FPGA that can reach nearly same frequency. If that wasn't case we wouldn't have processors, just builtin FPGAs that switch between GPUs and CPUs...

To beat CPU... just use something that uses a lot of simple math... +,-,xor,ror,rol etc. This doesn't have to be on floats, ints will suffice. Chacha20 might work well on GPUs. Note that this won't be slow on CPUs, it will just be faster on GPUs because it parallelizes well (and this is always case, because CPUs are complex beasts that can do more than GPU, except there just isn't enough of it for raw number crunching at that speed).

Honestly, most cryptographic primitives will be faster on GPUs because they frequently rely on number crunching, and rarely do any significant memory access and/or branching.

Just remember that there are still ASICs that will always win against you, because they are exceptionally good at number crunching (and if you are looking to outrun them, argon2 and CPU are your friends).


First of all, SVP is not known to be NP-complete. There are some hardness results for SVP, but just considering very specific scenarios (for instance, SVP is NP-Hard in the $\ell_{\infty}$ norm) or under other types of reductions (such as randomized or non-uniform reductions).

Even so, the AKS algorithm runs in exponential time, so, it doesn't give us any information about the hardness of SVP.

When we say that a problem is NP-hard, we expected that there is no polynomial-time algorithm to solve the problem, but there is nothing strange with the fact that we know exponential-time algorithms for the problem (and we usually know trivial exponential-time algorithms to solve hard problems...).


Known Plaintext attacks using standard greetings etc

Known Plaintext Attack (KPA) is the security level that is below of Chosen Plaintext Attack (CPA) that we want at least CPA from all ciphers. Actually, we want more in the modern cryptography; Ind-CPA.
The classical cryptography era contains lots of examples that can be easily broken with KPA attack; shift, permutation, Vegenere, and Hill ciphers are some examples.
In the modern era, the KPA can be used for key searching as below.

Brute-force attack; search for all keys

  # c = E(k,m) for some key k we are looking for
  for i in keys:
    if c == E(i,m):
       return i

An interesting example in the history was the RSA's DES challenges, which contains given partial information The unknown message is: on the full plaintext and the contestants are required to find the key given the full ciphertext. They used brute-force attacks similar to the above. The attack is successful since the key size of DES 56-bit.
This above can be still considered a classical way to find the key and the technological advances help to find the key. A modern novel attack is coming from Matsui and Yamagish in 1992 on their novel paper

A new method for known plaintext attack of FEAL cipher

This is now called the Lineart Attack. On attacking the DES, it requires $2^{43}$ known plaintexts by Matsui in 1994.

Linear Cryptanalysis Method for DES Cipher

If you want to learn about the Linear attack the tutorial by Heys is a good starting point.
Now back your specific question;

("Hello Alice" or other known parts of the message) be used to launch an attack. You don't know the whole PlainText but only part of the PlainText. So how exactly will it help?

First of all, with the Kerckhoff's principle, we assume that except the key we assume all known about the target system, like how the messages turned into bytes for encryption.

If the position is known as in the RSA DES challenges, then this knowledge can be easily turned into a known-plaintext if fits into one block. One needs at least 16 characters for AES and 8 for DES.
The Hello Alice is forming more than one block for DES Hello Al and ice?????. If you brute-force the DES then the first block can be used to find the key candidates, yes there be more than one candidate. Then the decryption of the next blocks can be used to pinpoint the messages.
# c = E(k,m) for some key k
# we are looking for the possibele key for full known message block m
for i in keys:
   if c == E(i,m):
      m' = D(i,c')             # c' is the other message blocks
      if m' is a valid string  # check the validity of m'
        return i

A special case if we don't have a full block, then execute the brute force by decryption, and for each possible candidate, which contains the partial information, look for the meaningful strings by decrypting the rest ciphertexts. This can be automized with tools like Linux's string command and possibly check the PKCS#5 padding at the end will eliminate most of the candidates.

If the position is not known
This is a little problem to be solved compared to brute force and really depends on the message size. If the message size is $t$ and the known message part is $l$ then one needs to look for $t-l$ positions. Therefore the cost of brute force was multiplied with $t-l$. For short messages, this is not a real problem, however when the message size is more than $2^{32}$ then the brute-force cost become $2^{80}$ for DES and $2^{160}$ for AES.


RSA KeyPair generation with Bouncy Castle provider: $e*d(φ(n))$ not equal to one

As CodesInChaos notes in the comments, the necessary and sufficient condition for $m^{ed} \equiv m \pmod{n}$ to hold for all messages $m$ is that $ed \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ is the Carmichael reduced totient function of the modulus $n = pq$.

As it happens, the Euler totient $\varphi(n) = (p-1)(q-1)$ is an integer multiple of $\lambda(n)$, so if $ed \equiv 1$ modulo $\varphi(n)$, then this also holds modulo $\lambda(n)$.  Thus, when generating an RSA key, it's OK to compute the private exponent $d \equiv e^{-1}$ modulo $\varphi(n)$ rather than modulo $\lambda(n)$, and indeed quite a few introductory texts on RSA (including, apparently, Wikipedia) do that for some reason, perhaps because it's arguably a bit easier to explain the math that way, or perhaps simply because the authors also mistakenly think that the necessary condition for key validity is $ed \equiv 1 \pmod{\varphi(n)}$.

However, this is not actually the case, and it's indeed quite possible for $(n,e,d)$ to be a valid RSA key even if $ed \not\equiv 1 \pmod{\varphi(n)}$, as long as $ed \equiv 1 \pmod{\lambda(n)}$.  Since using $\lambda(n)$ also yields the smallest valid (positive) private exponent $d$ for any given $e$ and $n$, and since computing $\lambda(n)$ is not significantly more difficult than computing $\varphi(n)$, most practical RSA implementations indeed do just that.


Why doesn't the formula work when checking two ECDSA signatures?

In ECDSA, the R value in the signature is not the elliptic curve point $kG$, but instead only its x-coordinate, that is, an integer.

So, what do you mean by R' + (C*G)?  In particular, what do you mean by the operator +?

If you mean "the + is an integer modular addition, that is, we take the x-coordinate of the point $CG$, and then add it (modulo $n$) to $R'$", well, that'll give you an integer that's unrelated to $R$ (as $R$ and $R'$ are related as elliptic curve points not integers, and integer addition and elliptic curve operations have little to do with each other)

If you mean "the + is an elliptic curve addition, that is, we find one of the points with x-coordinate $R'$, and add it (using the elliptic curve addition operation) to the point $C\cdot G$), well, that'll work half the time; there are (usually) two elliptic curve points with x-coordinate $R'$, and it'll work if the one you pick just happens to be the original $R'$ point.


What is the difference between CBC and GCM mode?

GCM and CBC modes internally work quite differently; they both involve a block cipher and an exclusive-or, but they use them in different ways.

In CBC mode, you encrypt a block of data by taking the current plaintext block and exclusive-oring that wth the previous ciphertext block (or IV), and then sending the result of that through the block cipher; the output of the block cipher is the ciphertext block.

GCM mode provides both privacy (encryption) and integrity.  To provide encryption, GCM maintains a counter; for each block of data, it sends the current value of the counter through the block cipher.  Then, it takes the output of the block cipher, and exclusive or's that with the plaintext to form the ciphertext.

Note two key differences:

What's being exclusive-or'ed; in CBC mode, the plaintext is exclusive-or'ed with data that the attacker knows (the IV or a previous ciphertext block); hence, that in itself does not provide any inherent security (instead, we do it to minimize the chance that we send the same block twice through the block cipher).  In GCM mode, the plaintext is exclusive-or'ed with output from the block cipher; it is inherent in the security model that the attacker cannot guess that output (unless he already knows the plaintext and the ciphertext).
What's being sent through the block cipher; in CBC mode, the plaintext is sent through the block cipher (after it's been 'randomized' with an exclusive-or); in GCM mode, what's being sent through the block cipher doesn't actually depend on the data being encrypted, but instead only on internal state.

As for how GCM uses an IV (I personally consider 'nonce' a better term for what GCM uses, because that emphesizes the idea that with GCM, you cannot use the same nonce for the same key twice), well, it is used to initialize the counter.


Small signature for packets using asymetric encryption?

A Signature-Scheme known for it's short signatures is the Boneh-Lynn-Shacham (BLS) Signature Scheme, that uses not only Elliptic Curves but Bilinear Pairings over the curve.
The paper can be found here and lists signature sizes provided. For example the paper states that you can

  … get a signature of length 154 bits with security comparable to 320-bit DSA or 320-bit ECDSA …


Honestly, it would be more secure, but not by much, and that is assuming you are using finite field inversion s-boxes.
A better use of multiple 8-bit s-boxes would be to make them key dependent, however in software that can have the unfortunate side effect of creating another side channel to leak information about the key.
If you want something based on the AES design but with small modifications that make it more secure, what you want is not more s-boxes, but a better s-box with more algebraic complexity. In terms of round design that is probably the only modification you can make before it strays too much from the original design.
The other place to look is the key schedule, which is very simple and fast. This is both beneficial and detrimental, as it is probably the weakest point of the cipher, but makes applications requiring key changes usable. Think a wifi chip that needs a different key for each connected device and needs to constantly switch keys to communicate with them. It can also "roll" to save memory on embedded systems, but this means that round subkeys can be used to recover the key.
From a software only perspective, security can be improved with changes to the key schedule, slowing it down and generating the subkeys using a one way function with less linearity.


Why is it not possible to tap into the HTTPS traffic specifically going from the server to the client?

I'm assuming you're talking about RSA. The more common DH algorithm uses ephemeral public and private keys generated by both the server and the client, although that's not relevant to this answer. The public and private keys are not used to exchange traffic. Instead, they're used to exchange a symmetric key which is used to encrypt data going both directions. This is what's called a hybrid cryptosystem.

Now, TLS in particular is a little more complicated than that. It uses two symmetric keys, one for each direction, in order to protect from certain kinds of attacks. however, the public key encryption is used to exchange a single master key which is used to generate the two symmetric keys, as well as some other keys used in other parts of the TLS protocol (such as MAC keys used for integrity).

For more details, see How does SSL/TLS work?


Is it necessary, that the public key is a prime number in the RSA algorithm?

There is no specific reason why $e$ is required to be a prime number.  It must be relatively prime to $\phi(n)$ (otherwise we can't decrypt uniquely); however that is the only hard requirement.  Assuming that 9 is relatively prime to $\phi(n)$, there is no reason why 9 can't be used as a public exponent.

However, selecting a prime value for $e$ does have this practical advantage; for prime $e$, then the requirement that it is relatively prime to $\phi(n)$ is equivalent to the statements that $p \ne 1 \pmod{e}$ and $q \ne 1 \pmod{e}$ (where $p$ and $q$ are the prime factors of $n$). If we use the common logic of selecting $e$ first, and then $p$ and $q$, this turns into a relatively simple additional criteria when doing prime selection.


Generating and distributing a secret without trusting the source

You'd use a KBKDF on the clients, using the earlier secret as Input Keying Material (IKM) using the random as salt or Info input. KDF's generally have an output size parameter as well.
Currently HKDF is considered a good KDF, and if you use the full function it supports a salt.
Basically you would be implementing a so-called ratchet, where each key depends on the previous one, but doesn't provide any information about the previous keying material.


Security of RSA variants with $e=n-2$ and $e=n$

Rather obvious, but does answer one of the questions: both can be reduced to the security of RSA with $e' = a_n n (n-2)$ for any (reasonably sized) public integer $a$ which can be a function of $n$. For example, given $c \equiv m^n$ for a random unknown $m$, we solve $c^{n-2} \equiv m^{n(n-2)}$ for $m$. With probability at least $1/gcd(e,\lambda(n))$ the answer will be $m$.


Yes, it's still talking about the case where multiple hashes are needed to get to the key size. Such a function is called a key expand function.

It explains that they are taken independently (different contexts) over the passphrase (the data). A different context means that the calls to the hash functions don't interact; $H$ is seen as a single call to a complete hash function.

For example, with a 160-bit hash (e.g. SHA-1) and a 256-bit key, you would concatenate $H(p)||H(0x00||p)$, then take the leftmost 256 bits (i.e. discard the rightmost 8 octets).

If you needed a third hash block, that would be $H(0x00||0x00||p)$, etc.


The simple answer is also part of one weakness with all encryptions that use symmetric key, AKA pre-shared key. Key sheets that lasted 31 days where generated and sent out by courier or so. The weakness is ofcourse that if the enemies get their hands on it then they can read all the messages that used that key.
And yes - sometimes the allied did get their hands on a key sheet and then they had the keys for one network for up to a month.


To decrypt a cipher text encrypted using keyed substitution

When trying to decrypt any substitution cipher, my first step would be to count the number of times each letter occurs in the ciphertext, and plot the ranked letter frequencies.  Doing that for your ciphertext yields the following plot:

P: 84 ##########################################
B: 73 #####################################
V: 60 ##############################
K: 59 ##############################
E: 56 ############################
L: 52 ##########################
S: 47 ########################
A: 45 #######################
U: 44 ######################
O: 26 #############
T: 24 ############
Y: 21 ###########
Z: 21 ###########
Q: 19 ##########
F: 15 ########
C: 13 #######
N: 13 #######
R: 12 ######
H: 11 ######
M: 10 #####
D:  6 ###
X:  6 ###
G:  2 #
W:  1 #
I:  0
J:  0

(If you suspect you might be dealing with a simple Caesar shift cipher, looking at the same plot sorted alphabetically can also be useful, since you may be able to spot some distinctive patterns like the A/E/I triple peak that can reveal the shift amount.)

Comparing this plot with typical English letter frequencies, the general shape looks very similar, suggesting that this is indeed an monoalphabetic substitution cipher.  The next step, then, is simply to try a few substitutions and see if they make sense.

For example, we might guess that the two most common letters in the ciphertext, P and B, stand for the plaintext letters E and T respectively.  This guess yields the following partially decrypted message (shown with the ciphertext in lowercase, and the corresponding candidate plaintext below it in uppercase):

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
__E__ ___TT ___T_ E_E__ _T___ _____ _ET__ _____ __E__ _____ ____E __TT_ _____
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
___T_ _____ T_E__ __T__ __T__ ____T T_E__ _E__T _____ _TE__ _T___ __E__ ___T_
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
_____ ___TT _E_E_ ____T E_E_T _E_T_ T____ __TE_ _____ ____T _ET__ _ET__ ___E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E___ _T___ T____ _____ E____ ___E_ _____ _E___ ___T_ E___E T___T _T___ _____
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_____ _E___ __T_E ___ET ___T_ T____ ____E E____ _____ E____ _____ _____ ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_T__ T____ _____ _____ _TT_E _E___ _____ E__E_ _____ E____ _____ ____T T_E__
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
____E ___TT _____ TT_E_ E__T_ E____ __E__ ___E_ _E_T_ ____T _T_E_ ___E_ ___T_
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
_____ ___T_ _E___ ___E_ _E___ _E__T __T__ E__E_ E__E_ T__T_ ___T_ __ET_ E_E__
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
____E ____E _____ _____ T____ _E___ ___E_ ____E _____ _____ ____T E__E_ T____
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_____ _____ TT_E_ _____ ___T_ _____ _E___ E____ E____ ___E_ E_E__ ___E_ ___E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E____ T____ _____ __E__ _____ _____ T____ __ET_ E_T_T _____ _TE__ ___T_
popbn
E_ET_

The first thing you should check is that there are no unlikely letter sequences like TTT that might indicate a wrong guess.  In this case, there aren't any, so we can assume for now that our initial guess that P=E and B=T may be correct.  (If we did find some weird-looking letter sequences, we might want to try swapping the guesses around, and seeing if P=T and B=E would yield more sensible-looking results.  We could also try assigning either P or B to the plaintext letter A, which can also be pretty common, etc.)

Once we're reasonably confident about our initial guesses, we can see if we may be able to infer any other ciphertext/plaintext letter pairs from them, e.g. by spotting likely words in the partial plaintext.  Conveniently, the most common word in the English language is the definite article "the", which just happens to contain both T and E.  Looking for patterns of the form T_E in the partial plaintext above, we can see that several of them have U as the middle ciphertext letter.  We may thus tentatively guess that U might stand for H in the plaintext, and try another partial decryption:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE__ ___TT ___TH E_E__ _T___ _____ _ETH_ _____ __E__ _____ ____E __TT_ _____
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
___T_ _____ THE__ __TH_ __T__ ____T THE__ HE__T _____ _TE__ _TH__ _HE__ __HT_
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
_____ ___TT HE_E_ ____T E_E_T HE_T_ T____ __TE_ _____ ____T HET__ _ET__ ___E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E___ _T___ T____ __H__ E____ ___E_ _____ _E_H_ ___TH E___E TH__T _T___ _____
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_____ _E___ __THE ___ET H__T_ T____ H___E E____ _____ EH___ __H__ _____ ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_TH_ T____ _____ _____ _TTHE _E___ _____ E__E_ _____ E____ _____ ____T T_E__
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE ___TT _____ TTHE_ E__TH E_H__ __E__ ___E_ HE_T_ ____T _THE_ ___E_ ___T_
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
_____ ___T_ HE___ ___E_ _E___ _E__T H_T_H E__E_ E__E_ T__T_ ___T_ __ETH E_E__
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
____E ____E _____ _____ T____ HE___ __HE_ ____E __H__ _____ ____T E__E_ T____
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_____ _____ TTHE_ _____ ___T_ _____ _E___ E___H E_H__ ___EH E_E__ ___E_ ___E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E____ T____ __H__ __E__ _____ _____ T____ __ETH E_T_T _____ _TE__ H__T_
popbn
E_ET_

Again, we should check that the partial decryption looks plausible.  With the plaintext letters T, H and E tentatively assigned, one possible next step would be to look for plaintext patterns of the form TH_T, which might correspond to the (also fairly common) word "that".  As it happens, we find two such instances, both with the ciphertext letter K in the middle.  Looking at the letter frequency plot above, K is the fourth most common letter in the ciphertext, just slightly behind V in the third place, so it's entirely plausible that it might be the encryption of A, which is generally counted as the third most common letter in English on average.  With that guess, the partial plaintext becomes:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE_A ___TT ___TH E_E_A _T___ _____ _ETH_ _____ __E__ __A__ ____E __TT_ __A__
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_A_T_ ___A_ THE__ __TH_ __T__ ____T THE__ HE_AT A___A _TE__ _THA_ _HE__ __HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
___A_ __ATT HE_E_ ____T E_E_T HE_TA T____ A_TE_ _____ ____T HET__ _ET__ ___E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ AT___ T____ __H__ E____ ___E_ A__A_ _E_H_ ___TH E___E TH__T _T_A_ _____
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_____ _EA__ __THE ___ET H__T_ T_A__ HA__E E___A _____ EHA__ A_H__ _A__A ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T____ _____ __A__ _TTHE _E_A_ A_A__ E__E_ _____ E____ _____ _A__T T_E__
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE ___TT _____ TTHE_ E__TH E_H__ __E__ A__E_ HE_T_ ____T _THE_ A__E_ _A_T_
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
_____ ___T_ HE___ ___E_ _E__A _E__T HAT_H E__E_ E__E_ T__TA ___T_ __ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
____E ____E _____ A___A T____ HE_A_ __HE_ A_A_E __H__ ___A_ ____T E__E_ T___A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_____ A___A TTHE_ __A__ ___T_ A____ _E___ E___H E_H__ ___EH E_E__ _A_E_ A__E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E__A_ T____ __H__ __E__ _____ _A___ T_A__ __ETH E_TAT ____A _TE__ H__T_
popbn
E_ET_

Next, we could try to look for more partial words, or we could simply guess a few more common letters.  The most common ciphertext letters that we haven't assigned to any plaintext letter yet are V and E; both seem to be occurring in places where one might expect a vowel, so we might tentatively guess that they stand for I and O in either order.  Of the two choices, V=I and E=O yields a somewhat more likely-looking partial plaintext:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE_A __ITT I__TH E_E_A ITI__ _O__O _ETHI __O__ O_E_O __A__ _I__E _ITTI __A__
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_AITI ___A_ THEO_ __THI __TO_ O___T THE__ HE_AT A___A ITE__ ITHA_ _HE__ I_HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
___AI __ATT HE_E_ _O__T E_E_T HE_TA TIO__ A_TE_ _O__I ____T HETI_ _ETO_ _I_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ ATO__ TO_OI __HO_ E_O__ ___E_ A__A_ _E_HI _I_TH E_I_E THI_T _T_AI __O__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
__OO_ _EA_O __THE _I_ET HI_T_ T_AI_ HA__E E_I_A ___O_ EHA__ A_HO_ _A_OA ___E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T__I_ _O__I _IA__ _TTHE _E_A_ A_A__ E__E_ __O__ E_O__ _O__O _A_IT T_E_I
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE __ITT I__O_ TTHE_ EO_TH E_HI_ __E_I A__E_ HE_TO _OI_T OTHE_ A_IE_ _AITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
___OO ___T_ HEI__ O__E_ _E__A _E__T HAT_H E__E_ E__E_ TO_TA _O_T_ I_ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
__O_E __O_E _O_I_ A_I_A TIO__ HE_AI __HE_ A_A_E I_HO_ ___A_ I__OT E__E_ TI__A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_I___ AI__A TTHE_ __A__ __IT_ A_O_I _E_O_ E_O_H E_HO_ ___EH E_E__ _A_E_ A__E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__E__ E__A_ TO__I __HI_ O_E__ _O__O _A__O TIA_O __ETH E_TAT IO__A _TE__ HI_T_
popbn
E_ET_

Now we can spot the repeating pattern ATIO_, where the following ciphertext letter is always S.  The suffix "-ation" is quite common in English words of Latin origin, so we may guess that S=N, giving:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
_HE_A __ITT IN_TH E_E_A ITIN_ _O__O _ETHI N_O__ O_E_O __AN_ _IN_E _ITTI N_AN_
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_AITI N__A_ THEON __THI N_TO_ O___T THEN_ HE_AT AN__A ITE__ ITHA_ _HE__ I_HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
N__AI N_ATT HE_EN _O_NT E_E_T HE_TA TION_ A_TE_ _O__I N___T HETI_ _ETO_ _I_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ ATO__ TO_OI N_HO_ E_O__ ___E_ AN_A_ _E_HI _I_TH E_I_E THI_T _T_AI N_O__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
__OON _EA_O N_THE _I_ET HI_T_ T_AIN HA__E ENINA N__ON EHA__ ANHO_ _A_OA N__E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T__I_ _O__I _IA__ _TTHE _E_A_ A_A__ EN_E_ __O__ E_O__ _O__O _A_IT T_E_I
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
___HE __ITT IN_O_ TTHE_ EONTH E_HIN __E_I A__E_ HE_TO _OINT OTHE_ A_IE_ _AITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
N__OO ___T_ HEIN_ O__E_ _E__A _E__T HAT_H E__E_ E__E_ TO_TA _O_T_ I_ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
__O_E __O_E _O_I_ A_INA TION_ HE_AI __HE_ A_A_E I_HO_ ___A_ I_NOT E__E_ TIN_A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_I___ AI__A TTHE_ __AN_ __IT_ A_O_I _E_O_ E_O_H E_HO_ ___EH E_E__ _A_E_ AN_E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
__EN_ E__A_ TO__I N_HI_ O_E__ _O_NO _A__O TIA_O __ETH E_TAT ION_A _TE__ HI_T_
popbn
E_ET_

Now we're starting to have enough decoded letters that, with a bit of imagination, we can start making out more and more full words in the plaintext.  For example, near the end of the plaintext we have the sequence THE_TATION, with the undecrypted letter L in the middle.  Just about the only plausible English phrase that this could stand for is "the station", suggesting that L=S.  Again checking that the letter frequencies look plausible, we can try this and get:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
SHE_A SSITT IN_TH E_E_A ITIN_ _O_SO _ETHI N_O_S O_E_O __AN_ SIN_E SITTI N_AN_
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
_AITI N__AS THEON __THI N_TO_ O__ST THENS HESAT AN__A ITE__ ITHA_ _HE__ I_HTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
N__AI N_ATT HE_EN _O_NT E_E_T HESTA TION_ ASTE_ _O__I N___T HETI_ _ETO_ _I_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
_E_A_ ATO__ TO_OI N_HO_ E_O_S ___E_ AN_AS _E_HI _I_TH E_I_E THI_T _T_AI N_O__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_SOON _EA_O N_THE _I_ET HI_T_ T_AIN HAS_E ENINA N__ON EHA__ ANHO_ _A_OA NS_E_
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T__IS _O__I _IA__ _TTHE _E_AS A_ASS EN_E_ __O__ E_O__ _O__O _A_IT T_E_I
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
__SHE SSITT IN_O_ TTHE_ EONTH ESHIN __ESI AS_E_ HE_TO _OINT OTHE_ A_IES _AITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
N__OO ___TS HEIN_ O__E_ _E__A _E__T HATSH E__E_ E__E_ TOSTA _O_TS I_ETH E_E_A
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
S_O_E S_O_E _O_I_ A_INA TIONS HESAI _SHES A_ASE ISHO_ __SA_ I_NOT E__E_ TIN_A
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
_I__S AI__A TTHE_ __AN_ __ITS A_O_I _E_O_ E_O_H ESHO_ ___EH E_E__ SA_E_ AN_E_
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
S_EN_ E__AS TO__I N_HI_ O_E__ _O_NO _AS_O TIA_O __ETH ESTAT ION_A STE__ HIST_
popbn
E_ET_

Now, we can take a guess that the beginning of the plaintext, SHE_A SSITT IN_TH E_E_A ITIN_ _O_SO _ETHI N_ might read "she was sitting there waiting for something", giving us F=W, T=G, A=R, Q=F and Z=M.  Plugging those guesses in, we get:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
SHEWA SSITT INGTH EREWA ITING FORSO METHI NGORS OME_O __AN_ SIN_E SITTI NGAN_
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
WAITI NGWAS THEON __THI NGTO_ O__ST THENS HESAT AN_WA ITE_W ITHA_ _HERM IGHTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
N_MAI NMATT HEWEN _O_NT ERE_T HESTA TIONM ASTER _O__I NG__T HETI_ _ETOF FI_E_
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
RE_AR ATOR_ TOGOI NGHOM EFORS ___ER AN_AS _E_HI MIFTH EFI_E THIRT _TRAI NWO__
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
_SOON _EA_O NGTHE FI_ET HIRT_ TRAIN HAS_E ENINA N_GON EHA_F ANHO_ RAGOA NSWER
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
E_THA T_RIS _OFFI _IA__ _TTHE REWAS A_ASS ENGER _RO__ E_OFF FOR_O _A_IT T_EGI
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
R_SHE SSITT INGO_ TTHER EONTH ESHIN G_ESI AS_E_ HERTO GOINT OTHE_ A_IES WAITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
NGROO M__TS HEINF ORME_ MEGRA _E__T HATSH E_REF ERRE_ TOSTA _O_TS I_ETH EREWA
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
SMORE S_O_E FORIM AGINA TIONS HESAI _SHES A_ASE ISHO_ __SA_ IMNOT E__E_ TINGA
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
GIR_S AI_MA TTHEW __AN_ __ITS A_O_I _E_OM EFORH ESHO_ ___EH EREMR SA_E_ AN_ER
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
S_EN_ ERWAS TO_RI NGHIM O_ERF ROMNO _AS_O TIAFO RMETH ESTAT IONMA STERW HIST_
popbn
E_ET_

At this point, it should be pretty straightforward to fill in the missing bits of the plaintext, giving us:

lupfk llvbb vstbu papfk vbvst qeale zpbuv steal ezpme ohkso lvsnp lvbbv stkso
SHEWA SSITT INGTH EREWA ITING FORSO METHI NGORS OMEBO DYAND SINCE SITTI NGAND
fkvbv stfkl bupes yhbuv stbeo ewclb bupsl uplkb ksofk vbpof vbuky yupaz vtubk
WAITI NGWAS THEON LYTHI NGTOD OJUST THENS HESAT ANDWA ITEDW ITHAL LHERM IGHTA
sozkv szkbb upfps necsb papob uplbk bvesz klbpa yenxv stcrb upbvn xpbeq qvnpr
NDMAI NMATT HEWEN COUNT EREDT HESTA TIONM ASTER LOCKI NGUPT HETIC KETOF FICEP
aprka kbeah betev stuez pqeal crrpa ksokl xpouv zvqbu pqvdp buvab hbakv sfecy
REPAR ATORY TOGOI NGHOM EFORS UPPER ANDAS KEDHI MIFTH EFIVE THIRT YTRAI NWOUL
olees mpkye stbup qvdpb uvabh bakvs uklmp psvsk sotes pukyq ksuec aktek slfpa
DSOON BEALO NGTHE FIVET HIRTY TRAIN HASBE ENINA NDGON EHALF ANHOU RAGOA NSWER
pobuk bmavl xeqqv nvkym cbbup apfkl krkll pstpa oaerr poeqq qeahe ckyvb byptv
EDTHA TBRIS KOFFI CIALB UTTHE REWAS APASS ENGER DROPP EDOFF FORYO UALIT TLEGI
aylup llvbb vstec bbupa pesbu pluvs typlv klxpo upabe tevsb ebupy kovpl fkvbv
RLSHE SSITT INGOU TTHER EONTH ESHIN GLESI ASKED HERTO GOINT OTHEL ADIES WAITI
staee zmcbl upvsq eazpo zptak dpyhb ukblu prapq paapo belbk hecbl vopbu papfk
NGROO MBUTS HEINF ORMED MEGRA VELYT HATSH EPREF ERRED TOSTA YOUTS IDETH EREWA
lzeap lnerp qeavz ktvsk bvesl uplkv olupl knklp vluec yolkh vzseb pgrpn bvstk
SMORE SCOPE FORIM AGINA TIONS HESAI DSHES ACASE ISHOU LDSAY IMNOT EXPEC TINGA
tvayl kvozk bbupf myksx yhvbl kmehv dpnez pqeau pluec yompu papza lkypg ksopa
GIRLS AIDMA TTHEW BLANK LYITS ABOYI VECOM EFORH ESHOU LDBEH EREMR SALEX ANDER
lrpsn pafkl bemav stuvz edpaq aezse dklne bvkqe azpbu plbkb veszk lbpaf uvlby
SPENC ERWAS TOBRI NGHIM OVERF ROMNO VASCO TIAFO RMETH ESTAT IONMA STERW HISTL
popbn
EDETC

(If you're curious about the source of the plaintext, a quick Google search will reveal that it comes from chapter 2 of the book Anne of Green Gables by Lucy Maud Montgomery, published in 1908.)

Oh, and the keyword?  Well, we didn't really need it to decode the message, but since we now have (almost) the whole ciphertext alphabet, we can write it down sorted by plaintext letter to get:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
kmnopqtuvwxyzser?albcdfgh?

where the two question marks stand for the letters I and J that don't occur in the ciphertext, as they correspond to the rare plaintext letters Q and Z.  Guessing that I=Q and J=Z, we can see that the keyword is "serial", and the key letter is N.  (Of course, the keyword "serjal" would also work in this particular case, but as far as I know there is no such word in English.)


Calculate the complexity of HKDF with a 96bit salt and a 128bit key?

Does this significantly weaken my 128 bit PSK down to 96 bit? What is the true complexity of the resulting SESSIONKEY?

No it doesn't, key strength remains the same. It's remains at 128 bits. HKDF can even be run without a salt (although it's security proof strongly recommends you to use one).

However, if you use it many times, you might have a higher chance that a SESSIONKEY repeats. How that impacts security depends on the cipher mode and IV usage though:

If you use a 16 byte random IV and you'd use, say, AES-EAX then you'd still be as secure. If you'd use deterministic encryption and the each message differs then you'd still be as secure.
If the IV is static and you'd be using GCM then you're more likely to be in trouble and all security may be lost.

So the nasty answer is that we cannot really tell, it depends on the use case and threat vectors.


Is it necessary to generate a private key for each encryption process?

As you have correctly identified, there is a problem that with public key encryption you cannot encode long messages in an efficient way. Your message must be an element of a finite group and may therefore not exceed a certain number of bits.

Therefore often a hybrid approach with symmetric and asymmetric encryption is used. That is:

The sender encrypts his long message using a symmetric algorithm, using a randomly chosen secret key K.
The sender encrypts the secret key K using the public key of the recipient.
The sender sends the symmetrically encoded message and the asymmetrically encoded key K to the recipient.
The recipient first recovers K and then decrypts the long message.


How can I find the prime numbers used in RSA?


The state must be written/read along the columns:

63cab7040953d051cd60e0e7ba70e18c $\mapsto$ $
\begin{bmatrix}
63 & 09 & cd & ba \\
ca & 53 & 60 & 70 \\
b7 & d0 & e0 & e1 \\
04 & 51 & e7 & 8c
\end{bmatrix}
$

shift rows $\mapsto$ $
\begin{bmatrix}
63 & 09 & cd & ba \\
53 & 60 & 70 & ca \\
e0 & e1 & b7 & d0 \\
8c & 04 & 51 & e7
\end{bmatrix}
$ $\mapsto$ 6353e08c0960e104cd70b751bacad0e7

See Figure 3 in FIPS SP 197, 3.4 (http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf).


Selectively opening only a few commitments

Since your main concern is communication, then use something that can reduce communication cost. I can think of two possible directions.

1 Use a Merkle tree

The idea is to commit to all elements, then build a Merkle tree on top of the commitments, and send the root of the Merkle tree as the commitment of the whole set. To reveal an element, open its commitment and show the commitment is covered by the Merkle tree.

2 Use a cryptographic accumulator

  A (static) cryptographic accumulator scheme allows to accumulate a
  finite set $X = \{x_1 , . . . , x_n \}$ into a succinct value $accX$ , the so
  called accumulator. For every element $x_i \in X$ , one can efficiently
  compute a so called witness $witx_i$ to certify the membership of $x_i$ in
  $acc_X$ . However, it should be computationally infeasible to find a
  witness for any non-accumulated value $y \not\in X$ (collision freeness).

Essentially the accumulator serves as a commitment of a set, and each witness serves as the opening secret of the individual elements in the set.


Compression function to guarantee randomness of one time pads?

A one time pad (OTP) should by definition not have any patterns. An entropy source can have patterns, but an OTP by definition should consist of pure random bits.

In general you can create something that is close to a true random number generator by applying a cryptographic hash function over the output of an entropy source. According to NIST you should however provide twice the entropy within the input compared with the output. A cryptographic hash function is often referred to as a compression function.

Such a compression function should however not be confused with the underlying compression functions used for creating zip or bzip (etcetera) archives. Those are fully reversible compression functions, and will therefore only add some complexity, not security.

So there is probably somebody doing this, but no, it won't work.


Why are they called "commitment", "challenge", and "response"?

This is because:

For the commitment $t$, it comes first and uses the difficulty of the discrete logarithm problem to protect the value $v$. Once you've published the value $t=g^v \bmod q$, if someones knows the value $v$, then they can easily verify that the value $t$ corresponds to the value $g^v \bmod q$, but on the other hand it is really difficult to find the value $v$ knowing only the value $t$. Hence, you commit to the knowledge of the value $v$ by giving out the value $t$.
For the challenge $c$, you can see this value as being a "challenge": anybody able to give you a value $r$ such that $g^ry^c=g^v=t \bmod q$ must be knowing the value $x$, otherwise they wouldn't have been able to compute $r$ such that the $y^c=g^{xc}$ cancels out with the $g^r$ value. So you challenge them to provide you with a correct $r$ value.
And for the response $r$, it is an answer to the question of finding a value $r$ such that $g^ry^c=g^v$. If you know $x$ and $v$ then you can compute the value $r$ in such a way that the challenge would not be hard, but if you do not know those values, your chances to find a correct value $r$ are negligible. So you're responding to the challenge using that value $r$.

This is possible in the end because $g^ry^c=g^rg^{xc}=g^{v-xc}g^{xc}=g^v=t$ by definition of $y$ and $r$.

I'm speaking $\bmod q$ for all of it to hold, obviously.


Which MACs can be converted into a secure unkeyed hash function?

I have ask as part of my answer, "What problem are you trying to solve?"

Do you want a secure unkeyed hash function? If you do, then there are plenty of them around. Even some of the ones that are broken for some uses might be okay for yours (SHA-1 springs to mind -- note the discussion above on HMAC and how broken a hash function has to be). But really, you ought to look at SHA-256, SHA-512, or the new SHA-512/t construction.

If you don't like that, look at any of the SHA-3 finalists. (Full disclosure, I'm the co-author of Skein.)

You're right that HMAC is one of them -- but that's basically the null statement. HMAC is a wrapper around an unkeyed hash function that strengthens it against a number of attacks (and adds a key). If you remove the key (or make it a constant), then all you have is a function with two iterations of a hash function with a bunch of frosting and sprinkles over it. It is obvious that if you start with a secure hash function, make a secure MAC and then remove the key then that you will end up with a secure hash function.

What are you really asking? What do you really want to do?

Jon


It looks like you're asking the following:

Consider the following families of distributions over functions from $\{0,1\}^{n} \to \{0,1\}^{n}$:

$\{X_n\}, \text{ where } X_n \text{ is the uniform distribution over the set of functions } f : \{0,1\}^{n} \to \{0,1\}^{n} \text{ such that } f(0^{n}) = 0^{n} $

$\{Y_n\}, \text{ where } X_n \text{ is the uniform distribution over the set of functions } f : \{0,1\}^{n} \to \{0,1\}^{n} \text{ such that } f(0^{n}) \neq 0^{n} $

Are these families of distributions computationally indistinguishable?

I claim they are computationally distinguishable, assuming that each function can be evaluated on input $0^{n}$ efficiently. Consider the following distinguisher, which on input $f$ computes $f(0^{n})$ and outputs $X$ if $f(0^{n}) = 0^{n}$ and $Y$ otherwise. By the definition of $\{X_n\}$, if $f$ is drawn from this family, this distinguisher will output $X$. By the definition of $\{Y_n\}$, if $f$ is drawn from this family, this distinguisher will output $Y$.


I think you're looking for the Typex machine.

It was developed by the British and it had the major design flaw of the Enigma machine removed, which was the fixed-point-free permutation, meaning that no letter will be encrypted to itself.

A Typex simulator can be downloaded on Github (released by GCHQ). Unfortunately I could not find an online simulator, but maybe you'll have more luck.


Is it possible to change PGP / GPG Key Size on an exisiting key?

Thanks for the info Jens Erat

There is no way to "upgrade" an OpenPGP key. You will have to create a new one, and you will loose your reputation in the web of trust.

Think about:

Giving your new key with the old one, so other could follow the signatures
Revoking the old one after some time
Using a seemingly unnecessary large key as primary key and smaller subkeys for day-to-day usage. You will never need the primary key for anything but signing other keys (which is rare) and others verifying your signatures (cheap anyway).

Source


How should one handle the identity value and other "obviously" weak secret random values?

In RSA, ECDSA, ElGamal and quite a few other schemes, using a secret (random) value equal to 1 might not provide any form of security, while still being mathematically sound.

One could argue that the exponent '1' doesn't have any security (because it's easy to compute the discrete log of $1G$); on the other hand, you could equally argue that the value $z = 8827773752...7876547109$ equally does not provide any security, because an attacker could easily compute $zG$ and if he sees that, he knows the discrete log.

  Arguably this holds for secret values smaller than 80 bits, as it might otherwise well be attacked using a brute force search attack.

This is true, if the attacker knows apriori that the secret value was smaller than 80 bits.  Actually, if the attacker knows that, he can find the discrete log with $O(2^{40})$ effort, which is doable by private individuals with access to somewhat more than average computational resources.

On the other hand, taking a random $kG$ value, and making that guess will succeed (assuming a 256 bit curve) with probability circa $2^{-176}$.  In addition, this doesn't only apply only to secrets smaller than 80 bits; if the attacker guesses that the top 176 bits are the value $z$ (above), then he can compute $kG - (z2^{80})G$; if his guess is correct, that'll be in the range $0G$ to $2^{80}G$, and so the brute force effort will succeed (and with the same success probability).

Hence, it is hard to say that a point that happens to be in the range $1G … 2^{80}G$ is any weaker than a point that happens to be in the range $(z2^{80}+1)G … (z2^{80}+2^{80})G$ (and all points are in such a range, for some value of $z$).

  do we have some kind of guidelines for the generation of the "secret random values" we have in cryptographic software.

Why, yes, yes we do.  You pointed out the sections in FIPS 186-4 where they make recommendations (mandates, actually, we're talking about FIPS here) on how to generate such random values.

  even though it is crucial for $k$ values to be unbiased.

And these recommendations accomplish precisely that.  They do assume that the approved RBG that is used generates indistinguishable-from-random bit patterns; as far as we know, the approved ones do precisely this.

You appear to be asking for some tests that reject certain values (such as 1); such a test would introduce a bias (if possibly a tiny one); such a bias is precisely what we're trying to avoid...


What's the difference between single key-pair public key encryption and proxy re-encryption?

With two parties, using proxy re-encryption does indeed not make much sense. It becomes interesting when there are more parties. For example, suppose you receive encrypted mails, that transit through a server. Then you could want to forward one of your encrypted mails, stored on the server, to someone else (say, Bob). With a proxy scheme, you can just ask the server to convert this encrypted mail into a mail encrypted with the key of Bob, and to send it to Bob. In general, it provides a convenient way of managing databases of encrypted files in a multi-user scenario.

You can find more applications in the introduction of any paper on proxy re-encryption. For example, page 3 of this paper discusses examples in more details. This paper also mentions other applications (with references) in the third paragraph of its introduction.


Are there two-way encryption algorithms that include a work factor?

You can use bcrypt to derive a (long enough) key from your initial secret value, and then use the key for symmetric encryption. "Guessing" the key is an issue only when the key is part of a space of possible keys which is small enough that such guessing is a possibility -- i.e. when the "secret value" is a password. A 128-bit uniformly random key is immune to guessing by virtue of being part of a space of size $2^{128}$. So use bcrypt with your work factor, truncate the result to 128 bits, use AES, and you're done: any guessing will have to work with the password, and will thus greatly suffer from the bcrypt work factor.


How can I plot graphs of CP-ABE scheme using charm crypto?

1) Yes, you can use charm as a benchmarking tool for bandwidth performance, for CP-ABE, but not for computational performance, as charm is basically python over the PBC-library (https://crypto.stanford.edu/pbc/). We used charm for Dual-Policy ABE evaluation, but for subjective policies that becomes identical to CP-ABE, see http://dx.doi.org/10.1109/MILCOM.2016.7795382.

2) Bethencourt's cpabe toolkit and charm are actually parallel frameworks. You probably could tweak charm to use PBC via the cpabe toolkit, but there's no reason, as you can use PBC directly from charm as well (easier, in my opinion)


How can one validate with a public key a JWT signature generated with a private key?

I received the following explanation from a separate source.

Send:    { object | encrypt(hash(object), private_key) }
Receive: { object | signature }
Verify:  hash(object) == decrypt(signature, public_key)

This explains what I was struggling to understand.

There are two processes at work here: not just hashing, but also encryption. The actual hashing itself needs no secret parameter, it takes in only the object to be hashed (the concatenation of header + payload in the case of JWT). The resulting hash itself is then the input to the encryption, the result of which forms the signature, which can then be decrypted by the recipient to retrieve the original hash for comparison against the recipient's own computed hash.

Thus, instead of the sender and recipient performing similar calculations, with different secrets, to arrive at the same hash value:

hash(object, private_key) == signature == hash(object, public_key)

we rather have the sender and recipient performing complementary calculations to arrive back at the original input

decrypt(encrypt(hash_value, private_key), public_key) == hash_value

This makes sense with how I understand public-private key encryption.


Is it safe to use a timestamp to build a nonce?

This isn't a very good idea - your chances of collision are not that low (depending on the number of clients you have). At best, your chances are $2^{-32}$ for 2 active clients. You would be better of just using a secure random 96 bit nonce as recommended by the NIST guidelines for AES-GCM (note though that you must not send more than $2^{32}$ messages with the same key when using this construction so that the chance of IV colliding doesn't exceed $2^{-32}$)


My guess is that it is stated a round decimal number (e.g. 2000) of bits in order not to disqualify solutions using keys that can be up to the next round binary number (e.g. 2048) of bits, but are occasionally slightly less.

In particular, in RSA, when we make the product of two 1024-bit primes, the result is 2047 or 2048-bit. This scenario happens with some versions of PGP/GPG, and some SSH software. Contrast with FIPS 186-4, which wants 2048-bit moduli to be exactly 2048-bit, and towards that goal generates 1024-bit primes at least $2^{1023.5}$. TR-02102-2 is slightly more lenient, in a way that does not practically compromise security.


Frequency analysis of transposition ciphers

I did it for substitution ciphers but am unable to do it for transposition ciphers.

When it comes to transposition ciphers, it’s not really surprising frequency analysis doesn’t turn out to be as useful as it is when looking at substitution ciphers.

See, one important strength of transposition ciphers is that they are not susceptible to frequency analysis, since transposition ciphers do not change the symbols for each letter.

Instead of replacing characters with other characters, transposition ciphers just change the order of the characters. Typically, the text to be encrypted is arranged in a number of columns. These columns are then reordered, resulting in encrypted text. This means that, to decrypt/break a ciphertext created using a transposition cipher, you need to find the number of columns (which is usually based on a common factor of the total number of characters in the text) and then rearrange the columns accordingly.

Now, don’t get me wrong – frequency distribution is interesting to look at during a transposition cipher analysis, but for other reasons… frequency analysis on a transposition cipher shows that the constituent letters are what would be expected in a standard text (example: “e” is the most common English letter).

As you’re obviously just starting out to learn how to analyze and potentially decrypt/break transposition ciphers, you could check stuff like the “Analysis of columnar transposition ciphers” section of "Introduction to Cryptology and Cryptosystems" by Prof. H. Williams, which provides a first, rather simple insight.

UPDATE: Since the original PDF of Prof. Williams went offline, here’s an excerpt containing the 3 related pages. Please note that the excerpt I am making available here is provided for reference purposes only and does not represent a complete copy of "Introduction to Cryptology and Cryptosystems".

Also (in contrast to Wikipedia’s related article), there are ample pages online which provide nice examples of the cryptanalysis and deciphering… randomly picking one of them: “Transposition Cipher : nrich.maths.org”.