The fundamental difference between RSA-groups and prime order groups is that in RSA groups the multiplicative order of the group is unknown (without knowledge of the factorization). This allows much easier constructions for unforgeable signatures (although hashing and padding are required to ensure existential unforgeability).

With knowledge of the group order, a forger has more possibilities to calculate "useful" group elements. This results in the DSA formulas (and the related ElGamals signatures) to be more complex.

Let's have a look at what these formulas actually calculate, and for simplification I'll leave out all the modulo operations (they are applied in the correct way). The goal is to get expressions which only depend on the hash $H$, the signing key $x$, and the (random) blinding value $k$.

The signature is:
$$r=g^k$$
$$s=k^{-1}(H+xr) = k^{-1}(H+xg^k)$$

Let's look at the verification algorithm backwards:
$$v=g^{u_1}y^{u_2} = g^{Hs^{-1}}g^{x \cdot r s^{-1}}$$
$$=g^{s^{-1} (H+xr)}$$

Here is the interresting part: A valid signature will solve like this:
$$= g^{(k^{-1}(H+xg^k))^{-1} (H+xg^k)}= g^k = r$$

For a forger, this is differently: He can choose $r$ and $s$ arbitrarily, but he does not know $x$ but only $y=g^x$. To forge a valid signature, it has to fulfill this equation:
$$g^{s^{-1}H}y^{s^{-1}r} = r$$
However, we can not solve this equation without calculating some discrete logarithms.


Is there a partially homomorphic quantum secure public key cryptosystem with IND-CCA1 security?

Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations.

I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.


Is it safe to send a hashed password over HTTPS or what is the most secure method of authentication?

The most common way for web sites is to send the password itself to the server, which then uses a "password hashing function" (NOT a cryptographic hash) like Argon2id or bcrypt to create a digest (containing some settings, a unique per account salt, and the hash of the password), and then compares the digest to the value stored on the server for that user.
It's possible to do this twice: you can use a password hashing function on the client, then send the digest to the server, and then use another password hashing function on the full digest. This can be done with different settings for the work factor on the client and the server to reduce the workload the server needs to compute. The server should use a second salt, still unique per account. The big disadvantages of this are that most clients won't have code for a password hashing function, he per-account storage overhead is higher (need to store an extra digest, so probably about 64 bytes more per user), and the login process needs to send the client the work factor settings and one salt.
For some applications it's possible to have clients generate an asymmetric key pair, send the server the public portion, and then authenticate by signing a challenge the server sends. EG the server could send a 32-byte random value to the client, the client could sign it, and if the signature is valid for the stored public key the server grants access. SSH does this. Ed25519 SSH keys are small, and there's lots of support for SSH's format. The disadvantage is that users need to keep these keys stored, losing their private key means losing access, and leaking their private key allows attackers access (just like a password). If viable this is the most secure option.
There are also saPAKEs, like OPAQUE good article here, which don't require sending the server a copy of the password (or a hash of the password), but they're not standardized yet. I'd avoid these for now, but keep an eye out for them to become standardized. And do read that article, it describes common password use cases more thoroughly than I did here.


How slow is the hash used for Mac FileVault encryption?

Modern FileVault is a relatively slow hash. hashcat supports attacking FileVault 2 hashes as mode 16700.

As an example of real-world attack capability, if a seven-character password were truly randomly generated, then it would take a little more than seven years to fully exhaust on a rig with six reasonably fast GPUs:

$ hashcat -a 3 -m 16700 -w 4 filevault.hash ?a?a?a?a?a?a?a
hashcat (v5.1.0-1685-gf946e321) starting...

CUDA API (CUDA 10.1)
====================
* Device #1: GeForce GTX 1080, 7006/8119 MB, 20MCU
* Device #2: GeForce GTX 1080, 7027/8119 MB, 20MCU
* Device #3: GeForce GTX 1080, 7037/8119 MB, 20MCU
* Device #4: GeForce GTX 1080, 7027/8119 MB, 20MCU
* Device #5: GeForce GTX 1080, 7037/8119 MB, 20MCU
* Device #6: GeForce GTX 1080, 7027/8119 MB, 20MCU

[...]

Session..........: hashcat
Status...........: Quit
Hash.Name........: FileVault 2
Hash.Target......: $fvde$1$16$84286044060108438487434858307513$20000$f...704191
Time.Started.....: Wed Mar  4 20:23:59 2020 (11 secs)
Time.Estimated...: Tue May 12 22:42:02 2026 (6 years, 69 days)
Guess.Mask.......: ?a?a?a?a?a?a?a [7]
Guess.Queue......: 1/1 (100.00%)
Speed.#1.........:    59646 H/s (273.90ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#2.........:    59243 H/s (275.66ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#3.........:    59351 H/s (275.32ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#4.........:    59343 H/s (275.15ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#5.........:    60227 H/s (271.48ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#6.........:    59819 H/s (273.29ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#*.........:   357.6 kH/s
Recovered........: 0/1 (0.00%) Digests
Progress.........: 3932160/69833729609375 (0.00%)
Rejected.........: 0/3932160 (0.00%)
Restore.Point....: 0/735091890625 (0.00%)
Restore.Sub.#1...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#2...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#3...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#4...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#5...: Salt:0 Amplifier:2-3 Iteration:1024-2048
Restore.Sub.#6...: Salt:0 Amplifier:2-3 Iteration:1024-2048
Candidates.#1....: 1arieri -> 1p8xana
Candidates.#2....: 1(ZDERI -> 1uxMONA
Candidates.#3....: 1w9zana -> 1YiQUS1
Candidates.#4....: 1TdWERI -> 1#UDERI
Candidates.#5....: 1r0qwon -> 1kF~~~1
Candidates.#6....: 1O_ !!! -> 1@[1199
Hardware.Mon.#1..: Temp: 44c Fan: 80% Util:  0% Core:1784MHz Mem:4513MHz Bus:8
Hardware.Mon.#2..: Temp: 36c Fan: 81% Util: 19% Core:1759MHz Mem:4513MHz Bus:4
Hardware.Mon.#3..: Temp: 47c Fan: 80% Util: 42% Core:1860MHz Mem:4513MHz Bus:16
Hardware.Mon.#4..: Temp: 45c Fan: 80% Util: 33% Core:1759MHz Mem:4513MHz Bus:4
Hardware.Mon.#5..: Temp: 37c Fan: 80% Util: 52% Core:1898MHz Mem:4513MHz Bus:1
Hardware.Mon.#6..: Temp: 43c Fan: 80% Util:100% Core:1784MHz Mem:4513MHz Bus:1

Started: Wed Mar  4 20:23:47 2020
Stopped: Wed Mar  4 20:24:12 2020


The OP has provided the answer in a comment.

"In the second paper(V.Velichkov et al., The Additive Differential Probability of ARX), the table 2's order is not same as the original order.

For example, $S[i] =0$ when $(s_1[i],s_2[i],s_3[i])=(0,0,-1)$. So, there exists a difference.


Are short ElGamal keysizes acceptable (1024-bit or lower) in cases where security is only necessary in a short timeframe

This got me wondering in general if key sizes are flexible depending on "how long the encryption needs to last" - are there any guidelines here? Any pitfalls I'm not considering?

Yes, you can down-scale the bit-length, e.g. to 1536-bit and it will still likely stay somewhat secure. But do note that for discrete-logarithm over finite fields based cryptosystems there's a steep cutoff in security. Once the parameters are so small that you can break the scheme, e.g. within a week or longer on your hardware, you get "precomputed" data that allows to find any discrete logarithm of interest in a matter of seconds / minutes.

This observation was widely made first with LogJam.


Collusion resistant computing of same function by two servers

It sounds like what you really want is a Proof of Replication, where you can have multiple servers prove that they each have their own copy of a file.

The servers must each prove that they've been hosting their own redundant copy of file the whole time, and that they haven't just downloaded it just-in-time in order to create the proof. If you upload a file to a cloud service that claims they'll host N redundant copies of the file, they can use proofs of replication in order to confirm that they are in fact keeping N copies and not just one.

Protocol Labs (developer of IPFS and Filecoin) has developed a strategy for proofs of replication. Page 8 of the Filecoin Primer has a short description and diagram overviewing the strategy, and their Proof of Replication paper is more in-depth.

The basic idea is that each server is given a unique "sealed" replica of the data. The data may be easily recoverable from the sealed version. Creating (or recreating) the sealed version takes a predictable amount of time and may be done by anyone. The verifier can issue a challenge to a server that can only be answered by using that server's uniquely-sealed version of the data, and the verifier expects the server to answer within a timeout period that's shorter than the amount of time it would take for the server to download the data from another server and recreate the seal.


AES-GCM -- what is ICV and what happens if I don't use it

ICV is the integrity check value (beware that it may also mean Initial Chaining Value). You cannot do without for GCM mode.

I'm not sure what you mean with: "If integrity is not verified, my packet will be dropped anyway". GCM uses an authentication tag which provides cryptographic integrity. Unless you have another way of adding cryptographic integrity then you cannot just skip verifying the tag.

If you do have another authentication tag, say HMAC over the ciphertext, then you don't need GCM. You could use AES-CTR mode instead. Except for some changes during initialization AES-CTR mode is used within GCM to provide confidentiality.

Beware that GCM and CTR modes do directly leak the plaintext size and possiblty timing information. That's something to solve - or not - at protocol level.


How to extract MAC and AES keys using x9.63 based kdf

For that standard, it is covered in Section 5.1.3:

  Use the key derivation function KDF established during the setup procedure to generate keying data K of length enckeylen + mackeylen
  octets from Z and [SharedInfo1 ]. If the key derivation function
  outputs “invalid”, output “invalid” and stop.
  Parse the leftmost enckeylen octets of K as an encryption key EK and the rightmost mackeylen octets of K as a MAC key MK. If symmetric
  encryption method is XOR and backwards compatibility mode is not
  selected, then instead parse the rightmost enckeylen octets of K as an
  encryption key EK and the leftmost mackeylen octets of K as a MAC key
  MK.

In the end, it depends on the parameters enckeylen and mackeylen, which define the sizes of the keys for the symmetric encryption and the MAC, respectively.


Comparing Difference Distribution Tables


Is it necessary to prove EUF-CMA security of blind signature based on one-more type assumption？

One more type assumptions are a better fit for blind signature schemes since they fit their security model (e.g. receive valid but anonymous coins from a bank where you should not be able to spend more than you received).
Indeed they are stronger when compared to other types of assumptions (eg. DLOG).
However there have been proofs of security based on the dlog such as the proof of Pointcheval Stern on the Okamoto Schnorr blind signature unforgeability in https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf where the situation is better explained.


Which homomorphic encryption scheme has the same size of plaintext space and ciphertext space?

Is there a fully homomorphic encryption scheme that has the same size of plaintext space and ciphertext space?

