Can elliptic curve (25519) be used to encrypt file?

No, you cannot "directly" encrypt a file using ECC without generating your own algorithm. Encrypting a file would be extremely inefficient; this is because the block size of ECC is very small, leading to a very high overhead both with regards to data usage (the ciphertext would be strictly larger than the plaintext) as well as CPU-usage.

Yes, any curve can be used to encrypt something if it is suitable to perform ECDH. If ECDH is used then the curve can be used to implement EC-IES.

  I've seen the salsa20 and chacha stream ciphers but I am unsure if they are suitable. If so is there a pre-existing tool that can be used or is something like libsodium the way to go.

Any secure cipher is suitable. It may be smart to go for some existing protocol/library if you haven't implemented a secure protocol or library yet.

Using authenticated encryption should be preferred.


Let's start from the top and work down, using FIPS 202 as reference. Note that the KECCAK paper uses a somewhat different notation (!).
$$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M | 01, 224)$$
$$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M | 01, 256)$$
$$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M | 01, 384)$$
$$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024] (M | 01, 512)$$
this is explained as:

In each case, the capacity is double the digest length, i.e., $c = 2 \cdot d$, and the resulting input $N$ to $\operatorname{KECCAK}[c]$ is the message with the suffix appended, i.e, $N = M | 01$.

Now it is also given that

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

where $\operatorname{SPONGE}$ is defined as $\operatorname{SPONGE}[f, pad, r]$. This means that $r = 1600 - c$ which can be rewritten as $r = 1600 - 2d$.
This is the information that we need for chapter 4: SPONGE CONSTRUCTION

The padding rule, pad, is a function that produces padding, i.e., a string with an appropriate
length to append to another string. In general, given a positive integer $x$ and a non-negative
integer $m$, the output $\operatorname{pad}(x, m)$ is a string with the property that $m + \operatorname{len}(\operatorname{pad}(x, m))$ is a positive
multiple of $x$. Within the sponge construction, $x = r$ and $m = \operatorname{len}(N)$, so that the padded input
string can be partitioned into a sequence of $r$-bit strings. Algorithm 9 in Sec. 5.1 specifies the
padding rule for the KECCAK functions and, hence, the SHA-3 functions.

Here $N$ is the input string of Keccak / SHA3 and $m$ is therefore the length of the input string (in bits).
So great, we now can finally look at the definition of $\operatorname{pad10*1}$:

Within the sponge construction, $x = r$ and $m = \operatorname{len}(N)$

Let $j = (– m – 2) \bmod x$.
Return $P = 1 | 0^j | 1$.

Now negative modular calculations can be a bit confusing, but it is clear that no matter what, the maximum value of $j$ and thus the number of zero's is $x - 1$ or $r - 1$ as $x = r$. This is because $m$, the input length, can have any non-negative value. As this is for the sponge, this is also true for $\operatorname{KECCAK}[c]$ and therefore SHA3.
Now $m = \operatorname{len}(N)$ but $N = M|01$. In other words, the input $m$ is the message length - say $l$ - plus two bits. So that means that $j = (– m – 2) \bmod r = (– (l + 2) – 2) \bmod r = (–l - 2) – 2) \bmod r = -l - 4 \bmod r$. This maximum will be reached for $l = N \cdot r - 3$. This is kind of expected; if you have a minimal overhead of 4 bits for the padding then a message three bits shorter than the $r$ will require the maximum padding as the padding will overflow into the next block.

SHA3-224 means $r = 1600 - 448 = 1152$, so for $N \cdot 1152 - 3$ the maximum number of zero's is reached, which will be $r - 1 = 1151$ zero's.
Let's check this for $N = 1$: $\operatorname{len}(\{0,1\}^{1149}|01|1|0^{1151}|1) = 1149 + 1151 + 4 = 2304 = 2 \cdot 1152$. So that indeed leads to two times the rate $r$.

The usual input of hash algorithms isn't in bits, but in 8-bit bytes. In that case the input would simply be $N \cdot r$ for a maximum number of zero's that's of course $8 - 4 =4$ bits smaller. The number of zero bytes is of course $r / 8 - 2$ bytes.
Lets validate this again using SHA3-224. The first block of $r$ bytes would just be the message and the last block of $r$ bytes would consist of $06 | 00^{142} | 80$ in hexadecimals. This seems strange but that's because NIST uses little endian and flipped bit order (low order bits leftmost in the padding, but rightmost in the bytes, i.e. bit $b_7$ is on the right).


Is it OK to use r-value from ECDSA signature (r, s) to prevent replay attack?

I have to be honest and say that I never really understood why systems use the signature as the record rather than just the hash of the message that was signed. If that was used, then there would be no problem with using malleable signatures. If someone has a reason why not to just do what I said, please let me know and I'll change the answer.
More to the point of the question, there is no reason why not to just use the $r$ portion. If this repeats in two different valid signatures, then the signers can each learn the other party's private key. This is because by dividing the $s$ portions in the signatures, the $k^{-1}$ part falls away. Then, given one of the private keys it is easy to learn the other private key. As such, this should not be a concern to anyone (i.e., if it could happen then malleability is far from the problem).


Can one tell private key entropy from a public key?

Since the private key is a value, it's entropy is undefined. We could define the entropy (per key) of a process generating the private key, but we'll stick (except in 3) to the usual modeling of asymmetric key generation as a process producing both the public key and the private key from a random generator. We thus reformulate the question as:
Can we detect low entropy at the output of the random generator from the public key alone?
Sometime, depending on the nature and profoundness of the random generator defect, on the cryptosystem, and one how many public keys was examine. Situations where that's possible include:

When the generator twice outputs the same value, and we can see that it twice generated the same public key.
The generator's output during a key generation is, with sizable probability, among a known set small enough to be predicted, and we know the key generation algorithm (part of the standard theoretical hypothesis in crypto). We can apply the key generation algorithm to this set, and test if the public key is among the results. That can also yield the private key.
As a variant of the above, in cases where defects of the generator conspire to make the private key similarly restricted to a small set, and the public key can be efficiently computed from the private key. The later applies to many cryptosystems based of the Discrete Logarithm problem in some public group (ElGamal encryption, Schnorr signature, DSA, ECDSA, EdDSA). It also applies to RSA when the private key contain $e$, or/and $e$ is small enough to be guessable.

For many cryptosystems, these methods are the best known to detect a low-entropy source from the public key. For others including RSA (and more generally most cryptosystem relying on the difficulty of integer factorization), there are better ways. For example, if the prime number generator used to generate $p$ and $q$ of an RSA key returns values in a list of $2^{40}$ unknown (and un‑guessable) primes, that's detectable with good probability from about $2^{20}$ public keys (it also recovers matching private keys for some of the public keys). That's the GCD attack, and it happened, more than once.


Is there a term for cryptographic attacks where you can verify decryption without assuming any known structure on the plaintext?

You're missing that using a KEM for hybrid is not encrypting random garbage.
Say you have a chain of ciphertexts $C_1||C_2||\dots|| C_n$, where $C_1 = \mathsf{Enc}_K(k)$, where $k$ is an AES key, and $C_2||\dots||C_n$ is the result of encrypting some stream of plaintexts under the AES key $k$ in some mode of operation.

If we can compute $k = \mathsf{Dec}_K(C_1)$, we can easily check if we decrypted correctly by decrypting $C_2||\dots||C_n$ under the aforementioned mode of operation.
Assuming this data has any structure (or any way to distinguish it from random garbage essentially), one can bootstrap that to a method to distinguish $\mathsf{Dec}_K(C_1)$ from random garbage.

If someone did encrypt (using the block cipher mode of operation) some sequence of random data $P_3||\dots||P_n$ (one block is used for the IV in the mode of operation), we could no longer use the aforementioned method to distinguish a correct AES key.
Then the linked comments would still be problematic (from the perspective of an attacker) --- there's no way to distinguish a bunch of random garbage from random (provided its distributed the same), so its essentially hopeless to ask.

This is essentially making the point that just because $k$ is (hopefully) uniformly random on some domain by itself, the rest of the ciphertext blocks are highly dependent on it, which can be utilized to develop a "correctness test" for guessing $k$.
So $C_1$ satisfies the "random garbage" property, but $C_1||\dots||C_n$ (jointly) doesn't.

Your second question is interesting, but I can only comment on the first question unfortunately.


Vigenère, auto-correlation vs Kasiski examination

Kasiski's test only considers repeated sequences of characters, under assumption that the text contains repeated words with distance between them being a multiple of key length.

Autocorrelation analysis simply counts matching characters between shifted ciphertexts. Then you have to identify "maxima", which are shift distances with higher match counts than the others. The assumption here is that the text from the language correlates strongly with itself. This is more general than assuming the existence of long repeated sequences.


ElGamal malleability for a given function f(m)

To understand how this works, let's first recap how ElGamal works:

All parties agree on system parameters $(\mathbb G_q,q,g)$ first such that  and the order of $g$ in $\mathbb G_q$ is $q$. All the formulaes to follow need to be read as being done in $\mathbb G_q$ written multiplicatively, except if specified otherwise.

Next the recipient picks a random $x\in\mathbb Z_q$ and publishes $\beta=g^x$ as his public key and keeps $x$ as his private key.

Now finally the sender picks a random $y\in\mathbb Z_q$ himself and computes $c_1=g^y$ and $\beta^y=g^{xy}$. He uses this "shared secret" to multiplicatively blind the message $m\in\mathbb G_q$ as $c_2=m\cdot \beta^y$. The cipher text is now $(c_1,c_2)$.

Now you want to modify $(c_1,c_2)$ to $(c_1',c_2')$ such that $m'=m^k$ for arbitrary choices of $k$.

This is indeed trivial. First observe what happens if you calculate $(c_1',c_2')=(c_1^k,c_2^k)$. As you may already see, this means you actually calculate $(g^{yk},(g^{xy}\cdot m)^k)$ and this is exactly $(g^{yk},g^{xyk}\cdot m^k)$ which in turn decrypts to $m^k\bmod p$ as the recipient will just compute $c_1^x\equiv g^{xyk}$ to unblind the message $m'$.

In the above explanations, plug $\mathbb F_p$ (with $\mathbb P\ni q=(p-1)/2\wedge p\in\mathbb P$) in as your group $\mathbb G_q$ and $k=3$ to get the answer to exactly your question. Alternatively you may plug the group of the points on your favorite elliptic curve in as your $\mathbb G_q$ and pick $k=42$.


Working on subgroup of $\mathbb{Z}^*_p$ in practice

