Let $ALG_2$ be an algorithm that solves the RSA problem, can it solve the generalized Diffie-Hellman problem?

Suppose you had an algorithm $\operatorname{DL}(n, g, h)$ that, with probability $p$, successfully yields $x$ such that $h \equiv g^x \pmod n$.

Then you could define $\operatorname{FACTOR}(n)$ as follows:

Pick $g$ and $h$ uniformly at random.
Compute $x = \operatorname{DL}(n, g^2, h^2)$.

If successful, $h^2 \equiv (g^2)^x \equiv (g^x)^2 \pmod n$; hence $$n \mid (g^x)^2 - h^2 = (g^x + h) (g^x - h).$$

Fail if $g^x \equiv \pm h \pmod n$.

If not, then each of $p$ or $q$ must divide $g^x \pm h$ but not both.

Compute $\gcd(g^x \pm h, n)$.

This succeeds with about probability $p/2$—every quadratic residue $h^2$ has exactly four square roots modulo $n$, so there's only a 1/2 chance that $g^x$ is $\pm h$—and a handful of arithmetic.

Nobody has found a way to factor $n$ given an oracle to solve the RSA problem modulo $n$, so this suggests you're not likely to find a way to implement $\operatorname{DL}(n, g, h)$ in terms of your $\operatorname{ALG_2}(e, c, n)$ RSA oracle.  If you did, the editors of many reputable cryptography journals and conferences would like to hear from you!

This reduction breaks down if your DL algorithm works only for quadratic nonresidues.  On the other hand, if you it worked only for quadratic nonresidues, then you could probably use that to (somewhat inefficiently) solve the quadratic residuosity problem, and that might be publicationworthy in reputable cryptography journals; as far as I know nobody has found a reduction of RSA to QR or vice versa.


some of my confusions about DDH assumption

For the Legendre symbol and DDH: when working modulo a prime $p$, you can have have a group where DDH (apparently) holds. Namely, suppose that there is a known prime $q$ which divides $p-1$, and $g$ has order exactly $q$. This is easy to achieve if you generate $q$ first, then look for a prime $p = qr + 1$ for some random values of $r$; then, to compute $g$, take a random $h$ modulo $p$ and compute $g = h^r$ (still modulo $p$)(if you end up with $g = 1$, try again, but probabilities are very low of this occurring). It can be shown that $g$ is a square modulo $p$, which implies that $\left(\frac{g^a}{p}\right) = 1$ for all $a$.

In fact, the Legendre symbol is just a special case of a more generic method. Suppose that $g$ has order $n$, and $k$ is a non-trivial prime divisor of $n$. Then, given $g^a$ for some unknown $a$ modulo $n$, you can compute $(g^a)^{n/k}$, which will be one of the $k$ values generated by $g^{n/k}$. This reduces DDH to a group of size $k$; if $k$ is small then DDH becomes easy. The method with the Legendre symbol really is the case $k = 2$.

By choosing $g$ to have a prime order $q$ exactly, this method is fully countered, and DDH is hard again.

For groups where DDH is easy, but CDH is hard: the method above is only partial: it makes DDH easy in some cases, in that it can detect some situations where a given triplet $(g^a,g^b,g^c)$ is not a DH triplet ($c \neq ab$), but not all. To have a group where DDH is invariably easy, but CDH still hard, you need some more mathematics. The only known really practical solution (so far) uses pairings on elliptic curves. This requires choosing curves with some specific characteristics.


I couldn't reproduce the issue since you used some custom functions, but this works for me:

#include <openssl/bn.h>
#include <openssl/rand.h>
#include <stdio.h>

int main(void) {
    BIGNUM *test = NULL;
    unsigned char buffer[2048];
    FILE* fd = fopen("/dev/urandom", "r");
    fread(buffer, 1, 2048, fd);
    fclose(fd);

    test = BN_new();
    if (RAND_status() != 1)
        printf("Not enough entropy\n");

    RAND_seed(buffer, 2048);

    if (!BN_rand(test,2048,0,1))
        printf("Not enough entropy\n");

    printf("%s", BN_bn2dec(test));
    return 0;
}


Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation?

Clearing the lower 3 bits of the secret key ensures that is it a multiple of 8, which in turn ensures that no information, small as it may be, about the secret key is leaked in the case of an active small-subgroup attack.

The typical simple Diffie-Hellman key exchange works like this:

$$
\text{Alice} \xrightarrow{\hspace{3cm} a G \hspace{3cm}} \text{Bob} \\
\text{Alice} \xleftarrow{\hspace{3cm} b G \hspace{3cm}} \text{Bob}
$$

$a$ and $b$ are Alice and Bob's secret keys, and $G$ is the base point, which is $(9,\ldots)$ in curve25519. Alice computes $a\cdot bG$, Bob computes $b \cdot aG$, and the shared secret is derived by passing $abG$ through some key derivation function.

Now, as you have noticed, the order of $G$ is $p_1 = 2^{252} + 27742317777372353535851937790883648493$, whereas the number of points in the curve itself is $8 p_1$. This means that there are a few remaining points that have small order. An active attacker can, e.g., replace Bob's message $bG$ with a point of order $8$ and be able to find $a \bmod 8$ by inspecting following messages. When every valid secret key is $0 \bmod 8$, the attacker gets nothing.

One may argue that this wastes 3 perfectly good key bits to prevent an already ineffective attack. Notice, however, that the actual security of the scheme is tied to the order of the base point, $p_1 \approx 2^{252}$. Clearing those 3 bits (out of 255) does not reduce the keyspace since it still leaves 252 useful bits, giving roughly the same keyspace as the number of points generated by $G$.


Two different approaches for Key Expansion using the AES-256 algorithm?

The descriptions are the same thing.

The n and b constants on Wikipedia are simply the original key length in bytes and the number of bytes in the generated key schedule. Here, you have a 256-bit key generating a 60-word keyschedule, so n = 32 and b = 240.

I'm going to re-structure the provided algorithm to be more clear. The special case i mod 4 should be broken out as a separate block, I'll tweak the conditionals, and I'll reorder the cases to occur more sequentially.

if i mod 8 = 0:
    t = SubWord(RotateWord(W[i-1])) ^ RCon(i/4)
    W[i] = t + w[i-8]
else if i mod 4 = 0:
    W[i] = SubWord(W[i-1]) + W[i-8]
else
    W[i] = W[i-1] ^ W[i-8]

It's the same code, just written a little differently. It already looks more like the Wikipedia description.

The version here is word-based and uses the constant 8, whereas the Wikipedia version uses byte offsets and the variable n, which means it takes a bit of effort to compare computed offsets between them. Just in case it isn't obvious, note that W[i-8] here is equivalent to the frequently used phrase "four-byte block n bytes before the new expanded key" on Wikipedia.

Now compare the structure:

The first 8 words are a straight copy of the key.

Compare Wikipedia step 1 with the initial w[0] ... w[7] assignment here.
Both descriptions have a loop that generates the keys in sets of 8 words.

This is step 3 on Wikipedia. (The substeps there aren't numbered, but I'll refer to them as 3.x.)
The first word of each set of 16 has special processing.

Compare Wikipedia step 3.1 with the case i mod 8 = 0 here.

The t value in this step is the same as the "key schedule core" from Wikipedia. Note that the index value to RCon in the Key Schedule Core only increments once per loop. Here it increments 4 times per loop because it is a word-based counter, but we divide by 4 to re-normalize it.
The next 3 words have the simple definition: XOR the previous word with the word 8 words back.