As far as I know, none have this property and it makes sense when you think about it.

IF the plaintext and ciphertext spaces are the same size, you cannot achieve semantic security. A good example of this is RSA. In order to achieve semantic security in RSA, we shrink the plaintext space so that we can add random padding.

Semantic security is very important, especially when we are talking public key encryption. W/O it, an attacker can simply use the public key to encrypt guesses of ciphertexts and then compare with the ciphertext of interest to figure out the plaintext. FHE applications would be especially vulnerable to these sorts of attacks as we are likely not encrypting random values, but are encrypting values with some meaning (salaries, votes, etc) so that we can compute on these values.

  I want to pre-compute the result for all possible ciphertext of a homomorphic encryption. Is it achievable?

I am not exactly sure what you mean here, but I doubt it is achievable. The ciphertext spaces in modern public-key systems are huge ($2^{2048}$ for 2048 bit RSA for example). Precomputing all of that would take more storage space than you can even dream about having. For a comparison, the estimated number of atoms in the observable universe is $10^{82}\approx 2^{272}$. So even if you could store one pre-computation per atom, it would take more atoms than what we can even observe in the universe to store your table.

Now, for this example I used RSA. FHE ciphers today have larger ciphertext space than even RSA.


Using cryptographically random password as both the password and the salt

The whole point of a salt is to be unique to a set-password operation, so that attackers can't reuse work when they target multiple accounts (multiple users on the same server, multiple servers, or both). Using the password as the salt completely defeats the purpose.

The salt does not need to be unguessable or secret. The reason it's almost always a long-ish random string is to be statistically unique (in the literal sense), not to be securely unique: it's random so that the chance of two set-passwords using the same salt accidentally is negligible, not so that an adversary cannot guess it. A unique server name plus thread identifier plus timestamp would work as well, but that's not commonly done because it's hard to ensure you get a unique string this way in all environments (e.g. on a cloned virtual machine).

Most libraries automatically generate a random salt during the set-password operation and store the salt with other metadata together with the output of the password hashing function. In most programming environments, you'd need to do some extra processing to force a different salt during the set-password and check-password operations, and to change the storage format so that the salt is not stored (otherwise you'd just be storing your password in plain text). Do not do this extra processing: it would add complexity, only to reduce security even if implemented perfectly.

A password with 64 characters on a 62-character alphabet has about 381 bits of entropy, which is overkill: any data that it protects, or its transmission in communication, would at most be protected by a 256-bit key. 43 characters would give you 256 bits. 20 characters would give you 119 bits. With a password that long (and randomly generated, otherwise length is irrelevant), you don't actually need a password hashing mechanism: the purpose of password hashing mechanisms as opposed to ordinary hashing is to make guessing harder, but guessing a 119-bit secret is infeasible in the first place. So from a theoretical perspective, because your password is already high-entropy, using Argon2i or any other password hashing function with a defective salt won't actually reduce the security of your system. But you still shouldn't do it, both in case the system is ever used with a “normal” (lower-entropy) password and because it would increase the implementation complexity.


One-direction same size encryption algorithm that allows for partial replay

It sounds like you're describing a Commitment scheme.

A simple implementation would be that Alice makes a list of boat position + ":" + random 16 bytes (with a different random value per item). She sends Bob the hash of each list item at the start of the game, and later she can send Bob the plaintext of any of the hashes to prove the position of a boat is where it was when the game started. (The random value in the hash is to prevent Bob from brute-forcing the hash. If there only a small number of possible boat positions, then Bob could brute-force to reverse any hash easily if it weren't for the random value.)


Unable to understand the concept of a 1-bit PRF

what is a 1-bit PRF?

That would usually be a PRF with a 1-bit output, but the rest of the text clarifies it is meant a 1-bit input.

what is the $\{0,1\}$ in $F:\ K \times \{0,1\} \to K$ ?

It is the set with two elements $0$ and $1$. This also is the set of the possible values of the second/right/normal/non-key component of the input of the PRF $F$.
Note: a Pseudo Random Function Family (confusingly abbreviated PRF just like a Pseudo Random Function) has two inputs (equivalently: an input consisting of an ordered pair). The first (the left component of the pair) is the key, and the second (the right one) is the normal/non-key input (which is the single input of any particular member of the Pseudo Random Function Family). The member of the Pseudo Random Function Family corresponding to key $k$ is often noted $F_k$. By that notation $F_k(x)=F(k,x)=F((k,x))$. Here, $F_k:\ \{0,1\}\to K$ (that's a particular Pseudo Random Function for a certain key $k$), since $F:\ K \times \{0,1\} \to K$ (that's the whole Pseudo Random Function Family).

what does $G(k)[x]$ in $F(k, x\in\{0,1\}) = G(k)[x]$ mean?

The PRG $G$ takes an input $k$ and produces an output $G(k)$ consisting of two parts of the same width as $k$, as apparent in $G:\ K \to K^2$. This is the same as  $G:\ K \to K\times K$. That is, the output of $G$ is an ordered pair of bitstrings, assimilated to a bitstring twice as wide as $k$, that we split in two parts as wide as $k$, each from the same set $K$ as $k$ is from.
$G(k)[x]$ is the first or the second component/part of the output of $G(k)$, according to $x$ being $0$ or $1$. It's also the output of $F$ for input $(k,x)$ where $k$ is the PRF's key, and $x$ is the PRF's second/right/normal/non-key input, which is a single bit.

What exactly is $x$?

It's a bit. It's not an input of the PRG $G$. It selects among the two halves of the output of the PRG $G$ for input $k$, that is $G(k)$. We can think of $[x]$ as we'd do for [x] in a computer language with indexes.


Extracting key bits from linear cryptanalysis equation for SDES

The attack, as stated in sections 6.2 & 6.3, actually can only recover the quantity
$K_1[1,3]\oplus K_2[1,3]$.

What you would hope to do is, to use a similar approach via another high probability linear relation [usually there is more than one] and recover more relations between subkey bits. Eventually, the goal is recovering all the original key bits. Assuming enough relations between pairs of key bits are recovered, then you can use take one variable in each relation as an unknown, and use more plaintext/ciphertext pairs, by brute forcing over those values, and select the values that give the highest bias. This is quite tiresome for DES.

I suggest reading Howard Heys' tutorial on linear and differential cryptanalysis [google it], which now appears as part of Stinson's Crypto book (3rd ed.) as well, where a more clear examples of targeting subkey bits is given, for both linear and differential cryptanalysis.


Is the post-quantum scheme quantum-resistant without regard to QROM

I think you are somewhat confused, so I'll try to briefly describe the state-of-the-art to see if it helps.
The general design paradigm of a post-quantum KEM is separated into two steps:

Build an IND-CPA secure PKE, generally based solely [1] on the hardness of some computational problem.

Apply a general transformation (usually some variant of the Fujisaki-Okamoto transform) to convert the IND-CPA-secure PKE into an IND-CCA secure KEM

The only part where hashing (or any kind of ROM type stuff) strictly needs to enter the picture is in the second step. Is this step done solely in the ROM, or the QROM as well? This is relatively straightforward to check --- many authors rely on A modular analysis of the Fujisaki-Okamoto Transformation, which has a section on transformations in the QROM.
Do the authors use this? You can check their design specifications --- here is the specification for KYBER, a NIST PQC round 3 finalist. Section 4 discusses their security analysis, which includes analysis in the QROM. This is typical of "serious" constructions.
Note that the underlying IND-CPA-secure PKE that KYBER is building on does not mention QROM (or ROM for that matter) analysis, as one only really needs it (and the security modelling of hashing overall) in the transformation from IND-CPA security to IND-CCA security.
Also note that in general the QROM results tend to be weaker than the ROM results - the reductions are generally not tight without making some slightly less standard assumptions.
This is of course a much different statement than there being no QROM analysis though.

[1] This is not strictly true, often practitioners reach for other primitives (say PRGs / extendible output functions) for efficiency purposes, but these are not strictly required if one is ok with a slightly less efficient construction.


Can I combine two PRNGs to make use of more seed data?

Why are you afraid of "overseeding" the PRNG? The Java SecureRandom class specifies the setSeed function as:

public void setSeed(byte[] seed)

So just feed the 320 bits (40 bytes) data to the setSeed function and it will supplement the existing seed. Leave the compression into the state to the underlying SecureRandom implementation.

[EDIT1]

Note that the SHA1PRNG implementation simply uses the new seed in a message digest update, and that message digest is SHA-1, hence the 160 bit state.

[EDIT2]

Note that it may depend on the entropy source if the entropy represents 320 bits of true random data. The initial compression of the seed data will make sure that any random entropy from the entropy source is used.

Another reason to combine to PRNG's is when the PRNG algorithm is not fully trusted. In that case it is much better to switch to another PRNG. If one is vulnerable the other one will be vulnerable as well.

It is better to re-seed the PRNG more often if there is entropy to spare.


How to verify a number encrypted with an unknown key

You probably don't need to re-encrypt using the Paillier crypto system.

1) Alice encrypts $c_1=g^{m_1} r_1^n$ und $c_2=g^{m_2} r_2^n$ and computes $r_3=r_1 \cdot r_2$ and $m_3=m_1+m_2$, then sends $c_1$, $c_2$, $m_3$ and $r_3$ to Bob

2) Bob computes $c_3=c_1 \cdot c_2=g^{m_3} r_3^n$ - If the homomorphically computed sum matches the re-encryption Bob will believe that $c_3$ encrypts $m_3$

The basic idea is that $g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1 \cdot r_2)^n$

All cipher text operations are executed modulo $n^2$

This proof is backed up by Paillier's original paper.
Unfortunately the proof is not absolutely Zero Knowledge as the sum may give you information about the possible summands. However you may choose large similarly sized primes for the $r$s so an attacker would need an efficient solution for prime factorization (see other question here).


Multi-round Transposition/Playfair as a secure hand cipher in the computer age

Some years ago, someone (Terry Ritter maybe) suggested using Playfair as follows.

First: just normal Playfair with some key.
Second: add a single null at the front and at the end of the cypher text.
Third: go to First with new key.

This can be extended by repeating the process. The point of adding the nulls is to split letter pairs between rounds. You could improve it as suggested in your question by using a transposition cipher before the Playfair step. Computer attacks on Playfair often just exhaustive key guesses coupled with Playfair's lack of ability to diffuse the key through the plaintext. Transposition breaks up the keyword search and adding single null between steps increases diffusion.

Still, one needs a fairly long key for the Playfair part. Perhaps using parts of a shared book keyed off the date. (Bible, "Catcher in the Rye," "Texas Almanac," etc.)


Decryption issue with self-coded AES-128

All of your encryption rounds are incorrect, either due to incorrect round function or key schedule (or state alignment). Showing round 0 (round key addition before first round) will help show if the keys are being added correctly to the state.