When using any cryptosystem that relies on the Decisional Diffie-Hellman assumption (e.g., ElGamal, ECIES, Diffie-Hellman key exchange, etc.) then you need a group of prime order. Note that $\mathbb Z_p^*$ where $p$ is prime has order $p-1$. However, if $p=rq+1$ where $q$ is also a large prime, then you have a subgroup of $\mathbb Z_p^*$ of order $q$. If you take $r=2$, then these are the so-called safe primes (once it was thought that for RSA it's best to use these types of primes, and that's why they are called "safe"; however, today, it is accepted that it's best to just choose random primes for RSA). In order to get a subgroup of order $q$, indeed you just take the squares.

Answering your specific questions:

For the cryptosystems that I mentioned above, YES you MUST work in the subgroup.
You need to map any value that you need into the subgroup. You can map any value between 1 and q-1 by just squaring it.
No, you do not do $\bmod q$ on the elements (you do $\bmod q$ when working on values in the exponent).

I recommend that you take a book that gives the number-theory background necessary for crypto...


Are the S-boxes they are considering just random permutations of bytes that fit into an 8×8 table? How might they have chosen all the entries to get the S-box?

Yes, they chose a random s-box.

  Are they choosing a random S-box and then leaving it unchanged thereafter

Yes, it was unchanged.

  In Section 3.1 they state differential cryptanalysis will not pose a threat to variants of AES where the S-box is replaced by a randomly chosen 8-bit box. This is confusing. Do they mean one 8-bit element in the S-box? I thought the S-box was 256-bit, not 8.

AES s-box size is 8-bit (8-bits in X 8-bits out), which is 256 entries, represented as a 16x16 table of bytes, which is 4+4 input bits with 8 output bits.

  Still referring to Section 3.1. If a random S-box is secure against DCA and LCA, why make such an effort to design the one currently in use?

A random s-box must be represented as a table in both machine code as well as in analysis of the cipher, the one chosen for Rijndael can be represented as an equation or a much smaller block of code. It also has better differential and linear properties than a random s-box, even if random was sufficient.

  How does a random S-box cause the secret information to go from 128 to 256 bits (depending on the key size) to 1812 to 1940. I understand there is now more secret information owing to the secret S-box but I cannot see where these numbers (1812 to 1940) come from.

I am guessing the extra bits was the information required to generate the s-box, apparently 1684 bits.

Despite that fact, and the fact an attacker does not know the s-box, they were sill able to create practical attacks up to 6 rounds, there are other properties of s-boxes, and random ones usually suck in regards to those properties, where they do well is in algebraic complexity.


If you SHA something that already has work put into it, is it still safe?

Theoretically this provides less collision resistance than straight SHA-512 hashing or straight PBKDF2 hashing. The reason is that if you can find a collision in either function, you can either make the input to SHA-512 the same or can (potentially, even though it's practically very hard) exploit the collision in SHA-512.

Practically however, collision resistance stays the same, which is "unbreakable", as we don't know a way to break SHA-512 in that regard, nor do we know how to break the collision resistance of PBKDF2.

As for password-hashing, the application which seems most likely here, the additional hash won't make the construction weaker, as you still have to do the 1M rounds of hashing to get to the relevant SHA-512 input. Note however that using PBKDF2 for password hashing is strongly discouraged in all but the most extreme cases due to much better and stronger alternatives like Argon2 and bcrypt being available.


Alice wants to prepare Bob for a future message.
Alice generates a public key $(n, e)$ and private key $d$; she keeps the private key for herself only, and gives the public key to Bob up front.
When Alice has decided on the message $m$, she scrambles it and compresses it irreversibly into an integer $h$ the same size as $n$ by a public hash function $H$ of the message, giving $h = H(m)$, and computes $s \equiv h^d \pmod n$.
Alice sends Bob the signed message $(m, s)$.
When Bob gets a possibly forged signed message $(\hat m, \hat s)$, he computes $\hat h = H(\hat m)$ using the public hash function $H$, and rejects it unless $\hat h \equiv \hat s^e \pmod n$.

For Alice's original legitimate message, $s^e \equiv (h^d)^e \equiv h^{de} \equiv h \pmod n$, so Bob always accepts a legitimate message from Alice.
Mallory, who intercepted the message $m$ in transit, and wants to replace it by $\hat m$ (but who does not have the private key $d$), does not know the corresponding $\hat s$ that Bob will accept.
Bob can show the message to Charlie, if he also has Alice's public key, and Charlie can verify it too using the same procedure—Alice can't send one message to Bob and claim to Charlie she didn't sign that message.  (This property is called ‘nonrepudiation’ or ‘undeniability’.)


Why does the time complexity of RSA encryption and decryption depend on the size of the modulus?

The number of CPU cycles required to perform each multiplication increases with the size of the modulus $N$, since the operands can be as large as $N$, and also multiplication is followed by reduction modulo $N$.

Depending on what exactly you are analysing, you may sometimes consider $N$ to be constant (e.g., if you are comparing two exponentiation algorithms) and discard it when doing asymptotic complexity analysis, but if $N$ can vary, then certainly a larger $N$ means your computation will take more CPU cycles.


Known plaintext, unknown 128 bit block cipher

All modern block ciphers are supposed to be pseudorandom permutations, meaning that they cannot be efficiently distinguished from a truly random permutation without knowledge of the key.  (If a practical distinguisher were to be found for a particular cipher, that cipher would be considered broken by modern standards.)

This also implies that no two secure modern block ciphers (with the same block size) can be practically distinguished from each other, unless one knows the key being used.  Thus, unless the cipher being used is broken, or unless you can somehow find out the key, the answer to your question is "no".


Assume the message is an $n$-bit string with each bit drawn independently with $P(0) = p$.

Let $A$ be the event that the key bit is $0$.

Let $B$ be the event that there are $k$ zeroes in the ciphertext.

Then $P(A) = \frac{1}{2}$ and $P(B) = \frac{1}{2}{{n}\choose{k}}\left(p^k(1-p)^{n-k} + p^{n-k}(1-p)^{k}\right)$, since with equal probability we had $k$ zeroes or $n-k$ zeros in the message.

$P(B | A) = {{n}\choose{k}}p^k(1-p)^{n-k}$ since this occurs exactly when the message originally had $k$ zeros

Then $P(A | B) = \frac{P(A)P(B | A)}{P(B)} = \frac{p^k(1-p)^{n-k}}{p^k(1-p)^{n-k} + p^{n-k}(1-p)^k}$


HMAC was there first (the RFC 2104 is from 1997, while CMAC is from 2006), which is reason enough to explain its primacy. If you use HMAC, you will more easily find test vectors and implementations against which to test, and with which to interoperate, which again explains continued primacy. Being the de facto standard is a very strong position.

On many embedded systems, one may expect HMAC to be faster than CMAC, because hash functions are usually faster than block ciphers. This is not true if the platform includes some hardware optimization for a specific block cipher (e.g. dedicated AES opcodes), or if the messages are short (HMAC has the same asymptotic cost as hashing, but also a fixed overhead), or if you do something stupid like selecting a slow hash function as a basis for HMAC (e.g. Whirlpool). As with all performance things, actual measures are needed to reach any kind of definitive conclusion.

If you need to both encrypt and MAC, then the smart thing to do is not HMAC or CMAC, but rather to use an authenticated encryption mode which will do both properly, simultaneously, and at a lower cost (or at least so it is hoped). Usual candidates are EAX and GCM. The CAESAR competition was held to find new, better AE (Authenticated Encryption) ciphers.


Random Self-reducibility in Discrete Log

I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is how does it show that DL is hard in the average case.

Actually, Random Self-reducibility does not show that DL is hard in any case.  What it does show that if there exists a hard DL instance, then random DL instances are hard.

Remember, the "Random Self-reducibility" property is that we can take an arbitrary instance of the problem $g^x = h$, find $x$, and turn it into a random instance $r_1^y = r_2$, find $y$, and if we can solve the random instance, we can go back and solve our original problem.

How it shows that average instance is hard is by showing the converse; if the random instance had a nontrivial probability of being easy, then we can solve any arbitrary instance (by randomly transforming our arbitrary instance a number of times, and if we happen to hit an easy instance, which we have a good probability of doing, we get to solve the original problem).

All this formalism (which is what is tripping you up) is just expressing this concept in mathematical terms (as opposed to the verbal description I used).

Of course, if you try to do formalism, it is important to get the formulae right.

  The probability of success of an imperfect DL black box is $p(n)$ (for an $n$-bit string, and $p$ is a polynomial). So, in order to get a correct DL for an input $y$ is $1/p(n)$.

Actually, the probability would be $1/p(n)$; remember, probabilities are restricted to the range $[0,1]$

  Afterward, in a lecture the professor, went over describing that the probability of succeeding every time is

Actually, if the attacker is attempting to do this, he doesn't have a succeed every time; all he needs to do is succeed once.  A single success (that is, a random reduction into an instance that allows him to solve the DL problem) will tell time the answer to the DL problem he is actually interested in.

  $\left(1-\frac{1}{p(n)}\right)^np(n)$

That might be the probability that the attacker will need to perform precisely $n+1$ random reductions before hitting on an answer, but if so, I'm pretty sure you garbled that formula (as well as apparently using $n$ with two different meanings, the size of the DL problem, and the number of random reductions the attacker tries)


Are there any signature schemes for underpowered devices (8-bit microcontroller)?

For your application: "I need the (underpowered 8-bit) slave to be able to tell if a command issued is really trustable", RSA signature with low public exponent ($e=3$), or Rabin (an analog with $e=2$), is likely the most appropriate, assuming you can't trust the slaves to keep a key secret, which is the only realistic assumption unless that slave uses hardware with a level of physical security comparable to a Smart Card, like this 8-bit IC (link to TOE).

For example, a standard 8051 core running @4MIPS peak (48MHz xtal) or a 68HC11 @6MHz EClock (24MHz xtal) can verify a 1536-bit RSA signature ($e=3$) per PKCS#1 or ISO/IEC 9796-2 in 1 second, or about half that for Rabin ($e=2$), with well under 4kB of code, and little RAM. There are even faster Rabin-like schemes (though less common).

One problem is size of the signature: it is the same as the modulus, that is in my example 1536 bits (192 bytes) for PKCS#1, but the overhead can be much less with ISO/IEC 9796-2: max(34, 192-M) bytes where M is the size in bytes of the message/command, using a 256-bit hash like SHA-256, thanks to message recovery.

Update: Do not use Rabin with 160-bit public modulus, this is entirely unsafe, see this; such a modulus can be factored in seconds with public-domain tools like GMP-ECM, or perhaps even (with more time) an applet.

Update 2: The 8051 code quoted above uses a minor variation of straight textbook modular arithmetic, without Montgomery (which does not help for modular squaring or cube, at least in standard RSA/Rabin schemes) or Karatsuba, but with extensive low-level optimization in assembly. The variation (relatively straightforward but unpublished AFAIK) is that modular reduction occurs during the multiplication, rather than after, and within the same scanning of intermediary result. It works with no restriction on the modulus bit size or value. That has been used in a commercial implementation, developed and sold over a decade ago for POST of several brands and CPUs, and was (perhaps: is still) used for verification of Smart Card certificates, and/or signed code update. There was strong code size constraints, thus things are not optimized to the max for speed (no loop unrolling), rather for a balance of simplicity and reliability, size and speed. Here is an old commercial doc in French (full disclosure: this is my code & company). If you can make a few reasonable constraints on the public modulus, there are other optimizations leading to further simplification, and moderate speedup.

Update 3: 320-bit RSA modulus was already considered marginally safe 25 years ago, and I wildly guess would be factorisable in minutes on a single modern machine with a good MPQS or SIQS implementation like SIMPQS, or msieve if you find a wizard to get it running. And even with more decent RSA modulus size like 640-bit, the idea of short-lived public keys is hard to get right, especially if the devices must survive power loss. Unless I err, a trusted long-term key is required (chained certificates of short-term keys will not do). Also, your devices need a trusted source of current time (either internal or external). My advice is: forget about it for something secure; a symmetric MAC (as proposed in another answer) might be preferable.

Update 4, revisited: Your S08 CPU has 8x8->16-bit multiplication in 5 cycles. Unless I missed a divisor somewhere, that seems to be 125ns @40MHz. This is over 13 times faster than 10 cycles @6MHz on the HC11 (of 12 years ago) on which my code does 1536-bit RSA, $e=3$ well under 1 second. Bus cycles are also faster (20MHz vs. 6MHz) and I did not see mention of wait states for internal RAM. Despite the lesser instruction set (no 16-bit registers and addition), I guesstimate that a similar highly-optimized implementation on that S08 thing would check a 1536-bit Rabin signature in 0.2 second, give or take a factor of 2, using under 1kByte 416 or 608 bytes of RAM, depending on if the public key (in a form directly usable for computation) is present in Flash or not; this RAM is needed during signature verification only, and can be shared with other non-concurrent tasks; the 192 bytes of signature are included in this low RAM budget, and could be discounted if the signature is at a fixed address. Again this is in hand-tuned assembly, C compilers easily eat a factor of 10 or worst on multi-precision arithmetic, and keeping the RAM budget low requires some care.

Update 5a: A 1536-bit signature is only 192 bytes; and can, as well as the temporary variables necessary to check it, reside in RAM shared with the rest of the application; that is, the stack (which in any half-decent 8-bit development system I use is not the physical stack, but simulated by static analysis of the call tree). Thus you do not face a difficult RAM size issue using a decent RSA modulus key size in your application.

Update 5b: A "chain of certificates" introducing short-term public keys certified by the previous one would not be secure if the slave has to survive power loss, because the adversary can capture the current public key, cut power, factor that, restore power, and then forge a chain of certificates for fake short-term public keys of known factorization, that will be accepted by the slave, and boom the slave is "pwned". This is even if we assume that the slave has access to a trusted source of date/time, and each certificate carries a date/time of expiration.

Update 5c: The question and comments show a tendency to under-size RSA modulus, under the fallacy: if I can't factor it, surely that's good enough to bother my adversaries. That line of thought is wrong and dangerous, at least until one carefully researched the public state of the art (which, one must assume, any intelligent adversary will use), and has used power comparable to modern adversaries who could distribute factorization work on many (perhaps pwned) computers, and can safely assume none of the adversaries is smart enough to improve the state of the art. The sources quoted by keylength.com go one step further, and want some confidence that conceivable improvements in the state of the art, and true computer power available at a price, are unlikely to cause a break in a parameterizable number of years; that's one of the reason they ask for sizes way above the academic state of the art; and perhaps their known state of the art encompass more than the academic; and they of course have a desire to be on the safe side. I'm borderline prudent when I even discuss 640-bit RSA modulus for very short-term keys: 512-bit keys are routinely factored in days by enthusiasts on a shoestring; again see this here, as well as the true tale of banks using 321-bit keys way longer than reason and advise, in a high visibility/stakes application.


Collision resistance of partial SHA-256 hashes XOR'ed

Let tne hashlength be $d$. With $k=12,$ this is the $k-$ XOR problem. Fix $k.$ If the vectors are randomly generated and form a list of size roughly at least $2^{d/k},$ there exists a solution with constant probability bounded away from zero. This is because a list of size $M$ contains $$F:=\binom{M}{k}$$ subsets of size $k,$ and thus as
$\{x_1,\ldots,x_k\}$ ranges over these subsets the function $f(x_1,\ldots,x_k):=x_1\oplus \cdots \oplus x_k$ ranges over $\{0,1\}^d.$

This is a $F$ balls into $2^d$ bins problem and if $F\geq 2^d,$ the probability that $f$ misses the bin corresponding to your given hash value
$h_0 \in \{0,1\}^d$ is roughly $e^{-1}\approx 0.37.$ Taking $M=\Omega(k 2^{d/k})$ is enough here. However, finding the solution is computationally more expensive.

Wagner (see here ) has a recursive binary tree based algorithm for the $k-$ XOR problem $$x_1\oplus \cdots \oplus x_k=0 \qquad (1)$$ with $k=2^m,$ with time and memory complexity essentially
$$O(k 2^{d/(1+m)}).$$ The zero vector on the right hand side of (1) can be replaced by any constant vector.

Let $x_9,\ldots,x_{12},$ be arbitrary and use Wagner with $k=8$ to solve the $8-$ XOR problem

$$x_1\oplus \cdots \oplus x_8=c,$$
with $c=x_9\oplus x_{10} \oplus x_{11} \oplus x_{12}\oplus h_0.$ This can be done with complexity
$$O(k 2^{d/(m+1)})=O(8 \times 2^{256/4})=O(2^{67}).$$


From Factorisation of semiprimes to breaching confidentiality

I guess it depends on which scenario you are referring to. If it is RSA, being able to factorize $n = pq$ would compromise the security of that crypto-system.

This is because one could compute $\phi(n) = \phi(p)·\phi(q) = (p-1)·(q-1)$ since $p$, $q$ are two distinct primes and could calculate the private key $d$ from the public key $e$ by using the equation $e \cdot d = 1 \mod \phi(n)$.


Proving that the least significant bit of an elliptic curve discrete logarithm is $0$

Take a look at SNARGs, e.g. Bulletproofs (which are range proofs).
The proof may be slightly too large though.

Assuming that $a \in \{0, \ldots, q-1\}$ is your representative,
you want to prove is that you know a bit decomposition of $a$ with
$a = a_1 d_1 + a_2 d_2 + ... + a_k d_k$
where all $d_i$ are even and $\sum d_i = p-1$.
E.g. $d_i = 2^i$ but $d_k < 2^k$ otherwise you can get wraparound.
This trick is found in some range-proof paper(s).
Without this, it may be possible to find, for odd $a$, a bit decomposition $a_i$
with $a' = \sum a_i d_i$,
and $a'$ even (due to wraparound, $a = a' \mod q$).
Hence you don't get a proof for "(representative of) a is even".

One question though: Why is the last bit zero? If you just want to split
the exponents into two groups, using squares and non-squares is more efficient w.r.t. ZK.
It's simple and efficient to prove that $a = b^2$ (with standard sigma
protocols).

