How can I verify a client's identity by requesting a digital certificate?

Ok, I'll assume you have collected the data from the form. The next step is to confirm the user's identities based on the certificates they have. For this you have two options:

Send a S/MIME signed email to you which includes a chosen-by-you challenge in the message body. For this you could randomly generate a new email adress for each user so you can distinguish them if two happen to share some information. Also make sure that this random email address is in the message body because only that gets signed. Once you receive the email, you verify the certificate signatures, verify the root CA and the intermediates, verify the signature on the mail and verify the information in the certificat against what you had on the form for this specific person. If everything passes this person is confirmed. This assumes the user can use their certificate for e-mail signing.
Run a TLS client authentication. For this you'd give each user a random link when he has completed the form. Next he opens that link, the web-server will trigger a TLS client authentication and the TLS protocol will verify that the user has a) access to the private key of the certificate, b) will take care of all the signature verifications and whatnot and c) will verify that the cert chains up to a trusted root that you explicitely set up to accept for the client authentication. Following that your application-layer should get access to the client certificate information from your TLS implementation and need to verify that all the fields in the certificate match with the expected values from the form. This assumes the user's certificate is configured to be used with the browser which is (usually?) less common.

  So how do I then use this file to verify that the certificate is
  valid?

You don't without interaction. The certificate was issued to the holder of the private key associated with the public key in the certificate. This person is guaranteed to be the person from the certificate. If you just have the certificate you don't know that the person uploading it is in possesion of the secret key and thus you don't know whether this is indeed the "legitimate owner" of the certificate, thus you need one of the above approaches (which both shouldn't be too hard to implement).


Serpent intermediate rounds differs from example code, but result is still correct, is it a problem?

To check if it is a bitslice issue, we can look at a round output, this is round 1 from the example:

0000 0101 1111 1001 1111 1110 0101 1101 0101 0001 1010 0011 1011 1101 1111 1111 1001 1111 0000 1101 1110 1010 1100 0111 1010 1010 0111 0110 0011 0010 1010 1110

And yours:

0011 1101 0010 1111 1101 1110 1100 0011 0110 1111 1000 0111 0101 1011 0011 0001 0010 1100 0011 1011 0100 1101 1111 1111 0111 1011 1101 1111 1101 0001 0010 1000

To check for bitslicing, start selecting every 4th bit in one of them (starting at 0), then compare it to the first 32-bit word of the other

As we can see, every 4th bit of the example does indeed match the first 32-bits of your output. I also spot checked the final 16 bits which also match. I suspect that if you keep going with that round, all bits match, as would the rest of the rounds. A rapid way to check if that is probably the case is to convert to binary then use an iterative counter to count the number of 1 bits per round.


Given a set of numbers which return a response code, how can I find the algorithm used to produce the response?

There is demonstrably no general solution to this class of problems. Argument: we can construct the output as a Message Authentication Code (e.g. HMAC) of the other inputs, with a random secret fixed key; and what's asked is breaking the MAC.
This class of problems is not modern academic cryptography, which assumes the algorithms are known, only the keys are secret. That's per Kerckhoffs's principle (or really, the modern reading of his second principle) .
However, sometime it is possible to solve such problem:

When the program that produces the output is available, it can be reverse-engineered¹ (de-compiled, or/and observed running in a debugger). That's often how software copy-protection is broken.
When the device that produces the output is available, telltale signs of what it does internally might leak and allow a side-channel attack.
For some classes of algorithms, including CRCs, there are general attack techniques given a number of input/output pairs.

¹ If the algorithm is simple enough. It is possible to make a program that implements a function in essentially the shortest possible way, by using it's own code as key. This program is the canonical form of the algorithm. It can sill be ported to another CPU, with enough memory.


Generating a random number using a quantum computer

Yes, it is possible to use quantum computer as a true random number generator, by applying Hadamard gates to all available qubits in initial $|0\rangle$ state and measuring them in the standard basis; but this is inefficient way of generating random numbers because quantum computer requires time to cool down its qubits to the initial state before starting a new computation.

There are other cheaper and faster methods of generating random numbers using quantum effects, see for example ANU Quantum Random Numbers Server


I would have posted this as a comment if I could:
Please re-read the entire article that you have linked to.
All that was done was a brute force attack.

The reason brute force was possible was because the missing password was narrowed down to "about 22472" different possibilities.
And that 22000 was tried by a computer dedicated to doing such calculations.

This shows nothing about the security of the encryption scheme, only that when you know almost all of a password and have the means to try all possibilities efficiently, you can brute force it successfully.


Post processing of AAD and len A||C in a hardware AES GCM implementation

BouncyCastle (for Java) has code that performs the AAD processing anywhere in the stream. It does however require modular exponentiation and additional multiplication. GCM mode officially requires the AAD to be processed before the plaintext, but as stated, there is a way around that. I've asked for an explanation here

Len A||C is only required at the end of the processing anyway, so that should not pose a problem.


What quality would an interactive proof executed many times sequentially have that makes it zero knowledge that one executed in parallel would not?

Hint: look at the security proof of the zero-knowledge property of the first scheme. I recommend writing it fully and formally, if you want the solution to become clear. It relies on a common "rewinding" strategy, and requires in particular to guess in advance the challenge of the verifier, with non-negligible probability. Now, what happens to this strategy when we consider parallel repetitions instead? Can you see where exactly it breaks down? We can give you further hints if you explain exactly what you tried and tell us where you are stuck afterward.


When is each key used when encrypting an email using OpenPGP?

Let Alice have a key pair (PubKeyA, PrivKeyA), where the first is public, the second private,
and similarly for Bob (PubKeyB, PrivKeyB). Alice and Bob know each other's public keys in a reliable way (from a key server, or because they received them in person etc.)
If we use RSA keys, e.g., then they could use just one pair, so I'll assume this first.

When Alice sends Bob a signed message (signing is optional in PGP, but good practice), the following happens, simplified:

Alice generates a key K for some symmetric cipher algorithm, say AES (i.e. the program does, using a good random number generator, etc.)
Alice encrypts the message M using K, to get AES-Enc(M,K).
Alice encrypts K using PubkeyB, to get RSA-Enc(K, PubKeyB).
The 2 parts RSA-Enc(K, PubKeyB) and AES-Enc(M) are combined in an unambiguous way (so they can be split later) into an encrypted message M' = Enc(M, K, PubKeyB).
Alice uses her PrivKeyA to cryptographically sign M' (which mostly means hashing M' and "encrypting" the result with that private key, in the case of RSA), which gives us Sign(M',PrivKeyA)
Enc(M, K, PubKeyB) and Sign(M',PrivKeyA) are combined in an unambiguous way into the message that Alice sends.

Note that we need a secure mode of operation to AES to encrypt M using K, a secure way to encrypt the key K using PubKeyB (using a secure padding scheme, like OAEP), a secure hash function and way to sign (also using a padding scheme) and a good file format to unambiguously pack all the data in. Read up on the standards involving them...

Bob does the following (simplified) when he receives the message:

Split the message into M' = Enc(M, K, PubKeyB) and Sign(M', PrivKeyA).
Check, using PubKeyA, that Sign(M', PrivKeyA) is a valid signature for M'. Stop if that fails. If it succeeds Bob is confident that M' is intact and indeed sent by Alice.
Then split M' into RSA-Enc(K, PubKeyB) and AES-Enc(M).
Using his PrivKeyB, decrypt K from RSA-Enc(K, PubKeyB) and PrivKeyB.
Using K, decrypt M from AES-Enc(M) and K.

Now Bob has M too, and is confident it is the actual message Alice wanted to send, and was not tempered with in transit.

Like I said, the devil is in the details, but this is the essence of it.

Now, in practice, PGP creates 2 pairs per user, an encryption pair and a signing pair. Also the programs sends key-identifiers with the message to indicate which ones are used (in general, a user could have more public keys etc.)


Perfect Forward Secrecy with Pre-shared Key

A possible deficiency is that if the use made of any $K_j$ allows it to leak, all later security is lost. That makes $K_j$ plain unsuitable in some uses, e.g. directly as keystream for short messages.

The $K_j$ must be wide enough that it is extremely unlikely that a cycle is ever reached in deriving them. For plausible parameters that translates to $n^2<2\cdot|K_j|\cdot\epsilon$, where $\epsilon$ is a small acceptable residual risk, and $|K_j|$ is the bit width of $K_j$. If $K_j$ was a 128-bit key, with 100 keys per microsecond for a decade, I get $\epsilon\approx2^{-19.4}$. That could be a problem when some requirement prescribes a very low $\epsilon$, like $2^{-40}$.

The above two can be solved with a wide key (and hash), derived into a working key (perhaps shorter) using a Key Derivation Function such as HKDF or one of these, preferably not using the same hash function as the one used to derive the $K_j$.

Another: if the adversary can only test a candidate key $K_j$ at relatively high cost $C_0$, and in some conceivable uses of $K_j$ like encryption of a known constant block, an adversary trying brute force and for which hashing has much cheapest cost $C_1$ gains an enormous speed boost from how the $K_j$ are derived; something like $\mathcal O(\min(n,C_0/C_1))$, neglecting cost of a memory fetch per hash. That can be solved by using, in order to derive $K_{j+1}$ from $K_j$, instead of a hash, a slow key-stretching function, such as scrypt or the lesser PBKDF2, with cost parameter(s) such that $C_1\approx C_0$.

Last one that immediately comes to my mind: the receiver must forget the current $K_j$ only after validating the next one, or some later one if lost messages are part of the assumptions. And in the later case it is probably a good idea to limit the number of consecutive messages that can be skipped, else there is a trivial Denial of Service Attack.


What is the canonical way of creating Merkle tree branches?

If you have the index of the leaf, it describes the path from it to the root.

Specifically, the binary representation is a series of left (0) and right (1) turns from the root. If you're working your way up, the least significant bit says if the leaf is a left (0) or right (1) child, the next bit refers to the leaf's parent, etc.

This illustration makes it obvious:

The numbers on each node are the binary representation of that node's index in its layer.

So just listing the index of the leaf whose membership is being proven provides enough information to validate the proof.

Here's some simple pseudocode for validating a proof:

func isValidProof(leaf, index, nodes, root):
  currentNode = leaf
  for node in nodes:
    if index mod 2 == 0:
      currentNode = hash(currentNode, node)
    else:
      currentNode = hash(node, currentNode)
    index = index >> 1 // shift 1 right is essentially like dividing by 2, ignoring the remainder
  return currentNode == root


I found a few for shuffles.
The papers below will be good pointers for recent results.

Stephanie Bayer and Jens Groth: Efficient Zero-Knowledge Argument for Correctness of a Shuffle. EUROCRYPT 2012.
Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn: Verifiable Elections That Scale for Free. PKC 2013.
Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn: Succinct Malleable NIZKs and an Application to Compact Shuffles. TCC 2013.


How many computations does it take to figure out the input if you know the function and you know its output to another known function?

What you are describing here is attacking a password. The very definition of a cryptographic hashing function includes resistance to preimages. If you are given hash(x), it should be impossible to recover x. So not a lot of the information you state here will help you recover the preimage.

However, what you are touching on is brute forcing attacks. In that case you would take preimage X and perform hash(X) to determine if hash(X)==ExpectedHash. You do this for every possible combination that X could be until they are in fact equal. Then you do this for each hash.

As for how many computations would be required. That is a function of entropy. For example, the required information:

how many bits are required [min-max]
what is the maximum possible combination on each byte
is there any known space

and yes this problem would rise exponentially. say I have a password that can only consist of 0 or 1. That means I have 2 possible combinations for any position of my password. However adding an additional character to the password means that there are 4 possible combinations now, 00, 01, 10, 11. For each additional character I add adds more combinations in the form of 2^n. For very large bit counts this problem becomes extreme (which is kind of the point really). The end result of computations would be:

[# of computations per hash function of one preimage and compare]*[2^n]=[# of computations required]

Where n is the length of the password. This problem is even worse if you don't know the length of the password.

Some things you can do:

If you know certain things about the preimage you can reduce the number of calculations required. In your example you mentioned per-appending 0s. Well it might help, but only if it means you always know the length of the preimage. In that case it helps and in no other way (you cant say for sure how many 0's are in the image, and where they are). All you have done is said "there is no less number of bits than this, and no more" reducing the problem to a certain number of bits per preimage. Otherwise you would also have to try each combination from [0] all the way to [111111111...n]. The only thing you could do is say, I know that there are this many bits in the preimage. so only 2^n combinations. Now start from 0 and pre-append 0s from the last bit to the first. This would be the best method for this. But still require at maximum the number of computations listed earlier. Since you don't know if any 0s at all were pre-appended.

So to sum it up, Yes it can help, but in reality only in reducing the problem to one exponent. I don't think you can get lower than that without something really clever. Hope this helps!


Timing Attacks on ECDSA, ECDHE, AES and SHA2

The attack which you link to, on ECDSA, is related to the following: the signer computes several values $kG$, for random $k$ values chosen uniformly modulo $n$ ($n$ is the size of the subgroup generated by $G$). One such value is generated for each signature. It is important that the selection is uniform: even small biases can be exploited in order to make a key recovery attack. The crucial point is that each ECDSA signature consists in a pair $(r,s)$ where $s = (m+xr)/k \pmod n$ where $m$ is known (it is the hash of the signed message). Each signature involves a new $k$, thus a new $r$ (because $r$ is obtained from $kG$); the $r$ value follow a definite distribution modulo $n$. So if $k$ are biased, then the bias easily turns into an information leak on $x$ (the private key). As an extreme case, if a $k$ value is reused, then the two corresponding signatures suffice to recompute $x$ directly (this is what happened to Sony with their PS3 firmware signature system).

In the OpenSSL implementation of $kG$ on binary curves (using a variant of Montgomery's ladder), it so happens that the code was "optimizing" things by making $\lceil\log k\rceil$ iterations only; so that if $k$ was shorter than $n$ by, say, 3 bits (happens once every eight signatures or so) then the loop was slightly faster (3 less iterations). The attacker can detect that. If the attacker can make the target generate signatures on messages that the attacker knows (that's easy when the target is a SSL server; the attacker just has to connect), then the attacker can keep a subset of the signatures, precisely those where $k$ was "short". This becomes equivalent to a biased $k$ generation, and leads to private key reconstruction.

I describe this to show the important point: it is not specific to elliptic curves over binary fields. In fact, it is not specific to elliptic curves. A classic square-and-multiply implementation of a modular exponentiation for plain DSA could be equally vulnerable. Elliptic curves (in prime fields or binary fields) are not especially weak or strong in that matter. It is best described as a weakness of DSA (and variants, including ElGamal signatures and Schnorr signatures). To protect against it, the implementation must take care to take a constant time in all cases, so as not to leak information on $k$.

It seems unlikely that ECDH would suffer from a similar issue. With ECDH, leaking information about the private key length seems benign enough. The problem with DSA arises from leaking bias information on a value $k$ which is used along with the private key $x$ in "simple" operations (multiplication and division modulo a prime). Diffie-Hellman, be it modulo a prime or on an elliptic curve, does not feature such "simple operations" involving a randomly selected value and a permanent private key.

Moreover, in the case of ECDHE, the final "E" means ephemeral, which more or less implies that the DH private key will not live long. SSL/TLS server may reuse the same DH private key for a few connections (as long as the private key is kept in RAM only, it fulfills the "ephemeral" contract), but normal SSL/TLS servers tend not to do that much. Generating a new DH private key is efficient. This correspondingly severely limits the power of the attacker: timing attacks are statistical in nature, which means that they need to work over several measures which involve the same secret value. With ephemeral DH keys, the private keys can be regenerated often enough to defeat timing attacks in a quite generic way.

For AES, timing attacks are again based on implementation characteristics. Specifically, "normal" AES implementations use lookup tables, and thus exercise caches. The attack will work either on evicting parts of these tables from cache and then measuring the algorithm execution time (thus counting the number of cache misses involved during the execution), or on having the attacker's data evicted from cache when the AES block cipher runs, and then working out (again with timings) which parts of the data were impacted. In both cases, this allows the attacker to gain some information on the intermediate values used in the algorithm, leaking information on the key.

The attack is quite feasible when the attacker can run his own code on the same machine, so as to use the same caches (this is a setup which applies to traditional multi-user mainframes, but also to virtual machines, where one VM may spy on another). For a remote attacker, this has also been demonstrated in lab conditions, but then it depends on a lot of parameters, and the remoteness makes execution time harder to measure with high precision; applicability to any specific real-life situation is hard to assess.

There are table-free AES implementations (see this question) but they use specific CPU features, or are quite slower, or both. Recent x86 CPU have an hardware AES which is very fast, and immune to such timing attacks.

SHA-2 is a family of hash functions. As such, they don't have keys. If they contain no secret, then there is nothing to obtain through timing attacks...

A hash function may be used on secret data, though, in particular in HMAC. SHA-2 is all arithmetic operations, no tables, no data-dependent branches. It seems hard to make a SHA-2 implementation which would be susceptible to timing attacks.


Solving discrete log in partially known group

Pohlig–Hellman algorithm can't be used as is, but it can be modified to make use of known partial factorization of $n$. Suppose that you need to find such $x$ that $g^x=h$. This can be done as follows:

Choose small $k'$ such that $k'\ge k$. If the upper bound on $n$ is $n'$, then $k'=\lfloor\log_pn'\rfloor$ can be used.
Set $g'=g^{p^{k'}}$ and $h'=h^{p^{k'}}$. Now, the orders of $g'$ and $h'$ divide $s$.
Use baby-step giant-step algorithm to find discrete logarithm of $h'$ to the base $g'$. If a good upper bound on $s$ is not known, it is possible to run the algorithm multiple times with exponentially increasing upper bound.
Similarly, use baby-step giant-step algorithm to find $s$, for example, by finding discrete logarithm of $(g')^{-1}$ to the base $g'$. If $g$ is not a generator, you may find a value $s'$ different than $s$ (but it will divide $s$). In this case, $g$ lies in a subgroup of size $p^ks'$, so you may just assume that this subgroup is the whole group.
Then, use Pohlig–Hellman algorithm to find discrete logarithm of $h^s$ to the base $g^s$. Both elements are in the subgroup of size $p^k$.
Use Chinese remainder theorem to find the logarithm of $h$ to the base $g$.

To find $k$, first use the above algorithm to find $s$. Then, if you have a generator $g$, find the smallest $k$ such that $g^{p^ks}=e$, where $e$ is a neutral element. If there is no known generator, it is possible to use multiple random elements instead to make the probability of finding the correct $k$ arbitrarily close to $1$. There is no deterministic algorithm that works with arbitrary groups when no generator is known, because it is possible that all known elements will lie in the subgroup of size $p^{k-1}s$, so it will be impossible to tell that the real size is not $p^{k-1}s$ but actually $p^ks$.


Creating own ciphertext after a padding oracle attack?

You should be able to generate a ciphertext for any given plaintext using a padding oracle attack if you are using CBC mode. You'll need to be able to  modify the IV though for it to fully work.

This is because every time you scramble an earlier block, you can just fix it by modifying the cipertext for the block before that (or the IV for the first block). If you can't modify the IV you are stuck with being able to modify all blocks except for the first (and the first one will become garbage).

The idea is to start from the end, and create a random ciphertext block $C_n$ (this can be fully random, a set of zeros, or any particular value you desire). When you then use the padding oracle attack against this block, you'll receive the decrypted value of this block: $\operatorname{Dec}(C_n)$ (as that is what the padding oracle can do for you: decrypt any ciphertext you pass into it, no matter whether it's valid or not).

Note, that $\operatorname{Dec}(C_n)$ will be garbage, but, since you are using CBC mode you can modify the preceding block $C_{n-1}$ in a way so it will actually XOR $\operatorname{Dec}(C_n)$ to your chosen plaintext $P_n$: $C_{n-1} := \operatorname{Dec}(C_n) \oplus P_n$.

Once you're done, continue the steps. You already know $C_{n-1}$, calculate $\operatorname{Dec}(C_{n-1})$ using the oracle, and then set $C_{n-2}$ so the CBC mode will XOR it into $P_{n-1}$, etc.

The only problem is with the first block. If you have access to set the $IV$ then it's not a problem, you just make sure the $IV$ is set to a value so it will XOR $\operatorname{Dec}(C_1)$ into $P_1$. Otherwise you are stuck, and you have to keep the first block as garbage.

See also https://crypto.stackexchange.com/a/50027/34606


Concerning $(k_1, k_2, k_1)$ vs. $(k_1, k_1, k_2)$

$(k_1, k_1, k_2)$ can be split into $(k_1, k_1)$ with $2^{56}$ possibilities and $(k_2)$ with $2^{56}$ possibilities, so the meet-in-the-middle attack has cost $2^{56}$.

$(k_1, k_2, k_1)$ can be split into $(k_1, k_2)$ with $2^{112}$ possibilities and $(k_2)$ with $2^{56}$ possibilities or into $(k_1)$ with $2^{56}$ possibilities and $(k_2, k_1)$ with $2^{112}$, so no matter how you split it, the attack costs $2^{112}$.

=> $(k_1, k_2, k_1)$ is much stronger than $(k_1, k_1, k_2)$

Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?

Concerning EDE vs EED

Choosing encryption vs. decryption for the three steps has no effect on security.

By setting all keys to the same value you can emulate DES using 3DES with EDE and EED but not with EEE. Not sure if EDE offers any advantages over EED, except looking nicer due to being symmetric.

Why do we use encrypt-decrypt-encrypt (EDE) in 3DES, rather than encrypting three times?

Encryption-Decryption-Encryption


Are there any LFSR-based ciphers with variable feedback polynomials?