The key expansion is also very important, if that is not done correctly it will not work at all.

I will assume the decryption is also incorrect, but did not test, since whatever method fixes the encryption code should be applied to all code, resulting in correct outputs.

Given your plaintext and key, your state data should look as below.
The key schedule values are shown as a column in 32-bit unsigned value format, which is reverse byte order from the state array:

Key schedule
Round 00  d37608d2 7de9fb66 3611351b e01c2052
Round 01  d3979464 ae7e6f02 986f5a19 78737a4b
Round 02  602b1bbc ce5574be 563a2ea7 2e4954ec
Round 03  ae1a2098 604f5426 36757a81 183c2e6d
Round 04  92b7cba1 f2f89f87 c48de506 dcb1cb6b
Round 05  ed3103ae 1fc99c29 db44792f 07f5b244
Round 06  f6f4e5b9 e93d7990 327900bf 358cb2fb
Round 07  f96281ce 105ff85e 2226f8e1 17aa4a1a
Round 08  5b922d98 4bcdd5c6 69eb2d27 7e41673d
Round 09  7c61ae06 37ac7bc0 5e4756e7 200631da
Round 10  2bd6c1f7 1c7aba37 423decd0 623bdd0a

Plaintext and initial state
6162636465666768696A6B6C6D6E6F70

  61 65 69 6d
  62 66 6a 6e
  63 67 6b 6f
  64 68 6c 70

Round 0
  b3 03 72 3f
  6a 9d 5f 4e
  15 8e 7a 73
  b7 15 5a 90

Round 1
  e6 98 e8 00
  50 b2 f6 9e
  ab 2f 59 ef
  20 2a 9c 9b

Round 2
  3d 9c 10 14
  a9 7b e0 70
  23 36 5a 2a
  3d ec 58 6a

Round 3
  09 7b 15 83
  9e 40 b6 0c
  7d c8 eb a1
  5c 53 83 0f

Round 4
  27 6f bf b1
  8e 3e ac fe
  ec 2d e3 b2
  9d 79 ef d3

Round 5
  97 a3 91 e3
  e5 0a e3 e4
  c7 7c b1 f5
  cd e6 c1 20

Round 6
  64 ec 55 c1
  57 dd 8c 42
  52 2d 8f ec
  af 61 02 3f

Round 7
  16 c2 99 a8
  bb ce b3 80
  99 f9 dc bb
  64 01 d4 f2

Round 8
  9f 92 3e 56
  7f 4c 17 92
  c9 8f 8b 98
  96 25 9b c0

Round 9
  57 83 ab a9
  da 95 39 be
  3c 34 5a bf
  71 6b 7f 61

Round 10 (final ciphertext)
  ac db b2 d9
  eb a8 42 8a
  68 72 d6 23
  c4 bf 3d b0

Ciphertext
ACEB68C4DBA872BFB242D63DD98A23B0


What's the name of this random number generation algorithm?

The algorithm described is an unbiasing algorithm, which is a type of randomness extraction algorithm.
Another method is von Neumann unbiasing where you
can take 2 bits $(X_n,X_{n+1})$ and output $Z=0$ if
$(X_n,X_{n+1})=(0,1),$ output $Z=1,$ if
$(X_n,X_{n+1})=(1,0),$ and discard the two
bits otherwise. This gives exactly uniform
output bits, if the sequence $X_n$ is independent and identically distributed since both the above $(0,1),(1,0)$ have probability exactly $p(1-p)$.


What encryption mode should I use to protect a packet but the integrity of the entire packet, including its header, is protected?

What encryption mode should I use to protect a packet, such that the payload of the packet is encrypted, but the integrity of the entire packet, including its header, is protected?

If the context is to be ignored, this functionality is usually called Authenticated Encryption with Associated Data (AEAD) in cryptography. It has usually four inputs (and is deterministic in those):

A key - which must be uniformly random and unknown to any adversary
A nonce - which must be unique for a given key, you don't need to keep this secret
A plaintext message - which will be encrypted and integrity protected
Some associated data - which will only be integrity protected

Upon decryption, the key, the nonce, the ciphertext, and the associated data is given and is guaranteed that decryption only succeeds (yielding the plaintext) - assuming the adversary doesn't know the key - if this nonce and associated data have been used to produce this ciphertext.
Good schemes that satisfy this notion include AES-GCM, AES-EAX, and ChaCha-Poly1305.
However, there's a good chance that you actually want a higher-level primitive: A Secure Channel. Which given a key gives you a randomized / stateful / nonce-based encryption algorithm and a stateful decryption algorithm. These guarantee you that not only have no new messages been added without the knowledge of the key, they also guarantee you to detect whenever messages have been re-ordered or dropped.
Standard constructions for this include (pre-shared key) TLS and an appropriate selection from the Noise Framework.


XTS mode of operation and authentication

I assume you mean "random access" by "decrypting arbitrary part of ciphertext, operate on it, and securely encrypting it again".

The XTS mode is designed as a "Full-Disk Encryption" mode, which means it does not have the slightest concern with authentication.

From practical perspective, I recommend having a keyed tuple or tree hashing mode for authentication. Some of which are specified in NIST SP 800-185. You may also want to check out Sakura tree-hashing encoding scheme.

Update

Tuple hashing is a hashing scheme, where a sequence of bit/octet strings is hashed in such way, that guarantees the uniqueness of the output, even when otherwise their simple concatenation would have resulted in some ambiguity. For example, hashing the concatenation of "ab" + "c" would be the same as "a" + "bc", but the tuple hashing of $(\text{"ab"}, \text{"c"})$ would be different from $(\text{"a"}, \text{"bc"})$.

Tuple hashing is usually sequential, but it doesn't always have to be.

Tree hashing is an efficiently method for hashing long messages. Example include Merkle tree. During the SHA-3 competition, the Keccak team proposed the Sakura tree-hashing encoding scheme, to solve the shortcomings of various ad-hoc tree-hashing encodings.

I added the "keyed" in the previous text to mean that they're supposed to be used as authentication tag.


How can DNA Computing solve very complex problems that can present in cryptography?

The problem is scaling. Donald Beaver, looked at the factoring numbers with DNA. $10^3$-bit number will require $10^{20000}$ test tubes by using the Hamiltonian path idea of Adleman.

Adleman, also, observed that DES key search for 256 keys would occupy only a small set of test tubes. Let say $2^4$ tubes for $2^8$ keys. As a result we need $2^{56} / 2^{8} * 2^{4} = 2^{52}$ test tubes.

The previous statements are from previous DNA computing works directly on Cryptography. There are new studies on computing with DNA;

There is a promising technique, called CRISPR9 with many version that enables editing DNA even at home.
There is also interesting work called BLADE, where authors built 113 circuits from DNA.
And, the DNS USB memory, MinION.

Under these and other new improvements in DNA computing, in the very near future, one may come up with new results affecting Cryptography.

Update: How the Hamiltonian DNA computing is performed;

Encode the vertices with DNA and together with Watson-Crick complement. e.g. ;

ATLANTA DNA name ACTTGCAG complement TGAACGTC and

BOSTON  DNA nameTCGGACTG complement AGCCTGAC.

Here note that ACTT considered as the first name and GCAG considered as the surname.
The Edges defined as  GCAGTCGG where the first 4 char GCAG is the ATLANTA's first name and the last four char TCGG is the BOSTON's second name
Polymerases step; this gene produces the complimentary copies.
Ligases step; Ligases bonds the strand of DNA's together ( normally repairs DNA).
Polymerase Chain Reaction; used to remove all path not starting from starting node and not ending with the end node.
Gel-Electrophoresis, when current applied the negatively charged DNA molecules start to moves to the anode. The interesting part; the longer the DNA strand the slower it moves. So separation by length.
DNA synthesis. The DNA info extracted.

As one can see, the process completely biological, except Gel-Electrophoresis which is not a part of DNA process in nature.

This is almost the view of the step from bird fly of the article of Adleman in Scientific American. A more detail can be found here.

Hamiltonian path to Factorization

Now, let talk about how the Hamiltonian Path problem can be turned into a factorization problem that Donald Beaver used. This is mostly from, normally the reduction is mentioned in the famous Introduction to Algorithms book of Cormen at. al.

Build a non-deterministic polynomial-time turing machine;
given an $n$ and $k$ accepts if there exists some $m$ where $1<m<k$ and m divides n, or rejects otherwise.
For each query (n,k), by the Cook/Levin reduction  to construct a boolean circuit which is satisfiable iff the Turing machine accepts (n,k).
Reduction from Circuit-SAT to 3-SAT.
Reduction 3-SAT to Hamiltonian Path.
Solve the Hamiltonian Path problem with DNA.

Reductions are answer-preserving, so backward available.

This is the process that Donald Beaver looked into and said

  Even in the case of factoring, if every path in a superpolynomial computation is assigned a molecule, then a superpolynomial number of molecules will be needed. Merely fitting these molecules into a polynomial volume is an impossible task, but a necessary one: if the molecules are going to have enough time to mix and react, then light must be able to pass from one side of the test tube to the other within polynomialtime.
  This impossible task does fortunately expose new avenues for further research, leaving open the question of whether black-hole algorithms for factoring exist.

Any other algorithm, with current knowledge, must have to fallow the same reduction step to the Hamiltonian Path problem and will face the same impossible task.


Need help cracking a Vigenère cypher with a period of 2

Cracking a Vigenere cipher usually involves the below 3 steps:

The Friedman Test - The first thing you need is the length of the key (approximately at least). You can do this by finding the Index of Coincidence (IoC). Since Vigenere cipher is a polyalphabetic substitution cipher, its IoC should be near 0.038 for a given piece of cipher text. This is pretty nice webpage about IoC, its significance and how to calculate it. Once you have the IoC calculated, you can find the length of the key from the IoC by using the formula given in this document.
Splitting the text and Frequency Analysis -  Once you have the key length (say $l$), split the entire cipher text into multiple rows with $l$ columns. Now, each column here can be taken as a shift cipher. Frequency analysis can be used for an individual column to figure out the shift for that column. For example, if the frequency of the letter 'c' is the most in a column, then it is probably substituted for 'e' and so the shift here will be 2. Since the shift is 2, the key for this particular column is the letter 'b'. Likewise there will be $l$ shift ciphers with $l$ individual keys for each column or shift cipher. These $l$ keys will make the actual key of the Vigenere cipher.
Using the key to decrypt the entire text - After we compute the key, we can use it to shift the remaining of the text in each column (as is done in the encryption method of the Vigenere cipher). We will then combine the rows to get back the plaintext.

Note that you might have to perform the 2nd step multiple times since Frequency Analysis might not always give the right answer on the first shot.

Alternatively, after the first step, you can use the length of the key here to decrypt your cipher text in an automated way if you don't want to go through the hassles of step 2 and 3.

Hope this helps!