It seems hard to somehow express "is divisible by 2" efficiently,
because all calculations happen over finite fields,
hence every (non-zero) element is invertible.
So there is no such thing as "even and odd".
(Also: $1$ is odd, $1 + p$ is even, but $1 + q \equiv 1 (q)$.)
But: Polynomials make sense, e.g. squares $f(x, y) = x^2 - y$
or bits $f(b) = b (b-1)$.
The vanishing/zero sets of polynomials are "algebraic",
which helps in the group setting.


The $\parallel$ notation means concatenation. In this case, take the message $m$ (it's a sequence of bits), encode the value $r$ as a sequence of bits, and hash the sequence of bits that consists in $m$ followed by the encoded $r$.

In the step 4, you have a sequence of bits (hash output) that you must somehow convert back to an integer. This is again a question of encoding, but in the decoding direction this time. The underlying theme here is that you must have some convention that lets you encode integers into bits, and decode bits into integers. From a security point of view, the choice of convention is more or less open, but of course it is part of the algorithm specification: signer and verifier must agree on these details, otherwise the verifier won't accept as valid the signatures produced by the signer.

By the way, this is not DSA. DSA is specified by FIPS 186-4. What you describe is known as Schnorr signatures (there are several variants, e.g. on the order of $m$ and $r$ in the concatenation, or whether $s = \alpha h + k$ or $s = \alpha h - k$; all these variants procure more-or-less equivalent security). Historically, the distinction was important: DSA was defined at a time when Schnorr had patented his scheme, and the definition of DSA was carefully made to avoid that patent. Cryptographically, the difference also matters: the "security picture" of Schnorr signatures is better (we can make security proofs on Schnorr signatures, but we don't know how to do that with DSA; and DSA signatures are malleable, a property which is usually harmless but has allowed replay attacks in Bitcoin in the past).


Security difference(s) between Shamir's Secret Sharing Scheme and Blakley's Secret Sharing Scheme?

They are both perfectly (information theoretical) secure, as you mentioned, Shamir's Secret Sharing Scheme is more space efficient.
When Blakley's scheme is optimized by using finite fields, it eventually turns into Shamir's Secret Sharing Scheme.
They are equal from a security perspective.


AES encryption using a Diffie-Hellman question

Does AES create it's own shared secret symmetrical key after the DH process has completed?

No. AES uses the key that is produced by the Diffie-Hellman key agreement, possibly after key derivation using a KDF or PRF.

  With DH, I've always had conflicting answers, some say if you create a 1024 bit DH key then AES creates the 128 bit symmetrical key and passes it across, i don't feel like this is the case (i'm happy to be corrected either way). Some have also said that the key from DH is the key that AES uses for it's encryption. My question would be then isn't it just using a 1024 bit public/private key exchange to encrypt and decrypt data, or is it something in the middle?

Diffie-Hellman is an asymmetric key agreement protocol. It requires two Diffie-Hellman key pairs (generated using a secure random and the Diffie-Hellman key generation procedure). Either of these key pairs can be ephemeral (i.e. used once or just a few times) or static (persistent, part of a DH certificate). After the public keys are exchanged the Diffie-Hellman calculation is performed and a shared secret is produced - this is the base value from which the shared (AES) keys can be derived.

The shared secret is large and not fully random. So generally it is run through a key derivation function or KDF to calculate the keys from the shared secret. TLS/SSL calls this the pseudo random function or PRF - a more generic term. For older versions (1.0 and 1.1) the TLS PRF internally uses a combination of MD5 and SHA1 (doubled in the HMAC construction, which is further doubled); 1.2 uses SHA256 (in double HMAC) for the pre-existing cipher suites (which specify MD5 or SHA-meaning-SHA1 for HMAC on data records) but newly-defined suites can name a different hash for the PRF and some do use SHA384, in conjunction with AES-256 for encryption.

Besides the master secret the KDF also uses the identity of the client / server and a label to derive keys. In the end you should have a total of two or four keys: two if authenticated encryption such as GCM is used and four if the authentication (HMAC) is performed separately from encryption.
In 1.0 the KDF also derives two initial IVs for CBC suites (which was associated with a flaw, since fixed) and in 1.2 the KDF can also derive two partial IVs for GCM or CCM suites.

One of these keys are used to encrypt and possibly authenticate the messages from the client to the server and one for the messages in the other direction. It depends on the cipher suite if AES is used for encryption or not.

For TLS 1.3 the use of ephemeral keys is required (DHE or ECDHE). Authenticated encryption (an AEAD cipher) is required as well, so only two keys need to be produced for regular data encryption, although 1.3 also derives several more keys used during the handshake and optionally for special purposes. If RSA or ECDSA is used then it is only to authenticate the client / server; neither RSA or ECDSA will directly be involved in the key agreement.


Can modular multiplicative inverse be used to create a secure cipher?

The question uses the term "cipher" in a non-standard way: in cryptography, a cipher's key is usable for multiple messages, and that's explicitly not the case here. We'll extend the term cipher to something with the restriction that components of the key (here, $e$ and $d$) are used for a single message. We'll assume a supply of distinct random secret one-time key components $e$ and $d$ known to encrypting and decrypting parties.

It is asked if the "cipher is secure (or not)". The most standard modern definition of security of a cipher is indistinguishability under Chosen Plaintext Attack. That defines an experiment where an adversary chooses two plaintexts, gets them encrypted, and tries to match ciphertext and message (we'll ignore that this experiment normally uses ciphertexts obtained under the same key).

In this section, we assume there is no random padding (that is, $m_p$ is defined as $m$).

The cipher as stated is not secure per the modified CPA definition: an adversary can submit $m=0$ and $m'=1$, and can recognize the ciphertext $c$ for $m$ from the ciphertext $c'$ for $m'$, because $c=0$ and $c'\ne0$.

The additional restriction $0<m<N$ is not enough for security: if the adversary knows a divisor $d$ of $N$ with $1<d<N$, then the adversary can submit $m=d$ and $m'=1$ and can recognize the ciphertext $c$ for $m$ from the ciphertext $c'$ for $m'$, because $c\bmod d=0$ and $c'\bmod d\ne0$.

However, if the condition $\gcd(m,N)=1$ is imposed to adversaries, and if $e$ is chosen uniformly at random among the subset $\Bbb Z_N^*$ of integers in $[0,N)$ such that $\gcd(e,N)=1$ (this later condition is equivalent to existence of $d$), then demonstrably the cipher leaks no information about $m$ and is CPA-secure. Proof sketch: for fixed $m$, the function $e\mapsto c$ is reversible onto the finite set $\Bbb Z_N^*$, hence is a bijection, hence $e$ uniformly random implies $c$ uniformly random, hence $c$ leaks nothing about $m$.

Methods to impose the condition $\gcd(m,N)=1$ to adversaries include requiring $0<m<N$ and making $N$ either a hard-to-factor RSA modulus of factorization unknown to adversaries, or a prime. However neither is possible in the context (note: where $r$ and $r^{-1}$ are the $e$ and $d$ of the present question), since an adversary is the holder of an RSA private key for $N$, which allows to efficiently obtain the factorization of $N$ and implies $N$ is not prime.

Now we introduce padding. The question's encryption and decryption equations become
$$\begin{align}
c&=m_p*e\bmod N\\
m_p&=c*s\bmod N
\end{align}$$
All random paddings used in RSA (including OAEP) make $\gcd(m_p,N)=1$ overwhelmingly likely, including for adversaries knowing the factorization of $N$ and able to chose $m$ before padding. Therefore, with $N$ an RSA modulus, and a secure RSA random padding tailored for this modulus and using a random number generator not under control of adversaries, the cipher is CPA-secure (per our modified definitions of cipher and CPA-secure).

The choice of $N$ has no influence on security, and its factorization needs not be kept secret for the security of the cipher in the question.

If we leave the padding unspecified, security can depend on $e$ being uniformly random in $\Bbb Z_N^*$ (which can be obtained by taking $e$ uniformly random in $[0,N)$ until $\gcd(e,N)=1$, with this later condition overwhelmingly likely when $N$ is an RSA modulus). However, with OAEP padding, it is enough that $e$ is chosen in $\Bbb Z_N^*$ using a method yielding large entropy.


Why do the outputs of parties in an MPC protocol have to be indistinguishable from the ideal / real world (as opposed to inputs)?

Suppose you have a black box with some buttons and some lights. When you push the buttons, the lights go on and off. You wonder what's inside, but you cannot open the box. The only way to figure out what's inside is by pushing buttons and observing the lights.

Now suppose you have two black boxes. You wonder if they are the same on the inside. Again, you cannot open the boxes, so you cannot decide by inspection. You are reduced to pushing buttons, observing lights and comparing. If a sequence of button pushes usually causes a light on one box to turn on, while the corresponding light on the other box usually stays off, you know the insides are different (probably).

Note that if you have two exactly identical black boxes and push the buttons in exactly the same way on both boxes, their lights may still behave differently. That's because inside the box, there is a source of randomness, and each box may produce different randomness.

Now suppose the insides of the black boxes really are different, but if you press the buttons in the same way, the lights always seem to go on and off in the same fashion. For you, the black boxes are effectively identical, because you now have no way of distinguishing one box from another.

If you push different buttons on the two black boxes, they will probably respond in different ways. But that doesn't allow you to distinguish them.

That was easy. The tricky part is the interpretation.

Protocol input and adversarial tampering correspond to button pushing. Flashing lights correspond to protocol output and whatever the adversary can observe during protocol runs.

On the inside of the first black box, we have the real protocol's honest users and whatever infrastructure they use.

In the second box, we have two things. One thing (often called the ideal functionality) gathers up the honest users' inputs and computes the outputs in the required way. The second thing (the simulator) gets certain information about the inputs and outputs (the specified allowed leakage) from the first thing. It simulates observations for the adversary to enjoy.

Now we observe two things about the second box:

It will always do the computation correctly.
The adversarial observations are computed using only the allowed leakage, so nothing more than the allowed leakage will leak.

If the first box cannot be distinguished from the second box, it follows logically that this must also apply to the first box. Which means that we have established that our protocol is secure.


Yes, this sounds secure to me.  HMAC, like any secure MAC algorithm, is designed to be existentially unforgeable under chosen-plaintext attacks: that is to say, even if the attacker was allowed to request from you the MACs for any set of messages they wanted, they would not be able to compute a valid MAC for any message they didn't request it for.

(Of course, this is only guaranteed to hold if the hash algorithm used to instantiate HMAC meets the security assumptions set out in the HMAC security proof.  In practice, though, secure cryptographic hash algorithms like the SHA-2 family are believed to meet these assumptions — and, in any case, HMAC is a very robust construction and seems to be very tolerant of even rather poor hashes like MD5.)

Of course, I'm assuming that all clients will be getting their own HMAC keys, so that you can revoke keys if they're compromised or simply if the client stops subscribing to your service.


Weird exam question about RSA and Chunksize

Here's how I would interpret these two questions:

(C): if we are restricted to encrypting plaintexts that are bitvectors of a specific length, is 10 bits the largest bitvector Alice can encode (using Bob's public key), without causing any decryption failures when Bob needs to decrypt?

(D): if we are restricted to encoding ciphertexts as bitvectors of a specific length, is 11 bits the smallest bitvector Alice can produce (using Bob's public key), without causing any decryption failures when Bob needs to decrypt?


Finding length of a key for a given vigenere cipher using Index of Coincidence

The index of coincidence is significantly higher for

The correct keylength
All its multiples

Even if that is not the correct key, you will have a behavior like that. Assuming you have a high index at length $7$, then by the nature of the algorithm you will have a high index at $14, 21, 28, \dots$, regardless if that is the correct key or not.

So the best stragety would be, just to start with the lowest value and if it doesn't work out move to the next outlier (which is most likely your first value doubled). Things like calculatin the GCD of all the outliers, etc. is not wrong but unnecessary, if you can just iterate through and have a really high chance of success on your first (or first few) tries.

One more thing: This kind of analysis is only faulty for short texts (with being impossible to break if the keylength is as long as the message, and the key is chosen uniformly random and only used once), and for longer texts the law of large numbers (in particular, see the variance of the central limit theorem ) will cause all the other values to be really, really close to what you would exepct from a uniform distribution over the alphabet.


How can comparision like (>=,==) be done using homomorphic encryption?

You'll have to write the function you are trying to calculate as a polynomial in the two inputs $x$ and $y$. If you are working over the field with $q$ elements as plaintexts, you have to calculate for equality the polynomial $(x-y)^{q-1}$. Greater-than-or-equal (however you define that for finite fields) will be even more complicated.


The session key can be generated with a CSPRNG by Alice. Alice and Bob will already have static key pairs that don't change. Alice and Bob will create ephemeral key pairs, and these are newly generated every session.

Alice then signs her ephemeral public key with her static private key and sends this to Bob - this public key doesnt have to be encrypted in any way as it is a public key. Bob receives this, and verifies the signature using Alice's static public key. Bob goes through the same protocol so Alice can have his ephemeral public key.

Now there are two ways that this can go - a KEX (key exchange) or a KEM (key encapsulation mechanism).

For a KEX, both Alice and Bob combine their own ephemeral private key with the others public key, using DH(E) or ECCDH(E). This leaves them both with the same shared secret, which can be passed through HKDF to create a correctly formatted symmetric key of the desired length.

For a KEM, Alice would create a symmetric key of desired length, sign it with her static private key, and then encrypts it with Bob's ephemeral public key, and sends it to Bob, who can decrypt and verify they key. RSA would have to be used for this.

For a programming languages there's usually a module for pseudorandom numbers (PRNG) and for cryptographically secure pseudorandom number generators (CSPRNG). In Python, the random module is a PRNG, and the secrets module or os.urandom is a CSPRNG. For cryptography, there is a PyCryptodome or cryptography among some others.


Plaintext Size Limit for ECIES with AES-128 CBC mode

You are using CBC mode in ECIES. In the CBC mode the $i$-th ciphertext is calculated as

$$c_i = E_k(m_i \oplus c_{i-1})$$

where the $c_0=IV$

Now, there is a problem with CBC mode that is if the adversary can see that $c_i = c_j$ for some $i,j$ with $i \neq j$ then they can calculate:

$$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$

and by x-oring both sides they can learn

$$m_i \oplus m_j = c_{i-1} \oplus c_{j-1}.$$

This is ciphertext collision and the probability is given by the birthday bound, $\mathcal{O}(\sqrt{2^n})$, where the $n$ is the block size. So it is not advisable to have more than $2^{64}$ blocks. But in practice, you may reduce this into lower sizes to reduce the change of this attack from 50% to your target security level.


How to perform frequency analysis of a substitution cipher using a Base64 alphabet

I'll assume that the plaintext consists entirely of capital ASCII letters as in the example. This implies the high 3 bits of each byte of plaintext are 010.

It is useful to visualize how 3 consecutive bytes of plaintext map to 4 consecutive Base64 characters.

1. Frequency analysis of the last character of 4-char blocks in ciphertext

We see there is a straight mapping from the last of every three characters in the plaintext to the last of every four characters in the Base64 encoding (notice that the characters in Base64 codes the 5 lower bits of the character in the plaintext, on the right of the above picture, which are characteristic of the letter). It follows that we can perform single-letter frequency analysis on the ciphertext restricted to the last character of every block of four characters. If among the characters kept the last one is different from all the others, it likely represents = in Base64; all the other characters kept should be among 26 characters (else the assumption made above is disproved). The mapping, ordered by decreasing expected letter frequency in English plaintext (according to this source) is:

Plaintext          Plaintext          Plaintext          Plaintext
 | Base64           | Base64           | Base64           | Base64
 |  | Frequency     |  | Frequency     |  | Frequency     |  | Frequency
 E  F  0.12702      H  I  0.06094      W  X  0.02360      K  L  0.00772
 T  U  0.09056      R  S  0.05987      F  G  0.02228      J  K  0.00153
 A  B  0.08167      D  E  0.04253      G  H  0.02015      X  Y  0.00150
 O  P  0.07507      L  M  0.04025      Y  Z  0.01974      Q  R  0.00095
 I  J  0.06966      C  D  0.02782      P  Q  0.01929      Z  a  0.00074
 N  O  0.06749      U  V  0.02758      B  C  0.01492
 S  T  0.06327      M  N  0.02406      V  W  0.00978

and with a kilobytes of ciphertext, it is likely that the most frequent character in the fraction of the ciphertext kept corresponds to E in the plaintext, thus F in the Base64.

2. Frequency analysis of the first character of 4-char blocks in ciphertext

There is a function from the first of every three characters in the plaintext to the first of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the first character of every block of four characters. The characters kept should be among 7. Expected frequency is

Plaintext  Base64  Frequency
  DEFG       R      0.21198 = 0.04253 + 0.12702 + 0.02228 + 0.02015
  LMNO       T      0.20687 = 0.04025 + 0.02406 + 0.06749 + 0.07507
  TUVW       V      0.15152 = 0.09056 + 0.02758 + 0.00978 + 0.02360
  PQRS       U      0.14338 = 0.01929 + 0.00095 + 0.05987 + 0.06327
  HIJK       S      0.13985 = 0.06094 + 0.06966 + 0.00153 + 0.00772
   ABC       Q      0.12441 =           0.08167 + 0.01492 + 0.02782
  XYZ        W      0.02198 = 0.00150 + 0.01974 + 0.00074

It happens that the set of Base64 characters in the second method is a subset of the set for the first; this allows cross-checking the guesses.

3. Frequency analysis of the third character of 4-char blocks in ciphertext

There is a function from the second of every three characters in the plaintext to the third of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the third character of every block of four characters. The characters kept should be among 16 (except perhaps the last, which may map to = in the Base64 character set). Expected frequency is

Plaintext                               Plaintext
 | Base64                                | Base64
 |  | Frequency                          |  | Frequency
EU  V  0.15460 = 0.12702 + 0.02758      HX  h  0.06244 = 0.06094 + 0.0015
DT  R  0.13309 = 0.04253 + 0.09056      GW  d  0.04375 = 0.02015 + 0.0236
CS  N  0.09109 = 0.02782 + 0.06327       L  x  0.04025
IY  l  0.08940 = 0.06966 + 0.01974      FV  Z  0.03206 = 0.02228 + 0.00978
AQ  F  0.08262 = 0.08167 + 0.00095       M  1  0.02406
 O  9  0.07507                           P  B  0.01929
BR  J  0.07479 = 0.01492 + 0.05987       K  t  0.00772
 N  5  0.06749                          JZ  p  0.00227 = 0.00153 + 0.00074

Several of the characters in the Base64 character set for this third method also occur in the first two methods; this allows cross-checking the guesses.

Frequency analysis of bigrams

We can also consider bigrams in plaintext occurring in the last character of a block of three, and the first character of the next block; and how they map to bigrams in Base64 occurring in the last character of a block of four, and the character following. We can compute the common bigrams obtained in the ciphertext by keeping (as first character of bigram) the last character of a block of four, and (as other character of bigram) the next character; and compare to common bigrams in English (adding frequencies of up to 4 bigrams as we did in the second method).

This also works for bigrams in plaintext occurring in the last two characters of a block of three, mapping to bigrams in Base64 occurring in the last two characters of a block of four; again well be comparing to the frequencies of common bigrams in English (adding frequencies of up to 2 bigrams as we did in the third method).

Common/guessable trigrams in plaintext to finish the analysis

The above will allows recovering the mapping to ciphertext of no more than 36 out of 65 characters used in Base64. For the others, we should guess some aligned blocks of three characters in the plaintext based on what we already know and common English words, transcode these blocks of three plaintext characters to four Base64 characters, see if there is a contradiction with the established mapping of Base64 to ciphertext, and if not cautiously apply the new guesses.

Automated cryptanalysis

As rightly pointed in that other answer, heuristic algorithms can handle the search automatically. Still, I guess that the first three techniques (which can be adapted to different plaintext alphabets, e.g. with space, lowercase..) will greatly simplify the heuristic.


Is it OK to substitute a PRF for a random oracle?

Yes, when we're instantiating some crypto primitive that says 'insert Random Oracle here', we will in practice insert a PRF.

Now, you ask, why is that even slightly controversal?  Well, there are known constructions that are secure with a Random Oracle, but not secure with any specific PRF, see this paper for an example.  This has been taken by some as proof that the Random Oracle model ought not be trusted at all (as proof within that model need not apply in the real world).

On the other side of the argument, other people have pointed out that these constructions are highly artificial, and that attempts to avoid the Random Oracle model has resulted in worse security at times; see this paper to see this argument spelled out.


Good question and yes, it would appear that data is lost.  And technically, something clearly must disappear as 6 don't go into 4. But consider the overall architecture of DES:

Trace the flow of the left and right halves of an individual block of data.  You'll see that the 2 full 32 bit words flow unimpeded down though the Feistel network. No information is lost there, it's only XORed with, maintaining the width. So 64 bits go into the block, and 64 bits emerge.

You're actually referring to the internals of the DES cipher function which looks like:-

and you can identify the s boxes.  They indeed accept 6 bits and output 4, so something is lost due to the pigeon principle. But look at the expansion box above the s boxes.  Additional bits are created due the permutation, P. So what is lost, never really existed but was created within (and localised to) the cipher function. So similarly for the cipher function, 32 bits go in and 32 bits come out.

The reason this works can be considered by analogy, but don't take it too far.  Consider a single round.  DES's cipher function operates as a small pseudo random number generator keyed off a sub-key (round key) and the other half of the block's 32 bit data.  That is then XORed with the original data to encipher it. The streams then swap and the round functions repeat.  So as a (kind of) pseudo random number generator, the cipher function doesn't have to be invertible.

You could actually re-engineer DES using off the shelf hash functions like MD5 or SHA1 (both truncated to 32 bits) to see that transcoding is still possible. It's a common theme in cryptography to consider hash functions as the basis of ciphers, and some more insight can be found with the questions Construct an encryption algorithm using hash function. (I don't know how to handle the 3 way duplicates.)

Designers of these things tend to reflect the key schedule with the main algorithm. Whirlpool is similarly symmetric. I suspect that this was the only way the designers could think to easily expand a 64 bit key using a similar geometry to the main part, and still XOR with 32 bit half blocks. Hence they invented 48 bit sub keys. There's no specific reason on Earth to have 48 bit round keys. They could have been 32 bits and that would have made asymmetric 6 to 4 bit s boxes unnecessary.


Proving that a function is not invert-able (one way function)

I think you can prove $g$ is not guaranteed to be one-way by the following counter example. First let $S$ be the set of all strings in $\{0,1\}^{2m}$ that starts with $m$ zeroes. Take any OWF $f$ of the type you describe. Consider the function $f'$ that is identical to $f$ except on all inputs $x \in S$ it acts as the identity function. I.e. for all $x \in S$ we have $f'(x) = x$. Now if you use $f'$ to construct $g$ then $g$ will clearly not be one-way (because this means $g$ is just the identity function). So all you need to prove is that $f'$ is still a OWF.

Now I sketch an argument that $f'$ is in fact a OWF. Since $f'$ only changes the output of $f$ on a negligible amount of inputs, the distribution of output of $f'$ and $f$ on a uniformly random input should be statistically indistinguishable. However, if there exists an adversary $A$ that demonstrates that $f'$ is not a OWF, then that adversary would work as a distinguisher between the two output distributions. Thus,  $~f'$ must be a OWF.

I am not sure this is 100% watertight, so you may want to work through the proof yourself :).


Is this pairing scheme for establishing trust between two devices with self-signed TLS certs secure from MITM?

This is fine.  There is one corner case I would note which is that the message from 4 can be replayed in 6.  So the authenticated messages should include an indication of whether they are for step 4 or 6.  As for how short K can be: as long as necessary to get the guarantee you want from HMAC.


The answer to the second part of your question:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

So the number of active Sboxes is at least five.

See the answer to this question
and the following link for more details:


The strength of the scheme cannot be higher than its weakest element. Using OTP can give an impression of unbreakable strength, but actually the whole strength is the same as the strength of the encryption method used to share OTP keystream (AES?). Thus, the usage of OTP in such a scheme gives not more security than using normal encryption.

To your question How to share... ? For instance, you could deliver the OTP keystream to your friend in person, or your friend picks it up in person.


Computational binding implies Perfect hiding?

This is not correct. It could be not binding since you can open a commitment into two options. You can quite easily construct such a scheme artificially. For example, take any perfectly binding scheme $C_b$ and any perfectly hiding scheme $C_h$. Then, commit to a message $m$ by committing to $C_b(m)||C_h(0)$ or by committing to $C_b(\overline{m})||C_h(1)$. Then, when you decommit, if the perfectly hiding part is 0, take the message $m$ in the perfectly binding part. In contrast, if the perfectly hiding part is 1, take the complement of the message in the perfectly binding part.

Clearly, this is a computationally binding scheme only, since an all-powerful committer can break the binding of the perfectly hiding part, and so can recommit to either the message or its complement. In addition, the scheme is clearly only computationally hiding as well.


Can elliptic curve cryptography encrypt with public key and decrypt with private key like RSA?

Yes, there is a elliptic curve based public key encryption
Let $a$ be Alice's private key and $a=aG$ be her public key. Bob, who wants to send an encrypted message to Alice, does the following :

Bob chooses a random number $r$, $1\leq r\leq n-1$ and computes $rG$
Bob then computes $M+r\alpha$. Here the message $M$ (a binary string) has been represented as a point in $\langle G\rangle$
Bob sends the encrypted text pair $\langle rG,M+r\alpha\rangle$ to Alice

On receiving this encrypted text Alice decrypts in the following manner

Alice extracts $rG$ and computes $a\cdot(rG)=r\cdot(aG)=r\alpha$
Alice extracts the second part of the pair $M+r\alpha$ and subtracts out $r\alpha$ to obtain $M+r\alpha-r\alpha=M$

There is a drawback in this as block of plaintext has to be converted to a point before being encrypted, denoted by $M$ above. After the decryption it has to be re-converted to plain text.


Possible to decrypt every fragment of an ecrypted file on its own?

Unless I'm misunderstanding something this should be fairly easy to do.
The scheme of a stream cipher is the following :

                    Key
                     |
                     v
               +------------+
               |            |
     IV -----> |  Chacha20  +-----+
               |            |     |
               +------------+     |
                                  |
                                  v
MESSAGE ------------------------> +------>  CIPHER TEXT

Thus you have :
$$K_{stream} \oplus Message = CipherText$$

If afterward you split your $CipherText$ into blocks of $n$-bits. Then you will notice that the first $n$ bits of the $K_{stream}$ are used to encrypt the first $n$ bits of the $Message$ resulting into the first $n$ bits of the $CipherText$ and so on...

Therefore, in order to decrypt a $block$ on a separated device, you need to know its position into the full $CipherText$ (how many bits are present before), generate the $K_{stream}$ from the $Key$ and $IV$, drop the first $n$ bits of this $K_{stream}$ where $n$ is the position of the $block$ in the full $CipherText$, and then you can start decrypting your $block$.

Remarks:

you don't need to know the length of the full $CipherText$ but only the number $n$ of preceding bits.
you will need this number anyway when you will want to recombine the blocks on a single device.


Contrary to what Stephen says, you absolutely can compute the tag in parallel.

Here's how it works; the tag computation is essentially "assemble the AAD, data, the length field and $Encr(Nonce)$ into a series of values $x_n, x_{n-1}, x_{n-2}, ..., x_0$", and then "compute the polynomial $x_nh^n + x_{n-1}h^{n-1} + x_{n-2}h^{n-2} + ... + x_0h^0$

This computation is evaluated within the field $GF(2^{128})$; since it is a field, all the standard ways of rearranging the polynomial work.

For example, if we wanted to convert this into a three-way parallelism, we could compute $j = h^3$, and then the three polynomials in parallel:

$$tag_2 = j^0x_2 + j^1x_5 + j^2x_8 + ...$$
$$tag_1 = j^0x_1 + j^1x_4 + j^2x_7 + ...$$
$$tag_0 = j^0x_0 + j^1x_3 + j^2x_6 + ...$$

and then combine them for the final result $tag = h^2tag_2 + h^1tag_1 + h^0tag_0$

Obviously, we can tune this to whatever degree of parallelism that suits us, and we haven't changed the tag result in any way.

Stephen also notes that the entire message needs to be scanned to compute the tag; this is trivally true of any method that has a tag that's a complex function of the entire message.


I happened to see some similar question like this. The question mentioned about sending fake signature message. The method is like this:

Find some random string R.
Use the public key to encrypt the random string R, let the result be X.

(R,X) is your signature pair.(Think backwards)
When someone verifies the signature, he'll compare {R} with X which are equal.


How terribly flawed is this design for key storage?

To begin with, I see four potential problems with your key file.

The work factor (8) is probably too low. If we presume you pick your pass phrase by selecting $c$ words at random from a list of $2^{13}$ distinct words (e.g. correct horse battery staple) you get a pass phrase with $13c$ bits of entropy. (AFAIK the dictionary used by Diceware only barely contains $2^{13}$ words, but I presume it might be extended.) With a work factor $f$ you get an equivalent security strength $s = 13c+f$. A work factor $f=8$ is an odd choice, since it barely saves you of a single word in your pass phrase, to get an equivalent security strength that is greater or equal to your desired minimum security strength.
Presuming your $MAGIC$ parameter is a constant that is hard coded in your public source code, including the $magic$ tag is not consistent with your claim that the key file has no visible signal/structure. SHA-1 is fast enough, to make automatically searching for data that fits your format relatively easy.
There is at least one problem with your output lengths. The output length of SHA1 is only 20 bytes, but your pseudo code seems to pull 24 bytes from it. Also, if the bcrypt implementation you use conforms to the original paper (you seem to indicate otherwise), the maximum output length is limited to 192 bits or 24 bytes and not 32 bytes. Also, even if you use some form of PBKFD2 with bcrypt as PRF, the input length of bcrypt is limited to 56 bytes. A Diceware pass phrase with a minimum of $256-8$ bits of entropy is most likely to be longer than that.
According to the NaCl documentation, SecretBox performs authenticated encryption. This also adds structure to your key file, in the sense that an attacker will only need the key file, not both the key file and the encrypted database, in order to attack your pass phrase. While you don't specify exactly why you intend to put the encrypted key data in a separate file rather than a header of the encrypted database, or what you mean by "plausible deniability", this doesn't seem like a feature that is consistent with your general design.

The purpose of using bcrypt and other slow PBKDFs, is to to slow down attacks on the password, if the attacker should get hold of the cipher text, just enough to give all users an opportunity to change their passwords.

However, from your question it seems as if you intend to store the cipher text on an untrusted server. This means that it is not really a question of if the attacker will get hold of the cipher text. You must assume it has already happened, and that it is only a matter of time before the attacker manages to crack your password.

Presuming you use this scheme, what would be an appropriate usage policy?

Firstly, you have to change the password you use for encrypting the key file, with an interval that equals the time you expect it would take an attacker to crack your password, should the attacker have managed to get access to your files yesterday.
Secondly, as if that is not enough, you also have to change both the database encryption key and all passwords that are stored in the database, with the same frequency you change the password you use for the key file. Reason? Because the attacker only needs one generation of the key file and database pair, to be able to get to the contents of the database in that generation.

Consequently, in order to get this to fly, you really need a passphrase for the key file that contains enough entropy, to cause the password replacement interval to be 10 years or more. This means well above 80 bits of entropy in the pass phrase. Arguably, if you got a pass phrase that is that good, the bcrypt component is probably redundant. The extra bits of security strength you get by using bcrypt, are probably less than the confidence interval for your passphrase strength estimation. IOW, using bcrypt probably doesn't hurt, but you will have a hard time proving that it is necessary to get the desired security strength.


Expected Linear Complexity of a sequence

It means (usually) averaged over all sequences of a given length. Rueppel computes this in his book.

It's for an i.i.d. uniform sequence, Proposition 4.6. As $n$ goes to infinity by the law of large numbers this sample mean approaches the actual mean.

This was rigorously proved by Meidl and Niederreiter much later. Behind a paywall but you can see the abstract below:

https://ieeexplore.ieee.org/abstract/document/1042274/

The answer is nearly $n$ for $n$-periodic sequences.


RSA: How to compute plaintexts knowing ciphertexts, public key and relation between plaintexts

Since this is an exercise, I'll provide the links of the articles as a hint;

The linearity of the messages  is first studied when $e=3$

Low-Exponent RSA with Related Messages by Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reitert, EUROCRYPT 1996: Advances in Cryptology — EUROCRYPT ’96 pp 1-9

A more general case, where $e$ is not limited to 3 and the relation is linear is studied in

A New Related Message Attack on RSA Oded Yacobi and Yacov Yacobi, PKC 2005: Public Key Cryptography - PKC 2005 pp 1-8.

It is quite clear that these attacks are related to textbook RSA and it must not be used in practice.

For encryption, RSA has used either PKCS#1.5 padding or OAEP. Actually, we don't use RSA for encryption. We prefer it in digital signatures and that requires PSS padding or for Key Encapsulation, RSA-KEM.


Kerckhoffs’ principles – Why should I make my cipher public?

Actually, that wikipedia article you mention in your question already answers your question:

  It is moderately common for companies and sometimes even standards bodies as in the case of the CSS encryption on DVDs – to keep the inner workings of a system secret. Some argue this "security by obscurity" makes the product safer and less vulnerable to attack. A counter argument is that keeping the innards secret may improve security in the short term, but in the long run only systems that have been published and analyzed should be trusted.

But let's dive in deeper anyway...

Kerckhoffs’ principles

For reference purposes, here is Kerckhoffs' original text (from Auguste Kerckhoffs, "La cryptographie militaire", Journal des sciences militaires, vol. IX, pp. 5–38 "II. DESIDERATA DE LA CRYPTOGRAPHIE MILITAIRE.", Jan. 1883):

In plain text, this reads:

  1° Le système doit être matériellement, sinon mathématiquement, indéchiffrable ;
  2° Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi ;
  3° La clef doit pouvoir en être communiquée et retenue sans le secours de notes écrites, et être changée ou modifiée au gré des correspondants ;
  4° Il faut qu’il soit applicable à la correspondance télégraphique ;
  5° Il faut qu’il soit portatif, et que son maniement ou son fonctionnement n’exige pas le concours de plusieurs personnes ;
  6° Enfin, il est nécessaire, vu les circonstances qui en commandent l’application, que le système soit d’un usage facile, ne demandant ni tension d’esprit, ni la connaissance d’une longue série de règles à observer.

And here is my English translation for your convenience:

  The system must be physically, if not mathematically, indecipherable;
  It must not require secrecy, and may not cause inconveniences when it falls into the hands of the enemy;
  The key must be communicated and retained without the aid of written notes, and be changed or modified at the discretion of correspondents;
  It must be applicable to telegraphic correspondence;
  It must be portable, and its usage and its operation does not require the assistance of several people;
  Finally, it is necessary, given the circumstances that control the application, that the system is easy to use, requiring no mental strain, or the knowledge of a long series of rules to be observed.

The enemy knows the system

Kerckhoffs' surviving principle nr. 2 (of initially six design principles for military ciphers) says nothing else than that you have to look at the security of your crypto under the aspects of "the enemy knows the algorithm" and maybe even "the enemy carries the message". The well-known Claude Shannon once simplified Kerckhoffs' principle as: "the enemy knows the system".

The "advantage to the attacker" one might be thinking about when deciding to keep an algo secret, would practically be "just a matter of time for the attacker to find out" since keeping the algorithm secret would be relying on "security through obscurity", which we all know to be a bad idea.

The idea of Kerckhoffs' principle is that if any part of a cryptosystem (except the individual secret key) has to be kept secret then the cryptosystem is not secure. That's because, if the simple act of disclosing some detail of the system were to make it suddenly insecure, then you've got a problem on your hands. The gold standard for any secret keeping system is that all its details should be able to be made public without compromising the security of the system. The security relies on the system itself, not the secrecy of the system.

A good example of why Kerckhoffs' principle makes sense would be the German Enigma machine used in WWII. By stealing machines, the Allies knew everything there was to know about how the Enigma machine worked; they only had to read the manuals, use the code-books and look at the way the machine was constructed and worked. After all, they had a working example in their hands. Throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through espionage, betrayal and reverse engineering. And on occasion, ciphers have been reconstructed through pure deduction. For example, the German Lorenz cipher and the Japanese Purple code, and a variety of classical schemes.

Therefore, the core idea of Kerckhoffs' 2nd principle is still applied today. The security of HTTPS, SSL and ciphers like AES or RSA rely on the strength of the algorithm, not on keeping them secret. The algorithms are all published and detailed standards have been created which everyone can take a look at. The only "secret" is the key that's chosen when you connect to a secure web site (that's done automatically and randomly by your browser and the server) or when you encrypt a document using a program like GPG.

To recap: why publish the cryptographic algorithm?

Not publishing a cryptographic algorithm doesn’t make much sense as it's just a matter of time for the attacker to find out how your crypto works. Security gain can therefore only be of temporary nature.

On the other hand, publishing of a cryptographic algorithm tends to build trust because the publication of its internals allows the verification of related security claims.

In fact, you can even transport the answer to “why publish the cryptographic algorithm” down to a much simpler level: the security of the lock of your home's door does not depend on keeping the lock hidden and its mechanisms secret. Its security comes from you keeping the key safe. That is one of the most simple examples of Kerckhoffs' 2nd principle in action.

One of many examples

To provide an example, let me point you to — what I would call — an "über-publication": "The Design of Rijndael: AES - The Advanced Encryption Standard" by Joan Daemen and Vincent Rijmen.

This book, written by the designers of the block cipher, presents Rijndael (more commonly known as AES) from scratch. The underlying mathematics and the wide trail strategy as the basic design idea are explained in detail and the basics of differential and linear cryptanalysis are reworked. Subsequent chapters review all known attacks against the Rijndael structure and deal with implementation and optimization issues. Finally, other ciphers related to Rijndael are presented.

As you might have noticed: it didn't hurt the security of Rijndael/AES in any way that all its internals were published. Quite the contrary – related publications only resulted in more confidence in the cipher.


Multiple Hash Functions that work in either nesting

[Take 4.2, back to requiring only the PRP to be secret]

Improving on the line of thought in that other answer, we will craft two efficiently computable functions $H_1$ and $H_2$ each accepting two arbitrary strings as input, with output a fixed-size string, say 512 bit; and (I conjecture) indistinguishable from a random function (under the assumption that some parameters are secret) except for this superset of the desired property:
$$\forall(i,j)\in\{1,2\}^2,\forall(s_1,s_2,x), H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$$

We'll use as building blocks three 512-bit PRFs $P_0()$, $P_1()$ and $P_2()$ accepting an arbitrary bit string as input, and one 512-bit PRP $E()$ with $D()$ its reverse function, such that $D(E(a))=a$.We can build the PRFs as $P(m)=\mathtt{HMAC}_\mathtt{SHA512}(k,m)$ and three arbitrary distinct $k$. And by this famous result we can build the PRP as the four-rounds Feistel cipher with round functions $\mathtt{HMAC}_\mathtt{SHA256}(k,m)$ and four arbitrary distinct $k$.

For $i\in\{1,2\}$, define $H_i(s,x)$ as
$$H_i(s,x)=E\big(\text{ }D(P_i(s))+D(x)\bmod{2^{512}}\text{ }\big)\text{ when }x\text{ is a 512-bit string,}$$
$$H_i(s,x)=E\big(\text{ }D(P_i(s))+P_0(x)\bmod{2^{512}}\text{ }\big)\text{ otherwise.}$$Notice that in the above, $P_0(x)$ is now added without going through $D$; this avoid that knowledge of $P_0$ would allows creating collisions of the form $H_i(s,P_0(x))=H_i(s,x)$

The desired property $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ follows from commutativity and associativity of addition in $\mathbb Z_{2^{512}}$, and the $H_i$ functions appears much like random oracles, except for consequences of that property, to an adversary ignoring the PRP (but possibly knowing the PRFs).

By querying the functions/oracles $H_i$, it seems impossible to internally add 0, or otherwise create collisions, other than by chance. Computing $H_1(s,H_1(s,\cdots H_1(s,H_1(s,x))\cdots))$, where $x$ is a 512-bit string and there are $2^n$ iterations, has odds only $2^{n-511-k}$ to return to $x$; if we had used XOR instead of modular addition, we'd have $H_1(s,H_1(s,x))=x$.

Note: to an adversary knowing the PRP and PRF, the problem of finding collisions on $H_1$ unrelated to the property is tractable: it is a knapsack problem in $\mathbb Z_{2^{512}}$ with unlimited supply of random values to choose from.

Open problems:

Can this be proven secure (e.g. collision-resistant except per application of the required property); or broken?
Can we make a scheme secure yet fully public?
We do not need a full group operation (on the contrary, the neutral element and existence of an opposite are a risk), any commutative semi-group will do; is something more suitable than $\mathbb Z_{2^{512}}$?
Is $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ a consequence of $H_1(s_1,H_2(s_2,x)) = H_2(s_2,H_1(s_1,x))$?
If not, can we make a construction with only the originally asked property?


What schemes support signature aggregation?

I will have to read up on BLS, however, if I understand correctly by implementing the aggregation of $n$-messages, only the signature is aggregated - not the identities, so for an n-of-n multisig use-case it'll require knowing all public keys. I suspect you could make this tradeoff in both systems, but I will not spend the time to verify this conjecture.

The only other signature scheme that I know that supports aggregated signatures is Schnorr using Bellare and Neven. This supports n-of-n aggregated signatures and aggregated identities over a common message.


Why does "gpg --export-secret-keys" ask for a password?

man gpg...

  GnuPG  may ask you to enter the passphrase for the key.  This is required because the internal protection method of the secret key is different from the one specified by the OpenPGP protocol.

I guess that answers it.  Though if anybody knows more, feel free to share.


Is it secure to derive an AES key from a MAC?

It looks like, given your adversary model, things should be secure. HMAC as a randomness extractor has been shown to be good, especially when we can assume the hash function is collision resistant. That paper also has some results which tell how you could guard against the collision resistance being broken (basically use a hash function with larger output size). If SHA-256 is broken any time soon, however, we are all in a lot of trouble, so I wouldn't be too worried about that attack.


Why are NaCl secret keys 64 bytes for signing, but 32 bytes for box?

Opening and sealing a box involves your private scalar and the other party's public key. So the private key is simply the private scalar.

Signing with Ed25519 involves your private scalar and your public key (to strictly bind the signature to that key). Since computing the public key from the private scalar is expensive, NaCl chooses to store it as part of the private key.

An Ed25519 private key consists of a 32 byte seed (from which you can cheaply derive the 32 byte private scalar and the 32 byte hash prefix) and the 32 byte public key.

Different Ed25519 implementations chose different private key formats, Brian Warner's blog has the details.


S-AES RC[i] Generation. Can someone explain how to generate the RC[i]s for these two problems I have?

Your question missing some information about the source, however, one can give an answer based on S-AES i.e. Simplified AES.

There is a nice definition of S-AES here.

The Round Constant (RC) or the other name R-con has 10 values for AES and utilized for the key schedule to eliminate the symmetry by making each step of the key schedule slightly different.

i      1   2   3   4   5   6   7   8   9  10
RC[i] 01  02  04  08  10  20  40  80  1B  36

S-AES has defined only 2-rounds, thus the designers of S-AES have to choose only; two RC values. This is just a selection issue, not a generation as in AES-key schedule.

RCon[1] = 80
RCon[2] = 30

Note: S-AES is only an oversimplified AES for educational use.


What's wrong with my security model - or how can it be attacked?

Usernames

A hashed username is fine; a nice idea for the security paranoid actually. If all username records use the same salt, then a rainbow attack is theoretically possible - as is knowing that a user has X pieces of secured information (plus timestamps etc). But you need a single salt per table if the username is the tuple selection mechanism.

Secret Snippet (Title/Info/Visible Timestamps)

Depending on other features this service is providing, the password needn't be stored server-side to secure the secret snippets; thus avoiding the time cost of bcrypt. If user enters the wrong password your service can happily decrypt and return semantic garbage. If the user enters an unmatched username the server can happily invent a random editable list of random data; breaking any clue about viable usernames. Context-specific flags or checksum verification could be used by the client agent to discard deciphered garbage.

Storing a password on a server is usually used for authentication instead of  confidentiality. Whether a computer should do something for someone - instead whether the data returned is fit-for-purpose. The users can simply be told to pick an unguessable username if they don't want their data erased or modified; in a manner similar to disposable email inboxes. If the username is guessed, the content is still unintelligable.

Session Key

Seems legit. If session doesn't include the decryption password or aggregate AES key and user wants to see the plaintext content, the user's client-side will need to cache the password or plaintext; or the persistent session will still bug the user for a password on each page refresh.

Other Thoughts

Alternately, if the service simply stores secure information; then an ad-hoc public key approach can be used with decryption occurring on the client-side. And yes, to those naysayers, you can have unverified use of public keys; if a service is indifferent to whether the human using the username has changed or simply their password. A SSL framework provides the protection against man-in-middle attacks. If it doesn't - you have to reinvent a much larger wheel.


AES GCM mode and the message is the same as the password

From Wikipedia Key Derivation Function (KDF):

  In cryptography, a key derivation function (KDF) derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function

You have a password $p$, and you are using a KDF $k=KDF(p)$ to derive the key $k$ and then you encrypt the $p$ as $c=E_k(p)$, where $E$ is AES.

There is a problem here. How are you going to remember the $k$, if you keep the $p$, then what is the aim of encrypting it?

If you look at password manager you will see that;

  Password managers typically require a user to generate and remember one "master" password to unlock and access any information stored in their databases.

One of the benefits of KDF is we input to KDF a human rememberable password to generate cryptographic keys.

You have to use some way to store the $k$ if you delete/forget $p$ and input whenever necessary. Also, $k$ is generated what is the aim of encrypting the $p$? Just delete it?

and remember AES-GCM is authenticated encryption mode.


variant of Diffie–Hellman key exchange protocol

To show that the protocol is secure under DDH, we need a reduction $R$  that takes a triple as input and outputs a transcript and key such that

if the triple is a DDH triple, then the transcript and key are distributed identically to a real execution of the protocol
if the triple is random, then the transcript and key are distributed as if you ran a real protocol execution to get the transcript, but the key is random (and independent of the transcript)

The reduction $R$ takes a triple $(A,B,C)$ and sets Transcript=$(A,C)$ and Key=$B$.

If the triple is a DDH triple then there are values $x,y$ such that $(A,B,C)=(g^x,g^y,g^{xy})$. So $(A,C)$ is distributed uniformly in $G \times G$, which is exactly how a transcript of a protocol execution is distributed too. The key in a real execution is the unique value $k$ satisfying $k \otimes \alpha = \beta$ where $\alpha$ is Alice's message, $\beta$ is Bob's and $g^x \otimes g^y := g^{xy}$ (this is well-defined if you think about it). The reduction's key satisfies this property too since $C = A \otimes B$ is the definition of a DDH triple. So the reduction's transcript and key are identically distributed to real ones in this case.

If the triple is a random triple, then $(A, B, C)$ is uniform in $G^3$, i.e. each element is uniform in $G$ and independent of the other two. If you create a transcript together with a random key, then the transcript and key are distributed uniformly in $G^3$ too, so the reduction produces the correct distribution in this case too. Q.E.D.

Informally, think of the proof as follows: a DDH triple has two degrees of freedom, a random tuple has 3. A real transcript/key also has 2 degrees, a fake one 3. In both cases, the restriction that loses the third degree is that one element is a DH product $(\otimes)$ of the other two. So all your reduction has to do is match things up.

EDIT: General case

A transcript of a protocol looks like this (order may vary):

A1 to B: g^{a_1}
...
An to B: g^{a_n}
B to A1: g^{a_1.b}
...
B to An: g^{a_n.b}
shared key: g^b

A fake transcript (that is indistinguishable from a real one if it's secure) is the same except that the key at the end is $g^r$ for independent $r$. Note that even in a fake transcript, the same exponent $b$ is used for all messages from $B$.

Reduction $R$ takes a tuple $(A, B, C)$ and makes $n$ tuples by picking $u_i$ for $i$ from 1 to $n$ and sets $(A_i, B_i, C_i) = (A^{u_i}, B, C^{u_i})$.
It then outputs the transcript $A_1, \ldots, A_n, C_1, \ldots, C_n, B$.
If the orignal tuple was DDH, so are all these ones - so it is identical to a real transcript (in the real transcript, each $a_i$ introduces a degree of freedom; in the reduction, the $u_i$ do). And $B$ matches up too.

If the original tuple was random, $B$ is independent of everything else but the $A_i/C_i$ relations still hold so it's all distributed correctly.


Is it possible to use structures other than finite fields?

One does not always use finite fields in cryptography. RSA for instance is based on
residue class rings, discrete logartihm based cryptosystems work on suitable
additive/multiplicative groups but these are also finite rings/groups.

Why one uses finite algebraic structures and not the field of the
reals?

Elements of the field of the reals do not necessarily have a
finite representation and thus cannot be represented on computers
precisely (only approximations as floating point numbers of a certain precision). Consequently, field operations may only yield approximations of the resulting element. Working with such fields would introduce errors in the arithmetic operations, which we do not want in cryptography. Using finite fields allow to represent all elements precisely and also the output of any arithmetic operation in the field.
Furthermore, finite structures used in
cryptography provide us with hard problems useful for constructing cryptographic protocols, such
as the hardness of the discrete logarithm problem over suitable finite fields. Logarithms over the reals in contrast are easy to compute.


Are digital signatures using preprocessed paper pads possible?

The best answer I can come up with is using some sort of Geometric cryptography. It is based on the difficulty of trisecting an angle using a ruler and compass. So you could hand over people a triplet of some secret angle.


Is using quantum computing to break passwords non-sense?

Well, the best answer I can think of is by referring you to Scott Aaronson's wonderful blog.

Quoting the very header of the blog:

  If you take just one piece of information from this blog:
  Quantum computers would not solve hard search problems
  instantaneously by simply trying all the possible solutions at once.

So no, a quantum computer would not try to input all passwords simultaneously to the password checker: as you correctly guessed, this would be nonsense. But a quantum computer can still use the intriguing properties of quantum mechanics to perform some computations which we have no idea how to do using a classical computer, such as using Shor's algorithm to factor a big number in polynomial time, which allows for example to break the RSA cryptosystem. So, if you are on a conventional computer system, you encrypt your password (or any other sensitive data) with RSA, and send it over the network, then you should be afraid if there are (scalable, etc) quantum computers available - for anyone with such a computer will just break the ciphertext in a short amount of time, recovering the sensitive information you had hidden inside. If the password is kept locally and an adversary tries to guess it to log to some service, then a quantum computer will not help him.


Digital signatures with one-way function, can messages be longer than the signature?

Yes.

Signature length is generally unrelated to the length of the message and the length of the key.  Some signature schemes have very short signatures and long public keys, like CFS; some have short keys and very long signatures, like SPHINCS; some are more balanced in size, like Ed25519 or RSA-2048-FDH.  Only exotic signature schemes for very special purposes are limited to short messages—the vast majority are designed to handle messages of arbitrary length.

Pretty much every signature scheme is designed with a random function from messages to elements of some mathematical structure for the public-key cryptosystem.  This serves to destroy any relations in structured messages.  If we didn't do that, e.g. if we used RSA with the stupid verification equation $s^3 \equiv m \pmod n$ for a signature $s$ on a message $m$ under public key $n$, then you could trivially forge the signature $s = 1$ on the message $m = 1$ under any modulus $n$ because $1^3 \equiv 1 \pmod n$.  Instead, serious practitioners use a sensible verification equation like $s^3 \equiv H(m) \pmod n$ where $H$ is a random function from messages to $\mathbb Z/n\mathbb Z$ so you have no hope of finding an $m$ such that $H(m) = 1$.

Practical signature schemes are usually instantiated with a fixed hash function $H$ accepting arbitrary bit strings as inputs, like SHAKE256.  This is not simply ‘hashing a message, and then signing a hash’—the hash is an integral part of the signature scheme itself, not something you do in addition to signing; the security of the signature scheme relies critically on the hash.

In the signature scheme that Bitcoin uses with the OP_CHECKSIG operation, the message, a transaction, is an arbitrary bit string, mapped with SHA-256d (that is, two iterations of SHA-256, $m \mapsto \operatorname{SHA-256}(\operatorname{SHA-256}(m))$) into a scalar modulo the order of the curve secp256k1.


What is the exact meaning of the public key cryptosystem properties in New Directions In Cryptography by Diffie and Hellman

Well, it's good that you're trying to learn.  However, learning from the original seminal papers does have some issues that you need to be aware of.
For one, sometimes the original authors did not anticipate some issues that later contributions found (and for which common practice adjusted for).
For example, it is now recognized that public key encryption needs to be randomized; that is, it isn't in general secure to have a deterministic function $\text{Encrypt}(E_k, M)$.  After all, if an adversary obtains $\text{Encrypt}(E_k, M)$ and has a guess of the message $M'$, he can determine whether $M = M'$ by computing $\text{Encrypt}(E_k, M')$ (and seeing if that matches the ciphertext he has seen).  Because of this, we always use a randomized encryption function $\text{Encrypt}(E_k, M, r)$ (where $r$ is a random input), with the property that $\text{Decrypt}(D_k, \text{Encrypt}(E_k, M, r)) = M$, for (almost) all $M, r$ (the "almost" is there because we've found some methods that do have a small probability of decryption failure).
The other thing that feels like it needs to be called out (even though it has little to do with your actual question) is signatures - Diffie and Hellman mention signatures in the context of trap door one way functions.  It turns that that we have a variety of public key signature methods which are not based on trap door one way functions.
BTW: I'm not criticizing either Diffie or Hellman for not anticipating all possible issues - their work was truly groundbreaking.  However, quite a lot of thought has been put into extending this work; it is not surprising that some people found things that were originally missed.
That being said, here are answers to your questions:

What is the K? From what I understand, the K is like p and q in RSA? Because we choose prime numbers p and q first, and then we choose a public key e and derive a corresponding private key d from e using (p-1)(q-1) with the euclidean algorithm.

Well, no.  For any public key cryptosystem, there is a randomized process which generates the public key and the private key.  This randomized process can be modeled as being based on some 'seed' or 'random coin flips' (more modern terminology is, in fact, 'random coins').  The value K is this seed.
Diffie and Hellman reference this process when they write:
     In practice, the cryptoequipment must contain a true random number generator
     (e.g., a noisy diode) for generating K, together with an algorithm for generating
     the EK ~- n, pair from its outputs.

Later works have the cryptosystems specifically call out this algorithm as the 'key generation' (Gen) algorithm as one of the algorithms that define the cryptosystem, and assume that the true random number generator output is something generated outside the cryptosystem as an explicit input to the Gen algorithm.
For RSA, what we typically do is take this seed K, and use it to select the random primes p and q (and possibly e; the details depend on the exact algorithm used). The p and q values are really part of the private key and not the original seed.

Why is that in property 3, for 'almost' every K, it is computationally infeasible to derive DK from EK? What is the exact meaning of for 'almost' every K? There could be an exception where it is feasible to derive DK from EK?

Well, one issue that cannot be avoided is if the attacker took a guess to the original seed value K', and then fed that into the key generation process (which is public).  If his guess is correct, then that'd generate the exact same public key value $E_k$, and so he'd know his guess was correct (and he'd also get the private key value $D_k$, allowing him to decrypt.  This cannot be avoided, and so they need to put in this cavaet about this unavoidable attack (and possibly similar ones as well).  Actually, for most public key cryptosystems (no exception comes immediately to mind), there are better attacks than just guessing K; however that attack is still present.