Compare Wikipedia step 3.2 with the else case here.
The next word (the fifth of the round) has special processing. Compare Wikipedia step 3.3 with the case i mod 4 = 0 here. (Note that the i index here is zero-based, so i mod 4 = 0 means we're at an index of 5.)
The next 3 words have the same definition as two points above. Compare Wikipedia step 3.4 with the else case here.

That's all. They're the exact same thing, down to the step.


In "Lecture Notes on Cryptography" what does "PTM" mean?

As pointed out by hakoja in the comments:

  It means Probabilistic Turing Machine, see Section B.2.1.

where the following is written (emphasis mine, this is the full section B.2.1):

  Let $M$ denote a probabilistic Turing machine (PTM). $M(x)$ will denote a
  probability space of the outcome of $M$ during its run on $x$. The
  statement $z\in M(x)$ indicates that $z$ was output by $M$ when running on
  input $x$. $\Pr[M(x) = z]$ is the probability of $z$ being the output of $M$ on
  input $x$ (where the probability is taken over the possible internal
  coin tosses made by $M$ during its execution). $M(x; y)$ will denote the
  outcome of $M$ on input $x$ when internal coin tosses are $y$.


Yes, order of ciphers would matter in some practical scenarios, in particular if an adversary can subject the implementation to a DPA attack.

Consider the scenario where the same plaintext is encrypted several times using the same key, using some chaining mode other than ECB, a random IV, and the cipher in contact with the plaintext (on either the encrypting or decrypting side) is vulnerable to DPA. The known random IV allows recovering that cipher's key using standard DPA, and then a slight variant of DPA allows recovering the plaintext in all the subsequent blocks. It does not matter how the various ciphers are keyed, the plaintext can be short, but the key (of the attacked cipher) must be reused in many sessions.

Contrast that with the case where the cipher in contact with the plaintext is DPA-protected. Perhaps the others (in particular, the one in contact with the ciphertext, which is most exposed) can be broken, but (since the keys are independent), protection of the confidentiality of the plaintext remains at least as good a that of the cipher in contact with the plaintext.

Conclusion: if you must cascade block ciphers using truly independent keys for some reason (I can imagine an order from high-up, e.g. regulatory), and DPA is an issue, you want to put the one you are most confident with in contact with the plaintext. However if the ciphers share their key, that's the other way around: you likely want to put the most trusted one at the most exposed place, which is in contact with the ciphertext.

Update following Hunter's question: A situation where ciphers share their key would be a cascade of 3DES-CBC with 192-bit key (168 used), followed by AES-192, using the same 192-bit key for the two ciphers (a very poor choice when DPA attacks matter). Truly independent keys are chosen independently and randomly. Derivation from a single master key using a strong KDF is also fine if performed out of the reach of an attacker, assuming in particular no side-channel attack such as DPA can be mounted on the KDF.

Note: if the first encryption scheme in a cascade leaks information about the plaintext through the length of the ciphertext (e.g. has a built-in compression scheme), then the cascade might not be secure (as pointed in this comment to a related question). That does not apply in the context of the question, though.


NIZK Proof of knowledge N of M discrete logarithms (threshold)

A straightforward way to prove this when you can prove AND as well as OR statements about discrete logarithms is to take all the $K=\binom{M}{N}$ subsets $A_i=\{A_{i_1},\ldots,A_{i_N}\}$ with $N$ elements of points from the set of your $M$ points and prove the statement
$$PK\{(\alpha_1,\ldots,\alpha_N): \bigvee_{j\in K} \big( \bigwedge_{A_{j_i}\in A_j} A_{j_i}=\alpha_i P \big) \}.$$

If this proof verifies, then you convince the verifier that you know all $N$ discrete logarithms in one of the $K$ subsets of $N$ elements of all your $M$ discrete logarithms without revealing which one.

The idea of proving OR statements is due to Cramer et al.. Moreover, their result holds for arbitrary monotone access structures.

Non interactivity can be added as usual by using Fiat-Shamir and living with random oracles. This recent approach shows how you can use a related transform which does no longer requires programmable random oracles.


What is the lowest level of mathematics required in order to understand how encryption algorithms work?

Most encryption is based heavily on number theory, most of it being abstract algebra.  Calculus and trigonometry isn't heavily used.  Additionally, other subjects should be understood well; specifically probability (including basic combinatorics), information theory, and asymptotic analysis of algorithms.  There's also more math that's worth knowing to be a good programmer which is key if you really want to be an expert.  The number theory is more important with understanding asymmetric encryption, but does come up in symmetric encryption as well (e.g., in AES how to derive the S-box and MixColumns relates to understanding Galois fields).

First, you need to learn some notation.  Things like logical operators, most importantly for cryptography XOR (sometimes denoted as circle plus: ⊕), where 0 XOR 1 = 1 XOR 0 = 1, and 0 XOR 0 = 1 XOR 1 = 0.  It also helps to be able to understand the notation and language of abstract mathematics and set theory; e.g., {0,1}128 means the set of all strings that are made up of 128 binary digits (each digit is a 0 or 1).  Similarly, F: {0,1}64 → {0,1}128 means F is a function that maps a 64 bit input into an output that is 128-bit string.  You'll have to learn the difference between a function, bijection, permutation, etc, but again this is mostly just terminology of relatively simple concepts.

One of the most important topics is modular arithmetic.  E.g., 1 ≡ 64 (mod 21) where (mod N) means you only care about the remainder when dividing by N (since 64/21 = 3 with remainder 1; the modulo is 1).  One important notation to learn (that's a potential source of confusion) is that the (mod N) applies to both sides of the equation; so you could equivalently say 8^2 ≡ 1 (mod 21).  Many programming languages (e.g., C, Java, python, javascript) use % to do modulo division -- e.g., 64 % 21 gives 1.  The cool thing about modular arithmetic is that you can just do normal arithmetic (addition and multiplication) and reduce at the end (or at any step in the middle) as modular arithmetic forms a finite field; e.g., 8 ≡ 29 ≡ 50 (mod 21) so since 8*8 ≡ 64 ≡ 1 (mod 21) we also know that 29*8 = 232 ≡ 29*50 = 1450 ≡ 1 (mod 21).  With modular arithmetic there's no difference both 8, 29, 50 represent the exact same number.

You'll need to understand things like Fermat's little theorem, Euler's theorem (based on totient), Euclid's algorithm for greatest common denominators (specifically Euclid's extended algorithm to generate multiplicative inverses), Carmichael numbers, Fermat primality test, Miller-Rabin primality test, modular exponentiation, and discrete logarithms.

If you want to go further you may want to learn about things like finite fields (specifically Galois fields), polynomial rings, elliptic curves, etc.  This isn't meant to limit things; e.g., cryptography (and attacks on cryptography) aren't necessarily limited to these types of math.  E.g., NUTRUEncrypt is based on lattices/shortest vector problem, and the McEliece Cryptosystem is based on Goppa codes, but again you still need to learn the math above to be able to understand this math.

And then you have the basic math background to learn about cryptography, which isn't just the math but also involves using the math in secure ways.  (For example, textbook RSA c = m^e mod p q is insecure for a variety of reasons - you should use a secure randomized padding scheme to your message and likely combine with symmetric encryption for long messages).

Free Electronic References

The Handbook of Applied Cryptography - Chapter 2 has a decent introduction to these concepts for the advanced learner -- it introduces concepts very quickly and compactly, and is probably better as a reference or second/third attempt at the material.
Chapter 1 of Algorithms by DPV (specifically sections 1.2 to 1.4) give a gentler introduction to the math behind RSA.  (2015 Update: This pre-print of the book appears to be have taken off the one of the authors' academic website.  The good textbook is available for purchase on amazon.  I believe you can still find the book for free via google search for "Dasgupta  Papadimitriou Vazirani algorithms pdf", though I am not directly linking as I am not sure it is being shared by a copyright holder with authority to legally share the book.)
Shoup - A Computational Introduction to Number Theory and Algebra - From the preface "Number theory and algebra play an increasingly significant role in computing and communications, as evidenced by the striking applications of these subjects to such ﬁelds as cryptography and coding theory. My goal in writing this book was to provide an introduction to number theory and algebra, with an emphasis on algorithms and applications, that would be accessible to a broad audience."  Very detailed and fairly accessible.
Stick-figure introduction to AES at various levels of complexity with the last level showing where the number theory goes in.
The Udacity Applied Crypto course.  More of an introduction to the cryptography than the math behind it, but introduces the math when necessary.
Dan Boneh's Coursera cryptography course.  Solid introduction to cryptography, again introducing the math when necessary.


Different encryption standards and how they relate to auth and algorithms

PKCS#7 - Subsequently CMS, typically used for generating and verifying digital signatures.

I wouldn't go for 'typically' there. There are three main uses of PKCS7/CMS today:

signature on various kinds of data ranging from Java or Windows code to PDF documents
signature on and/or encryption of mail messages or attachments in S/MIME
as a container for certs and/or CRLs, as described in the Q you linked for PKCS12 (and others too)

I don't have numbers and I'll accept the first might be more common, but the others exist.

I understand digital signatures, calculate the hash [and] encrypt with the private key so you can verify, with the public key, that the message was not tampered with and that it came from the correct sender.

No. This is a commonly repeated mistake, but signatures are not 'encrypting with the private key' or 'encrypting backwards'. For RSA only, not other algorithms, there is a mathematical similarity which 30-ish years ago led people to use this description, but the actual signature and encryption schemes are vitally different, and more importantly differ semantically, so informed people no longer say this. See my growing list of Qs or As on this at https://security.stackexchange.com/questions/159282/can-openssl-decrypt-the-encrypted-signature-in-an-amazon-alexa-request-#159289 . As relevant here, compare any CMS even the earliest in 1999 which says SignerInfo.signature "is the result of digital signature generation, using the message digest and the signer's private key" and defines signature generation and verification to use private key and public key respectively but otherwise leaves them to other standards, versus actual PKCS7v1.5 which was redistributed by IETF in 1998 but actually published by then-RSALabs in 1993, which says SignerInfo.encryptedDigest "is the result of encrypting the message digest and associated information with the signer's private key" and in 9.4 essentially copies part of the then-current version of PKCS1.
It is true that digital signature allows the verifier to be certain that the data is untampered and is 'from' (or at least was seen/approved by) the party holding the private key, which should be unique (more below), and can (at least try to) verify that the signer is the 'correct' sender according to whatever criteria are relevant to that correctness.

I see that PKCS#7 can use AES, which is a symmetric key algorithm. Does this make sense, and if so is this common or how would that work?

Only for 'enveloped' (that is, encrypted) messages, not for signed messages or detached signatures; as I said above I don't have numbers on usage.

I was told to download a PFX file in order to authenticate with an API, similar to (link) ... how does that authentication work? I'm getting the private key and cert in the form of a .pfx file from the server, does that mean that the server is just self signing this and this is essentially mutual TLS using a self signed cert? If not, we then just be using TLS (so encrypted with the servers public key) with the message content being our payload signed with our private key?

This is very likely TLS with client authentication also called mutual authenication or just mutual TLS, yes. The certificate must be one that is trusted by the server(s) you connect to; this can be self-signed by the server, it can be signed by the server acting as a CA, or it can be obtained from some other CA which signs it. It doesn't matter to you as long as the result is trusted, although if you are curious you could look at the certs with any of the many tools that can look at a PKCS12/PFX, or a cert or several certs extracted from one.
TLS never encrypts data with the server's public key. TLS encrypts, and authenticates, data in both directions using symmetric algorithms with per session (and connection) 'working' keys which are created by 'key exchange' process during the initial handshake. See e.g. https://security.stackexchange.com/questions/20803/how-does-ssl-work/ for an extensive but slightly out of date explanation -- it hasn't been updated (yet?) for TLS 1.3 which was released in 2018 and is now becoming more and more common. The oldest and now mostly obsolete key exchange, called 'static' or 'plain' RSA, does encrypt the premaster secret using the server public key, but newer key exchanges (especially in 1.3) use Diffie-Hellman signed by the server private key and verified by the client with the server public key (from its certificate, after validation). Conversely, client auth in TLS always signs handshake data with the client private key and it is verified by the server using the client public key (ditto).

Similar for PKCS7. I completely understand how we verify the signature with the public key. How how do we handle the authentication if we are sending data across to some API (typically speaking)? Because technically once we have something that we have a digital signature, really anyone anywhere can send this, so how would we know it is being sent by a particular client or do we not care?

Creating a digital signature that will verify successfully requires using the private key, and the whole concept of public-key cryptography is that only the 'owner' has the private key; everybody else should have only the public key. Thus if a particular key belongs to client X, only client X can create signatures with that key. However in your example, where the server is apparently passing out PKCS12's containing private keys willy-nilly, which is not considered good practice, this guarantee is greatly weakened: it is definitely possible for that server and anyone else who gets a copy of 'your' PKCS12 to forge data (in this case connections) from 'you'. Although if your connections are to this same server, its ability to forge a connection doesn't matter too much, because it could just as easily lie about what it received on a legitimate connection.


Is Encryption without knowing the input directly possible at all?

What you're describing sounds a lot like mental poker.  That is, your Alice has a number of messages ("cards") that she wants to shuffle and deal to the other players, in such a way that she can prove to the other players that she does not know who got which cards.

Various protocols have been proposed for mental poker; see the linked Wikipedia article for some examples.  Apparently, there currently exists at least one practical and secure implementation of such a protocol.


The problem is small enough that the desired PRP can be implemented as a small array of 16 values initialized using the Fisher-Yates shuffle, with a pseudo-random generator deciding the indexes of the shuffles. That's probably the simplest, thus the best except perhaps when side channels (such as cache-induced timing variations) are a consideration.

Something NOT suitable is using a Feistel cipher with many rounds and a large random key defining the round functions: this is bound to generate an even permutation, thus only half of the $16!$ permutations would be obtainable. However this defect can be fixed by using 2-bit modular addition instead of 2-bit XOR to mix the output of the round functions: $R_{i+1}=((L_i+F(R_i,K_i))\bmod 4)$. This can be made constant-time, and also works nicely for permutations of $2^k$ elements with $k$ large enough to preclude the Fisher-Yates approach, which requires about $k\,2^k$ bits of memory.

The problem is well studied in Format Preserving Encryption, which offers a number of other techniques that remain suitable for much larger sets (contrary to Fisher-Yates), including some that exactly balance the odds of the resulting permutations (contrary to Feistel cipher with mixing by modular addition).


Is adaptive security the same as full security?

I don't know what you mean by "full security", but "adaptive" just means that the oracle queries from the attacker depend on the results of previous queries. In contrast, "non adaptive" means that the attacker simply makes all the queries in batch, that is, without adapting his queries from previous results.

Update: based on the paper from your comments, it seems that "full security" is opposed to "selective security". Both "full" and "selective" security are defined in Chapter 2.3.3 of that paper. According to that definition, both models are adaptive, since queries from Phases 1 and 2 are adaptive.


Is it better to encrypt before compression or vice versa?

Neither:

Encrypting first and then compressing does not work.
Compressing first can leak information about plaintext content through the ciphertext length, as poncho mentioned in comments to another answer.

Specifically, compression allows an attacker who can control parts of the message that is encrypted to reveal things about the other, secret parts, like cookies in the case of web traffic. It is most dangerous in a live protocol like TLS. Some forms of compression (e.g. truly constant bitrate lossy video/audio compression) may be immune to such attacks (but even then there might be side channel attacks due to the compression).

In most cases you should just encrypt the uncompressed data and be done with it.

Data storage and transmission is usually cheap enough. If you cannot live without compression, you must do it first, but then you have to really know what you are doing and likely accept at least some loss of security.


Questions regarding static Diffie-Hellman (ephemeral-static) usage in TLS

Preliminarily, your question and this answer only apply to TLS versions through 1.2. TLS 1.3 no longer has any static Diffie-Hellman, and also no longer has ciphersuites that include/determine the key-exchange and authentication method(s) at all.

  It is said that Alice and Bob publicly agree to use a modulus p and base g. As it turns out p and g are values in the certificate, so is it safe to say that p and g is always dictated by the server?

Depending what you mean by 'dictated', maybe. The server and/or its operator(s) may have been subject to constraints. It is possible to choose DH parameters (p,g[,q]) which are insecure, either by mistake (e.g. a bug) or deliberately/maliciously, and it is very difficult to detect that insecurity (especially if deliberate) by looking at the parameters.
To prevent this authorities sometimes require(d) use of pre-vetted and often standardized parameters, such as the DH groups created for IKE (IPsec) in RFC2409 and RFC3526, some of which are also used for SSH, or the recently-standardized groups for TLS (including 1.3) in RFC7919, and some people choose to use them even when not required.

The CA (and if applicable RA) that issued the certificate could be among those that impose constraints. Certainly some CAs do require certain sizes of RSA and DSA keys, and (standardized) curves for EC algorithms, and I recall hearing of some that required specified parameters for DSA.
Since I have never heard of any (real) CA issuing any DH cert(s) at all, it is entirely speculative what policies such a hypothetical, imaginary CA would have.

It is true however that the parameters are at least communicated or confirmed by the server to the client in the server's certificate in its Certificate message.

  What if client certificate is used ?

You said 'Assume that the client is not using certificate authentication' so it's not. If you change that assumption it depends what kind of key the client has certified.

If the client like the server has a cert for a DH key then that key must use the same parameters as the server's; see e.g. RFC5246 7.4.6. In that case the DH is actually static-static not ephemeral-static, and the ClientKeyExchange message is effectively empty; see 7.4.7.2.

OTOH if the client has (and the server requests/permits) a signing cert then the client still generates, sends, and uses an ephemeral key in the same fashion as without a cert, but signs the partial handshake (including ClientKeyExchange) with CertVerify; see 7.4.8.

  Continuing if the server sends its public component (is that really the server’s public DH key) and uses its private component (is that really the server’s private DH key?) what does the client do? Does it generate an ephemeral pub/private DH key pair on the fly and sends / uses its public key and private key in the same way as the server?

A DH keypair and both of its halves (private and public) is always relative to a set of parameters. Whether you view the keypair and/or keys as including those parameters, or simply being linked to them, is kind of philosophical. For comparison, this Q was assigned number 71581 by crypto.SX. It certainly is wrong to just call it question 71581, because there are lots of other questions in other places, including other Stacks, with the number 71581. But we could say this is question 71581 on crypto.SX, or this is crypto.SX question 71581 -- is one of those more correct than the other, and if so, why?

However, as Maarten explained in some detail on your previous Q, the designers of X.509 certificates (which TLS uses) chose to nominally separate those values: the parameters (for DH, at least p,g) are stored one place in the SPKI data structure, and the public key relative to those parameters, which is the constrained integer (or equivalently integer residue class) conventionally notated y or Y, is stored in a different though nearly adjacent place. But both/all parts must be present to use the key.

Coming back to Earth, the client either generates an ephemeral keypair (for the same parameters) or uses its certified, static keypair (for the same parameters) as answered above. For a static keypair it sends the Y value by sending the cert (which duplicates the parameters); for an ephemeral keypair it sends the Y value in the ClientKeyExchange message (and does not need to send the parameters). In all cases both peers do the DH computation using their own X and the peer's Y, and then proceed with the rest of the TLS key deriviation process.

  Continuing on the last question, does such a setup not provide PFS because the server uses static values ? If I record a 100 of TLS conversation in such a scenario, would the private DH key from the server allow me to decrypt all of them?

Yes. If the server uses a static key for key agreement, compromising it allows decrypting prior sessions which used that key. That is one reason these key exchange methods were practically never used in the protocols where they existed, and have now been removed. As an example OpenSSL did not implement any static-DH for decades, from its creation (as SSLeay) in the 1990s until 1.0.2 in 2014, and then removed it (along with static-ECDH) when the state machine was redesigned in 1.1.0 in 2016; during much of that time I subscribed to their support maillist and never saw a single question, request or complaint about this lack.
For completeness, forward secrecy is also lost if the client uses a static key, but that can only occur if client-auth is used which it rarely is even with key exchanges which are used unlike static-(EC)DH.


On Proving That a Primitive Does Not Exist

(Note that this attempted answer contains a significant amount of guessing and must not be considered reliable!)

If one assumes "there is a general reduction from $P$ to $Q$" to mean "existence of $Q$ implies existence of $P$" (which is up to interpretation since the authors do not clearly define that term, but it seems somewhat reasonable), then the statement in question is wrong: Under this assumption, it can be reformulated as

  If the existence of $Q$ does not imply the existence of $P$, then $Q$ does not exist.

...whose contrapositive

  If $Q$ exists, then the existence of $Q$ implies the existence of $P$.

is equivalent to "there is a reduction from $P$ to $Q$", and this is clearly untrue in general.

My best guess is, still under the assumption mentioned in the beginning, that this is a simple typo and they actually meant

  Note that to show that no general reduction from $P$ to $Q$ exists requires proving that $P$ does not exist

...which is true (and still conveys the point they are trying to illustrate) since its contrapositive

  If $P$ exists, then the existence of $Q$ implies the existence of $P$.

is obviously a tautology.


Would LWE problem be still secure if error were like this $e=2e_1$?

It will remain same. Here it will not effect the security because 2 is invertible in the prime q field. In case q is not prime then security will be compromised.


Significance of repetition in XOR cipher text

What is the significance of the repetition? Does it mean that a 6 character key was used and repeated across the same characters within $P_1$ and $P_2$?

I'm assuming your assumption about this being an xor cipher with the pad used twice for two ciphertexts.

It does not mean a 6 character key was used. A one time pad used twice could result in this behavior.

It means that the first 6 characters of the first plaintext xored with the first 6 characters of the second plaintext results in .81afg. Furthermore, the 2nd 6 characters of the first plaintext xored with the 2nd 6 characters of the second plaintext results in .81afg. We also know where the bits in the two plaintexts are equal and where they are different, but we don't know what the bits are.

Now that doesn't help much, does it. If I had to guess, though, I would guess that there is a 6 character sequence at the beginning of each plaintext that repeats 6 times. If this assumption is correct, then we know that the sequence changes between the encryptions (otherwise we'd get all 0's). Remember though that this is just a guess.


Which crypto libraries/programs do we have the most confidence in?

The question is subjective in nature, and this comment is also subjective. It was too long to leave as an actual comment so I'm posting it as an answer, although it isn't really an answer, it's a comment. This is for posterity, I guess -- this thread is already high in Google searches.

NaCl is probably the most widely respected library. It's authored by someone (Daniel J. Bernstein) with an established track record writing secure software and who understands a lot of practical and theoretical subtle security issues. It's also aimed at high-level use and encapsulates details when possible, as opposed to the more common library approach of just providing an open-ended generic API for a lot of cryptographic primitives. That makes NaCl harder to misuse, which is important since some vulnerabilities are simple innocent misuses of libraries. Few other libraries can make similar claims.

I think good audits are hard to come by. My general impression is that very few people are qualified to perform a good audit, and many of those who are qualified are only qualified to evaluate a few areas. What's more, the well-qualified are in high demand with other things and probably have minimal interest in taking the initiative on an auditing project. It isn't lucrative because a good audit:

takes a long time
is unlikely to pay much (probably nothing unless bug bounties or grants are involved)
unlikely to bring fame to the auditor unless they find something huge
is potentially a liability to the auditor if they miss something that is discovered later

So I don't think there's much incentive to drive high-quality audits.

Popular libraries/applications have had bugs sit unnoticed for a long time, which I think is evidence that audits are rare. History shows examples of bugs going unnoticed for a long time, sometimes even if when we know of them.

The Debian weak keys bug existed for over a year and a half before it was caught. The developer who made the mistake had even explicitly described his change on a public mailing list and asked if the change was secure (the question went unanswered). Let that sink in: A popular open-source library was used for 21 months with a somewhat obvious fatal mistake that was described on a public mailing list.
Look at the list of OpenSSL vulnerabilities (you can filter the more important ones) and use the release dates to match the earliest fixed version against the oldest known vulnerable version. The percentage that existed for 2 or more years before being discovered and fixed is impressive, several lived for over 4 years. Bugs are hard to find and often long-lived.
This isn't library-specific, but I think the lesson holds: The BEAST attack against TLS 1.0 exploited a theoretical vulnerability that had been published 9 years earlier (and fixed in the practically unused TLS 1.1). Even when we know of vulnerabilities, we sometimes don't fix them if it's inconvenient and the attack doesn't seem practical.

I picked on OpenSSL a bit there because it's very popular, open-source, and documented, which made it easy. (Worth noting that the source code is a mess, which probably doesn't encourage anyone to read it.) Other libraries have some similar patterns, and less popular projects may have misleading vulnerability lists because OpenSSL's vulnerabilities are popular when they show up and likely to get a CVE. Is a contributor for a less-popular project going to report every bug they fix, evaluate it as a potential vulnerability, and then file a CVE? I don't know.

In contrast, Truecrypt doesn't have a published list of vulnerabilities, and who knows what subtle fixes are going unreported (or reported under opaque names like "security fix #XYZ") in closed source libraries like Microsoft's. How can we get even a high-level assessment of their vulnerability histories?

My personal feel is that good audits are very hard, very rare, and the majority of auditing is done by the maintainers themselves. To me, the trustworthiness of a library is more centered around who maintains it than how popular (and supposedly more "eyeballed") it is.

Again, this is my general impression and is a subjective response that doesn't fully answer a subjective question.


How can I repeatedly prove I have data another has seen without sending the data and without the other storing the data?

I will just add few comments to the excellent answer and links provided by PulpSpy above which might help you getting the more correct paper from the pool of thousands of paper written in this area, both by theoreticians and practitioners.

If you want to have a proof that prove the possession of any bit of the data file, then the paper of Atienese et al. cited by PulpSpy doesn't work (they work for more practial scenario and are very fast). Naor and Ruthblum, actually, gave the protocol in The Complexity of Online Memory Checking for proving data possession at any granularity. They called it memory checkers. They also relaxed the notion of memory checkers to prove the result for something called authenticator, which can be seen in the same vein as the definition of Proof of Data Possession and Proof of Retrievability, first defined by Juels and Karlinski in Pors: proofs of retrievability for large files. Incidentally, both the papers came in the same conference, presented one after the other. The work of Atienese et al. was later shown to possess the stronger notion of Proof of Retrievability by Waters and Shacham in Compact Proof of Retrievability.

The literature for this problem is very old and Naor and Ruthblum has a very detailed literature survey in their paper. You may find the reference therein quiet useful. For recent works, there has been quiet a few works on this area.


How exactly is an enigma simulation software supposed to encrypt alphabets?

I guess you already figured it out but my guess is that you forgot to move the first rotor 1 step before starting the encryption. That also impacts what letter it arrives to on next rotor and so on.

The complete path is

KBD-A>SB>A - A>ETW>A - B>(1)R3>K - J>(2)R2>B - B>(3)R1>D - D>UKW>H
  - H>(3)R1>D - D>(2)R2>C - D>(1)R3>G - F>ETW>F - F>SB>F-light

Keyboard A arrives to plugboard (Steckerbrett) as A, leaves the plugboard as A, arrives to Entry wheel as A, leaves as A, arrives to the first rotor at level B, gets rewired to K and so on.
Typing 3 more "A" gives

 A>SB>A - A>ETW>A - C>(1)R3>M - K>(2)R2>L - L>(3)R1>V - V>UKW>W
       - W>(3)R1>R - R>(2)R2>G - I>(1)R3>V - T>ETW>T - T>SB>T  :T

 A>SB>A - A>ETW>A - D>(1)R3>F - C>(2)R2>D - D>(3)R1>H - H>UKW>D
    - D>(3)R1>B - B>(2)R2>J - M>(1)R3>C - Z>ETW>Z - Z>SB>Z  :Z

 A>SB>A - A>ETW>A - E>(1)R3>L - H>(2)R2>U - U>(3)R1>K - K>UKW>N
    - N>(3)R1>N - N>(2)R2>T - X>(1)R3>Q - M>ETW>M - M>SB>M  :M


Why approximately $2^{(n+1)/2}$ queries?  Because it makes the attack work.

As far as your final comment, it sounds like you are confusing $(n+1)/2$ with $2^{(n+1)/2}$.  If we use AES, then $n=128$, so $(n+1)/2=64.5$.  However, $2^{64.5}$ is a very large number.  The exact number of queries is not important as long as it is approximately $2^{64.5}$, and it is easy to choose an integer near that number.


You are confusing two different security notions.

The proof you describe is regarding the Onewayness under chosen-plaintext attacks (OW-CPA). Basically, this notion covers the idea that it shouldn't be possible for an adversary to decrypt a given ciphertext (i.e., encryption is one-way), even if he can encrypt chosen plaintexts. As the proof shows, ElGamal is OW-CPA secure under the Computational Diffie-Hellman (CDH) assumption.

However, you are asking about indistinguishibility (i.e., guessing if an encryption is for one message or another). That's a different notion (and actually, a much more relevant one). It can be shown that ElGamal is IND-CPA secure under the Decisional Diffie-Hellman (DDH) assumption, which is weaker than CDH. Your understanding is correct: if an adversary can break OW-CPA, then it certainly can break IND-CPA. In security we are actually interested in the contrapositive: if a scheme is IND-CPA, then automatically is OW-CPA.

Regarding the OW-CPA proof of ElGamal, you have to know that in the OW security game, the adversary does not choose the underlying message, but the challenger. That means that the challenger doesn't even have to know the actual underlying message for the challenge ciphertext (that's why it can output a random $Z$ for the ciphertext).

Now, if an adversary can break OW-CPA, it means that he is capable to decompose $Z$ into $m$ and $g^{ab}$, in order to output $m$. The challenger then uses the result from the adversary to compute $g^{ab}$ as $Z/m$. Note that each time the adversary outputs a correct $m$ (which happens with probability $\epsilon$), the challenger succeeds in computing $g^{ab}$, since for each random $Z$, there is always one $m$ such that $Z = m g^{ab}$.


Why is the complexity of RSA-1024 80 bit and not 86 bit?

Presumably, it's because they rounded it down to a nice round number of bits.  Nobody's going to use an 86.76611925028119 bit key in practice, but an 80-bit key is plausible.

Besides, the 86.whatever bit symmetric key length is only approximate, anyway: even using the GNFS, implementation details could easily swing it several bits either way, and of course, if someone finds a better algorithm to attack RSA then all bets are off.  All we can really say with any confidence is that, using the best algorithms publicly known today, cracking a 1024-bit RSA key is about as hard as cracking an 80 to 90 bit symmetric (e.g. AES) key.  Which is a pretty wide margin (adding 10 bits to the symmetric key length makes it about 1000 times harder to crack), but that just reflects how hard it is to estimate these things.

Actually, I think Reid already answered the first part of your question pretty well in his comment, so let me just quote him here:

  "First, directly evaluating asymptotic expressions is quite imprecise. But more importantly, the NIST is an administrative organization, and their purpose in that table was to define a set of key sizes for various primitives that give a specific level of security. The intent is that you might decide 112 bits of security is enough for your application, then use the key sizes/algorithms suggested in the table. So they picked commonly-used key sizes that were slightly above the desired security level. The extra margin also gives you a bit of leeway in terms of Moore's law."

As for your other questions, the $o(1)$ in the complexity formula for GNFS that you quoted is little-o notation.  Basically, it means that there's an unknown term there that tends to zero as $n$ tends to infinity.  Of course, the little-o notation, on its own, doesn't really tell us anything about how big the unknown term might be for any given finite value of $n$, but in practice, we may generally assume it to be negligible.

(Actually, the $o(1)$ term doesn't seem to appear in the reference cited by the Wikipedia article for the formula.  It might just be a mistake in Wikipedia.  Looking at the edit history of the article, it seems to have been inserted in this edit, which removed an earlier $O(\cdot)$ from around the entire expression.)

As for why it says "modulus size" instead of "key size", you're right that those two terms are often used interchangeably for RSA.  However, technically, an RSA key consists of two parts: the modulus $n = pq$ (which is common to the public and private keys) and either the public exponent $e$ or the private exponent $d \equiv e^{-1} \bmod n$.  Using the word "modulus" instead of "key" makes it clear that we don't want to include the length of those exponents (since they don't affect the difficulty of factoring the modulus) in the number, even though they're technically part of the key.


Does the use of English words weaken diceware passphrases

I don't believe that looking at the diceware phrase is very helpful.

Instead, look at it this way; there are $7776^7 \approx 2^{90.47}$ possible 7 word diceware phrases, and diceware will select one of those possibilities uniformly.

That means that the probability that one specific phrase is selected is at most $2^{-90.47}$.  Or, in other words, if someone were to guess random diceware phrases, he would make an expected $2^{90.47}/2 = 2^{89.47}$ guesses on average before hitting the right one.

  Is it not the case, however, that using English words in place of the underlying dice-throw numbers reduces the entropy of the passphrase.

No; there is a one-to-one mapping between diceware throw numbers and valid diceware phrases; one can take the phrase, and map it back to the throws that generated it.  And, a one-to-one mapping never effects the entropy.

What it does effect is the 'entropy-per-character' measurement; because the diceware phrase is (usually) lengthy, the 'entropy-per-character' measurement is a bit low.  However, we don't really care about the 'entropy-per-character', instead, we care about the security that the entire passphrase gives us.

Remember, the 'entropy of a passphrase' is a bit misleading; if we talk about entropy, we need to talk about the process that selected the passphrase.  In diceware, we have a very different process than if someone were writing some English text (and so the entropy estimates that may be valid for human generated English text do not apply to diceware generated texts)


calculating a group element in a discrete log problem

If you know the factorization of $b$, it's easy.  One way would be to compute $x^{-1}$, the multiplicative inverse modulo $\phi(b)$, and then compute $c^{x^{-1}} \bmod b$

If you don't know the factorization of $b$, it's hard; in fact, it's essentially the RSA problem.


Why is a CSR signed and which key is used for signing?

[Why] is the CSR istself signed?

The CSR is signed to ensure consistency of the data in it in a similar way to how root certificates are also self-signed. Additionally signing the CSR proves ownership of the private key corresponding to the public key in the CSR.

  [Which] key is typically used?

The private key which is associated with the public key embedded in your CSR.


No OFB_DRBG isn't directly vulnerable to attacks.

However from a theoretical standpoint there is one point speaking against it and in favor of CTR_DRBG.

Speed. CTR can be parallelized (can encrypt counters in parallel), OFB can't (encrypting state over and over again)

So the main reason is speed I'd guess and of course adding OFB_DRBG wouldn't have added anything to the portfolio, as CTR does the same job, but better.


Prepend information about encryption implementation to the stored data

This is fine. Be sure to verify all the values and include them when computing the MAC.


Why should the RSA private exponent have the same size as the modulus?

Well, first off, it appears that these requirements are a bit confused.  If the requirement is that for a given modulus $N$ and public exponent $e$, that the corresponding private exponent $d$ satisfies $d > N\!/2$, that rules out all public keys (!).  You can see that from the necessary and sufficient relation $de = 1 \mod \operatorname{lcm}( p-1, q-1 )$, and so if $d$ exists (which it will of $e$ is relatively prime to $\operatorname{lcm}(p-1,q-1)$), then there exists a $d > 0$ with

$$d < \operatorname{lcm}(p-1, q-1) = (p-1)(q-1) / \!\operatorname{gcd}(p-1, q-1) \\ \le (p-1)(q-1) / 2 < N\!/2.$$

So, what other interpretation can we give to this rule?  Well, one alternative is that you must use a private exponent $d > N\!/2$, even though it is not the smallest possible.  However, as such a $d$ always exists, that actually mandates no requirements whatsoever on either $N$ or $e$ or the generated signatures or encrypted messages, and so cannot affect the security of a generated public key.  In any case, when you're doing the RSA private operation, you generally use the CRT optimization, and so you don't actually use the value $d$ directly (and a larger than necessary value of $d$ would give you exactly the same CRT parameters).

The bottom line is that if you need to conform to these requirements, you'll need clarification on what the requirements actually are; the literal interpretation doesn't make sense.

Now, for your actual question: what is the purpose of this rule?  Well, the document does go on to give this justification (if I remember my French correctly):

  "Using specific private exponents (for example, small private exponents) to improve performance is forbidden because of practical published attacks in this area"

It appears that they are indeed worried about the published attacks against $d < N^{0.5}$, and possible refinements on that attack that might work for larger $d$.

As for the probability that a random public key will yield a small value of $d$, well, it turns out to be quite unlikely (if $e$ wasn't chosen specifically to make $d$ small).  The easiest way to see this is to assume a modest $e$ (for example, 65537), and note that

$$d \cdot e > \operatorname{lcm}(p-1, q-1)$$

and hence

$$d > \operatorname{lcm}(p-1, q-1)/e \approx \frac{N}{e \cdot \gcd(p-1, q-1)}.$$

Hence, $d$ cannot be small unless $\gcd(p-1, q-1)$ is large; that is, if $p-1$ and $q-1$ share a large common factor.  Because the probability of $\gcd(p-1, q-1) > k$ is $O(1/k)$, this means that in practice, a small $d$ never happens by chance.

Lastly, it isn't quite true that with other standards, there's no check on the value of $d$.  For example, FIPS 186-3 does have the requirement that $d > 2^{\mathit{nlen}/2}$.


No, there is no known way to achieve what's asked.

SHA-256 is a Merkle-Damgård hash using a compression function built per the Davies-Meyer construction. Assuming the known input fits 55 bytes (that is, can be expressed as at most 110 hex characters, which either matches the question, or is close to that), it is padded into a single 512-bit block $B$. What's asked amounts to finding 256-bit $I$ with $E_B(I)\boxplus I=H$ where $E$ is a 64-round 256-bit block cipher having 512-bit key $B$, $H$ is the 256-bit desired output, and $\boxplus$ is 256-bit addition without carry across 32-bit boundaries. For an idealized cipher, there's demonstrably nothing better than brute force to solve this problem, and we do not know a significantly better method for the particular cipher used in SHA-256.

For larger input, what's asked seems to require breaking that same problem except for a different (or a few different) values of $H$ obtained by breaking the second and possibly later round(s), thus is likely not much easier (rather, slightly harder). And provably, if we could break the multi-rounds problem in general, that would allow to break the one-round problem with about the same work.


Let's make it slightly simpler by proving the case of two variables with no tuple indexing to clutter it up.  Fix two random variables $X$ and $Y$.  Is $H_\infty[X] \leq H_\infty[(X, Y)]$?

For each $x$, we have $$\Pr[X = x] = \sum_y \Pr[X = x, Y = y].$$  Note that since probability masses are always positive, $\max \Pr[\cdots] \leq \sum \Pr[\cdots]$; then the sense will get reversed because $p \mapsto -\log p$ is a decreasing function:

\begin{align}
  H_\infty[X]
  &= -\log \max_x \Pr[X = x] \\
  &= -\log \max_x \sum_y \Pr[X = x, Y = y] \\
  &\leq -\log \max_x \max_y \Pr[X = x, Y = y] \\
  &= -\log \max_{x,y} \Pr[X = x, Y = y] \\
  &= H_\infty[(X, Y)].
\end{align}

Then to prove that $t \mapsto H_\infty[(Z_1, \dots, Z_t)]$ is increasing, take $X = (Z_1, \dots, Z_t)$ and $Y = Z_{t+1}$.


AES s-box – How do I calculate the inverse of this field equation?

In a finite field, there are basically two main algorithms to compute an inverse:

The Extended Euclidean Algorithm, also known as as "extended GCD". There is a variant called Binary GCD. In a finite field of characteristic 2, where addition is bitwise XOR, the binary GCD is easier to implement.
Fermat's little theorem, which is easily generalized: if the field order is $n$ (in your case, $n = 2^8 = 256$), then the inverse of $x$ is $x^{n-2}$, because $x x^{n-2} = x^{n-1} = 1$. This holds because in a field of order $n$, the invertible elements are a multiplicative group of order $n-1$, thus exponentiation by $n-1$ must yield the multiplicative neutral element $1$.

If you already have a multiplication function (mul()), then the exponentiation can be done in relatively few calls to that function. For instance:

static inline unsigned
invPow(unsigned x)
{
        unsigned x2 = mul(x, x);
        unsigned x3 = mul(x, x2);
        unsigned x6 = mul(x3, x3);
        unsigned x12 = mul(x6, x6);
        unsigned x15 = mul(x12, x3);
        unsigned x30 = mul(x15, x15);
        unsigned x60 = mul(x30, x30);
        unsigned x120 = mul(x60, x60);
        unsigned x126 = mul(x120, x6);
        unsigned x127 = mul(x126, x);
        unsigned x254 = mul(x127, x127);
        return x254;
}

In this C function, variables are named out of their contents: x60 contains $x^{60}$. Also note that invPow() returns $0$ for an input of $0$: zero does not have any inverse, but the AES specification formally says that when computing that operation, we use zero as its own "inverse".

Now this will hardly be efficient. You could first precompute a table of inverses, but that would be a look-up table, that you want to avoid.

An optimization is to use a tower of fields: the finite field of size $256$ can be defined as an extension of degree $2$ over the finite field of size $16$. This was described in a succinct note by Rijmen, and allows computing inverses in $\mathbb{F}_{256}$ by doing the relatively simpler task of computing inverses in $\mathbb{F}_{16}$. If you go down that road, you will want to read this article by Boyar and Peralta, who describe the currently best known implementation of the AES S-box in terms of logic gates.

Going down to logic gates is expensive in software, since this means doing more than a hundred boolean operations for each S-box invocation. However, such techniques offer considerable speed-ups if used with bitslicing, especially on machines with large registers. The Käsper-Schwabe implementation is well-known, using 128-bit SSE2 registers. Other similar implementations, using only 32-bit or 64-bit registers, can be found in BearSSL (which also handles the case of the reverse S-box, which is needed for decryption with AES/CBC; the Käsper-Schwabe code supports only the forward S-box, since they target only AES/CTR).


Should Increment functions be near-constant time?

Actually, Maarten isn't quite correct; in most cases, the counter doesn't have to be updated in constant time (because it's not secret); however in one case it does: GCM with an IV size that's not 12 bytes.

The reason the counter needs to be secret in this case is not because how it is used, but how it is generated.  It is initialized to $GHASH_H(IV||0^{s+64}||len(IV))$; if the attacker can learn the lower bits of this value (based on whether or not an internal carry has occurred), he can gain information on the internal value of $H$, and if we can fully recover that, then he can forge.

In this (admitedly obscure) case, it would be wise to fully disguise whether the carry occurred.  Here is some code that should be safe on most processors to do that:

void IncrementCounterByOne(byte *inout, unsigned int size)
{
    for (int i=int(size-1), carry=1; i>=0; i--) {
        int t = inout[i] + carry;
        inout[i] = t & 0xff;
        carry = t >> 8;
    }
}

It runs slower than your code (because it reads and writes every byte); however it avoids data dependent operations (on most CPUs and compilers)


Do you mean that if you have a key of length $l$ say $k_1, ..., k_l$, and a plain $m_1, ..., m_n$, that you want to do $c_i = m_i + \sum_{j=1}^l k_j$ ? (Each plain letter is added with each key letter)

If this is the case, this is exactly like doing a Caesar cipher with 1 shift for all of the letters.


I don't know where you get that the central element can not be $1$, because the Cardan grille does not have any special "requirements" as you're implying. In the original version, a piece of cardboard has several holes cut in it (= the grille) and when it is placed over an innocent looking message, the holes cover all but specific letters spelling out the secret message.

Simpler put: the holes you are cutting, identify the letters of the secret message. The other parts (which are covered) are the text to be ignored.

Let me give you a hint by providing you with a practical example…

The harmless looking, to-be-transmitted message could read:

ALL THOSE TEENIES ARE CRAZY KIDS!

and (taking your boolean $1$ and $0$ approach) the grille could look like this:

100010000010000000100010000010001

then the hidden message would be readable by applying the grille like this:

ALL THOSE TEENIES ARE CRAZY KIDS!
100010000010000000100010000010001
A...T.....T.......A...C.....K...!

ATTACK!

That's all that's to it. So, there are no other requirements but the obvious one: if someone puts the grille on your text, only the hidden message should be readable…

In other words (and to answer your question by the letter): the only requirement of the grille is to have "holes" where the hidden message's letters, numbers, and/or symbols are located, so that when the grille is applied to a harmless looking message (like a letter or book page), the hidden message is the only thing that remains visible because everything else is covered by the grille.

You might want to check Wikipedia's related article if you need another, more classical example.

EDIT

Looking at your edit, it becomes obvious that there's an additional step you're talking about... meaning we're indeed not talking about a pure "Cardan grille". A pure "Cardan grille" would not touch/change the text the grille is applied to. It's just a paper with holes showing you what letters of the plaintext are the secret message.

The rotating matrix your latest edit shows is something completely different. It could be called a grille cipher, but it's definitely not a Cardan grille… it could be a derived Fleissner grille (also known as "turning grille"), but I would need to be able to check the article you've been reading (see my link-request). It could well be that the article you've been reading talks about multiple grille cyphers; maybe even a combination of them. Until I've read that article , I can only guess… Fleissner grille.

If it's a Fleissner grille (or derivate), you might want to look at this related PDF which explains them (as well as attacks on it). Besides that, this website practically explains the Methods of Transposition as used in the Turning grille, including the center symbol thing you've noticed and are asking about.

You'll notice this image of a turning grille in action also has that 3x3 matrix in it's inner ring.

As for the 3x3 matrix itself, it's logical that if you rotate it around the middle, the symbol at the center will not move/change. Yet, I expect that what your edit shows is just part of multiple steps of remixing the 3x3 matrix. Otherwise, you're indeed correct - the non-changing center symbol would be one of the weakest parts of the matrix-mixing process.

As for the requirements of mixing, rotating and shifting a matrix… that is defined by the individual cipher implementation, not via generalized rules that apply to every cipher.


what is SALSA20 Nonce and its requirements

The treatment of nonces is the same for most stream ciphers, they only differ in length. In the case of Salsa20 the nonce is 64 bits, and there is a related cipher XSalsa20 which extends the nonce to 192 bits.

The caller/application provides the nonce. Typically the protocol or file format you're implementing specifies how to treat the nonce.

The essential property you need to ensure is that you never reuse a (key,nonce) pair.

Sometimes you use a counter, for example the message number in a network protocol. This counter can be used to prevent replay attacks.
Sometimes you use a random value which is convenient when you want to avoid state. But that requires XSalsa20 not Salsa20, since to be likely unique a random value should have 128 bits and Salsa20 only has a 64 bit nonce.

An addition warning if you're using the asymmetric box function: Both directions (A->B and B->A) generate the same XSalsa20 key so a nonce used in one direction must not be reused in the other direction. Typically that's achieved by either using different keys for both directions or by use non overlapping nonce spaces.


There is a simple way based on repeated linear interpolation, known as the Shannon-expansion.
With this you can extract the ANF expression from any black-box map function (for example, an S-Box) using on the order of $2^n$ evaluations for an $n$-bit Boolean function. It's slow but remarkably simple. I will demonstrate using $2$-bit function.
$$f(x_0,x_1)$$
can be expanded in the first bit
$$\small{f(x_0,x_1) = f(0,x_1)(1-x_0) \; + \; f(1,x_1){x_0}}$$
and then again in the second bit
$$\small{f(x_0,x_1) = f(0,0)(1-x_0)(1-x_1) \; + \; f(0,1)(1-x_0)x_1 \; + \; f(1,0){x_0}(1-x_1) \; + \; f(1,1){x_0}{x_1}}$$
Repeating this with larger functions, the pattern becomes clear. The $k$th term in this expression simply multiplies $\small{f(x)}$ with either a $x_i$ or $\small(1-x_i)$, depending on the setting of the bit in the input to the map function.
So for a larger Boolean function, the first term would be
$$\small{f(0,0,0,0,\ldots,0) = (1-x_0)(1-x_1)(1-x_2)(1-x_3)\ldots(1-x_n)}$$
and the final term would be
$$\small{f(1,1,1,1,\ldots,1) = x_0 x_1 x_2 x_3\ldots x_n}$$
The ANF can then be derived from this expression by multiplying out the parenthesis. This is laborious by hand, but a small amount of code in a computer program.
Here is the idea implemented in C++
#include <iostream>
#include <vector>

/* black-box map function to extract ANF */
int map(int x) {
  int sbox[] = {0x01, 0x0a, 0x04, 0x0c, 0x06, 0x0f, 0x03, 0x09, 0x02, 0x0d, 0x0b, 0x07, 0x05, 0x00, 0x08, 0x0e};
  return sbox[x % 16];
}

int num_input_bits = 4; /* number of map input bits to consider */
int num_output_bits = 4; /* number of map output bits to consider */

/* (1-x_0)(1-x1)x_2 = x_2*(1 + x_0 + x_1 + x_0*x_1) */

int main() {
  /* step 1) calculate ANF of the map function */
  int num_input_states = 1 << num_input_bits;
  for (int i = 0; i < num_output_bits; ++i) {
    std::vector<int> anf(num_input_states); /* accumulate ANF here */
    for (int j = 0; j < num_input_states; ++j) {
      int bit = (map(j) >> i) & 1; /* extract map output bit */
      if (bit == 1) {
        for (int k = 0; k < num_input_states; ++k) { /* "broadcast" result to ANF terms */
          if ((j & k) == j) { /* does this bit contribute to this ANF term? */
            anf[k] = (anf[k] + 1) % 2;
          }
        }
      }
    }
    /* step 2) print the ANF expression */
    std::cout << "y_" << i << " = ";
    int term_count = 0;
    for (int j = 0; j < anf.size(); ++j) {
      if (anf[j]) {
        std::cout << (term_count++ != 0 ? " + " : "");
        size_t factor_count = 0;
        for (int k = 0; k < num_input_bits; ++k) {
          if ((j >> k) & 1) {
            std::cout << (factor_count++ != 0 ? "*" : "");
            std::cout << "x_" << k;
          }
        }
        if (factor_count == 0) {
          std::cout << "1"; /* empty product */
        }
      }
    }
    if (term_count == 0) {
      std::cout << "0"; /* empty sum */
    }
    std::cout << std::endl;
  }
  return 0;
}

Which outputs the ANF representation of your S-Box:
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


Generate fixed length cipher text from arbitrary length plaintext

That is quite impossible. Lets assume that such an encryption scheme would exist and assume that it always outputs ciphertexts of length $n$ bits.

Then, because the scheme is assumed to encrypt plaintexts of arbitrary length, it in particular encrypts all plaintexts of length $n+1$ to ciphertexts of length $n$.
However, there exist twice as many plaintexts of length $n+1$ than ciphertexts of length $n$. So by the pigeonhole principle there exists at least one ciphertexts that encrypts more than one plaintext. This directly implies, that decryption would be impossible in such a scheme.


Performance of ECDSA, ECKCDSA and ECGDSA

If you want to know practical measurements, which depend not just on the signature scheme family but also on the choice of curve and so on, your best approach will be to submit the software you are considering using to eBATS, unless you are also concerned with specific hardware not represented there in which case you're in a better position to do your own measurements than anyone else.

That said, we can estimate costs of the arithmetic required for straightforward implementations of these signature schemes.  Let $B$ be the standard base point in the curve group in question, $n$ its order, and $A$ another curve point serving as public key, with $A = [a]B$ for secret $a$ known only to the signer.

Verification.
The verification equations for a signature $r, s \in \mathbb Z/n\mathbb Z$ on a message $m$ (and certificate hash $h$ in ECKCDSA) are:

ECDSA: $r \equiv x\bigl([H(m)\,s^{-1}] B + [r s^{-1}] A\bigr) \pmod n$
ECGDSA: $r \equiv x\bigl([r^{-1} H(m)] B + [r^{-1} s] A\bigr) \pmod n$
ECKCDSA: $r = H\bigl(x\bigl([r \oplus H(m, h)]B + [s]A\bigr)\bigr)$

(I'm omitting details of checking the ranges of $r$ and $s$, rejecting zero, etc.  If you run with the scissors included in this post and you stab yourself to security death, it's your fault, not mine!  Consult the standards for what you need to pacify auditors.)

It is hard to imagine that verification performance would be different between comparable implementations of ECDSA and ECGDSA, because you can trivially express one as the other with different parameters.  The ECKCDSA verification equation involves an extra hash, but that is likely to be negligible compared to the cost of the inversion it avoids altogether.

Signing.

Here $k$ is a scalar modulo $n$ chosen uniformly at random.  I'm omitting all the details of fenceposts required by the procedure in the standards, and the additional step of verifying the signature after generation to confirm no faults.

ECDSA: Compute $r = x([k]B)$; $s$ must be a root of $H(m)\,s^{-1} + r s^{-1} a - k$ modulo $n$, so compute $$s \equiv k^{-1} (H(m) + r a) \pmod n.$$  Thus, the cost is

1 elliptic-curve scalar multiplication,
1 inversion modulo $n$ to compute $k^{-1}$,
2 multiplications modulo $n$ to compute $r a$ and $k^{-1} (H(m) + r a)$, and
1 addition modulo $n$ to compute $H(m) + r a$.

ECGDSA: Compute $r = x([k]B)$; $s$ must be a root of $r^{-1} H(m) + r^{-1} s a - k$ modulo $n$, so compute $$s \equiv a^{-1} (k r - H(m)) \pmod n.$$  The substantive difference from ECDSA is that the element we must invert is the long-term secret $a$, so we can just store $a^{-1}$ rather than recompute it, rather than the per-signature secret $k$.  Thus, the cost is

1 elliptic-curve scalar multiplication to compute $[k]B$,
2 multiplications modulo $n$ to compute $k r$ and $a^{-1} (k r - H(m))$, and
1 addition modulo $n$ to compute $k r - H(m)$.

ECKCDSA: Compute $r = H(x([k]B))$; $s$ must be a root of $r \oplus H(m, h) + s a - k$ modulo $n$, so compute $$s \equiv a^{-1} (k - r \oplus H(m, h)) \pmod n.$$  Once again, we invert the long-term secret rather than the per-signature secret, so the cost is

1 elliptic-curve scalar multiplication to compute $[k]B$,
1 multiplication modulo $n$ to compute $a^{-1} (k - r \oplus H(m, h))$, and
1 addition modulo $n$ to compute $k - r \oplus H(m, h)$

(and 1 $\lceil\log_2 n\rceil$-bit xor to compute $r \oplus H(m, h)$, which should be negligible).

Cost of inversions.
How much does an inversion cost versus a multiplication or an addition?  Usually inversion will be computed using Euler's theorem with square-and-multiply exponentiation in Montgomery form.  This costs $\ell + w$ multiplications into $2\ell$-bit integers, $\ell$ squarings into $2\ell$-bit integers, and $2\ell + w$ additions into $\ell$-bit integers for the Montgomery reductions, where $\ell = \lceil\log_2 (n - 2)\rceil$ is the length of $n$ in bits and $w$ is the Hamming weight of $n - 2$, plus a little more to get the Montgomery multiplication started.

So outside the elliptic-curve scalar multiplications, inversions dominate the time spent, and there is probably a measurable difference to be had by avoiding them.  Could you do better than generic square-and-multiply exponentiation using a custom multiplication chain?  Yes, but unless $n$ has a very special form (which is hard to imagine!), inversion would still dominate.  Replacing one multiplication by an xor in ECGDSA vs. ECKCDSA?  Probably not going to matter to you.

Could you do ECDSA without per-signature inversions?
Yes: you could swap the rôles of $r$ and $s$ and effectively get ECGDSA and nobody would be any the wiser, except for the auditors hired to study your software who crash your party wondering why you aren't following the letter of the bureaucratic government standard mandating a wacky bizarro variant of Schnorr signatures with unreasonably slow signing procedures.

Inversion-free alternative.
May I interest you in the Schnorr-based EdDSA, which avoids inversions altogether for signing and verification, and is widely available in high-quality software running in constant time with defense against broken random number generators at signing time?

(Schnorr's patent expired a while ago, so you don't have that excuse to hide behind any more!)


Efficiently computing the neutral element in a ring isomorphic to Z/NZ?

This is a spectacularly ambiguous, poorly-posed question, so I'm going to instantiate it in a way that I find interesting.  If this wasn't the question you wanted answered, then edit your question to do a better job of asking a well-formed question.

$\newcommand{\tri}{\mathbin{\triangle}}$
I'm going to assume we are given an integer $N$ of unknown factorization, and we have a representation of elements of $\mathbb{Z}/N\mathbb{Z}$ as bit strings, via some representation function $[\cdot] : \mathbb{Z}/N\mathbb{Z} \to \{0,1\}^*$.  Thus, $[x]$ is the representation of $x \in \mathbb{Z}/N\mathbb{Z}$.  Define the operations $\triangle,*$ so that $[x+y] = [x] \tri [y]$ and $[xy] = [x] * [y]$.  Or, in other words, define $\tri$ by $s \tri t = [\langle s \rangle + \langle t \rangle ]$ where $\langle \cdot \rangle : \{0,1\}^* \to \mathbb{Z}/N\mathbb{Z}$ is the inverse map of $[\cdot]$, and similarly for $*$.

(In terms of the original question, the bit strings play the role of the ring $S$.)

Suppose we are given the following abilities (and only these abilities):

We have a black box that, when invoked, will generate a random element $r$ in $\mathbb{Z}/N\mathbb{Z}$ and output $[r]$ (it won't tell us $r$, though).
We have a black box that, when given $s,t$ as inputs, will output $s \tri t$.
We have a black box that, when given $s,t$ as inputs, will output $s * t$.

The question becomes: can we compute $[1]$, a bit string that is the representation of $1 \in \mathbb{Z}/N\mathbb{Z}$?  In other words, we're looking for a generic algorithm that will work correctly no matter what representation map $[\cdot ]$ happens to be chosen.

And the answer is: no, there is no efficient algorithm to compute $[1]$, given only these operations.  This can be shown, using the same techniques used to show lower bounds in generic black-box groups, e.g., the same techniques used to show that there is no polynomial-time generic algorithm for the discrete log in a generic group.

How do we show it?  I'll start by illustrating a proof, for the case where we are only allowed to invoke the first black box once: we can generate a single random value $[r]$, and then we can apply $\tri,*$ polynomially many times.  Here's the proof.  Let $x_0=r$, and let $x_i$ denote the $i$th element of $\mathbb{Z}/N\mathbb{Z}$ that we compute.  For instance, if our algorithm takes $[r]$ and computes $s = [r]\tri [r]$ and then computes $t = s*[r]$ (say), we'll have $x_0=r$, $x_1=r+r$, $x_2=x_1x_0$.  Say that the algorithm runs for $k$ steps.  For the algorithm to be correct, we need it to output $[1]$, or in other words, we need to have $x_k=1$.  Notice that each $x_i$ can be expressed as some polynomial of $x_0$, say, $x_i=p_i(x_0)$ (this can be proven by induction).  So our algorithm corresponds to a polynomial $p_k(\cdot)$.

If the algorithm is correct, we must have $p_k(r)=1$ with high probability over the random choice of $r$.  Is this possible?  It turns out that this is not possible, if $k$ is not too large and if $N$ is hard to factor.  In particular, if $\Pr_r[p_k(r)=1]$ is large, then we get an algorithm for factoring $N$ with $k$ steps and with a non-trivially large success probability.  Here's why.  Define the polynomial $q(\cdot)$ by $q(x)=p_k(x)-1$.  By assumption, $\Pr_r[q(r)=0]$ is large, i.e., the polynomial $q(x)$ has many roots.  On the other hand, it can't have too many roots: it has at most $k^2$ roots, by a simple application of the Chinese remainder theorem, so if $k$ is smaller than $\sqrt{N}$, $\Pr_r[q(r)=0]$ is large but strictly smaller than $1$.  Now suppose $N=PQ$, and consider the polynomials $q(x) \bmod P$ and $q(x) \bmod Q$.  Notice that

$$\Pr_r[q(r)=0] = \epsilon_P \times \epsilon_Q$$

where $\epsilon_P = \Pr_r[q(r)=0 \pmod P]$ and $\epsilon_Q = \Pr_r[q(r)=0 \pmod Q].$

Since the left-hand side ($\Pr[q(r)=0]$) is large, then both right-hand side terms ($\epsilon_P,\epsilon_Q$) must be large.  In particular, $q$ has many roots modulo $P$ and many roots modulo $Q$.  So, here is an efficient algorithm for factoring $N$. We pick $r$ randomly, compute $q(r)$, and then compute $\gcd(N,q(r))$.  Notice that this outputs a non-trivial factor of $N$ with probability $\epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P)$.  Since $\epsilon_P \times \epsilon_Q < 1$ but both $\epsilon_P,\epsilon_Q$ are large, it follows that $\epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P)$ is large, i.e., this algorithm for factoring $N$ has a large success probability.

So this is a reduction which shows that any efficient solution to this problem immediately yields an efficient algorithm for factoring.  As a consequence, we should not expect any efficient solution to this problem (since we don't expect there to be any efficient algorithm for factoring).  The reduction is tight, since I have shown in the comments that if you can factor $N$, then it is easy to solve this problem.

Technically, I only proved the result for algorithms that make just one call to the first black box (the one that generates a random value $[r]$).  However, this proof technique can be extended to algorithms that make any feasible number of calls to the first black box, by looking at multivariate polynomials instead of univariate polynomials.  These are basically the same techniques used to show that there is no generic algorithm for the discrete log (in generic/black-box groups) that runs faster than square-root time.


How was the AES MixColumns matrix constructed?

Any full rank $n \times n$ circulant matrix $A$ with all entries nonzero generates an MDS code. The entries here were picked for efficient fast multiplication, as far as I can recall.

Do refer to the book suggested by @SEJPM for more.


How to generate the exact AES key in both client and server side?

There are two main ways to have the same symmetric key on both parties:

key exchange using asymmetric crypto
generate the key from a known secret (eg: a password), such as using a password-based key-derivation function

The former is what you will find in TLS, where public key infrastructure is used to verify the other party's public key.
The latter is used in things like command-line encryption tools to derive a symmetric key from a password (and salt).
If you wish to setup a secure communications channel, your first choice should be TLS unless you have a very good reason not to use it.


If what the program does is "take your password, use that as-is as the key to a (modified) RC4 encryption algorithm, and use that keystream to decrypt the entire file", well, there is no obvious weakness to take advantage of.  Partial information doesn't help you much (for that matter, they could have given you the entire decrypted file, and it wouldn't help you to recover the key -- RC4 is pretty good at hiding that information).  As for the S[i] = 0xFF - i modification, well, there's no obvious weakness that causes.  At worse, that would change how certain related key attacks would work; since related key attacks do not appear to be relevant here, that is unimportant.

So, you can obviously do brute-force on the password, but unless the password is only a couple of characters long (or they give more clues about it), that's not likely to yield a result.

Hence, the obvious question is "is that a true representation of the challenge"?  Or, do they (say) reset the RC4 algorithm periodically (rerunning the Key Setup Algorithm from the original key)?  Do they stir in something when they reset the algorithm?

BTW: as for WEP, they don't use the same IV+Key to encrypt multiple packets.  Instead, they use different IVs (and the same key), and just concatinate they two when forming the key they give to RC4.  Because the RC4 Key Setup Algorithm doesn't do a great job of hiding information and so leaves some correlations between the original key and the initial parts of the key stream.  These correlations aren't enough to take advantage of if you're given one key stream (or even a few hundred), but given enough, it allows us to deduce the original key.


Contrasting Key Rotation Requirements : Asymmetric vs. Symmetric Ciphers

I have not seen a proof of theorem, but I'm guessing such results arise from basing the security of block cipher modes purely on their behavior as pseudo random functions.

Another factor is that block ciphers are not pseudorandom functions (PRF), but pseudorandom permutations (PRP). That means that as you get close to the birthday bound you do not see the collisions that you would expect from a PRF. This is significant with some modes of encryption.

However, yes, even with a PRF if you have collisions in the input to the function you start to lose security, so that puts a bound on things.

In the case of CBC mode the theorem concerns the probability that two ciphertext blocks are equal (and thus the inputs). This happens with significant probability as you get to the birthday bound. From such a collision the attacker finds that $p_i \oplus p_j = c_{i-1} \oplus c_{j-1}$, the right side of which they know.

  Or is there an analog for the CBC theorem that necessitates rotation of asymmetric encryption keys after some critical number of encryptions under the same key?

Yes, there are analogs.

If you are talking about pure asymmetric encryption like padded RSA, there is a chance that the random padding collides with an earlier one and you leak plaintext equality. E.g. if you encrypt the same plaintext twice with RSA-OAEP and have parameters such that there is $x$ bits of randomness, the probability of the randomness colliding and getting two equal ciphertexts is $2^{-x}$, in which case an attacker knows they must be the same plaintext.

If you use hybrid encryption, there is similarly a probability that the random symmetric keys used are equal, which would encrypt the same plaintext to the same symmetric ciphertext, again leaking equality.

(These are not the best attacks on RSA, just an example that bounds exist.)

Does that mean that you must rotate keys? Not really. The actual bounds for secure RSA sizes and padding algorithms are large enough that you will not hit them. A limited signing key lifetime may be a good idea for other reasons - in case you lose the key and in case better attacks come along - but you are not practically limited in the data you can encrypt or sign.


No, there do not seem to be any real attacks beyond those.

Note that MICKEY 2.0 is part of the eSTREAM portfolio and the one portfolio cipher that was very successfully attacked (pdf), F-FCSR, was removed (pdf) quickly thereafter. So you might expect MICKEY to be removed as well if a good enough attack is found.

The second review (pdf) of the portfolio from 2012 says:

  It has been noted, e.g. Gierlichs et al [29], that straightforward implementations of the MICKEY ciphers are likely to be susceptible to timing or power analysis attacks. Otherwise there have been no known cryptanalytic advances against MICKEY 2.0 or MICKEY-128 2.0.


Chosen-Ciphertext Attack on Rabin: Factorize n

By following the above advice (taking the equations for r and s given in the article and writing r-s) you will notice that q is  a divisor, therefore GCD(|r-s|,n) cannot be 1. There are only two options left since n is only divisible by q and p.


I can see at least one disadvantage of using 16 S-box to change the 16 bytes. The size of the code and the look up tables (should you use such implementation) would increase the size of the code. This increases the surface of exposure for cache timing attacks.

Due to the strong alignment of AES, i.e. differences are constrained within the byte, using one S-box or multiple ones (assuming that they share the same cryptographic properties: $P_{diff} < \frac{4}{256}$) would not really change the security of the whole algorithm. The probability of differential trails would be relatively similar.

So from a Linear and Differential cryptanalysis point of view, while making the research for differentials slightly harder, it would not increase the security against these attacks.

About Truncated Differentials, this attacks explores whether or not a difference is present on the bytes rather than on the bits. Therefore having multiple S-box or a single one, is likely to have no changes on it (only influence could be on the MixColumns).

About Boomerang and H.O.D I can't tell.

TL ; DR: using 16 S-box makes mainly the analysis of the block cipher harder (16 S-box to prove secure). It also makes the implementation of the block cipher harder (more places to screw up).


You need to split up your key into eight 7 bit pieces, and put these 7 bits into a byte each. The parity is in the least significant bit on most platforms, so the 7 bits need to go into the most significant bits. Of course, as the key is probably in bytes, you need to shift and combine the values in the bytes to retrieve the 7 bits.

It's possible the library does not require the parity bits to be set. In that case you don't need to calculate the parity. Otherwise you simply create the parity once you've got the 8 bytes.

Following code is in Java (which makes it a bit awkward because Java bytes are signed and most calculations assume integers).

// --- create 64 bit key from 56 bit key
// least significant bit can have any value
key64[0] = (byte) (key56[0] & 0xFE); // << 0
key64[1] = (byte) ((key56[0] << 7) | ((key56[1] & 0xFF) >>> 1));
key64[2] = (byte) ((key56[1] << 6) | ((key56[2] & 0xFF) >>> 2));
key64[3] = (byte) ((key56[2] << 5) | ((key56[3] & 0xFF) >>> 3));
key64[4] = (byte) ((key56[3] << 4) | ((key56[4] & 0xFF) >>> 4));
key64[5] = (byte) ((key56[4] << 3) | ((key56[5] & 0xFF) >>> 5));
key64[6] = (byte) ((key56[5] << 2) | ((key56[6] & 0xFF) >>> 6));
key64[7] = (byte) (key56[6] << 1);

// --- set parity in time independent of the values within key64
for (int i = 0; i < key64.length; i++) {
    // if even # bits, make uneven, take last bit of count so XOR with 1
    // for uneven # bits, make even, take last bit of count so XOR with 0
    key64[i] ^= Integer.bitCount(key64[i] ^ 1) & 1;
}


Lets assume an adversary knows one LD signature for message $M$ as well as public key $pk$ and can generate a forgery for an arbitrary different message $M'$. Clearly, there exists at least one bit position where the messages differ, i.e. $M_i \neq M'_i$, as $M \neq M'$. So, for simplicity assume there is only one bit difference. Then the adversary can take all signature values for the signature on $M'$ from the signature on $M$ besides the value for this single bit position. For the signature value of this bit it must hold that $f(sig_i) = pk_{i,M'_i}$ as otherwise verification would fail.

So if the adversary is able to generate a valid forgery it obviously is able to find a value $x$ that satisfies $f(x) = pk_{i,M'_i}$ for given $pk_{i,M'_i}$. This is per definition finding a preimage of $f$.

To get back to your question: The adversary might learn some information about $sk_{i,M'_i}$ from $pk_{i,M'_i}$. But that is not enough to produce a forgery as a forgery requires knowledge of a complete value $x$. Even more: it is not required that $x = sk_{i,M'_i}$ for the forgery to be valid.


Efficient peer to peer untrusted signature aggregation

BLS Multi Signatures - the aggregated signature is the product of signatures
Homomorphic Signature Schemes - the aggregated hash is the product of (prime) hashes.
(not a signature) it might be worth investigating signing Homomorphic Hashes, you cannot combine them


If G is a secure PRG and G' is a function of G, is G' secure?

Hint: Consider the function $G'(k) = f(G(k))$, where $f(x) = 0$ for all $x$.  Clearly, $G'$ is a function of $G$.  Is $G'$ a secure PRG?


Mostly.

The two problems are actually more closely equivalent in a gap model than in a non-gap model.

Square-DH clearly reduces to CDH either way, but CDH reduces to two calls to Square-DH (you have 3, but you can use $(u-v)^2$ to make it 2).  This is fine if the Square-DH adversary is always right, but maybe the adversary only solves the Square-DH problem with probability $\epsilon$.  The reduction doesn't know whether the adversary succeeded, so it solves CDH with probability only $\epsilon^2$.

If you get to try many times to solve CDH, you have to run the Square-DH adversary $O(2/\epsilon)$ times, and make $O(\epsilon^2)$ guesses, which is somewhat loose... unless you have a DDH oracle, like in the gap model.  In that case, you can filter out wrong Square-DH attempts.  The reduction is still not perfectly tight, though.  It can solve the CDH problem in time $t$ Square-DH calls with a probability which is to first order $t^2\epsilon^2/2$ when $t\ll1/\epsilon$.  So if your adversary is inaccurate and you don't have much time, it's still a loose reduction, but if you have $\approx 1/\epsilon$ time, it becomes tight again.


Is there any problem to reuse the prime p, g and a in Diffie-Hellman?

Actually, there is one potential problem to reusing $a$ values:

Background: $g$ generates a subgroup of size $q$; $q$ is a divisor of $p-1$, but it is usually selected as a prime, and is hence less than $p-1$ (which is obviously composite).

What an attacker could do is, for any small prime $r$ which divides $(p-1)/q$, he can potentially learn $a \bmod q$; he does this by negotiating with you, selecting as his share a value $g^b \cdot h$, where $b$ is a value he knows (doesn't matter what it is), and $h$ is a value of order $q$.  Then, when you'll do is generate a shared secret $(g^b \cdot h)^a = g^{ab} \cdot h^{a \bmod r}$; he can easily compute $g^{ab}$, and so he knows the shared secret is one of $r$ different values (depending on the value of $a \bmod r$).

If $(p-1)/q$ has a number of small primes, the attacker can deduce quite a bit about $a$.  One example of such a $p, q$ pair which has been actually proposed is Group 23 of RFC 5114; this particular group has $$(p-1)/q = 2 * 3 * 3 * 5 * 43 * 73 * 157 * 387493 * 605921 * 5213881177 * 352891
0760717 * 83501807020473429349 * C489$$ (where $C489$ is a 489 digit composite), and so the attacker can actually deduce enough to make brute force search of a 256 bit exponent feasible.

Now, there are several ways to protect yourself from this:

When you receive a value $b$, always check to see if $b^q = 1$; if not, someone is playing games.  This works, but it is expensive.
Use a 'safe prime' group; that is, one where $p-1 = 2q$.  This implies that the attacker can learn one bit of $a$ (the least significant bit), but nothing else.
Don't reuse $a$ values; what the attacker learns is the value $a \bmod r$ for the $a$ you used with the exchange with him; if you use different values of $a$ for unrelated exchanges, this doesn't buy him anything.

Also, note that the idea of using $q = p-1$ really isn't a protection; if $q$ has a small factor $r$, the attacker can also learn $a \bmod r$ just by examining $g^a$, hence the same vulnerability is there (except that not reusing $a$ doesn't actually provide protection).


Does encrypting with MGF1/SHA-512/1024-bit seed equal to a 1024-bit key block cipher?

This is not a block cipher.  It is a stream cipher: you are using SHA-512 to generate a one-time pad to encrypt the message.

The security—meaning the attacker's expected cost to break it—is at most $2^{512}/t$ if there are $t$ users of the system.

How the best possible security of this system relates to the best possible security of a 1024-bit block cipher depends on the block cipher.  The idealization of this system—a uniform random 1024-bit pad—has the same security as an ideal 1024-bit block cipher.  But a practical block cipher has a key, and it is typically smaller than $\log_2 2^{1024}! \approx 1024 \cdot 2^{1024}$ bits long.

In practical terms, you should focus more on everything else about your application's security.  For example, you didn't mention authentication, which suggests I can possibly destroy confidentiality by forging messages like EFAIL.  There is no point in pushing anything beyond a 256-bit security level, if there was any point going beyond a 128-bit security level in the first place as you get with AES-256-GCM or crypto_secretbox_xsalsa20poly1305.


Why is Vigenère Autokey self-synchronizing?

"Autokey" refers to an encryption method that uses the plaintext itself to generate the ciphertext. "Self-synchronization" of a stream cipher is not an encryption method. It is a modern (from 1946) process for a stream cipher to update its state based on the previous ciphertext.
Is Vigenère's Autokey Cipher an example of a self-synchronizing stream cipher?  No, but it could be coded, one supposes, to be self-synchronizing for certain methods of transmission and reception.
Background
Girolamo Cardano (1501-1576), a prolific writer and mathematician from Milan, came up with the first autokey cipher in 1550, but he designed it very poorly. As David Kahn explains in The Codebreakers (Macmillan, 1967), "He employed the plaintext as a key to encipher itself, starting the key over from the beginning with each new plaintext word." (Kahn, p.144).
Blaise de Vigenère improved on Cardano's work when he "did not recommence his key with each plaintext word, which was his [Cardano's] weakness, but kept it running continuously." (Kahn, p. 147). This innovation was "entirely forgotten" until the latter part of the nineteenth century. Vigenere's autokey is stronger than the famous "Vigenère Cipher" that was later mistakenly attributed to him, but it is a relic of the past.  Picture pen and paper, or even better, quill pen and parchment.
This idea of an autokey cipher that does not repeat the keyword has been used in some more modern cryptographic methods--rotor machines, for example--and the principle is still relevant. So, autokey is a symmetric encryption method with a curious history and many variations (also see Bellaso's method from 1564; Kahn, p. 144). On the other hand, self-synchronization of a stream cipher means maintaining its correct state.


Does "double RC4" exhibit the same weaknesses as standard RC4?

It can be attacked in the same way, but not as efficiently.

The RC4 "NOMORE" attack (pdf), for example, uses both Fluhrer-McGrew biases, which are biases towards certain pairs of values in certain positions, and Mantin's "ABSAB biases", which are repetitions of bigrams. Both of those biases will survive a XOR of two keystreams, but will be less frequent.

A rough estimate would be that you need quadratically as much ciphertext, so that you can attack first one layer and then the next. That would imply  >$2^{55}$ captures instead of the ~$2^{28}$ in the attack demonstration, which would likely be too much to use in practice. However, depending on whether or not the two keystreams are aligned, that could be an overestimate or an underestimate.

It seems possible that a XOR of two independent RC4 keystreams would be too strong to practically break in such a manner, even if it was significantly below the strength implied by key size. However, distinguishing attacks require less data and are more likely to be feasible. (The attack in question decrypts cookies or other suitable data.)


Is AES-CTR or ChaCha20 vulnerable to a time-memory trade off?

This is not a concern; the model of costs that the paper uses is unrealistic.  In the paper, they state:

  In other words, the attacker is given unlimited amount
  of time in preparation

(Section 2, second paragraph)

That is, they assume that the attacker can easily spend $O(2^{128})$ time (or more, if necessary) to generate a Hellman table (or Rainbow table) for AES-128.

Yes, once an attacker does that, he can attack AES-128 (at least, against the plaintext he used while building the rainbow table) faster than he would otherwise.

However, it is generally believed that $O(2^{128})$ effort is infeasible, even as a one-time effort.