Why probabilistic syntax for encryption schemes?

Why is the mechanism of encryption formulated in this way?

Writing $D(d,E(e,\alpha)) = \alpha$ would imply that $E(e, \alpha)$ is a unique value, and it generally is not in practice (as most encryption schemes are, in fact, nondeterministic; that is, there are a number of ciphertexts that correspond to any specific plaintext).

The text as written $\text{Pr}[D(d,E(e,\alpha)) = \alpha] = 1$ accounts of the fact that $E(e, \alpha)$ can take on a number of different values (with some probability distribution), and so matches reality (while respecting the formalism).

  I read later in the book that this definition may have the probability bound relaxed to allow for some negligible chance that decryption is not possible, and that this may be necessary for certain public-key encryption schemes.

Yes, it comes up in most lattice-based public key encryption schemes and in some code-based public key encryption schemes.  I have personally never heard of a symmetric system that had the possibility of a decryption failure; that is, where the decryption of the correctly encrypted (and unmodified) ciphertext would not result in the original plaintext.


Bilinear Map over group of unknown order

Is it possible to build a bilinear map where the underlying group is an RSA group?

I.e. $e: \mathbb{Z}_N \times \mathbb{Z}_N \rightarrow \mathbb{Z}_N$ where N is an RSA modulo?

If we can build a nontrivial bilinear map over arbitrary RSA groups, then we can solve the DDH problem over a prime field.  Here's how:

The DDH problem is: given $g, p, g^a \bmod p, g^b \bmod p, g^c \bmod p$, is $g^{ab} \bmod p = g^c \bmod p$ ?

To solve this, we select a prime $q$ and compute $n = pq$, and then construct a bilinear map $e$ over that ring.

Then, you find the value $h$ with $h \equiv g \pmod p$ and $h \equiv 1 \pmod q$; this is a simple application of CRT

Then, the same process allows you to find $h^a$ from $g^a$ (as $h^a \equiv g^a \pmod p$ and $h^a \equiv 1 \pmod q$, and similarly $h^b$ and $h^c$

Then, you compute both $e(h^a, h^b) = e(h, h)^{ab}$ and $e(h, h^c) = e(h, h)^c$; if they're the same, then $ab \equiv c \pmod{p-1}$

We do not know how to solve the DDH problem over arbitrary prime fields, hence there is no known way to generate nontrivial bilinear maps over RSA groups.


Factorization of the public value $N$ from the RSA cryptosystem

Since $p$ is a factor in both $N_1$ and $N_2$ you can simply calculate $p$ by using Euclid's algorithm.

Once you have $p$ you can then calculate $q_1$ and $q_2$ (simply divide $N_1$ by $p$ to get $q_1$ and divide $N_2$ by $p$ to get $q_2$).


Modular exponentiation on calculator for textbook RSA

If your calculator is able to compute $n^2$, you can compute $m^e \bmod n$ using the binary exponential method.

In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$.

Now, with the algorithm below, you can compute $c$:

  $z:=1$
  $\text{for } i:= \ell \text{ down to } 0 \text{ do:}$
  $\quad z:=z^2 \bmod n$
  $\quad \text{if } e_i = 1 \text{ then } z:=(z \cdot m) \bmod n$
  $\text{end for}$
  $\text{return } z$


Take a look at FIPS 140-2 Annex A. It lists the following:

Symmetric Key

AES, Triple-DES, Escrowed Encryption Standard

Asymmetric Key

DSA, RSA, ECDSA

Hash Standards

SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256

Random number generators

See annex c

Message authentication

CCM, GCM, GMAC, CMAC, HMAC


AES mode which verifies data integrity AFTER decryption

Yes, you are correct, as long as it really only is the AES part which could dysfunction.

Quoting another source, for example Wikipedia's CCM page:

  These two primitives are applied in an "authenticate-then-encrypt"
  manner, that is, CBC-MAC is first computed on the message to obtain a
  tag t; the message and the tag are then encrypted using counter mode.

Note that we generally do not recommend to do "Mac then Encrypt", however CCM is a mode of encryption which features its very own proof of security, so you are good to go.


Is $g(x)$, the first $(n -\log(n))$ bit of $f(x)$, a (strong) one-way function?

Without knowing the details, note that any algorithm can utilize the $n-\log n$ bits of $g$ to invert it, can then brute force the remaining $\log n$ bits in time complexity $O(2^{\log n})=O(n),$ thus inverting $f.$

This will at most multiply the overall complexity by a linear factor, thus cannot achieve more than a polynomial gain between inverting $f$ and inverting $g$.


Same message space for different public exponents

The RSA system in the question uses

a common modulus $n$ shared by multiple public exponents $e$
message space $[0,n)$
a 1024-bit mosulus $n$ with > 6 prime factors

This leads to security issues:

Given a private exponent $d$, matching $e$, and $n$, it is possible to factor $n$ (see answers to this). Then, because of 1, it is trivial to find the private exponents for all other $e$, and decipher all cryptograms. This is a disaster if any of the various $d$ falls in the hand of an adversary (including if the various $d$ are held by persons with diverging interests).
Message space $[0,n)$ of 2 strongly suggests textbook RSA, where encryption of $m$ in the message space is as $c\gets m^e\bmod n$. This is unsafe, in particular because a guess of $m$ can be trivially verified from $c$, $n$, and $e$, which all are assumed available to attackers. That's a disasters for a coin throw, the name of person on the class roll, a credit card number... Proper RSA encryption use random encryption padding, e.g. as in RSAES-OAEP of PKCS#1v2.2, with typically a reduced message space.
If 1 is combined with textbook RSA, and the same message is sent encrypted under multiple $e$, it can be deciphered without knowing any $d$ or the factorization of $n$ (see this).
The 1024-bit key size of 3, although seriously obsolete, would remain extremely hard to attack with 2 or 3 factors of about equal size. But with at least 7 factors, one must be 147-bit or less, and ECM can pull it out with little effort.


Examples of flattening code to create an R1CS

This sort of programming logic for the ZK SNARK systems can be developed into Arithmetic Circuits using Zokrates, a toolbox for zkSNARKs on Ethereum. It helps you use verifiable computation in your Decentralised Applications, from the specification of your program in a high-level language to generating proofs of computation to verifying those proofs in Solidity, the Smart Contract Langauge for Ethereum Blockchain. Please find a sample programming logic written for Zokrates below.

Once you compile the code, you can proceed to the circuit setup. It creates a prover key and verification key. These keys are derived from a source of randomness, commonly referred to as “toxic waste”. Once it is generated, you can proceed to generate a Solidity contract which contains the generated verification key and a public function to verify a solution to the compiled program. Then you can compute a witness for the compiled program. A witness is a valid assignment of the variables, which include the results of the computation.

def main(field a, field b, field c) -> (field):
    field result = 0
    result = if a + b > c  then a + b else 1 fi
    result = if a + b < c  then c else 1 fi
  return result


In NIST modulus and key size recommendations is `group` equivalent to modulus and `key` equivalent to exponent?

Yes, when using cryptosystems based on the difficulty of the Discrete Logarithm in $\Bbb Z_p^*$ or a subgroup thereof, a key size recommendation of a 3072-bit group means that the modulus $p$ is 3072-bit, and a 256-bit key implies that a private exponent (a key) is 256-bit.

In some (as far as I know: all) NIST contexts, a 256-bit key additionally implies that the order of the public generator $g$ is a 256-bit prime $q$, and (thus) that $p-1$ has that 256-bit prime factor $q$, and public keys belong to a subgroup of $\Bbb Z_p^*$ having order $q$. The generation of $p$ and $q$ is described in FIPS 186-4 appendix A (Dave Thompson's comment explains that's for various sizes including 3072/256).

In all contexts, a private exponent should be at least twice as wide as the security level in bits, which guards against Baby-step giant-step and Pollard's rho. It is good and customary that $p-1$ has a large prime factor $q$, and that the order of the generator $g$ is a multiple of that $q$. That $q$ should be at least twice as wide as the security level in bits, which guards against Pohlig-Hellman.

The width of $p$ is dictated by resistance to a Discrete-Log extension of GNFS, which is why recommendations for this parameters match those for RSA public moduli.

In Diffie-Hellman, it can (but need not) be chosen $p$ such that $q=(p-1)/2$ is prime, and thus $g$ of order $(p-1)/2$ or $p-1$, even when the key is narrower.


Security of Diffie Hellman in specific cyclic group

If $p$ is a prime of the specified structure then the order of the multiplicative group $\mathbb Z_p^*$ is $p-1=\prod_{j=1}^k q( j)$. As you may notice this is a product only consisting of small factors and thereby called smooth.

We actually know an attack on groups with smooth order, called Pohlig-Hellman-Algorithm and the specified structure yields the optimal performance for that algorithm to compute discrete logarithms.


How to Check Strength of RSA Public Private Key

RSA public/private key pairs are no exception: there is no way to assess that a cryptographic key is strong by looking at its value; only ways to assess that it is weak. And lack of signs that it is weak is no good indication that it is strong. Arguments are extensions of:

A key which value leaked is totally weak, and has exactly the same value as before it leaked; hence examining the key's value can not demonstrate that the key is strong, or provide a solid indication about that.

Extension: a key that was generated by a strong method from the output of a public Cryptographically Strong Pseudo Random Number Generator which seed was chosen in an undisclosed way, is weak and indistinguishable (by definition of  Cryptographically Strong) from one generated similarly except from a truly random seed, which is strong.

It is even hard to conclude that an RSA key is weak by looking at its value (except in extreme cases, like a short public modulus, or when all but one of its prime factors can be compressed into a very small amount of information); in particular, tests concluding that an RSA key does not meet criteria expected for conventionally generated RSA keys are no proof that it is weak: an RSA key can still be strong if it has regular patterns in half the high-order bit of the public modulus $N=p\,q$, or/and some of the high-order bits of $p$ and $q$; or a private exponent $d$ significantly smaller than $N$.

So what can be done? Basically, have the key generation process competently audited. By extension, the audit should also cover how the key is kept secret, including during use.

One common modern referential for RSA key generation is NIST's FIPS 186-4, section 5 and references including Appendix B.3 (with some origins in ANS X9.31:1988); but that has limitations:

FIPS 186-4 formally allows only for 1024-bit, 2048-bit, or 3072-bit public modulus; the former is obsolete, and 4096-bit or even more is increasingly common, for reasons that are at least understandable.
FIPs 186-4 requires public exponents $e>2^{16}$ and public moduli with two primes factors, when sometime performance considerations dictate otherwise (the public key function is up to about 8 times faster with $e=3$ than with $e=65537$; for constant modulus size the private key function is up to nearly $k^2/4$ times faster in software when there are $k$ factors, and using available hardware support might require $k\ge3$).
FIPS 186-4 does not give prescriptions for a random generator complete with entropy source and testing procedures; it is thus perfectly feasible that an intentionally weakened random number generator makes an implementation honestly certified compliant to FIPS 186-4 vulnerable selectively to those in the know.
FIPS 186-4 has 5 methods (B.3.2 to B.3.6), and choice can be a burden; they vary according to several criteria

Use of any RNG (possibly non-deterministic), or of a PRNG with seed of precisely twice as many bits as the conventional security strength of the key prescribed by SP 800-57 Part 1;
Use, or not, of auxiliary conditions on the primes generated (being $p$ such that $p-1$ and $p+1$ each have a large auxiliary prime factor); notably, that complication is mandated for 1024-bit moduli, and thus unavoidable for conformant implementations that need backward compatibility. That contributes to the significant difficulty of making a marketable truly FIPS 186-4 implementation for constrained environments such as Smart Cards.
Use of probable or provable primes, for the factors of the public moduli or/and the auxiliary primes.

The precision of FIPS 186-4 is a double-edged sword: that makes it feasible to automatically prove non-conformance without false positives; but that makes it feasible to exploit a conformant FIPS 186-4 implementation using a known rigged RNG without knowing the details of the implementation.
FIPS 186-4 is totally lacking about protection against side-channel leakage and fault attacks, including during key generation, even thought that conceivably can matter in some cases (e.g. Smart Cards supposed to securely generate a key on the field).

A less common referential is ETSI TS 102 176-1 V2.0.0 (2007-11), which pays its simplicity at the price of vagueness:

  To generate the key pair two prime numbers, $p$ and $q$, are generated
  randomly and independently, satisfying the following requirements:

  the bit length of the modulus $n\;=\;p\,q\;$ must be at least MinModLen; its length is also referred to as ModLen;
  $p$ and $q$ should have roughly the same length, e.g. set a range such as $0,1 < | \log_2p - \log_2q | < 30$;
  the set of primes from which $p$ and $q$ are (randomly and independently) selected SHALL be sufficiently large and reasonably uniformly distributed.

Notice the use of e.g. in the second bullet; and that the bounds then proposed are extremely different from those of FIPS 186-4, are not met for about 1/3 of keys generated according to FIPS 186-4, and often lead to private keys that can not be moved to many implementations designed for FIPS 186-4.


How to jusify {e,n} is a valid RSA public key?

That depends on exactly what you mean by a "valid RSA public key"; in general, it is difficult to validate a public key without the corresponding private key (unless the public key is obviously bad).

If you mean that there is a corresponding private key $d$ such that $(M^e)^d = M \mod N$ for all messages $M$, then there are two conditions; if both are met, then there will always be such a $d$:

$e$ is relatively prime to $\phi(N)$; if $N$ has k distinct prime factors $p_1$, $p_2$, ..., $p_k$ then $\phi(N) = (p_1-1)(p_2-1)...(p_k-1)$
$N$ is squarefree; that is, there is no integer $n > 1$ such that $n^2$ is a divisor of $N$.  Or, in other words, all the prime factors of $N$ must be distinct.

Note that there are varients of RSA for which a public key might not meet these assumptions; they deal with the fact that $M^e$ might not have a unique inverse in various ways.

As for how to determine whether a public key meets these criteria, well, neither critieria is feasible to verify for a large key.  On the other hand, it is easy to note by inspection that your examples do not; they both have an even value of $e$, and even numbers are never relatively prime to $\phi(N)$ (which is also even).  In addition, your second example has $N=117$, which is not square-free (as it has a divisor of $3^2$).

On the other hand, a "valid RSA public key" might mean a key that meets the above constraints, and is secure.  This implies that $e>1$ (easy to validate), and $N$ is hard to factor.  If $N$ is large enough to be not easily factored, this also is hard to validate.

Thirdly, by a "valid RSA public key", you might mean "all of the above, and in addition, someone knows the private key".  The only way you can accertain that is to work with the person who is supposed to know the private key (and, for example, have a Zero Knowledge Proof that they do indeed know the factorization of $N$).


Given infinite unencrypted and encrypted texts, can I find the algorithm?

summmary

In general, no.
An attacker who has lots of ciphertext+plaintext pairs may never be able to reverse-engineer an algorithm from them.
An attack may not even be able to distinguish which one of a large group of known encryption algorithms was used to generate those ciphertexts.

However, various weaknesses in some algorithms and protocols are known.
If such an algorithm was used, the attacker may find it relatively easy to rule out all but a few or perhaps only 1 of the known encryption algorithms.

details

Some people who build modern ciphers try to make their ciphers "indistinguishable from random".
Several modern ciphers (especially ones intended for use in steganography) are not currently known to be susceptible to such a distinguishing attack.

No matter how many ciphertext+plaintext pairs the attacker collects that were properly encrypted using a single one of those algorithms using a single long-term key,
there is no known practical way for that attacker to distinguish a new message encrypted using the same algorithm using the same long-term key from a freshly generated series of bits from a hardware random-number generator.
This implies that there is no known practical way for that attacker to discover which one of those algorithms was actually used.

Cryptanalysts have discovered distinguishing attacks for many vulnerable ciphers.
If an attacker collects enough ciphertext-plaintext pairs encrypted by such a vulnerable cipher, that attacker can rule out most other ciphers, narrowing down the possible algorithm to a few or perhaps only 1 known vulnerable encryption algorithm.

When an attacker has samples of both the plaintext (called a crib), and its encrypted version (ciphertext), the attacker can mount a known-plaintext attack.

The people who build modern ciphers try hard to make their ciphers immune to known-plaintext attacks.
Most modern ciphers are not currently known to be susceptible to known-plaintext attacks.

However, many historic ciphers (most famously, the Enigma cipher) can be partially or completely broken by a known-plaintext attack.

Many distinguishing attacks and known-plaintext attacks depend on the person doing the encryption using the same key for large numbers of messages.
Sometimes that number is so extremely large that these attacks are impractical.
Other times that number is large but not improactical, and cryptographers recommend periodically rekeying long before such attacks are practical (RFC4253, RFC4344, etc.).

In practice, many communication protocols transmit the specific encryption protocol used, transmitted in plaintext in the header before any ciphertext, at the beginning of every message.
An attacker only needs to look at that header to know which encryption algorithm was used.

If someone encrypts enough messages with the same key using a block cipher in electronic codebook mode,
and an attacker gets enough ciphertext-plaintext pairs,
then even without knowing which particular block cipher is used,
the attacker can decrypt any block in any new encrypted message whenever a block of plaintext in the new message happens to match a block of known plaintext.

In theory, if an attacker has an "infinite amount" of computing power,
that attacker try every possible encryption key in every known encryption algorithm and see if it "works".
Such a brute-force attack can in theory recover the key for almost all known encryption algorithms.
(The one-time pad and closely related ciphers are completely immune to a brute-force attack).
Fortunately for people who are not attackers, the amount of work required for such a brute-force attack usually makes them impractical.


Is the security of MAC function is based on HASH function

It is widely known, generally, that a MAC is a HASH with key.

Nope; there are plenty of perfectly good MACs that, if you know the key, aren't very good hashes at all.  Examples of this would include CMAC and GMAC; in both cases, if you know the key, it's easy to generate an image that MACs to a specific value.

However, lets assume that you're talking about HMAC specifically (which is a specific type of MAC based on a hash function).

  So, if I used MAC that uses strong key but weak HASH such as MD5. Does this means my MAC does not provide security and can be forged?

Depends on how weak the MAC is.  With MD5, we can easily generate collisions (that is, pairs of images that hash to the same value), however that's not useful in attacking HMAC-MD5 (assuming the attacker doesn't know the key; if he does, he can use that knowledge to create two values that HMAC-MD5 to the same tag).  In fact, there's no known attack against HMAC-MD5 that's more effective than "brute force search of the key".