I think the reason this is not so popular is a combination of the three reasons you surmised. It is quite difficult to control properties of such a generator. There was at least one paper (can't recall reference) where the suggestion was to use a secret key to make a choice out of a collection of primitive LFSR polynomials.

I do know of another unpublished example, but I need to find my hardcopy of the manuscript to give you the gist of the design, which may take a day or two. It was never submitted for publication, to the best of my knowledge.


Why does FS&K's SHAd-256 construction zero-prefix the inner message?

If $H(x)$ is a random oracle, then $H(H(0^b \mathbin\| x))$ is indifferentiable from a random oracle[1] (Theorem 5, p. 444; note that [1] uses the name ‘HMAC’ for this particular construction, at odds with the standard meaning of the name), but $H(H(x)) = H^2(x)$ is not[2], and there are protocols that can be exhibited (as [2] does) which are secure if instantiated with $H$ but trivially breakable if instantiated with $H^2$.

The reason that $H(H(0^b \mathbin\| x))$ works as a random oracle is essentially the domain separation of the inner hash and the outer hash: there is no string of the form $0^b \mathbin\| x$ that coincides with a string that $H(\cdot)$ could yield as an intermediate value.

The protocol in [2] that is breakable with $H^2$ but not $H$ is a mutual proof-of-work game:  Two parties aim to prove to each other that they have each spent the work to compute $\hat H^n(x)$ and $\hat H^m(y)$ for some $(n, x)$ and $(m, y)$ chosen by the opposite party, and for some hash $\hat H$.  When instantiated with $\hat H = H$, the protocol works; when instantiated with $\hat H = H^2$, one party can ask the other to compute $u = \hat H^n(x)$ where $x = H(y)$ and $n = m - 1$, and then return $$H(u) = H(\hat H^n(x)) = H(\hat H^n(H(y))) = \hat H^{n + 1}(y) = \hat H^m(y)$$ at a total cost of two $H$ evaluations, rather than $m$ as expected, completely destroying the protocol.

This protocol is contrived.  Maybe your protocol doesn't have this affliction.  But while there is a theorem that $H(H(0^b \mathbin\| x))$ is safe for all protocols, this counterexample means that you have to separately study any protocol that you consider instantiating with $H(H(x))$ to see whether $H(H(x))$ is a problem for that protocol.

The theorem serves as a free cryptographer for everyone to sign off on the use of $H(H(0^b \mathbin\| x))$; if you want to use $H(H(x))$ you have to hire a personal cryptographer of your own to review your particular use of $H(H(x))$, and cryptographers aren't cheap.  If you already have a personal cryptographer (or auditor), the theorem lets them save work auditing your work and spend their time and energy on the rest of the work.


Is it possible to create a "proof-of-upload" system for BitTorrent ratio tracking?

The current specification says that tracker GET requests specify the following variables:

uploaded=... (bytes)
downloaded=... (bytes)
left=... (bytes)

This is great for public trackers but is poorly designed for private trackers. The problem is that the numbers don't always add up as they should and this can be for several reasons. For example, you might notice two users uploaded variables increase by 100MB over a period of time, but the sum of downloaded reported by the swarm might only increase by 150MB over the same period. This could be because someone is cheating, or it could be that someone else has unexpectedly left the swarm without reporting their extra 50MB downloaded. Smaller accounting errors might also occur due to packet loss between peers.

The core problems:

Transfer statistics are only reported to the tracker in aggregate, so in the event of contradictions, it is difficult or impossible to tell exactly which peers were involved in some change of total uploaded or downloaded bytes. (Over time an algorithm might be used to guess cheating clients, but this is still not 100% accurate.)
Since private trackers typically reward users which keep a good upload:download ratio, this creates an incentive for a peer to:

Claim it has uploaded more data than it really has
Claim it has downloaded less data than it really has

To prevent this kind of cheating, the above two problems must be solved. First, it is necessary to introduce some form of detailed accounting. Second, it is necessary to change the way statistics are reported so that there is no longer any benefit or incentive to do the wrong thing.

NOTE: When I first provided this answer, I gave a non-cryptographic method which would only need a relatively small extension of the BitTorrent protocol. However, I then came up with a far superior method involving cryptography, which is now given here. I have moved the non-cryptographic method to another answer so as to not clutter this one.

Cryptographic solution:

The tracker and each peer should have a public/private key pair.
The torrent metadata should contain the tracker's public key, to be used to establish secure communication with the tracker. This ensures encryption and prevents MITM between the tracker and clients.
When a client connects to the tracker, it should inform the tracker of its public key fingerprint. If the tracker does not know the public key, it should request it from the client.
When the tracker responds with a (partial) list of peers, it should include the public key fingerprints for each of those peers.
The tracker should also provide the client with a signed token such as expiry:SIGNATURE(client_ip:client_port:client_public_key_fingerprint:expiry), signed with the tracker's private key. The expiry, a UTC UNIX timestamp perhaps 24 hours from then, ensures that peers can only participate in the swarm while they are welcome by the tracker (i.e. not banned).
As expiry times are important for this protocol to work, the client may need to record and use a clock offset if the time reported by the tracker is very different to its own.
When the client connects to a peer, it should first provide its public key fingerprint and signed token. After the peer verifies the token, they will exchange public keys as necessary, and use them to establish secure communication. This ensures encryption and prevents MITM between peers.
After successfully downloading a number of blocks from an uploading peer, the uploader will request a download chit from the client, to be signed with the downloader's private key. This chit is described in the next section, but to put it briefly, it is proof of bytes sent which the uploader may give to the tracker. A client which refuses to provide valid download chits will quickly be blocked by its peers.
When next connecting to the tracker, a client which has been uploading data should take each downloading peer's public key fingerprint and append the latest download chit(s) it has received from that peer since last time. The client should then sign this list of chits and send it to the tracker.
The tracker should process the chits in sequence, verifying signatures and skipping any chits with which are out-of-order or have very old timestamps (e.g. over 7 days old). The tracker can then log how much data has been downloaded and uploaded by each peer. The tracker should respond with a success code, after which the client should clear those chits from memory (but still keep track of the previously used chit timestamps for each peer).

In addition to much stronger security and full encryption, this system ensures it is impossible for an uploader to unilaterally cheat about how much data they have transferred. While not directly prevented, downloaders who try to cheat will quickly be blocked from participating in the swarm.

Download chit specification:

The chit should contain the following fields:

bytes_downloaded
utc_unix_timestamp
SIGNATURE(bytes_downloaded:utc_unix_timestamp:uploader_public_key:torrent_hash)

How often an uploader requests a download chit may depend on the time since the last chit was requested, when it next intends to contact the tracker, the size of the torrent, and the degree to which the uploader trusts the downloader.
The uploader may either request a chit with the same timestamp as the last chit sent to this uploader for this torrent, or a chit with a new (current) timestamp.
If the downloader has lost the timestamp it last used for that peer on that torrent, or if it never received data from that uploader on that torrent, it should just provide a new chit.
The byte value of the chit should be the number of bytes successfully downloaded from that uploader on that torrent since a chit with an earlier timestamp. If no chit with earlier timestamp is known, this should just be all the bytes successfully downloaded during that session.
Essentially, a chit with the same timestamp can be used to replace a previous chit of lower value, or in case the previous chit was lost during transfer. Since the tracker will only accept one chit with a given timestamp, the uploading peer should always keep the one with the highest byte value. Here's an example session from the perspective of an uploader:

 --> sends 2MB
 --> requests new download chit
<--  receives 2097152:1396945746:3653e8fa74765d18903b77435b87174be1271315
 --> sends 3MB
 --> requests same download chit
<--  receives 5242880:1396945746:81ffed9eca4325b277ba258e2e0 CORRUPTED
 --> requests same download chit
<--  receives 5242880:1396945746:81ffed9eca4325b277ba258e2e01ee20ad462a7b
 --> continues to send another 3MB to peer
 ==> meanwhile, sends download chit to tracker (with associated info)
<==  tracker says OK
 --> requests new download chit from peer
<--  receives 3145728:1396946262:b8b1a71da192440158adc307cab5befaafb2229e
     ...

Of course, a client may be both downloading and uploading from the same peer, so there may be download chits being transferred in both directions.
It is the responsibility of the uploader to request download chits.
It is the responsibility of the downloader to provide valid chits for past data transfers, going back up to at least one hour (or some standard amount of time). That is, a downloader should not be expected to provide download chits for data received more than that time ago, though well-behaved clients should honestly provide chits for older data if they are able.
The uploader should adjust its trust of a downloader's IP and public key based on the reception of valid download chits. If the level of trust drops too low, the uploader should refuse to upload to that peer for some amount of time (perhaps permanently). Note that it is possible for a non-cheating downloader to lose some block data during transfer or have a client crash or system failure and lose knowledge of bytes transferred, which is why some leniency is needed.

Mitigating tracker connection problems:

As a further benefit, this infrastructure could, with some small additions, allow partial decentralisation of the tracker's role. That is, the swarm could still function effectively and record most data transfers even if only some of the seeders could connect to the tracker some of the time:

If you are unable to connect to the tracker currently, but still have an unexpired token from that tracker, you could attempt to use a DHT to find another peer. Once you authenticate to that peer, they can send you a list of other peers they know (PEX). Usually PEX and DHT are disabled for private torrents, but in this case only the clients authorised by the tracker will be able to both know how to look up the DHT and successfully authenticate to a peer in the swarm. There are two options which could be used for the DHT:

A private tracker-specific DHT. Clients would need to keep records of possible bootstrap nodes specific to the tracker, and all communication would need to be authenticated with tracker-signed tokens.
The standard global BitTorrent DHT, but with a special process to find the right hash. The hash would be found by encrypting the regular torrent hash with a special key given by the tracker when you last connected. The key would be shared by all torrents on the tracker, but would be regularly updated (e.g. twice a day). To achieve this, when the client receives its authentication token from the tracker, the tracker should also send the client a list of the keys the client should use at which times during the token's lifetime. Peers found with this method should be encrypted with the same key, and all further communication would be done with tracker-signed tokens.

If the client cannot connect to the tracker to send a list of download chits, it could instead sign them and send them to another peer with token expiry indicating more recent tracker communication. To make this system more fair for the clients doing the work, there could be a standard fee for this, to be paid as a download chit. For example, if the list of accumulated download chits is 2 KB in length (including uploader public key fingerprint), then the client might need to append a chit worth 20 KB or 30 KB for the forwarding peer before signing. In order to cash in their chit, the forwarding peer would need to send the whole signed list to the tracker at any point in the future (or in turn forward the chits again to a third peer). (The formula for the fee would need to be considered carefully.)


IV generation best practice for AES-256 CBC

I saw some SWIFT code that generates IV for AES 256 from selecting 16
  characters from a-zA-Z0-9 space.

  Is this secure? Sufficiently secure?

Almost always, when you see that modern ciphers are initialized by strings then the developer doesn't really understand that ciphers operate on binary data. This is a development practice that has got a special name: stringified code, where each parameter is a string, no matter what.

The characters that are used are almost the base 64 alphabet, which uses 6 bits for each byte. That means that you have (128 / 8) * 6 = 96 bits of security. We'll excuse the 64Ki options left out. That's still plenty of IV space for most usages, fortunately.

It does limit the amount of messages to encrypt with this kind of random IV though; keep to around 4 billion messages ($2^{32}$) or less for high security, and possibly a thousand times ($2^{42}$) more if you want to live dangerously.

The bigger problem is that I would not trust any developer that would use a string as key or IV. That's a $\color{red}{\text{red flag}}$: I'd start looking for other issues, because those are almost certain going to exist.

  What is the best practice to generate IV for AES 256?

  Will picking random 16 bytes from 0x0-0xff be good?

Yes, that is probably the best way of generating an IV for CBC mode. There are other ways of doing the same though. For many modern modes (that are based on CTR mode) you are however only required to use a nonce. In that case, a random IV may still be the best way forward, but a counter has advantages as well. For instance, a counter is less likely to repeat (the chances of an IV colliding are relatively high due to the birthday problem).

Do make sure that you are using a well seeded cryptographically secure random number generator.

  We want to store key and IV in Database and retrieve it for encryption/decryption. We want to store it as a string of values (i.e "1, 255, 126, 124 ..." - 16 values like this). Than decrypt using this as bytes.

That's a bad idea because for any mode the IV should not repeat for the same key. Generally, this is achieved by keeping / prefixing it to the ciphertext. Keeping a key in the database makes little sense as well. The key should be harder to access than the fields that it is trying to protect after all.

Finally, the problem with strings is that they are commonly hard to delete from memory. Generally, you want to remove keys once they are not used anymore. For IV's that's less of an issue, as they can be made public without compromising security.


Does a thermodynamic limit on key search apply to quantum computers?

From this Thermodynamic Analysis of Classical and Quantum
Search Algorithms, Sep 29, 2017;

  For the problem of collision finding, previous work suggested that quantum algorithms were unlikely to provide an asymptotic advantage in terms of circuit size (despite using fewer oracle queries). Our thermodynamic analysis leads to a similar conclusion. We compare in detail the classical collision finding algorithm of Van-Oorschot and Wiener, and the quantum collision finding algorithm of Brassard, Høyer, and Tapp (BHT) including parallelized generalizations of BHT. We find that the energy consumption
  required to search for collisions on a range of size $N$ using a memory of size $M < \mathcal{O}(N)$ in time $t$ is $\mathcal{O}(N/Mt)$, regardless of the choice of algorithm

  For the problem of unstructured search, it was known previously that Grover’s algorithm does achieve a quadratic speedup over classical exhaustive search, both in terms of circuit size, and in terms of oracle queries. Quite surprisingly, we do not find a quantum advantage using our thermodynamic analysis. On the contrary, we find that a Brownian implementation of classical random search can achieve the same asymptotic performance as Grover’s algorithm (up to logarithmic factors), where we measure the performance in terms of running time, memory size and energy consumption.

According to this article Battle between Quantum and Thermodynamic Laws Heats Up, March 30, 2017 in Scientific American, we don't have the same heat and efficiency rules there, yet.

  Many physicists hope that rebuilding thermodynamics from the laws of quantum mechanics will help to settle long-debated conundrums. Whether the concepts of heat and efficiency apply to tiny electronic components and even atom-sized machines.

The Quantum Thermodynamics Revolution is also a nice article to read.


Would this prevent FNV1a 32 bit hash collision?

First of all, "Is collision less likely for individual characters than for strings?"

The answer to this is yes. In fact, experimentally verifying shows that for 8-bit ASCII characters the collision chance with FNV1a is 0. This is however not an impressive feat, seeing that the output is 4 times as large as the input.

However, using this you no longer have a hashing function in the traditional sense. Each character gets replaced by simple substitution table, and becomes 4 times as long.

As for security, this is useless. This is a simple unkeyed substitution cipher which can be broken by either statistical analysis within minutes, a good eyeball or even one chosen plaintext. This scheme doesn't follow Kerckhoffs's principle, which is also very bad.


You can easily embed a Boolean circuit into the field $GF[2^k]$ for any $k$. Once you have done this embedding, you can then run any perfectly secure protocol. However, note that perfect security requires $t<n/3$ and so a minimum of 4 parties (with 1 corruption). For $n=3$ and $t=1$, it is possible to get statistical security.

Note that for the specific case of $n=3$ and $t=1$ you can also use a dedicated for Boolean circuits. For semi-honest adversaries, one example is High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority.


Are Fujisaki commitments binding if the factorization of the group is known?

Yes! Note that in the original scheme there are two secrets the committer does not know:

The factorization of the modulus: $N=pq$
The value $a$ such that $h^a=g$.

Therefore, the commitment scheme is still binding, even if the factorization is known. Let's assume committer wants to open the commitment $c=g^m h^r \mod N$ to a different $(m^{*},r^{*})$. It means that she needs to find values $(m^{*},r^{*})$ such that:

$$g^m h^r=g^{m^{*}}h^{r^{*}} \mod N $$

$$\iff g^{m-m^{*}}h^{r-r^{*}}=(h^a)^{m-m^{*}}h^{r-r^{*}}=1 \mod N $$
Which equivalently gives the following equality in the exponents:
$$\iff a(m-m^{*})+(r-r^{*})=0 \mod \phi(N) $$

Even if committer knows $\phi(N)$, she does not know $a$, therefore she cannot break the binding property, unless she additionally breaks the Discrete-Log in $\mathbb{Z}^{*}_p$ or $\mathbb{Z}^{*}_q$.

In most definitions of the Fujisaki commitment scheme, $N$ is chosen to be a product of safe primes, so commiter cannot even use Pohlig–Hellman algorithm efficiently, to calculate discrete logs modulo primes.

Trivially, if also $a$ is known to committer, then she can decommit to any $m^{*}$ by choosing an appropriate $r^{*}$ through solving the last equation in the exponents.


What does "overwhelming" mean in cryptography?

"With overwhelming probability" means that an event happens with probability at least $1−2^{Ω(n^\varepsilon)}$ for a constant $\varepsilon >0$.

Example: In a public key cryptosystem where $\mathcal{PK}$, $\mathcal{SK}$ and $\mathcal{R}$ are the spaces of public keys, secret keys, and sender randomness respectively, if $∆_{\mathcal{R}}$ denote the distribution on $\mathcal{R}$, then we require the usual correctness condition: for all $pk ∈ \mathcal{PK}$, all $sk ∈ \mathcal{SK}$, and $b ∈ \{0, 1\}$, we have $Dec_{sk}(Enc_{pk}(b; r)) = b$ with overwhelming probability over $r ← ∆_{\mathcal{R}}$.


Is IPsec IND-CCA secure provided the used block cipher is a pseudorandom function?

I would like to know which mode of operation is used by IPsec

That depends on what is negotiated; if we assume we're using AES as the block cipher, then the standard modes (that is, ones which have transform numbers assigned by IANA) are CBC, CTR and GCM.

  and whether my approach makes sense.

Sounds good to me.


Using the S-box package of SageMath used
S = SBox(1, 10, 4, 12, 6, 15, 3, 9, 2, 13, 11, 7, 5, 0, 8, 14);

f0 = S.component_function(1)
f1 = S.component_function(2)
f2 = S.component_function(4)
f3 = S.component_function(8)

print ( "y0 = ", f0.algebraic_normal_form())
print ( "y1 = ", f1.algebraic_normal_form())
print ( "y2 = ", f2.algebraic_normal_form())
print ( "y3 = ", f3.algebraic_normal_form())

Return a Boolean function corresponding to the component function $b\cdot S(x)$.

and the output
\begin{align}
y_0 &=  x_0 x_1 + x_0 + x_1 + x_2 + x_3 + 1\\
y_1 &=  x_0 x_1 + x_0 x_2 + x_0 + x_2 + x_3\\
y_2 &=  x_0 x_3 + x_1 x_2 x_3 + x_1 x_3 + x_1 + x_2\\
y_3 &=  x_0 x_2 x_3 + x_0 + x_1 x_3\\
\end{align}
The blow the result of the article
\begin{align}
s_0 &=  1 + a + b + ba + c + d \\
s_1 &=  a + ba + c + ca + d\\
s_2 &=  b + c + da + db + dcb\\
s_3 &=  a + bd + dca\\
\end{align}
And the result form Conchild code \begin{align}
y_0 &= 1 + x_0 + x_1 + x_0*x_1 + x_2 + x_3\\
y_1 &= x_0 + x_0*x_1 + x_2 + x_0*x_2 + x_3\\
y_2 &= x_1 + x_2 + x_0*x_3 + x_1*x_3 + x_1*x_2*x_3\\
y_3 &= x_0 + x_1*x_3 + x_0*x_2*x_3\\
\end{align}
Martin R. Albrecht provides another method with SageMath
from sage.crypto.sbox import SBox

S = SBox (1, 10, 4, 12, 6, 15, 3, 9, 2, 13, 11, 7, 5, 0, 8, 14)
P.<y0 ,y1 , y2 ,y3 ,x0 , x1 ,x2 ,x3 > = PolynomialRing ( GF (2) , order ='lex')
X = [x0 ,x1 ,x2 , x3 ]
Y = [y0 ,y1 ,y2 , y3 ]
S. polynomials (X=X , Y=Y , degree =3 , groebner = True )

The result is compatible with the article but the $y_i$'s reversed.
[y0 + x0*x1*x3 + x0*x2 + x3,
 y1 + x0*x1*x2 + x0*x2 + x0*x3 + x1 + x2,
 y2 + x0 + x1*x3 + x1 + x2*x3 + x3,
 y3 + x0 + x1 + x2*x3 + x2 + x3 + 1]


Discrete logarithm problem is easy in a cyclic group of order a power of two

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$.

Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $x$.  In other words, $\log_gh = x$, and for Groups of order $2^k$, this discrete log is easily computed like so:

Interpret $x$ as a $k$ bit number, i.e. $x = c_02^0 +c_12^1 + c_22^2 + c_32^3 ...+ c_{k}2^{k}$ where the coefficients $c_0, c_1, c_2...c_k \in \{0,1\}$.  You can find the value of $c_0$ by raising $g^x$ to the power $2^{k-1}$ modulo $p$.  If $c_0=0$ then all the other terms in $x$ are divisble by 2, thus $x=2y$, and so by Euler's totient theorem, $$(g^{2y})^{2^{k-1}}\equiv g^{y2^k} \equiv g^0 \equiv 1 \mod p$$
If however $c_0 = 1$, then raising $g^x$ to the power $2^{k-1}$ mod $p$ will return the result $p-1$.  So by looking at the result, you can see directly what the value of $c_0$ is.  Now that you have the value of $c_0$, subtract the term $c_02^0$ from $x$ (i.e. multiply $g^x$ by the modular multiplicative inverse of $g^{c_02^0}$).

Now you can find out what the value of $c_1$ is, by using the same approach:  raise $g^{x-c_02^0}$ to the power $2^{k-2}$.  If $c_1=0$, then all the remaining terms in $x-c_02^0$ are divisible by 4, and so $x-c_02^0 = 4y$ and $(g^{4y})^{2^{k-2}} \equiv g^{y2^k} \equiv 1 \mod p$.  If on the other hand $c_1=1$ then again the result will be $p-1$.  Subtract the term $c_12^1$ from $x-c_02^0$, and repeat the procedure for $c_2$.  Continue until you have discovered all the coefficients for $x$: you now know what $x$ is.


Are there any security issues related to use the same SALT in PBKDF2 for all IDs?

Yes, you can build a rainbow table or brute force the ID's.

An attacker could build up a table with tokens. Once the table exists the attacker can try all possible ID's until one of them matches. That way the function is reversible and your requirement to keep the ID secure has faltered.

Of course if the ID has enough entropy then the brute force attack will be impossible. But in that case you would not need the PBKDF2 function in the first place.

I don't see why you could not store a salt with a specific token by the way. Generally tokens are short lived.

Disclaimer: this is just a direct answer to the question, not a protocol analysis.


Why is Diffie-Hellman Insecure If Order of the Generator Has Only Small Prime Factors?

But I couldn't see any other reason why the order of g should have a large prime factor.

Let $p$ be the Diffie-Hellman modulus. The order $q$ of the subgroup generated by $g$ must have at least one large prime factor to prevent the use of Pohlig–Hellman algorithm. The complexity of this algorithm $$\mathcal O\left(\sum_i {e_i(\log n+\sqrt p_i)}\right)$$ where $e_i$ is the power of the prime factor $p_i$. In short, the larger one of the $p_i$s the higher complexity.

  Why should it be at least 2k bits long (instead of k bits long)?

The $\text{k}$-bit is the required for the target security. The generic attacks on Discrete logarithm problem have $\mathcal{O}(2^\text{k/2})$ complexity thus you need to start at least from $2\text{k}$.

Note: The safe primes $p = 2q+1$  guarantees that the order of $g$ is $q$ or $2q$.

  It also says the private keys a and b should also be 2k bits long.

No, the $2\text{k}$-bit for the choice of $a$ and $b$ is not necessary. As you can see from this answer;

  The standard Decisional Diffie-Hellman assumption holds for the case that $g^{x_a}$ and $g^{x_b}$ are uniformly distributed in the group (which should be a prime-order subgroup).

There is also a linked article (Short Exponent Diffie-Hellman Problems) for this issue in the comments of this the answer.


Can a billion elliptic curve keys be generated on a laptop in less than an hour?

The very fastest elliptic curve algorithms can generate a key-pair in about 40k cycles on a modern CPU. A high end laptop has four cores running at about 3 GHz, so it can generate about 300k key-pairs per second, or a billion per hour. (The cost of SHA-256 is negligible in comparison.)

However, secp256k1 is nowhere near the fastest curve. It takes 10 times as long to generate a key-pair with many algorithms, according to the above link, so it would likely take tens of hours at least to iterate the search space. A more mainstream laptop and you may be looking at several days.

So if you just brute force generate key-pairs looking for a matching one, you can't get it done in an hour even with a much better implementation (unless you get lucky).


How is it possible to parallelize a hashing function to crack an iteratively hashed password?

The bit about parallelization is not for hashing one password. But the attacker, by definition, has a lot of passwords to try, and these can be computed in parallel, provided that the function maps well to whatever parallel architecture the attacker would like to use. In the case of the multi-SHA-1 method you describe, it maps very well on GPU. Note that the same can be said about PBKDF2, which is why I tend to recommend bcrypt, which is more resilient to GPU.

Although I do not immediately see any obvious problem with your SHA-1* function, it has the generic issue of being homemade and of not having been investigated thoroughly by dozens of cryptographers during several years. Therefore I would not trust it.


Can I use MAC as CTR mode nonce, if my messages are non-repeating?

Yes, but to use a known algorithm that specifies precisely that, take a look at the SIV mode of operation . "SIV" stands for Synthetic IV. IV is the initialization vector, which is the nonce (or the nonce and initial counter value, depending on the definitions).

Unsurprisingly it relies on CTR mode for confidentiality and CMAC for the authentication tag that doubles as IV - much like CCM.

The problem with CCM is that you would have a chicken/egg problem as the MAC is calculated at the end of the protocol. Although you could implement the protocol differently, I'd recommend to use a tried and tested mode instead.

Besides that, CCM mode is - at least in my opinion - a horrible mode to implement.

SIV does have the problem that it is a full two pass protocol; you will have to go over each packet twice to encrypt: one pass for creating the SIV and on pass to encrypt. Decryption is easier as you already have the IV ready, so you can at least combine the two passes.


How were the DES S-box values determined?

There is a good article from Coppersmith which explains it. Basically, the designers of DES had envisioned differential cryptanalysis (a good 15 years before differential cryptanalysis was rediscovered by Biham and Shamir, and published); they could measure how well DES could resist differential cryptanalysis for a given set of S-boxes.

So they generated a huge bunch of random S-boxes, measured them all and kept the best.

It turns out that although the DES designers did not know of linear cryptanalysis (discovered in 1993 by Matsui), having S-boxes which resist differential cryptanalysis kinds of defeats linear cryptanalysis as well.


CSPRNG made out of Block Cipher running in CTR Mode?

If CSPRNG is constructed out of AES in CTR Mode, does it satisfy 2nd characteristic? i.e Compromise of internal state will not lead to reconstruction of prior stream of random numbers?

No, assuming you mean the CSPRNG is just AES in CTR, the state is simply the key and the IV, therefore compromise will allow trivial generation of both past and future outputs.

Exposure of just the key is also as bad, as you can decrypt the output using the key (in ECB mode) to recover the IV.


How Were secp*k1 elliptic curve generators chosen?

Well, I'm not privy to how Certicom selected these parameters, however I can tell you that it doesn't really matter; if the generator they selected is weak, then all generators on that curve are weak.

In particular (and assuming that the curve has a prime number of points on it; this is true for the Certicom curves):

If you can solve the discrete log to a specific generator $G$, you can solve it to any base (by solving two instances of the generator $G$ problem)
If you can solve the computational Diffie Hellman problem with a specific generator $G$, you can solve it to any base (by solving $\log p$ instances of the generator $G$ problem).

Hence, if there is a weakness with their generator, then their curve is weak (except possibly against the decisional Diffie-Hellman problem; I don't know of a similar reduction there).

Demonstrating the first reduction is quite straight-forward; suppose thatwe are  given an Oracle, that, given $aG$, recovers $a$ (with $G$ being our distinguished generator).  Then, given an instance which consists of $H$, and $aH$, with $H$ being an arbitrary point, we call the Oracle twice, once with $H=bG$, and once with $aH = cG$, recovering $b$ and $c$.  Then we can compute $a = b^{-1}c \bmod q$ (where $q$ is the order of the curve); this is our answer.

The computational Diffie-Hellman case is somewhat more complex.  For that, we suppose that we have an Oracle that, given $aG$ and $bG$, computes the value $abG$.  Then, the problem we are trying to solve is, given $H$, $aH$ and $bH$, compute the value $abH$.

To see how to we proceed, let us designate $c$ as the value $H = cG$.  Now, we don't know the value of $c$, however we can compute the point $c^2G$ (by using our Diffie-Hellman Oracle, with the inputs $cG$ and $cG$).  Extending this observation, we can compute $c^kG$ with $\log{k}$ calls to the Oracle.  So, we compute $c^{q-2}G = c^{-1}G$ (with $\log{q}$ Oracle calls, and $q$ is the curve order).  Then, with $aH = acG$ and $bH = bcG$, we can compute $abH = abcG$ with two more Oracle calls.


This sounds suspiciously like the first extra credit assignment out of Dan Boneh's Cryptography I on Coursera.  Dan gives you a great hint in the assignment listing for this one.  Take a look at an ASCII chart and note what happens when you XOR something with space rather than with an alphanumeric.

Once you've got that sorted out, your best bet is to XOR things together, as you suggest, and use the knowledge gained from Dan's hint on XORing with space to build a histogram of candidate plaintext characters for each position.  My first cut at this assignment got about 85% of the characters, and filling in the rest was simple due to the common digraphs of english.


This is a classical example.

Here is the proof system…

Bob gives two gloves to Alice so that she is holding one in each hand. Bob can see the gloves at this point, but Bob doesn't tell Alice which is which. Alice then puts both hands behind her back. Next, she either switches the gloves between her hands, or leaves them be, with probability $1/2$ each. Finally, she brings them out from behind her back. Bob now has to "guess" whether or not she switched the gloves.

By looking at their colors, Bob can of course say with certainty whether or not Alice switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way Bob could guess correctly with probability higher than $1/2$.

If Bob and Alice repeat this "proof" $t$ times (with a large $t$), Alice should become convinced if the gloves are indeed differently colored; because if they would have the same color, the probability that Bob would have succeeded at identifying all the switch/non-switches is at most $(1/2)^{t}$.

(Furthermore, the proof is "zero-knowledge" because Alice never learns which gloves have what color; indeed, she gains no knowledge about how to distinguish the gloves… but the proof system helps her.)

In case anyone has problems understanding zero-knowledge proofs, I would like to point to “Zero-Knowledge Technique (PDF)” (PDF) which contains a colorblind example similar to mine, as well as a few more examples explaining ZKP, including the example by Jean-Jacques Quisquater which has been published in “How to Explain Zero-Knowledge Protocols to Your Children” (PDF). That should help…


How to formally say that the integers modulo $p$ for a prime $p$ gives results that are "more random" than for a composite $n$?

Can we get more precise than this?

Actually the "randomness" of the resulting values is not the blocking issue with composite moduli for DH.

What is much more severe is the fact that if you know the factorization of the modulus $n=pq$, then solving $g^x\bmod n$ is essentially the same as solving $g^x\bmod p$ and $g^x\bmod q$ both of which are substantially easier than solving the problem for $n$ itself (using eg GNFS). Afterwards you can cheaply recombine the solutions with CRT.

In particular note that using a 2048-bit safe prime for DH yields a secure (unauthenticated) key exchange (with effort needed of about $2^{112}$ to break it) whereas if you were to use eg balanced factors that would drop to solving two 1024-bit discrete log instances, both of which need about $2^{80}$ work (so $2^{81}$ in total). This is considered feasible if you have the right amount of funding (eg nation-state level). Obviously if you use unbalanced factors the run-time of attacks is dominated by the larger factor and at that point you may just do away with the smaller one and save yourself the computation time (for your normal exchanges).

If you don't know the factorization, things become harder, but so does uncertainity. You have to trust that whoever generated the composite modulus actually doesn't know the factors (and thus is able to much more easily break the security). Also it allows for parameter replacement attacks which in turn do allow such attacks. This is not a theoretical attack. And in fact with such a parameter replacement attack you could just sneak in a value that is a composite of 4x 512-bit primes, nobody could factor that (easily) but with about a week of pre-computation every discrete log instance with that modulus could be solved in a matter of seconds.

So TL;DR: By using composite moduli you only gain a lot of headaches and neither speed nor security.

If the above is too complex try the following:

We use primes for the modulus in Diffie-Hellman because it gives us no speed nor a security advantage not to use them. In fact quite the opposite, if we used composites, we could split the relevant hard problem of discrete logarithm along the factorization and solve both sub-problems in parallel. Even worse each of these instances is significantly easier to solve due to the large reduction due to the solving algorithm's complexity growing really fast with the problem size. If we don't know the factorization we'd have to trust the generator of the modulus not to exploit the above weakness against us and attackers may replace our parameters with theirs, giving them backdoor access to the data.


Could one make an asymmetric encryption scheme based on Sudoku?

Sure. How efficient vs secure is another matter.

Look up Merkle's puzzles, as well. A latin square as a higher dimensional object can be related to differential properties of good mappings.


should one worry about timing attacks with signature verification?

Correct.  In fact, often—and pretty much always for their modern cousin EdDSA—the verification procedure is implemented with variable-time operations, because there are no secrets involved.

However, you may wish to take care in case you rely on key privacy anywhere in your protocol.  The paper is presented in the public-key encryption setting (distinguishing ciphertexts under one unknown key from ciphertexts under a distinct but also unknown key), which is straightforward to transfer to the public-key signature setting (distinguishing signatures under one unknown key from those under another)—but maybe the adversary in your case wants to learn which public key you're verifying signatures of, and does so by probing how long it takes to compute a rejection with various different signatures.  It's a stretch—and maybe it's actually moot for some reason that I haven't thought of—but I'm not aware of any research on that specific question.


Using RSA encryption to encrypt large files

Is the resulting ciphertext practically decryptable in anyway without the private key?

No, you would need the private key. There is no practical limit on the amount of times that you can encrypt with a public key. I would make sure that the randomness within the padding is at least 128 bits though. Also note that decrypting many times with a private key makes the algorithm more vulnerable against side channel attacks (which often rely on statistics). Furthermore, it disallows you to protect the private key with a PIN or password for each decryption.

  What factors affect the speed of encryption in this case? The RSA key size? The block size? The padding type?

Yes, yes and yes.

The RSA key size is of utmost importance because larger key sizes will affect performance hugely. Furthermore, RSA key sizes grow very fast if you require more key strength. RSA-3072 is providing about 128 bit security, but you need to go over 16Kbit of key size to reach 256 bits. And those kind of operations are certainly very slow, specifically when it comes to private key operations.

The block size used for the plaintext differs from the one for the ciphertext (i.e. the input is always smaller than the output) due to the padding requirements. The block size for the plaintext is generally 11 smaller than the key size for the less secure PKCS#1 v1.5 padding and differs by the hash value for OAEP. The block size of the ciphertext is identical to the size of the modulus in bytes.

The padding type is generally not much of a problem when it comes to encryption speed. RSA private key operations are rather slow, and the unpadding won't take much time compared to them. The generation of the padding however relies on a secure random number generator. Random number generation can be fast, but it might also block or slow down the system by other means.

Note that performance is only one reason why direct encryption with RSA should be shunned. The expansion of the ciphertext compared to the plaintext is another big reason. And as indicated, requiring the private key to be available for batch operations may well put it at risk.


About Cryptography in a Character Language

For designing a cipher, one first has to decide about the alphabet.

This is a bit problematic for a language like Chinese, since it is not really clear how many (and which) characters should be used. The number of signs known by people differs greatly. You don't want that your encrypted message is un-decryptable just because you used some unknown character in the ciphertext. One possibility here would be to restrict the ciphertext alphabet to some "known to everyone" subset (while still allowing a greater alphabet on the plaintext side).

Assuming we have decided on an alphabet, we also should decide on some encoding of this alphabet, i.e. some ordering of the signs, or a mapping to numbers. This allows using some simple mathematical formula/algorithm for the actual encryption, instead of having to use a "translation table" as the key (which would be quite big in the case of a big alphabet).

Every monoalphabetic substitution cipher can be presented as a "big table", and thus breaking the big table algorithm also breaks each other (monoalphabetic) algorithm (which in fact are only ways to write the big table in a shorter way).

So, how to break a monoalphabetic cipher? Just like always. In a language like Chinese there are more frequent words (= signs), too, and more or less frequent two-word or three-word combinations, just like in our European single-sound-alphabets, too. The problem is just that there are more different signs, and thus you need a lot more text to get significant samples. Then we try the most probable words first, and try to fill in the rest, and see if it starts to make sense. Some signs used only once or twice are quite probably not decodable at all, if multiple different ones would make sense here.

The reason that modern substitution ciphers on really large alphabets (like AES) are comparatively quite secure even in ECB mode (in other modes they are not pure substitution ciphers), is that you don't get as much blocks to find many repeated ones - and that you simply can't write down the whole substitution table, for space and time reasons.


Are there any non Canonical Verifiable Cryptographic MACs

See Message Authentication, Revisited. This paper presents MACs with different properties, and in order to achieve these properties randomization is used. Since the MACs are probabilistic, the verification cannot be canonical.


In general we nowadays use fixed paddings or a stream mode of operation such as CTR.

Authentication tags are usually used to validate integrity/authenticity. Examples of authentication tags are those created by calculating a MAC or HMAC over the ciphertext and additional data such as the IV. In general known plaintext - including the padding - should not be used to validate integrity/authenticity.

Authenticated ciphers combine a mode of operation and authentication scheme using the same key. Many of them apply CTR mode encryption instead of a mode that requires (internal) padding.

If padding is required, then PKCS#7 padding should be preferred as it seems to be the ad-hoc standard within the defined standards. Basically you should not tie any security claims on the padding though (except possibly the one that subliminal channels are not possible in your particular protocol).


Is a bit string pseudorandom if it starts with predictable bits?

No, first of all, you've defined it to be a bit string. A bit string is not a number although you can of course interpret it as a specific number.

Furthermore, it is not pseudo-random if we assume that the number is between 0 and the maximum value for S, as it clearly is either in a range, or it ends with a lower end bits set to a specific value.

Now if we assume big endian then you can however consider $S$ pseudo random in the range $\Big[N \cdot 2^m, (N + 1) \cdot 2^m \Big)$ where $N$ is the big endian value of the first $n$ bits of $S$.

I don't know what we can call $S$, it's a constructed bit string. With the HMAC it could be some kind of token, but that's speculating on a specific use case for it.


Does the SHA hash function always generate a fixed length hash?

Yes. By the definition in FIPS 180-4, there are exactly
160 bits in the output of SHA-1
224 bits in the output of SHA-224
256 bits in the output of SHA-256
384 bits in the output of SHA-384
512 bits in the output of SHA-512
224 bits in the output of SHA-512/224
256 bits in the output of SHA-512/256


Please explain parameters of RFC5639 Elliptic Curves including brainpoolP160r1

The order of the curve $\#E(\mathbb{F}_p)$ is different from $p$. In fact, according to Hasse's theorem, $\#E(\mathbb{F}_p)=p+1-t$ where $t$ the Frobenius trace satisfies $|t|<2\sqrt{p}$. So the gap between $\#E(\mathbb{F}_p)$ and $p$ is at most $2\sqrt{p}$. Note that, if $\#E(\mathbb{F}_p)=p+1$, $\textit{i.e.}$ $t=0$, the curve is supersingular. For brainpoolP160r1, the order is 1332297598440044874827085038830181364212942568457 (160-bit). You can play with sage code:

p = 0xE95E4A5F737059DC60DFC7AD95B3D8139515620F
A = 0x340E7BE2A280EB74E2BE61BADA745D97E8F7C300
B = 0x1E589A8595423412134FAA2DBDEC95C8D8675E58
x = 0xBED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3
y = 0x1667CB477A1A8EC338F94741669C976316DA6321
E = EllipticCurve(GF(p),[A,B])
G = E(x,y)
G.order()
E.order()


RIPEMD-160 uses precisely the same padding and endianess convention as MD5.

Everything is little-endian, with the exception of the order of bits in bytes, which is kept big-endian. If the message is $n$-bit, it is appended a single bit at 1 and $511-((n+64)\bmod512)$ bit(s) at 0 , then the representation of $n$ on 64 bits. The resulting padded message is an integral number of 512-bit blocks, which are each considered 16 words of 32 bits.

Note: It follows that the padding bit at 1 corresponds to a byte mask with value $2^{7-(n\bmod 8)}$. The $n\bmod 8$ last message bit(s) are in the high-order bit(s) of that byte, which $7-(n\bmod 8)$ low-order bit(s) are 0.

Suppose the message is the one-character string "a", and that is coded in ASCII as the single byte 61h = 01100001b = 97.

That's the bitstring 01100001. $n=8$, thus the padding is 1 followed by 439 0 (with the first eight bits of that padding 10000000 corresponding to byte 80h), followed by the length $n=8$ represented as the bitstring 00001000 00000000 00000000 00000000 0000000 00000000 00000000 0000000 (with the first eight bits 00001000 corresponding to the byte 08h).

Showing this as a string of 64 bytes with bytes and 32-bit boundaries shown (and individual bytes shown in big-endian hexadecimal), the padded block is

61 80 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   08 00 00 00   00 00 00 00

Packing that into 32-bit words using little-endian convention (and individual 32-bit words shown in big-endian hexadecimal), we get

00008061      00000000      00000000      00000000
00000000      00000000      00000000      00000000
00000000      00000000      00000000      00000000
00000000      00000000      00000008      00000000

or in decimal { 32865, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0 }.

Note: a former version of this answer did not take into account the exception to little-endianness in the conversion of bytes to/from bits, and used uppercase ASCII code in the example. I'm confident about the present revised version.

Simple demonstration and example output for the reference code rmd160

// Demonstration of rmd160 - public domain
// note: on machines with more than 32-bit unsigned long, rmd160.h requires a simple change
#include "rmd160.h" // at http://homes.esat.kuleuven.be/~bosselae/ripemd160/ps/AB-9601/rmd160.h
#define SIZEOFHASH  20      // size of the hash in bytes
#define SIZEOFBLOCK 64      // size of a block in bytes

// including the code simplifies compilation+linking into a tool
#include "rmd160.c" // at http://homes.esat.kuleuven.be/~bosselae/ripemd160/ps/AB-9601/rmd160.c

// hash a byte buffer in memory
void hashmd160(
    const byte  *iData,             // input
    size_t      iDataLength,        // size of input in bytes
    byte        oHash[SIZEOFHASH]   // result (must be allocated by caller)
    )
    {
    dword       vHash32[SIZEOFHASH%4==0 ? SIZEOFHASH/4 : -1 ];      // the hash, as 32-bit words
    dword       vBlock32[SIZEOFBLOCK%4==0 ? SIZEOFBLOCK/4 : -1 ];   // a block, as 32-bit words
    size_t      vb;
    int         vj;
    // start hashing
    MDinit(vHash32);
    // hash full blocks; needed only when iDataLength>=SIZEOFBLOCK
    for (vb = iDataLength/SIZEOFBLOCK; vb!=0; --vb)
        { // make a little-endian copy of SIZEOFBLOCK bytes from iData to vBlock32
        for (vj = 0; vj<SIZEOFBLOCK/4; ++vj, iData += 4)
            vBlock32[vj] = iData[0] | iData[1]<<8 | (dword)(iData[2] | iData[3]<<8)<<16;
        compress(vHash32,vBlock32);
        }
    // hash remaining bytes
    MDfinish(vHash32, (byte *)iData, iDataLength, iDataLength>>16>>16);
    // make a little-endian copy of SIZEOFHASH bytes from vHash32 to oHash
    for (vj = 0; vj<SIZEOFHASH; ++vj)
        oHash[vj] = (byte)(vHash32[vj>>2]>>((vj&3)<<3));
    }

// hash each argument, print its hash and the (quoted) argument
int main(int argc, char *argv[])
    {
    byte    vHash[SIZEOFHASH];
    int     vj,va;
    for(va=1; va<argc; ++va) {
        hashmd160((const byte *)(argv[va]),strlen(argv[va]),vHash);
        for (vj = 0; vj<SIZEOFHASH; ++vj)
            printf("%02x",vHash[vj]);
        printf(" \"%s\"\n",argv[va]);
        }
    return EXIT_SUCCESS;
    }

/* Example output
9c1185a5c5e9fc54612808977ee8f548b2258d31 ""
0bdc9d2d256b3ee9daae347be6f4dc835a467ffe "a"
8eb208f7e05d987a9b044a8e98c6b087f15a0bfc "abc"
5d0689ef49d2fae572b881b123a85ffa21595f36 "message digest"
f71c27109c692c1b56bbdceb5b9d2865b3708dbc "abcdefghijklmnopqrstuvwxyz"
12a053384a9c0c88e405a06c27dcf49ada62eb2b "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
b0e20b6e3116640286ed3a87a5713079b21f5189 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
9b752e45573d4b39f4dbd3323cab82bf63326bfb "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
*/


I have a new cryptography algorithm, what should I do?

Do you think that such algorithm can be commercialized[...]?

This is very unlikely. AES is fast enough for most applications and where it isn't one usually uses (the cheap) hardware acceleration to fix that. Other common scenarios have the usually fast enough for them ChaCha stream cipher. This only leaves true edge cases on ultra-low power devices but this has active research going on with free schemes and some efforts from NIST, so a scheme with no proper analysis will not impress / interest most people.

  [Is it] possible to somehow [make] a profit on it (I also thought about a patent)?

Patenting a cryptographic algorithm has a great history of seeing it being unused for at least the lifetime of the patent and potentially afterwards as well due to standardization and implementations having already chosen other schemes which are good enough. Examples of this are the OCB mode of operation which is faster than most other known authenticated encryption algorithms but has seen little use due to patents and Schnorr signatures which are only now seeing standardization - after the patents expired which in fact prompted (EC)DSA to be created to avoid the legal issues.

  it looks like algoritm runs faster than AES

Without proper security analysis speed claims will likely not be interesting. After all 4-round AES also runs faster than AES but is somewhat easily broken.

  Maybe some of you guys work in cryptography and can give me some advice? Or maybe should I publish it somewhere on the internet and forget about profits or even authorship (because what can I do as nobody in the cryptographic industry)?

While some active users here do work in cryptography, note that Crypto.SE does not accept questions to analyze non-trivial primitives as this cipher most likely would be. Publishing it and hoping someone will have a look at it because they find it interesting may be your best bet (sci.crypt and reddit's /r/crypto may be starting points for advertisement) though paying a professional cryptographer is the only "sure" way to get proper attention at the scheme.

Having a reputation in the academic community for cryptanalysis would indeed also help in getting more interest - especially as good schemes by people without reputation are indistinguishable from bad schemes by people without reputation with the latter being far more likely. Additionally most people don't react too well to their pet project being broken which means such analysis takes a lot of time and yields no satisfying result for anybody involved most of the time which is why most people don't do it (for free).

What could make this scheme potentially interesting is if it had a security reduction from (S)PRP security to some known / proven pseudorandomness result of the Collatz problems - but even then probably mostly for theoreticians.


Text cipher option that can decrypt the same ciphertext to two DIFFERENT and DESIRED outputs given DIFFERENT keys (and/or alphabet)

I've been thinking about this for a while and I can only think of one possible solution.
If you want to share two different messages with the same cypher text then you might be able to use a "one-time pad" with multiple decryption possibilities, or rather multiple one-time pads for the same text.
So if I were to have the following cypher text
GTEROSDFEE
Each one-time pad takes individual letters in the cypher text and assigns an other letter;
Thus, with the same cypher text, with one one-time pad I would get
HELLOTHERE
(pad: G->H, T->E, E->L, R->L, O->O etc.)
And with an other one-time pad I would get
GOODBYEYOU
(pad: G->G, T->O, E->O, R->D, O->B etc.)
This can be practical for short messages that do not use too many characters, as to decrypt you must know the unique decryption for each individual column of characters of text.


If the first key-bit is flipped, which DES s-boxes are affected?

Permuted Choice 1 determines how an input block is loaded into C and D Registers:

Permuted Choice 1 is selection permutation describing how to load C and D registers from 8 successive bytes of input key, noting the LSB is only used for parity. (The big endian bit in byte ordering is from IBM).

Permuted Choice 2 determines which C and D Register bits are used as input to f(R,K):

Permuted Choice 2 is also a selection permutation selecting two 24 bit values from each of the C and D 28 bit registers which are shifted according to the key schedule.

The DES standard also defines which selected Key bits are associated with each S Box:

This shows the E Permutation as values of R exclusive OR'd with selected key bits as input to the 8 S Boxes.

The Key Schedule causes rotations in the C and D registers bringing different key bits into play in different rounds.

The program keytab.c reproduces two tables from the Meyers Metyas book Cryptography.

Invoking keytab -b will fill an input block with input block indexes for each position convert those locations to the appropriate locations in the C and D Registers, iterate the key schedule and produce the selected Key for each round through PC2 giving a list of Ks bits referencing the input block indexes:

  Bit  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
KS
   1  10 51 34 60 49 17 33 57  2  9 19 42  3 35 26 25 44 58 59  1 36 27 18 41
   2   2 43 26 52 41  9 25 49 59  1 11 34 60 27 18 17 36 50 51 58 57 19 10 33
   3  51 27 10 36 25 58  9 33 43 50 60 18 44 11  2  1 49 34 35 42 41  3 59 17
   4  35 11 59 49  9 42 58 17 27 34 44  2 57 60 51 50 33 18 19 26 25 52 43  1
   5  19 60 43 33 58 26 42  1 11 18 57 51 41 44 35 34 17  2  3 10  9 36 27 50
   6   3 44 27 17 42 10 26 50 60  2 41 35 25 57 19 18  1 51 52 59 58 49 11 34
   7  52 57 11  1 26 59 10 34 44 51 25 19  9 41  3  2 50 35 36 43 42 33 60 18
   8  36 41 60 50 10 43 59 18 57 35  9  3 58 25 52 51 34 19 49 27 26 17 44  2
   9  57 33 52 42  2 35 51 10 49 27  1 60 50 17 44 43 26 11 41 19 18  9 36 59
  10  41 17 36 26 51 19 35 59 33 11 50 44 34  1 57 27 10 60 25  3  2 58 49 43
  11  25  1 49 10 35  3 19 43 17 60 34 57 18 50 41 11 59 44  9 52 51 42 33 27
  12   9 50 33 59 19 52  3 27  1 44 18 41  2 34 25 60 43 57 58 36 35 26 17 11
  13  58 34 17 43  3 36 52 11 50 57  2 25 51 18  9 44 27 41 42 49 19 10  1 60
  14  42 18  1 27 52 49 36 60 34 41 51  9 35  2 58 57 11 25 26 33  3 59 50 44
  15  26  2 50 11 36 33 49 44 18 25 35 58 19 51 42 41 60  9 10 17 52 43 34 57
  16  18 59 42  3 57 25 41 36 10 17 27 50 11 43 34 33 52  1  2  9 44 35 26 49

  Bit 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
KS
   1  22 28 39 54 37  4 47 30  5 53 23 29 61 21 38 63 15 20 45 14 13 62 55 31
   2  14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55  7 12 37  6  5 54 47 23
   3  61  4 15 30 13 47 23  6 12 29 62  5 37 28 14 39 54 63 21 53 20 38 31  7
   4  45 55 62 14 28 31  7 53 63 13 46 20 21 12 61 23 38 47  5 37  4 22 15 54
   5  29 39 46 61 12 15 54 37 47 28 30  4  5 63 45  7 22 31 20 21 55  6 62 38
   6  13 23 30 45 63 62 38 21 31 12 14 55 20 47 29 54  6 15  4  5 39 53 46 22
   7  28  7 14 29 47 46 22  5 15 63 61 39  4 31 13 38 53 62 55 20 23 37 30  6
   8  12 54 61 13 31 30  6 20 62 47 45 23 55 15 28 22 37 46 39  4  7 21 14 53
   9   4 46 53  5 23 22 61 12 54 39 37 15 47  7 20 14 29 38 31 63 62 13  6 45
  10  55 30 37 20  7  6 45 63 38 23 21 62 31 54  4 61 13 22 15 47 46 28 53 29
  11  39 14 21  4 54 53 29 47 22  7  5 46 15 38 55 45 28  6 62 31 30 12 37 13
  12  23 61  5 55 38 37 13 31  6 54 20 30 62 22 39 29 12 53 46 15 14 63 21 28
  13   7 45 20 39 22 21 28 15 53 38  4 14 46  6 23 13 63 37 30 62 61 47  5 12
  14  54 29  4 23  6  5 12 62 37 22 55 61 30 53  7 28 47 21 14 46 45 31 20 63
  15  38 13 55  7 53 20 63 46 21  6 39 45 14 37 54 12 31  5 61 30 29 15  4 47
  16  30  5 47 62 45 12 55 38 13 61 31 37  6 29 46  4 23 28 53 22 21  7 63 39

These represent Table 3-10 First Set of 24 key Bits in K(i), the Key used at Round( i) and Table 3-11 Second Set of 24 Key Bits in K(i), the Key Used at Round(i) found in Chapter 3. The Data Encryption standard the section Description of the Data Encryption Standard and subsection Generation of Key Vectors Used for Each Round of DES, of Cryptography A new Dimension in Computer Data Security subtitled A Guide for the Design and Implementation of Secure Systems, by Carl H. Meyer and Stephen M. Matyas published in 1982.

The tables demonstrate the Permuted Choice 2 selected C and D register contents given in input block indexes for the 16 rounds of DES.

The KS bits tell us which S Boxes each input block key bit is used on in each round.

Note that for input block bit 1 (the most significant bit of the first byte of key) is used as input to S Boxes 1 through 4 in 14 rounds.

Taking in to account e-suishi's comment the answer is achievable through research either reading or applied practice.  You could also note the process undertaken by the keytab program matches that described by fgrieu's comment.

In this case keytab generates the schedule key for each of the 16 rounds by providing an integer value representing the input block index instead of a 1 or 0 representing a binary value.

The idea comes from the original BSD libcrypt implementation of DES (des0.tar.gz, file crypt.c) which used integers to represent individual bits.

Doing algorithm-design or cryptanalysis can imply validating what you read.


Difference between $F_2^n$ and $\Bbb F_2^n$ for a field

Some authors write $F_q$ for the finite field of order $q$.  Some authors write $\mathbb F_q$.  Some authors write $\mathbf F_q$.  Unless there's a typo, or unless your pet author is particularly confusing and as a personal peculiarity makes a nonstandard semantic distinction between them, which one you use is a matter of taste.  And as we all know—de gustibus non disputandum est: only with gusto can taste be argued.

What parts of the text you are reading are leading you to a state of confusion?  Maybe you can ask a question about those in particular.


Using bcrypt derived keys for encryption?

BCrypt is considered more secure

The theoretical security of bcrypt has received less scrutiny than that of PBKDF2, SHA2 and HMAC.  PBKDF2 is thus widely standardised (e.g. in NIST SP800-132 and PKCS #5) while bcrypt is not.

In practice the security (resistance to brute force attack or dictionary attack) of bcrypt and PBKDF2-HMAC-SHA512 can be controlled by a workload parameter.  bcrypt is more secure than PBKDF2 in the sense that: if you select the workload parameters such that the algorithms use the same computing time on a general-purpose CPU, then an attacker able to choose their hardware (CPU, GPU, FPGA, or ASIC) can attack PBKDF2 4 to 6 times more effectively than bcrypt at the same cost (see the scrypt paper).

As a heuristic we could say that a password hashed with PBKDF2 should have 2 to 3 bits more randomness than a password hashed with bcrypt to achieve equivalent security (against a brute force attack; for equivalent workload parameters).

  Would it be secure to take the sha-512 hash of the key produced by BCrypt and split that

No, but you're on the right path by splitting the operation into a step that produces a key, and a step that expands the key.  The trick is to select the right primitives for these operations.

To expand a key - that is, to produce using one key a stream of derived random output suitable for use as key material - you need a Pseudorandom Function Family (PRF).  SHA-512 is not a PRF, but HMAC-SHA512 is.  Using HMAC-SHA512 would be a secure - but not ideal - solution.

A better solution is to use HKDF which splits key derivation into extraction and expansion steps.  By using bcrypt or PBKDF2 you have already extracted a pseudorandom key (HKDF calls this a PRK) from the password.  You can apply the HKDF expansion step to that PRK to produce derived keying material of any length; equivalently you could use one of the Key Derivation Functions from NIST SP800-108.

See also Do any security experts recommend bcrypt for password storage? for more on PBKDF2 vs bcrypt.


How can I validate a hashed password if all I have is another hash?

With the method below, the server never sees either the password or the key the password decrypts.

To generate a password:

The client generates a new RSA key, encrypts it with the password (using something like PBKDF2 to generate a symmetric key), and hands the server the RSA public key and the encrypted private key.

To Authenticate:

The server sends the client the encrypted RSA private key and a challenge. The client uses the password to decrypt the RSA private key and then signs the challenge. The client sends the signed challenge back to the server. The server verifies the signature with the RSA public key.

Caution:

Make sure changing passwords involves creating a new private key, not re-encrypting the old one with the new password.

--

This has an extra request. You can avoid that with two tricks:

Have the client store the encrypted private key so it doesn't need to ask the server for it.
Have the client store a sequence number to use as the challenge (or a timestamp and a random number), so it doesn't need to get a challenge from the server.


Retrieve message from rsa ciphertext based on some conditions

let \begin{equation}
x*y=m^{e+d-2} \mod n \qquad (1)
\end{equation}
\begin{equation}
m(x+y)=(m^{e}+m^{d}) \mod n \qquad (2)
\end{equation}taking $log_m $ for each from (2) side with respect to $\mod n$, we will have
\begin{equation}
log_mm(x+y)=log_m(m^{e}+m^{d}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)=log_m(m^{e})+log_m(1+\frac{m^d} {m^e}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)\ge log_m(m^{e})+log_m(\frac{m^d} {m^e}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)\ge e+d-e \mod n \qquad
\end{equation}
\begin{equation}
d\simeq  1+log_m(x+y)\qquad (3)
\end{equation}
substitute $(3)$ in $(1)$
\begin{equation}
x*y=m^{e+(1+log_m(x+y))-2} \mod n \qquad
\end{equation}
\begin{equation}
x*y=m^{e-1}m^{log_m(x+y)} \mod n \qquad
\end{equation}
\begin{equation}
m^{e-1}=(x+y)^{-1}(x*y) \mod n \qquad
\end{equation}


Are hashes only used to confirm data integrity when used for distributed ledgers?

Can hashes be used in other ways? For example, can a hash be used as an address to locate data?

Hashes of many kinds figure prominently almost everywhere in cryptography: stream ciphers, key derivation, message authentication, public-key signatures, public-key encryption, noninteractive zero-knowledge proofs, etc.  They are indeed sometimes used as an address for data in content-addressed storage systems like Tahoe-LAFS.

  Since a hash is only one way I am guessing someone cannot obtain the original data before hashing, which means a hash is only a confirmation that data is unaltered?

If a hash function $H$ is second-preimage-resistant, and you know $h = H(m)$, then it is hard for an adversary to retroactively find $m' \ne m$ such that $h = H(m')$ even if they know $m$.
If a hash function $H$ is collision-resistant, then it is hard for an adversary to actively find $m' \ne m$ such that $H(m') = H(m)$, which would enable them to hand you a benign message $m$ for you to review, and later substitute a malicious message $m'$ for it without anyone being any the wiser because the hash didn't change.

  If data in the past is altered, the current hash encompassing previous data will change, but where is the original hash to compare it to that lets a user know that a hash has changed? I am guessing the correct hash is held by a majority of people in the DLT?

This depends on the details of the protocol.  Nothing can be said in general.  But usually in a complex data structure like a Merkle tree or a blockchain (which is a kind of pathologically unbalanced Merkle tree), the current hash is calculated over some data together with the previous hash.


The master key has to be stronger in the sense that it's more sensitive than session keys.

The information used to derive session keys are not necessarily secret, so if it's easy to recover the master key, an attacker will be able to compute all the derived keys.

On the other hand, recover a single session key will not help you to recover the master key and so other session keys.

Thus, the effective security strength of the session keys is limited by the effective security strength of the master key.

Say you have:

$$K_{session, i} = \operatorname{KDF}(K_{master}, I)$$

where

$\operatorname{KDF}$ is a one way Key Derivation Function;
$I$ is non-secret key derivation information and
$K_{session, i}$ is a session key derived from a specific $I$.

It's not possible to recalculate $K_{master}$ from $K_{session}$ because the $\operatorname{KDF}$ is one way.

You can however brute force $K_{master}$ together with a known $I$ to derive any $K_{session, i}$.


Is Paillier a stream or block encryption

Stream Ciphers
A stream cipher produces key streams usually small sizes as bits (or bytes or words,...) that are x-ored with the message bits to produce the encrypted stream ( or call it the ciphertext). A stream cipher stores an internal state and updates it for the next output. They are also called state ciphers since the encryption depends on not only key and plaintext but also the state.
More formally; let $s$ be the state, $f$ is the next state function, $g$ is the function that produces the keystream $z_i$,  and $h$ is the function that produce encryption of $m_i$ with the key stream $c_i$.
\begin{align}
s_i &= f(s_i,k)\\
z_i &= f(s_i,k)\\
c_i &= h(z_i,m_i)
\end{align}
Block Ciphers
A block cipher operates on blocks and more formally it is a family of permutations. We need a mode of operation to operate on data; CBC, CTR, GCM, etc... There is no stored information inside the block cipher and they are called memoryless ciphers.
More formally: A block cipher with $b$-bit block size is a family of permutations;
$$E:\{0,1\}^b \times \{0,1\}^k \to \{0,1\}^b$$ where each key $k\in \mathcal K$ selects a permutation form all permutations of $\{0,1\}^b$
We expect that this family of permutations forms a Pseudo-Random Permutation (PRP).
Block vs Stream
The distinction is not clear when a mode of operation like CTR mode turns a block cipher into a stream cipher (normally CTR mode is designed for PRF, not for PRP). One, however, can see the real distinction is that if a cipher designed as a stream cipher then it has internal states.
Paillier
Pailler is neither a block cipher nor a stream cipher, it is a public key system in which you need two keys; the public key and private key.
In the Paillier cryptosystem, the encryption of $m$, $0 \leq m < n$ is performed with a public key $(n,g)$ as $c=g^m r^n \bmod n$, where $r \stackrel{R}{\leftarrow}\mathbb{Z}_n^*$.
The message is recovered wiht the private key ($\lambda,\mu$) as $m = L(c^\lambda \bmod n^2) \cdot \mu \bmod n$ where $L = \dfrac{x-1}{n}$.
Long messages with Paillier
If you want to encrypt long messages for a target $A$ with Paillier, then you can divide it into parts where each has at most length $<n$ end encrypt each target with the public key of $A$ with a new random $\lambda$ per block. The problem is tracking the order of the parts. It can be achieved either externally or internally. Externally is clear, internally you must leave some space for the tacking. Still, I will not call this block cipher. Can CBC like encryption be performed, yes and keep in mind to not reuse the $\lambda$
Turning into a stream cipher is also possible but has dangerous paths. Consider using as CTR mode. You need to select a nonce and a counter and encrypt it and then x-or the block with the output. If you omit the generate a new  $\lambda$ for each block, this is going to be a catastrophic failure.
Lack of
Still, there is no integrity and authenticity. The Paillier cryptosystem is malleable by design, remember public key encryption is free and the Paillier cryptosystem has additive and multiplicative properties. Therefore one needs at least HMAC.
Forget it
Remember, we don't use public-key cryptography for encryption, we prefer/advise using hybrid-cryptosystem like DHKE/AES-GCM. Public-key cryptography is slow compared to symmetric encryption. AES has tremendous speed with the hardware support and even GCM has, too. ChaCha20 is very fast even without hardware support. Stick to advice and use a hybrid cryptosystem.


Normal El Gamal is multiplicatively homomorphic: $E(x) E(y) = E(xy)$.

If you want to make it additively homomorphic, you fix some generator $g$; then you transform the integer $x$ to the group element $g^x$ before encrypting with El Gamal.  With this transformation, $E(g^x) E(g^y) = E(g^x g^y) = E(g^{x+y})$, so now you have an additive homomorphic property.

To decrypt, you need to be able to take the discrete logarithm.  This can be done efficiently if the value $x+y$ is known to be "not too large".

For a bit more of an overview of this approach to making El Gamal additively homomorphic, see the following question: Can Elgamal be made additively homomorphic and how could it be used for E-voting?.  Then, check out Why is the discrete log problem easy when the exponent comes from a binomial distribution? for details of specifically how to do the decryption, and how small the messages need to be to ensure you can decrypt in a reasonable amount of time.
In the future I encourage you to use the search function to check whether the question has been asked before.

If $x+y$ is usually so large that the above methods don't work, then you'll need a different cryptosystem; simple El Gamal isn't gonna work for you.  The Paillier cryptosystem might be a good choice.