Please don't use this advice as an excuse to use HMAC-MD5, however.

On the other hand, a sufficiently weak hash (e.g. MD4) does give you a weak HMAC; and so the answer to your question is "yes, a weak hash can give you a weak HMAC"; the hash just has to be weaker than what we know MD5 to be...


AES sub-bytes is defined over the finite field $GF(2^8).$ This field has 256 elements. Its multiplicative group $GF(2^8)^{\ast}$ has 255 elements. In any multiplicative group $a^N=identity$ for all $a$ in the group. This means the multiplicative order of all the group elements (the smallest power they can be raised to and obtain 1) divides $N.$ Here, by definition of AES, $x$ actually has maximal order $N=255$ Thus $x^{255}=1$ and $x^{254}=x^{-1}$ due to its maximal order. Sub-bytes is defined using the inversion $x^{-1}$ if $x\neq 0$ and $x$ if $x=0.$ The formula $x\mapsto x^{254}$ captures both cases.

All functions defined on a finite field can be represented as polynomials. Thus given any input/output table for a function on a finite field, Lagrange interpolation (definition widely available including on Wikipedia) can be used to find the polynomial corresponding to that function, assuming the table representation is a well defined function.


Is it necessary to worry about timing attacks when comparing SHA256 or Argon2 hashes?

Comparing hashes of strings does not fully defeat timing attacks.

For example, if we try to find a password by timing attack of

if (strcmp(sha256str(input),sha256str("honey7dew"))) ...

where sha256str outputs the SHA-256 hash of its input as a 64-char C string in hexadecimal (4 bits per char), and we initially do not know "honey7dew" but suspect that string might be a password with low entropy, we can do the following (assuming we can guess the number of characters matched by strcmp)

let k = "" (the hash prefix known so far)
for each password p in a list of common passwords, by decreasing popularity

let h = sha256str(p)
if h starts with k

submit p as input and find the number n of matching characters
if n is 64, p is the password, stop
set k to the first n characters of h

and it will find the password with only a few hundreds of online submissions (this can be improved significantly by avoiding submission of p that we know are not right, because we previously submitted a p0 with h0 matching h over at least 1 more character than k is).

Update per comment: the attack works just the same if the hash is salted, and the salt known to the attacker (but if there are restrictions to the number of online queries for a given salt, these restrictions might make the attack impractical).
If the hash is entropy-stretching (e.g. Argon2), the attack essentially allows to find the "honey7dew" low-entropy key/password with the same computational cost as if as if its hash was known, replacing that knowledge by a moderate number of online submissions.
If "honey7dew" is replaced by something with high entropy (hopeless to guess), there demonstrably is no attack enabled by timing of the comparison: if there was one, it would break the first preimage resistance of the hash.
If the salt is unknown to the attacker (that's often called pepper) and large enough, it is essentially an extension of the the key/password, and again there demonstrably is no attack enabled by timing of the comparison.


Most lattice based encryption and/or key-exchange algorithms are based on the LWE or Ring-LWE problems. Typically, their security is shown using a reduction to an average-case instance of the (Ring-)LWE problem.

As pg1989 commented, Regev proved a very important hardness theorem for LWE in 2005. Essentially it's a quantum, polynomial-time reduction using an oracle for LWE to solve the approximate SIVP problem (given a lattice, find a full-rank set of lattice vectors where the longest such vector is nearly as short as possible). This is very useful, because it is a worst-case hardness guarantee: as long as some SIVP instances are hard, then a random LWE instance is also hard.

A similar quantum worst-case hardness theorem exists for Ring-LWE to approximate Ideal-SVP (given an ideal lattice, find a vector nearly as short as possible). Note that classical reductions exist as well (at least for LWE), but with some extra restrictions on the parameters.

Both these problems have been intensively studied and appear to be intractable for reasonable approximation factors. IE, you can find exponential approximation factor solutions in polynomial time, or find polynomial approximation factor solutions in exponential time. Quantum algorithm attempts don't fare much better.

Now to answer your question: why are (discrete) Gaussian distributions used? Because (discretized) Gaussian error distributions are assumed in the worst-case hardness theorems that are essential to the security of (Ring-)LWE.

I don't really know if similar theorems are known/possible using other error distributions. My best guess is that the Gaussian nature of the error distribution is essential to the reduction.


Do known-plaintext attacks exist for public key encryption?

Known-plaintext attacks are key-recovery attacks. By design, an asymmetric cipher cannot be susceptible to known-plaintext attacks; it would be completely worthless.

The property you describe that asymmetric ciphers such as textbook RSA lack is called semantic security. Some considerations:

In practice, RSA might be used only to encrypt a randomly generated key for a symmetric encryption algorithm, since encrypting a large message would be very slow with RSA alone. If that key is long enough (e.g., 256 bits), it isn't feasible to launch an attack encrypting every possible plaintext; there are too many of them.
If RSA itself is used to encrypt the message, proper implementations apply some random padding to the message.
Symmetric ciphers do (should) not suffer from this, since you need the secret key to encrypt a message.

Last, it's not possible to enumerate all existing attacks on public-key cryptography. They're different for every cipher and even for different implementations of the same cipher (see blinding).


Is there an application of fully homomorphic encryption scheme such that encryption key and evaluation key are different?

On the literature, these are called 'keyed fully homomorphic encryptions', with three keys: $\mathit{pk}$ is the public encryption key, $\mathit{sk}$ is the secret decryption key, and $\mathit{ek}$ is the secret evaluation key.

Yes, the scenario actually makes sense at least for the cloud computing: there, only the 'cloud provider' needs to do homomorphic evaluation, and there's really no need to extend the capability further.

Rather, I think that it is the other way around: of course we can extend the evaluation capability to anybody, but why do we need to do that?  One reason might be that if the application is not about cloud computing, perhaps there could be reasons that an arbitrary person needs to evaluate ciphertexts homomorphically.  But, there could be many scenarios where the keyed FHE would be fine.

Moreover, for keyed FHE, you can actually define and achieve IND-CCA security: the reason why IND-CCA is impossible for FHE is the malleability, and when the adversary does not have the homomorphic evaluation ability, the attacker can no longer carry out the obvious CCA attack, so to an 'outsider' without $\mathit{ek}$, the scheme can be IND-CCA, but of course to an 'insider' with $\mathit{ek}$, the scheme can be at most IND-CPA.


What's the point of a Meet In The Middle attack using i.e. double AES with throw-away keys?

As mikeazo points out, a meet-in-the-middle (or any other known plaintext attack) against AES is believed to be infeasible; I'll generalize your question to "if we never reuse a key, why do we care about known plaintext attacks?  If the attacker already knew the message, why do we care if he could decrypt it?"

The reason is that the attacker might be able to use that attack even if he has partial information about the plaintext.  For example, suppose that the attacker knew (or guessed) that the text of the message that Alice sent Bob starts off with:

"Hi, Bob!  The password to my bank account is "

In that case, the attacker may be able to use the known partial plaintext to recover the key; if he is able to do that, he can then decrypt the rest of the text, including the bank password.


Does concatinating mutliple digests of hashes from CSRN result in a CSRN?

Yes it most certainly is, on the assumption that the hashing algorithm used is cryptographically secure and uniform in its output.

As a thought experiment, consider that after Elliptic Curve Diffie Hellman, the shared secret's (curve point) x co-ordinate is recommended by good practice to be passed through a hashing algorithm to derive a key.

This is because the shared secret, whilst a random element of the curve generators cyclic subgroup, may not be uniform key material.

Thus, we can trust that good hashing algorithm's will not erode the underlying entropy of an input (beyond truncation), and should provide uniform output.

Thus I would deduce that concatenated hashes of cryptographically secure input should result in a cryptographically secure output of equal entropy to the input (assuming the hash output length is approximately equal to the CSRN input length).


end-to-end encrypted chat app with symmetric + public key encryption, TLS and cert pinning

One problem is that the server is in complete control of authentication and trust, and could easily claim that X has a new key-pair, causing Y to encrypt the symmetric key for a server-controlled key. So at least against some attack scenarios you effectively lack end-to-end encryption.

Another issue is that the use of a long-term symmetric key to directly encrypt the messages means that there is no forward secrecy. If the symmetric key is at any point compromised, all communications between the parties can be decrypted, even those that happened far before.


What is the difference between strong/weak alignment?

Truncated differential cryptanalysis was introduced by Lars R. Knudsen at FSE 1994.

The Keccak team provides an summary of this technique as follows:

  In truncated differential cryptanalysis one divides the function input, output and intermediate computation values in sub-blocks, typically of equal size (e.g. bytes). Whereas in classical differential cryptanalysis one studies propagation of differences that are fully specified, in truncated differential cryptanalysis one only specifies whether a sub-block is active (has a difference) or is passive (has no difference).

It has been applied by J. Daemen and V. Rijmen on AES, the idea is therefore to indicate if a byte has a been modified or not in order to retrieve a distinguisher.

In the case of a strong alignment, the truncated differences can be easily constrained and followed. In the case of a weak alignment, differences spread extremely fast and it makes really hard for a subdivision of the input space to be found.

On Keccak ($\iota \circ \chi \circ \rho \circ \pi \circ \theta$) we ignore the $\iota$ operation as it is irrelevant from a Xor difference point of view. Lets consider a subdivision of 5 bits (due to the size of the somewhat S-box substitution: the $\chi$ function) and assume we have a difference on that group.

We will ignore $\theta$ due to its operation being difficult to visualize, basically, the active difference is spread over the slice and the slice behind  (by $z$ coordinate) in the state.

Then we have $\pi$, if a truncated difference of 5 bit is active then the slice will be set to active.

.

So now we have 5 active truncated difference to track.

Then we have $\rho$, which spreads the differences among the $z-axis$ :

Thus, the active truncated differences are now 25.

In other word, the number of active truncated difference in Keccak increases really quickly $\mathcal{O}(25^n)$. This what we call a weak alignment.


Secure multi-party private set intersectio: Protocols supporting MULTI-party VS supporting TWO-party

I think that you are mixing between the terms "applications" and "implementation", let me explain.

In your question you took some secure two-party computation (2PC) and you showed that when using it in a "black-box" fashion and also each party gets the result of the computation on each pair of the inputs then the protocol leaks a lot of information that should not be leaked. This is true. But it doesn't mean that a secure multi-party computation (MPC) is useless! It just simply means that the protocol that you described (using 2PC) is leaking information and thus it is not secure!.

This multiparty set intersection is INDEED an application for MPC, it is just not implemented as you said but has some designated protocol that implements it (not necessarily through 2PC).

I hope that it clarifies the things.


Why is x^8 + x^4 + x^3 + x + 1 used in AES's Rcon?

The polynomial $x^8+x^4+x^3+x+1$ is the minimal irreducible binary polynomial of degree 8, in the sense that:

it has the smallest possible number of terms for an irreducible binary polynomial of that degree, and
among all the irreducible binary polynomials with the same degree and number of terms, it has the smallest exponents.

In particular, it is the degree-8 polynomial listed in Seroussi's well known table of low-weight binary irreducible polynomials published in 1998, and the first degree-8 polynomial listed in Appendix 2, Table C of Lidl & Niederreiter's Introduction to Finite Fields and Their Applications (1986).  It's quite plausible that the AES authors may have simply looked it up in one of these tables, or in some other similar list.

In any case, the use of such "canonical" minimal polynomials is hardly unusual in crypto.  For example, the GCM mode polynomial $x^{128}+x^7+x^2+x+1$ is also the minimal irreducible polynomial of degree 128, while the Whirlpool polynomial $x^8+x^4+x^3+x^2+1$ (differing from the AES polynomial by the replacement of the $x$ term with $x^2$) is the minimal primitive binary polynomial of degree 8 and is explicitly documented to have been picked from the Lidl & Niederreiter table.


Is there a Pseudo Random Permutation Generator that can output all values of the length of N

Use any true random permutation generator that relies on random input. Then replace the random input with the output of a PRNG primitive.


Is SHA-256 bijective on a certain domain?

Of course it is. If you tightly restrict the input domain, then the problem is simple. The function is deterministic, so just inject clusters of random bits within the input domain of interest (domain $A$).  You then select unique hashes (co-domain $O$) and discard the colliding input/output pairs to create input sub-domain $B \in A$. You will have nullified collisions and will have a bijection as $B \to O$.
Note: We haven't seen collisions on SHA-256 output domains yet, but the above theory holds. And using this brute force approach, the co-domains become more biased towards a bijection as the input domain deceases in cardinality, as $p(\text{bijection}) \propto \frac{1}{|A|}$ through simple computability.
But I'm having a hard time understanding a cryptographic use for such strange domains. I'm unconvinced that sha256inv would actually exist at all as restricting inputs is kinda cheating. And they still only analytically compute one way as $\text{sha256}:B \to O$ which is due to fundamental pre-image resistance. $\text{sha256inv}: O \to B$ remains elusive. And general $\text{sha256inv}: O \to A$ must remain impossible as you've deliberately eliminated collisions which we know mathematically exist.

P.S. $|A|= 916 \times 10^6$, if you consider 5 no. 62 alphanumeric values chosen by total randomness. That's easily computable on an enthusiast's machine.
P.P.S. My last para refers to your comments.


Is double AES-CBC encryption with the same key and IV unsafe?

No, it is not possible.

The encryption step of CBC is $c_i = E(c_{i-1} \oplus p_i)$. When you double encrypt, the previous block ciphertext gets XORed with an independent block cipher output. The only place where something weird could happen is the beginning.

If you assume that the (identical) IV $I$ is prepended to the ciphertext, as is common, you get $I, E(I \oplus p_1), ...$ after the first encryption and then:
$$I, E(I \oplus I) = E(0), E(E(0) \oplus E(I \oplus p_1)), ...$$

This is wasteful, easily detectable due to the encryption of the zero block in every message, but not decryptable by an attacker. If the IV is not prepended, it is even more clearly not an issue. (However, there is no reason to believe it would be a good idea to do this either.)


ECDSA Signing and verifying signatures between Python and JS

An ECDSA signature is, formally, a pair of integers $(r,s)$. There are two main conventions for encoding these integers into bytes:

Encode both integers into unsigned big-endian, using the same size for both, and concatenate the values. This is the traditional way in, for instance, PKCS#11 and OpenPGP; python-ecdsa apparently uses that format.
Encode the integers as an ASN.1/DER structure (a SEQUENCE of two INTEGER values). This is what is normally used in everything that relates to X.509 certificates, and also in SSL/TLS exchanges. jsrsasign apparently uses that format.

Conversion between these formats can be done, but it is surprisingly tricky to do correctly (it's a parser, after all). It seems that python-ecdsa can also encode and decode ASN.1-based signatures (see the functions sigencode_der() and sigdecode_der(), for instance).


How can I avoid calculating with huge numbers when implementing the RSA algorithm

$\def\Z{\mathbb Z}$Usual (i.e. real life) RSA works with huge numbers, not with small numbers like 53 and 26. (The numbers there are, for example, 1024-bit numbers for the lowest acceptable security level nowadays.)

But anyway, the core mathematic operation behind RSA is modular exponentiation - you exponentiate not in the ring of integers $\Z$, but in the modular ring $\Z/_{n·\Z}$ (where $n$ is the modulus). You get the same result by exponentiating in $\Z$ and then reducing, or by reducing after each multiplication step ... and the latter avoids the overhead of really huge numbers.

So, you calculate $c = (…((m · m \bmod n) · m \bmod n ) · … · m \bmod n)$, such that each intermediary result is a number smaller than $n$, instead of calculating the huge number $m^e$ directly.

(This is the naive exponentiation, which takes $e$ steps - there are faster algorithms which only need around $\log_2 e$ steps, like square-and-multiply.)

But your example is faulty, too - the public exponent is normally a number smaller than the modulus (which is a part of the public key, too, and actually the more important part).


For (a), what if you query the signing oracle on $m' \equiv -m \mod N$?  Can you see how to compute $m^d$ given $(-m)^d$?  (Hint: $d$ is odd.)

For (b), try showing that doing this is equivalent to solving the RSA problem.


AES reverse Rijndael key schedule with decryption round keys

Yes, in fact it is quite simple. You are looking at the round subkeys for what is called the equivalent inverse cipher. The decryption round subkeys are generated by performing the InverseMixColumns operation on the encryption round key, the exact same operation used by the decryption function. The code you posted uses a series of byte table lookups (U1 to U4) and XORs to perform the InverseMixColumns operation. Note that the round subkeys are 128-bits or 16 bytes, as that is the size of the block.

In order to convert the decryption round subkey into the encryption one, all you need to do is perform the forward MixColumns operation on the subkeys, except for the first and last round keys, as these are whitening subkeys and are not changed. And of course you need to use them all in reverse order.


Does concatenation of two pair computational indistinguishable distributions still indistinguishable?

If $(X \approx X')$ and $(Y \approx Y')$, then it holds that $(X \times Y) \approx (X' \times Y')$. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$ from $(X' \times Y')$ with probability $1/2+\varepsilon$; the adversary returns $0$ if he estimates that the sample comes from $(X' \times Y')$, and $1$ else. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$. Given access to such an adversary, we construct a distinguisher $D$ for both $(X,X')$ and $(Y,Y')$ as follows:
$D$ asks for a challenge $x$ to the first challenger, which comes from $X$ with probability $1/2$, and from $X'$ with probability $1/2$. Similarly, $D$ asks for a challenge $y$ to the second challenger, which comes from $Y$ with probability $1/2$, and from $Y'$ with probability $1/2$. Then, it sends $(x,y)$ to the adversary, which returns a bit $b$. $D$ simply forward $b$ to both challengers. Note that with probability $1/2$, $x$ and $y$ come from the same side of their pair of distributions (id est, with probability $1/2$ either $(x,y)$ comes from $(X,Y)$ or $(x,y)$ comes from $(X',Y')$). In such a case, the adversary returns the correct guess $b$ with probability $1/2 + \varepsilon$; in the other case, which happens with probability $1/2$ too, the adversary returns the correct guess with probability (at least) $1/2$. Overall, given two challenges $x$ and $y$, and by feeding the pair $(x,y)$ to the adversary, $D$ wins the challenge against both challengers with probability $1/2(1/2 + 1/2+\varepsilon)=1/2+\varepsilon/2$. Hence, up to a factor $2$ in the distinguishing advantage, being able to between $(X,Y)$ and $(X',Y')$ implies being able to distinguish between $X$ and $X'$, as well as between $Y$ and $Y'$.


Over large characteristic fields, I am not aware of any "point generation method" that can be computed faster than a base field exponentiation, and I would be very surprised if such a thing existed even if you do not require constant running time. So your best bet in general is probably Icart's function (I'd pick that one over Elligator if I didn't need injectivity), which won't be fast enough for your purposes.

Over binary and ternary fields, however, it is possible to do better. For example, in the binary field case, you can use the binary Shallue–van de Woestijne encoding, which can be computed with simple base field arithmetic and half-traces, as discussed by Brier et al. in Appendix E of this paper.

Some colleagues and I have an implementation paper that should appear on the IACR ePrint archive shortly, and it computes that function to a 254-bit binary curve in well under 10,000 Haswell cycles, so your goal is easy to achieve on newer CPU architectures (I think recent AMD CPUs should be quite fast as well). Nehalem doesn't have a carry-less multiplier, however, so binary field arithmetic might be quite slow in practice on that architecture.

Incidentally, as this question falls squarely within my research interests, I'm quite curious about your concrete use case if you can say something about it.


Is the same true for HMAC ?

Yes, HMAC outputs are hashes of something so after $2^{n/2}$ you expect two to match.

However, this alone does not help the attacker. The attacker cannot compute the MAC value themselves, so they need to wait for the user to generate that many values. And it does not amount to a forgery attack because the attacker cannot produce a MAC value for any other message than the ones for which they have already seen them.

Even if the attacker had a collision attack on the underlying hash that alone would not help. HMAC is provably secure under some lesser assumptions (second preimage resistance and pseudorandomness, say).

So yes the "birthday paradox" applies to HMAC, but no that does not mean an attack.


Is it an overkill to add external integrity check to the AES-GCM encoding?

Theoretically, there is no issue adding some kind of MAC on top of authenticated encryption's builtin. However, in practice there might be subtle flaws with composing the particular primitives you're using, or you may make an implementation flaw that renders them both vulnerable to a side-channel attack that didn't exist previously. Ultimately, it's best to stay away from getting creative with protocol design - just use the best-known implementation of the best-known primitive for the job.


Power analysis and exponentiation by squaring

You can begin by first reading the seminal paper of Paul Kocher. He gave the reference for Timing and Power analysis attacks. The best is to read the papers, and understand the philosophy of Side Chanel Attacks.
The method he described, has been enhanced by many authors, and it become impossible to ignore how to securelly implement algorithm on embedded systems.
After that the most destructive attacks is the one introduced by Dan Boneh known as the "Faults Attack".


A block cipher is any cipher that works(encrypts, decrypts) on data in blocks (more than just one bit or one byte). A stream cipher is a cipher that works on the data one bit or byte at a time.

For example, DES is a block cipher because it works on the data in 64 bit chunks. This means that when you want to encrypt something with DES, you must first break it into 64 bit chunks, and encrypt each chunk with DES. Same with decryption.

An example of a stream cipher is RC4. If you want to encrypt using RC4, you need to encrypt each byte individually. There is no need to create chunks of that data, because RC4 works on the data one bit at a time.

You cannot choose a blocksize, because it's generally dictated by the algorithm you choose. How you send the data is not related to how you encrypt the data. That means a block cipher only says that you need to encrypt in a block, but says nothing about how you should transmit the data.


Why do key exchange protocols need secure clock synchronization?

Kerberos requires synchronised clocks mainly to ensure the messages are fresh and to thwart replay attacks. The messages include timestamps so that those with outdated timestamps (e.g. more than 5 minutes) will be thrown away (although there is still a time window in which replay is possible).

Many key exchange protocols don't use timestamps because clock synchronisation is often problematic and difficult. Nonce based based challenge response is used instead to prevent replay attacks.


You then take $T$ and left shift it one bit. If the carry from that operation is a 1, then you XOR in 0x87 on the bottom byte. That becomes the pre- and post-crypto XOR material for the next block and so on.

What's going on here is a finite field multiplication in the field $GF(2^{128})$, modulo the irreducible polynomial $x^{128} + x^7 + x^2 + x + 1$; if you look closely at the exponents of last four terms of that polynomial, they correspond to the positions of the one bits in 0b10000111 = 0x87.  This shift-and-conditional-XOR trick is a cheap way of "doubling" a binary string in $GF(2^{128})$, i.e., multiplying it by the polynomial $x$, whose binary representation is the numeral for two.  So sometimes you see the exact same thing notated as $2^n \cdot E_k(0)$, where the dot denotes multiplication in whichever finite field has been fixed for that context.


There is an obvious problem with your solution; it allows cheating during the reveal.

Here's how it'd work; suppose Alice's favorite movies are Avatar and Titanic.  She assigns a random number 19 to Avatar (along with Commit(Avatar)) and 28 (and Commit(Titanic)) to Titanic.  She passes them to Bob, who assigns 42 to 19 (which was originally Avatar), and 37 to 28 (which was original Titanic).  Note that he can't include Alice's commitments, otherwise Alice would know which card was which.  So, Bob publishes 37 and 42 (in some order).

Now, it comes time to reveal 42.  We ask Bob what 42 originally stood for; Bob is supposed to answer 19 (and Commit(Avatar)); however, there's nothing stopping him from answering 28 (and Commit(Titanic)); only he knows the mapping, and it's not detectable if he changes his mind.

The obvious solution is to make Bob do commitments as well.  That is, Alice sends Commit_A(Avatar) and Commit_A(Titanic) (the random numbers really don't do anything that the commitments themselves don't); Bob then publishes Commit_B(Commit_A(Avatar)) and Commit_B(Commit_A(Titanic)) in some order; when it comes time to reveal a card, we send Commit_B(Commit_A(Avatar)) to Bob, which opens his commitment (and publishes the random number he used, so others can confirm it), and then sends the Commit_A(Avatar) to Alice, which reveals the original Avator (and, again, she publishes her random number so others can again confirm it).

It generalizes in the obvious way if Carol and Dave also want to play.  However, one problem with it (and it's really a problem with the problem statement, not the protocol) is that if Dave decides to quit (either because his computer crashed, or if he is just feeling ornery), then we can't reveal any of the cards.  A more sophisticated protocol can be designed that will allow any M of the N parties to reveal a card; however, this is going to be a lot more complicated.


How does certificate-based encryption solve key revocation problem?

The revocation status of a certificate is application dependent, meaning that if the application under which you perform the encryption or decryption does not check for revocation status with the CA, then you may still proceed and encrypt or decrypt the message.
You should consider the loss of a private key of a certificate as a loss of your password in a symmetric encryption environment. The same argument applies to PKE.

The same applies to a signature verifications: a well behaved program should check the revocation list when verifying a signature, but this depends on the application developer interests. I can verify a signature as a valid one in certain programs without consulting a revocation list at all.
You can easily test this, for example, by checking on a signed windows program on a computer that is not connected to the internet (look at the Digital Signature tab in the Properties pop-up dialog box of a signed executible): The digital signature of the program would be reported as OK (if indeed nobody messed with its bits) even though the revocation list has not been consulted.


Yuval's attack is slightly different from the standard birthday attack where we look for a repeated output in a single family of inputs. Instead we look for a repeated output across two families of inputs with at least one member of each family producing the repeated ouput. The probabilities are slightly different, but in a complexity sense are both $O(\sqrt H)$ for output ranges of size $H$ (or $O(2^{m/2})$ for $m$-bit output values) where in the worst case outputs are approximately uniformly distributed.
One can see this in an approximate sense as generating $n$-outputs in each family creates $n^2$ pairs of values with one half of each pair coming from each family. Each pair has a $1/H$ chance of matching the two halves. We can approximate the chance of finding a repeat as
$$1-\left(1-\frac1H\right)^{n^2}$$
and for $n\sim\sqrt H$ this will be about $(1-1/e)$. Note however that this is not a rigorous estimate as the probabilities are not independent. More rigorous derivations are possible (see Girault et al., Eurocrypt '88).


Can AES-NI be used to accelerate asymmetric encryption?

These are the AES-NI instructions listed by wikipedia:

AESENC:   Perform one round of an AES encryption flow
AESENCLAST:   Perform the last round of an AES encryption flow
AESDEC:   Perform one round of an AES decryption flow
AESDECLAST:   Perform the last round of an AES decryption flow
AESKEYGENASSIST:  Assist in AES round key generation
AESIMC:   Assist in AES Inverse Mix Columns
PCLMULQDQ:    Carryless multiply (CLMUL)

If the asymmetric crypo in question were to use any of these operations, then yes, it could be accelerated by the appropriate hardware instruction.

However, standard asymmetric primitives such as RSA and Diffie-Hellman do not use these sorts of operations. Without knowing specifically what asymmetric algorithm you had in mind, we can conclude the answer is probably "No".


Is it possible to find two sets such that their hash xor summation is the same?

As for the feasibility of finding such a colliding set, well, as long as the sets are allowed to be relatively long (e.g. at least as long as it bit values being xor'ed), then it is easy.

First off, we assume that the hash output is $n$ bits.  Then, we select $n+1$ distinct values $X_i$ and set $\delta_i = Hash(X_i)$.  Then, we use linear algebra to find a subset of the values $\{ \delta_1, \delta_2, ..., \delta_n \}$ that xor to $\delta_0$ (note, there is a probability that there won't be such a subset; that probability can be minimized by including a few extra values).

With such a subset $\{ \delta_{z_0}, \delta_{z_1}, ..., \delta_{z_k} \}$, we have $$Hash(X_0) = Hash(X_{z_0}) \oplus Hash(X_{z_1}) \oplus ... \oplus Hash(X_{z_k})$$

That is, the sets $\{ X_0 \}$ and $\{X_{z_0}, X_{z_1}, ..., X_{z_k} \}$ collide


Efficient and stateless anti-forgery method

If you don't want to store the anti-CSRF tokens on the server, for most purposes it is sufficient to simply store the token as an HTTP cookie on the client.  The OWASP wiki calls this technique "Double Submit Cookies".

The reason this works is that, in the standard CSRF attack scenarios, the attacker cannot directly read or modify the user's cookies.  Indeed, if the user's authentication credentials are also stored in cookies (as is very commonly done in modern web applications), any leak of cookie data already implies a much more fundamental security failure than a mere CSRF attack.

Of course, an attacker might be able to gain (full or partial) access to the user's cookies via an XSS or other injection attack or through session fixation, but this is mostly outside the scope of CSRF prevention and must be addressed by other means.  (One exception to this are login CSRF attacks, which can be used to carry out session fixation; the solution there is to ensure that authentication entry points are also protected with anti-CSRF tokens.)

One possible improvement on the basic Double Submit Cookie technique I might suggest would be to let the anti-CSRF token included in the submitted form data be derived from the cookie value using a secure MAC (such as HMAC) with a secret key stored on the server.  This has a few advantages over simply using the plain cookie value as the token:

Merely learning (or guessing) the cookie will not allow an attacker to mount a CSRF attack, since they won't be able to derive the token from the cookie without knowing the key.
Conversely, leaking the token will not allow an attacker to reconstruct the cookie; in particular, this means that the user's normal authentication credentials may be safely used to derive the anti-CSRF token, without need for a separate cookie.
By including additional data, such as a form identifier and/or a timestamp, in the MAC input, the token can be made specific to that additional data.  This can compartmentalize the attack surface e.g. by ensuring that an attacker who learns the token for one form will not be able to attack another form in the same application, and that they will be able to carry out attacks only for a limited time.

Edit: Something I forgot to clearly mention in my original answer is that, if you derive the anti-CSRF token using a MAC, you don't necessarily need a cookie at all — all you need is something that is unique to the user.  If you're using cookie-based authentication, using the user's session ID / auth token as the MAC input is a natural choice, but in principle you might as well use e.g. the username instead.

Of course, it's desirable for anti-CSRF tokens to be short-lived, so if you're using a long-term stable value, such as the user name or ID, as the MAC input, I'd very much recommend combining it with a timestamp.  Otherwise each user would be tied to a single token value, such that leaking the token would make the account permanently insecure.  A convenient trick, if you don't want to include explicit timestamps in your forms, is to take some value that changes, say, hourly (e.g. the Unix timestamp divided by 3600), include that in the MAC calculation, and accept any tokens that match the MAC for the current or the previous value.

OK, I guess I should describe the MAC-based scheme explicitly, since it really doesn't bear very much resemblance to the original Double Submit Cookie scheme any more.

Let:

$K$ be a secret key known only to the server (guard this well, and change it if you have any reason to suspect it might have leaked),
$\operatorname{MAC}_K$ be a secure Message Authentication Code (e.g. HMAC) with the key $K$,
$U$ be a unique per-user (or per-session) value which may or may not be public, such as a session ID, a username, etc.,
$S$ be a timestamp of appropriate granularity (either explicitly included in the form data, or implicitly included using the trick described above),
$F$ be an (optional) form / action identifier, and
$D$ be some (optional) extra data included in the form (or used to constrain the form and reconstructible on submission, such as a list of allowed choices in a menu) that you want to protect against modification.

When creating a form, calculate the anti-CSRF token $T$ as $$T = \operatorname{MAC}_K([U, S, F, D])$$ where $[U, S, F, D]$ denotes a string uniquely encoding the tuple $U$, $S$, $F$, $D$.  Include $T$ (and $S$, if not using the timestamp trick described above) as a hidden field in the form.  (If you have plain links that need CSRF protection, you can use the same method; in that case, it's often perfectly reasonable to use the entire URL — excluding the token, of course — as $D$.)

When you receive a form submission, first check that the user is properly authenticated and that the timestamp in the form (if any) is not too old.  If those checks pass, recalculate $$T' = \operatorname{MAC}_K([U, S, F, D])$$ and compare it to the token $T$ included in the submitted form, accepting the submission only if they match.  (If using the implicit timestamp trick, you should also calculate $$T'' = \operatorname{MAC}_K([U, S-1, F, D])$$ and accept the form if either $T = T'$ or $T = T''$.)

Of course, a clever user will notice that there's nothing special about the $F$ and $D$ values in the MAC calculation — they're just arbitrary inputs that, if changed, change the MAC value in a way which, as long as the MAC is secure, an attacker cannot predict without knowing $K$.  You may also notice that the optional inclusion of the extra data $D$ in the MAC calculation makes this technique more powerful than just a classic anti-CSRF token, since it can prevent certain attacks (namely, those involving modification of $D$) even if the attacker has access to the entire form, including the token $T$.  I included this feature in the spec above since it can sometimes be useful, and since we get it essentially for free, at no extra cost in complexity.  Of course, you don't have to use it if you don't want to.

Note: Ensuring that an attacker cannot recover $U$ even if they learn $T$ requires the MAC function to satisfy some additional security properties beyond the standard ones (resistance to existential forgery) demanded of such functions.  However, in practice, most secure MACs (such as HMAC instantiated with a preimage resistant hash function) do have the necessary properties, and in any case, the standard CSRF attack model assumes that the attacker cannot learn $T$.  Still, if you're really paranoid, you may want to choose $U$ such that leaking it will not compromise security.


With the extra information you've provided, there are $4^{\left\lfloor \frac{n^2}{4} \right\rfloor}$ possible grilles to consider.

Specifically, consider an $n \times n$ grille with just one hole, and make a mark on the paper through that hole with the grille in each orientation.  If you do that, you'll see that there will always be exactly four marked positions on the paper, placed symmetrically around the center (unless $n$ is odd and the hole is in the middle of the grille, in which case all marks will be in the same position).

Clearly, with the grille in its original orientation, exactly one of these four positions must have a hole: if two or more of them had holes, the same letters would show through all of them, and if none of them had holes, the letters in those positions would not be visible in any orientation (contradicting the claim that the plaintext has $n^2$ letters).

(Incidentally, if the requirement that no letters are visible in more than one orientation is taken strictly, it means that the center position cannot have a hole for odd $n$, meaning that the plaintext length for odd $n$ can be at most $n^2-1$.  So we must either relax one of the requirements or rule out odd $n$.)

Each grille has $n^2$ positions (including the center position for odd $n$) and thus $\left\lfloor \frac{n^2}{4} \right\rfloor$ of these 4-position cycles.  (The floor is there for odd $n$; if $n$ in even, $n^2$ is divisible by 4.)  Assuming maximal plaintext length, each of these cycles must contain a hole (and, as shown above, cannot contain more than one hole).

By symmetry, each of these holes can be in any of the four positions within their respective cycle.  Thus, we have $\left\lfloor \frac{n^2}{4} \right\rfloor$ independent choices, with four options for each choices, giving us a total of $4^{\left\lfloor \frac{n^2}{4} \right\rfloor}$ possible sets of choices.


I have created values for RSA encryption but it doesn't always work

Your message has to be smaller than n to be correctly encrypted / decrypted with RSA.