Decimal point in keyspace notations? (eg 2^54.15)?

I mean for O notations, we usually state only the degree of the highest order polynomial (that expresses algorithmic complexity), ignoring the factors and lower order powers.

Consider an imaginary runtime of $5x^{2.5} + 2x - 3$. As $x$ gets large this is almost entirely dominated by $x^{2.5}$. However, $x^2$ is significantly smaller than $x^{2.5}$, especially when $x$ gets large - so when notated in Big-O notation this would indeed be $O(x^{2.5})$ or $O(x^{2}\sqrt{x})$.

However, we're not talking about Big-O notation of an algorithm here. We're talking about key spaces, which are of a specific size, rather than a coefficient of something that might be big. So you'll have to decide on a case-by-case basis whether or not the fractional part is "significant" or not. In this case, $2^{27.08}$ is about 5% larger than $2^{27}$. Apparently the author found this difference significant.

Note that the original fraction came into place due to the author insisting on using $2$ as the base of the exponent. The exact keyspace is $2 \cdot 10^{16}$, which is approximately $2^{54.15}$.


The first question is already answered here.

For the second question, a single key $k \in \left\{0,1\right\}^{168}$ can be trivially converted back and forth from three keys $k_1, k_2, k_3 \in \left\{0,1\right\}^{56}$ – there is no semantic difference between the two. DES itself operates only on 56-bit keys, and triple-DES requires three independent DES operations. Software that implements triple-DES can trivially be written to either accept a single 168-bit key or three 56-bit keys.


Should RSA primes p and q differ in length by "a few digits"?

The quoted recommendation is generally considered obsolete in the context of RSA with secure parameters, and is either disregarded, or replaced by asking that $\left|p–q\right|>2^{(n/2)–100}$ where $n$ is the number of binary digits for $N=pq$. This modern rule was in ANSI X9.31 (1998), and is still in FIPS 186-4 (2013), appendix B.3, criteria 2(d).

This quoted recommendation, and its modern counterpart, are intended to make $p$ and $q$ different enough to guard against Fermat factorization, and improvements thereof. The basic Fermat factorization technique enumerates integers $b$ from $0$ onward, stopping when $N+b^2$ is a square $a^2$, revealing $p$ and $q$ as $(a+b)/2$ and $(a-b)/2$ (within order). Numerous improvements exist allowing to skip some $b$, and reducing the cost of the squareness test.

However, with $p$ and $q$ of equal size and $n\ge512$, but $p$ and $q$ otherwise mostly random, all known improvements of Fermat factoring have fully negligible odds to succeed (because the number of $b$ to enumerate by the basic Fermat factoring method is $\left|p–q\right|/2$, which is higher than $2^{212}$ with odds better than $1-2^{-40}$, and none of the known improvements lowers the $2^{212}$ steps to something workable). Notice that $n=512$ is so small that it provides only very limited security (see this), and that the pointlessness of trying Fermat factorization (compared to other factorization techniques) grows when $n$ grows.

The quoted recommendation only makes sense for toy examples of RSA, say when $p$ and $q$ both are about 9-10 decimal digits (thus $n\approx64$). And then a few digits can safely be taken as 2 digits; or even (in decimal) reduced to a single digit, as long as the leading digit of the largest prime is not 1.

Rules in ANSI X9.31 and FIPS 186 prescribe (in the interest of interoperability of devices using RSA private keys they did not generate) that $p$ and $q$ are primes in range $[2^{(n-1)/2}\dots2^{n/2}]$, implying that they have the same number $n/2$ of binary digits (and that their number of decimal digits differs by at most one, if at all). This goes straight against the wording of the quoted recommendation. According to my memories of Robert Silverman's account: the requirement that $\left|p–q\right|>2^{(n/2)–100}$ (for $n\ge1024$) was introduced (although technically not needed) to please the ANSI X9.31 standard's committee, sponsored by bankers, who wanted a simple rebuttal to a court argument on the tune of: "I claim that my client did not produce that signature! One simple explanation is that the modulus has been factored. An expert has testified that Fermat factoring, known since the 17th century, potentially could do that, and allow such forged signature. No precaution against it was taken! Whoever carelessly specified that signature system must bear the consequences!".


Can RSA be securely used for "blind decryption"?

Let's try to simplify and abstract your protocol a bit.  Instead of your server and client, we just have two parties, let's call them Sally and Charlie.

Charlie has a key pair $K = (K_i, K_u)$ for a suitable asymmetric cryptosystem $\mathcal E$.  We assume that this cryptosystem is partially homomorphic, such that $\mathcal E_K(a) \otimes \mathcal E_K(b) = \mathcal E_K(a \odot b)$, where $\otimes$ and $\odot$ are two group operations.
Sally knows the public half $K_u$ of Charlie's key pair, so that she can compute $\mathcal E_K(a)$ given a plaintext $a$, but not the private half $K_i$ that would let her compute $a$ from $\mathcal E_K(a)$.
Sally has a message $\mathcal E_K(m)$ encrypted with Charlie's key pair, and wants to decrypt it without revealing the decrypted message $m$ to Charlie (or to anyone who might impersonate him).
Charlie wants to help Sally decrypt her message, but does not wish to reveal his private key $K_i$, or anything equivalent to it, to Sally (or to anyone who might impersonate her).

The protocol you've suggested amounts to Sally picking a random element $r$ uniformly from the group of all possible plaintexts, encrypting it using $K_u$ to get $\mathcal E_K(r)$, and sending $\mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$ to Charlie.  Charlie then decrypts the message, and sends $m \odot r$ back to Sally, who applies the group inverse $r^{-1}$ of $r$ to obtain $m = (m \odot r) \odot r^{-1}$:

  $S:\ $choose $r$ uniformly at random, compute $E_K(r)$ and $r^{-1}$;
  $S \to C:\ \mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$;
  $C:\ $decrypt $\mathcal E_K(m \odot r)$ to get $m \odot r$;
  $C \to S:\ m \odot r$;
  $S:\ $compute $m = (m \odot r) \odot r^{-1}$.

The first security claim (that Charlie cannot learn $m$) should be easy to prove, regardless of the specific cryptosystem used.  Since the plaintexts form a group, and $r$ is chosen uniformly at random from that group, $m \cdot r$ is also uniformly distributed, and so reveals no information about $m$ to anyone who doesn't know $r$.  Indeed, even if Sally repeats the protocol with several different random values $r_i$, and so reveals $m \odot r_i$ to Charlie, this will give him no additional information as long as all the $r_i$ are uniformly chosen and independent of $m$.

The tricky part is the second claim, and especially the part about Charlie not revealing "anything equivalent to $K_i$" to Sally.  After all, in the protocol as described, Charlie is acting as an unrestricted decryption oracle!

It seems to me that, for this protocol to make sense at all, we need at least the following assumptions:

Sally cannot be compromised in any manner that would directly reveal $m$ to the attacker; she can only be made to disclose $\mathcal E_K(m)$.
Access to Charlie is strictly limited, so that even if an attacker obtains $\mathcal E_K(m)$, they cannot simply query Charlie for $m$.

The latter assumption may indeed make sense in your scenario, where Charlie is physically connected to Sally (and only intermittently so connected, being securely stored at other times), if we also assume that Sally is resistant to active compromise (i.e. she may certain data items, but an attacker cannot modify her behavior).  That's a pretty huge assumption in practice, but if you're willing to make it, the protocol described above seems like it should work.

(That said, if you're really willing to make all those assumptions, why not simply have Charlie store $m$ and provide it directly to Sally upon request?  I'm having some trouble coming up with a reasonable attack scenario where that wouldn't be secure, yet the protocol above would be.)


Is it safe to use the hash of the data as the key to encrypt them?

It's kind of pointless to use the hash over the data even if you only hand over the key to the receiver of the ciphertext.

First of all, it's insecure. Consider an empty or very simple message. In that case an attacker can guess the message, create the hash, and verify correctness by decrypting.

Second, it binds the key to the data of the message. You will have to refresh the key each time you change the message. The idea of symmetric ciphers is that you can reuse the key for different messages. This scheme is not as bad as a one-time pad where the key has to have the size of the message as well, but it is still very inefficient.

Creating a secure key for most symmetric ciphers isn't hard; you just take 128 to 256 bits of secure random data and use that as key. There is no need to make the key dependent on the plaintext message. If you communicate with another party then often key agreement (DH or ECDH) is performed to agree on a key instead. There are of course countless other methods of key establishment.

In case the key is reused then you would have to use a different IV for each message. This IV can however be included with the ciphertext; it doesn't need to remain secret.

Note that this answer assumes a cryptographically secure hash such as SHA-2 or SHA-3. It doesn't consider a keyed hash or PRF such as HMAC-SHA-2 or KMAC-SHA-3.


What to do with a last chunk of 503 bits in SHA1?

The answer is in both sources you linked.

Pseudocode from the Wikipedia article:

  append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
  append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
  is congruent to −64 ≡ 448 (mod 512)
  append ml, the original message length, as a 64-bit big-endian integer. Thus, the total length is a multiple of 512 bits.

From the SHA documenation:

  Suppose  that  the  length  of  the  message, $M$,  is $l$ bits. Append the bit "$1$" to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $l+1+k\equiv 448 \mod 512$.

In both instances, the number is the smallest non-negative solution to the same congruency, just noted slightly differently. If you have an example where $-1$ would be a solution to the congruency, then the actual value of $k$ is $511$.


The following is an analysis of the CCrypt protocol described here. Note that this breakdown of ccrypt mostly focuses on possible weaknesses that may also be present in other protocols.

Key derivation

ccrypt does not apply a well known Password Based Key Derivation function. As no salt is applied rainbow tables can be constructed (although the generated keys must still be validated against the ciphertext by at least a single Rijndael decrypt).

Dictionary attacks are made easy as no work factor or iteration count is used by the protocol; CCrypt even contains code to perform a targeted search for passwords that are close to a given password. Initial verification of the resulting key can be performed against the magic after the IV is decrypted with the resulting $R$. That said, the resulting key is well randomized using all available characters, even if the protocol is relatively unorthodox.

Nonce & IV generation

The file encryption does not contain an authentication tag. Therefore anybody can create bogus messages. Messages may be swapped as well to fool the user into decrypting the wrong message. You just need a copy of the IV for an existing ciphertext for this. Non-authenticated encryption can be OK for providing confidentiality for stored ciphertext, as long as the user is aware of it. In general it is hard to protect against an adversary swapping ciphertext, even if integrity protection and authentication is added to the ciphertext. A warning with regard to the lack of integrity protection and authentication is included in the description of ccrypt.

The nonce is not fully random. If the input for the nonce generation can be made identical (mainly time-of-day in seconds & microseconds, process ID and count should be relatively easy to repeat) then an identical key stream will be generated for identical passwords. In that case high amounts of information about the plaintext could be retrieved by XOR-ing multiple ciphertext against each other (at least for initial block and possibly blocks of ciphertext). The lack of a secure random number generator on many platforms has been indicated as the reason for this design choice.

Password validation

There is an almost negligible chance of $1\over{2^{32}}$ (because the magic is 32 bits) that the wrong password is accepted to decrypt a ciphertext. This could however be exploited by an attacker claiming to have a correct password for a file.

Cipher usage

CCrypt uses it's own C source code for the Rijndael implementation, although it seems directly derived from the C code for the NIST competition. It is unknown if this implementation is secure against side channel attacks. It doesn't matter as much as CCrypt is mainly used to encrypt files locally.

Full block CFB is used as mode of operation. This is known to be a secure mode. An IV is generated and the highest block size and key size are used. So there are likely no big issues with how the Rijndael cipher is deployed.

Password security

As with any scheme to perform PBE (Password Based Encryption) the security of ccrypt is highly dependent on the quality of your password. A disadvantage of a scheme that only relies on symmetric encryption primitives is that you need to supply your password both for encryption and for decryption. For OpenPGP you would only require your password to unlock the private key during decryption.

Conclusion

In conclusion the key derivation scheme and the nonce generation are not standardized and leave something to be desired. The password is however hashed in such a way that it is unlikely that any entropy in it is lost. Rijndael - not AES - is deployed correctly so the protocol seems secure. The project only has one author as this time, but Peter seems to be responding to requests.

It would be advisable to make sure that nobody else is logged in when encrypting / decrypting your data as the implementation does not seem to be tested against side channel attacks. Furthermore, as the documentation indicates, you should not assume this protocol offers integrity protection or authentication of the plain- and ciphertext.


What is the link between the parity check matrix, double-error-correcting codes and APN permutations?

This quite technical connection was ultimately proved in the paper

  C. Carlet, P. Charpin and V. Zinoviev. Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), pp. 125–156, 1998.

See also the paper by the same authors plus Dobbertin in the IEEE Transactions on Information Theory, around the same time. I'll give an executive summary in its classical form without all the equivalences discovered later.

In pseudorandom sequence design, the Gold Sequences have the form
$$
g_t=T(a z^t)+ T(z^{(2^k+1)t}), \quad t\geq 0
$$
where $T$ is the trace map from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2},$ $z$ is a primitive element in $\mathbb{F}_{2^n}$ and $gcd(n,k)=1.$

The sequence $T(az^t)$ is generated by a primitive LFSR corresponding to the characteristic polynomial $M_z(x)$ of $z$ and has period $2^n-1.$ The sequence $g_t$ is a sum of this sequence with its decimation by $2^k+1.$

Sequences taken with all their shifts form cyclic codes.

The Gold sequences viewed as a cyclic code in classical form have $k=1$, thus they are generated by the product $M_z(x)M_{z^3}(x).$

This means that the zeroes of this code are the union of those of $M_z$
$$
\{z,z^2,z^4,\ldots z^{2^{n-1}}\},
$$
and of $M_{z^3}:$
$$
\{z^3,z^6,z^{12},\ldots z^{3\cdot 2^{n-1}}\},
$$
thus have the 4 consecutive zeroes $\{z,z^2,z^3,z^4\}$ giving a cyclic BCH code of minimum distance $d=4+1=5.$


Is it safer to generate your own Diffie-Hellman primes or to use those defined in RFC 3526?

Generating your own group for Diffie-Hellman is not a tough issue; but it is somewhat expensive (it depends on the context, but a 25 MHz ARM device would not like to do it often) and it is not really needed: a good point of DH (and DSA) is that the group parameters can be shared between many users, with no ill effect on the confidentiality of their respective private keys.

For plain Diffie-Hellman, what you need is $p$, $q$ and $g$, such that:

$p$ is a big enough prime (2048 bits are more than enough nowadays);
$q$ is smaller, but still big enough (say 256 bits), prime value which divides $p-1$ ;
$g$ is a generator of a subgroup modulo $p$ with an order that is a multiple of $q$.

The DSA standard (FIPS 186-3) includes a rather detailed procedure for generating adequate group parameters (see annex A), which would be fine for DH too.

There is another side to the issue. While randomly chosen $p$, $q$ and $g$ are good for DH with overwhelming probability, it is possible to specially craft $p$, $q$ and $g$ values such that breaking discrete logarithm modulo $p$ (with generator $g$) would be easy (or at least easier). This can be a problem if your application entails producing the DH group parameters and having other people use them for their own key pairs. If you generate the group parameters but do not tell how you generated them (in a verifiable way), then other people could suspect you of having purposely made them weak. For completely usable group parameters which are immune to such suspicions, you need "nothing up my sleeve" numbers. Annex A of FIPS 186-3 describes the generation process in full details precisely so that it can be verified to be random. RFC 3526 uses $\pi$ for the same reasons.

Therefore, reusing published group parameters is a good idea, both for performance (no need to do the generation yourself, you can save on CPU and also code size) and for trust that can be put into the results by other people.


Representing Ed25519 p curve in hexadecimal byte string

The constant is named minusp, thus it's $-p \pmod {2^{256}}$, or $2^{255} + 19$, encoded in little-endian.

Assuming you want the hex string in big-endian, which is the way numbers are usually written, you get:

$p = 2^{255}-19$ = 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED

$2^{256} - p = 2^{255}+19$ = 8000000000000000000000000000000000000000000000000000000000000013


Can minimum encrypted message length be used to identify public key algorithm or derived some of its features?

For the most common public key encryption mechanisms such as RSA PKCS#1 encryption mechanism, it is indeed possible to deduce the key length from encrypted length.

In addition to encrypted length, you may want to look at encrypted data. In case of RSA observing encrypted data will reveal e.g. modulus, i.e. basically the public key.

This is generally the case with public key encryption: observing encrypted messages eventually allow to learn the public key.

It is not usually not possible to detect what one of of PKCS#1 paddings was used. However, occasionally, the encrypted message is encapsulated so that it conveys more information on the message. Have you been able to examine encrypted bytes produced by the device, to check if there are e.g. some DER encoded header or other additional information?


Zero-Knowledge Proofs are effectively built to prove knowledge of data without revealing it. So what you ask is very possible indeed!

Let's say that we're going to use Schnorr's identification scheme (but tons of other ZKPs exist, you can research Fiat-Shamir, Feige, Guillou-Quisquater, Schnorr digital signature; and those are only the first ones. Now there are SNARKs used in ZCash blockchain etc.).

A and B both know userID, which is converted to some secret/private number x.
Both interact with a verifier to prove knowledge of userID. (g is a public generator for some group, and all this is done modulo some prime number, but for ease of read I won't put that here. You can look the wikipedia for schnorr's identitifation protocol)

They disclose the public key y = g^x. Generate a random r, r' (for A and B respectively). Disclose t = g^r and t' = g^r'. [commitment step]

Verifier sends a number c, c'. [challenge step]

A responds s = r - cx. Verifier checks by computing g^s y^c == t [response step]

Explanation: g^s y^c = g^(r-cx) g^(cx) = g^r = t

Verifier is then convinced that A knows the secret key x, hence the userID.

Same for B: s' = r' - c'x => g^s' y^c' = g^(r'-c'x) g^(c'x) = g^r' = t'.

Both entities A and B proved knowledge of userID without disclosing it.

Hope this helps :)

EDIT: I just tilted on the "owned" part. Here we prove knowledge of, not ownership. I imagine a server could send a unique token derived from the userID and send it to A, derive another to send to B (thanks to some salt). Both A and B would prove knowledge of these tokens, which have been issued by the server, so the server would effectively be convinced of their ownership of that data.

Just an idea in case the previous thoughts weren't really answering your question ^^


In this answer I'm assuming that a key is used to encrypt more than one message.

The first weakness is that CBC with fixed IV leaks if messages share a common prefix.
The second weakness is that it makes a padding oracle attack much more severe. Consider a device that knows the key and decrypts a ciphertext you send to it. While it won't tell you the plaintext, it'll leak if the padding was valid (e.g. via an error message or timing). Such a device acts as padding oracle.

For normal use of CBC with PKCS#7 padding and a known (variable or fixed) IV, such a padding oracle will allow an attacker to recover the message associated with plaintext, but it will not leak the key.

When using a fixed secret IV, it doesn't recover the plaintext of the first message block directly, rather it recovers $m_1 \oplus \mathrm{IV}$. When the attacker has access to several ciphertexts, this behaves like a many-time-pad thanks to the reused IV. Due to the redundancies of natural languages this should allow recovery of the IV given only a few ciphertexts.

If the key is reused as IV this IV recovery attack becomes a key recovery attack.

I don't expect either of these weaknesses to help a ransomware victim, since the first is only a minor leak and the second requires a padding oracle, which you probably won't have.


What is the difference between order of base point and curve order in EC?

What's difference between n & #E(FP)?

The difference is that $n$ is the smallest positive integer where $nG = O$; while you correctly state that $\#E \cdot G = O$, that doesn't mean that $\#E$ is the smallest integer that makes this happen.  There may be a smaller integer $n$; $n$ will always be a factor of $\#E$, however it can be smaller.

As for why we would want to make it smaller, that is, why would we want to have an $h = \#E/n > 1$, well, that's exactly what this question addresses.


Quantum algorithm for elliptic curve's private keys

Shor's algorithm, which runs only on quantum computers, solves all discrete-logarithm problem instances over all groups.

This obviously includes the elliptic curve discrete logarithm problem at the heart of ECDH, ECDSA and ECIES. For a more detailed discussion of the details, see this recent paper.

However, there are things we can do with elliptic curves that are believed to which we don't know better quantum algorithms, like elliptic curve supersingular isogeny-based key exchanges.


Each byte act as a polynomial in $\operatorname{GF}(2^8)$

You will multiply the elements of the matrix in (Galois Field) $\operatorname{GF}(2^8)$ and add them in $\operatorname{GF}(2^8)$

here is a link where you can find a wonderful explanation for $\operatorname{GF}(2^8)$


Significance of parameter q in NTRU lattice attack

Basically, the norm of the secret key does not depend on $q$, while the norm of the second minimum of the lattice does, so, when you increase $q$, you increase the gap between the first and the second minima of the lattice, which makes the problem easier.
For instance, if the secret key is composed by two degree-$(N-1)$ polynomials $f$ and $g$ with coefficients in $\{-1, 0, 1\}$, then we have $||(f, g)|| < 2N$.
One basis of the lattice $L$ that we use in attack is
$$
\begin{pmatrix}
I_N & H \\
0   & q\cdot I_N
\end{pmatrix}
\in \mathbb{Z}^{2N\times 2N}
$$
So, it is clear that $\det(L) = q^N$ and $\dim(L) = 2N$.
Then, by the Gaussian Heuristic, we expect the short vectors of $L$ to have norm close to
$\sqrt{N}(\det(L))^{1/\dim(L)} = \sqrt{Nq}$.
Because $(f, g) \in L$ and $||(f, g)||$ is smaller than the value predicted by the Gaussian Heuristic, there is a "gap" in $L$, that is, we expect that
$\lambda_1(L) = ||(f, g)||$ and
$\lambda_2(L) \approx \sqrt{Nq}$.
Now, roughly speaking, if the vector that we recovered is shorter than the second shortest vector, then it has to be the first shortest vector.
So, when we run a lattice basis reduction, if we recover a vector smaller than
$\sqrt{Nq}$, it will already be (a short multiple of) $(f, g)$ and we win.


You cannot assume that a text-based input is an acceptable replacement for a key in cryptographic algorithms. The default assumption used to design algorithms is that the key is generated randomly; specifically, generated in such a way that the key is unpredictable and comes from a uniform random distribution of all possible keys.

If you use text instead of random bits there are plenty of problems:

You reduce the number of keys that need to be tested
Your input will have patterns that may make your key more likely to belong to a class of weak keys. If a set of weak keys exists for an algorithm, using one of them will cause the algorithm to exhibit biases that could make it insecure.
Passwords chosen by humans are far more predictable than the typical person assumes. If you need to keep encrypted data safe then you need to be smart with your password.
A password might be shorter or longer than an algorithm's normal key size. (Padding and truncating here is a bad idea, especially when password- based key derivation functions exist.)

How one might (correctly) encrypt a file using a password:

Generate a new random password not used for any online services
(or otherwise shared with anyone). How do you do that?

Don't use things like your favorite sports team or a birth date.
Generate a random string of characters from something like /dev/urandom. A string, if the length is $n$ and the characters come from an alphabet of size $m$, has up to $\log_2(m^n) = n \log_2(m)$ bits of entropy
Generate a string of $n$ random words from a dictionary of $m$ words, using spaces or periods or commas as word separators. This also has $n \log_2(m)$ bits of entropy.
If you want to generate a memorable password, no computer required, and you have a fair six-sided die, then use Diceware. I recommend one of the EFF lists over the original word list.
Make sure your password has enough entropy to prevent brute force guessing. The minimum you want is probably 100 bits. Some might say 80 bits or 128 bits. (When you generate a password for websites you can go much lower, but that's because it's a different application of passwords.)

Generate a nonce
Use a key derivation function. For example, scrypt if (you commit to using a lot of RAM), bcrypt, or Argon2d. The functions I listed accept passwords as input and "stretch" them. They make brute force guessing harder by making the attacker and the person who has legitimate access to the file do extra work. Use it to derive a symmetric key of 256 bits (if it's available even if entropy isn't 256 bits and you fear quantum computing) otherwise choose a key size and algorithm with at least 128 bit security level.
Create an output file, store the nonce in plaintext, then append the ciphertext and authentication tag of the encrypted input file to the output file.
Remove data from the original plaintext file from any storage place or memory where someone could gain access to it.

To decrypt a file use the same key derivation function, check that the authentication tag is correct, and decrypt the data using the nonce and key.

There are some details and warnings I am leaving out because they're answered in other questions here, at http://security.stackexchange.com/ and on many other websites.


Why is variable rotation uncommon in cryptographic primitives?

One issue is that data-dependent rotations (such as you describe) is patented by RSA data security (or, at least, was, the patent may have expired).  RC5 and RC6 was created by the holder of this patent, however such a patent could be enforced against someone else, and so people have shied away from it.

More minor issues would include:

It is likely to take variable time on lower-end CPUs, and hence potentially vulnerable to time-based side channel attacks.
Such variable rotates are moderately expensive in hardware (when they need to be implemented in constant time); yes, you can construct a barrel shifter, but that takes a number of gates and interconnects.


Yes, you can modify the initialization vector to accomplish your goal (as mentioned in the comments, the initialization vector is the first block of the cipher text). So, by computing a new initialization vector, $IV_2 = IV_1 \oplus x$, the cipertext/IV pair $(c_1, IV_2)$ is a valid encryption of $m_2$ with CBC mode. This is because $m_2[1] = m_1[1] \oplus x$, so
$$m_2[1] \oplus IV_2 = (m_1[1] \oplus x) \oplus (IV_1 \oplus x) = m_1[1] \oplus IV_1$$ This way, the first blocks of input to the blockcipher are the same for both messages ($\oplus$'d with their respective IVs), and the encrypted outputs are valid for both messages.


The automatic way to find f is by using the Miller algorithm.

But you can also see this directly here:
Since the line y=0 is not tangent to E , y is a uniformizing function.
You can write  $(x-1) = y^2*((x-2)(x-3))^{-1}$, where $(x-2)*(x-3)$ has neither a zero nor a pole at (1, 0). This says exactely that (1,0) is a double zero of the function x-1. Since it has a double zero it must also have a double pole at $\infty$. This gives you
\begin{equation*}
div((x-1))=2[(1,0)]-2[\infty]
\end{equation*}

In a similar way you can show this for the points (2,0) and (3,0)

Now you have all 2-torsion points, lets find the other points:
x=0 gives $y^2 = -1$, which solves to y=2 and y=3
x=4 gives $y^2 = 1$, which solves to y=1 and y=4
Since the group has 8 elements, at least two of those points must have order 4.
That all 4 points have order 4 can be shown by a direct calculation(2 squarings are sufficient).
One can also see this by a direct argument:
If the group would be cyclic, it would have 4 elements of order 8. This would let no place for an element of order 4. Therefore the group cannot be cyclic and all 4 elements, which are not 2-torsion elements, must have order 4.


In the Quadratic Sieve, why restrict the factor base?

The condition $\genfrac(){}{}{a}{b}$=+1 doen't matter as the product of 2 QNR is a QR.In fact the idea of locking for numbers satisfying $x^2-y^2=k.n$ was firstly introduced by Gauss (1801) and was developped by Kraichick (1920) by searching for special sequences of the form $Q(x_i)=x_i^2 -n$ which factorize over small primes $\prod Q(x_i)=v^2$. In the exemple you gave the number of QNR are even, then in the product only QR factors are present.
Selecting larger primes outside the factor base, need additional ressource in storage and computation and doen't give additionnal advantage in the form of Fermat difference.


What you need for this is something called an $n$-wise independent hash function (like "pairwise independent" but $n$ instead). Such a hash function has the property that when applied to at most $n$ different inputs, its outputs are completely random. These can be constructed efficiently; e.g., a random polynomial of the appropriate degree works. What you actually defined with $E$ in your question is a linear polynomial with random coefficients and this is pairwise independent. There has been significant research on how to construct these, how to construct such functions that are almost independent, and so on.

Having said all of the above, you don't really gain anything cryptographically with this, since the size of the key still needs to be larger than the size of everything you compute. So, you may as well use the one-time pad each time. However, there are other applications that such functions are useful (mainly in complexity, but they are also sometimes used in crypto).


Is the following scheme secure for different cipher

Actually, it's option 1: the attacker won't be able to compute anything, as long as a secure cipher is used.

The reason for this is that one of the requirements of a security cipher is resistance to known plaintext; that is, a message encrypted by the cipher with a key is secure even if the attacker can get the text of another message (and corresponding ciphertext) encrypted with the same key.

Your attack reveals M2 to the attacker and so the attacker has the pair C12 and M2 (a known plaintext pair) along with the ciphertext C11; this is exactly a known plaintext scenario; because a cipher is not considered secure unless it is invulnerable to a known plaintext attack, the attacker learns nothing about M1.

Note that your stream cipher example is not a counterexample to this, because this usage of a stream cipher is not particularly secure.  For example, even without any known plaintext, the encrypted messages C11 and C12 allows an attacker to compute the value of M1 exclusive or'ed with M2; depending on the language that M1 and M2 are in, this is often enough to deduce the values of M1 and M2 (and so this example isn't even secure against a ciphertext only attack.

Because of this, we never use a stream cipher in that manner; you should either use a distinct key for each message, use successive portions of the key stream to encrypt successive messages, or use a stream cipher that take a nonce (which modifies the stream cipher output).


Select known data (known to several parties)

If the data is already known then there is no reason to distribute it. You could just refer to it.

  Mix data with secret key and generate SHA-1 hash

That's what you use a HMAC for.

  Mix SHA-1 hash with secret key and generate HMAC

You'd normally use your symmetric key only once.

  Is there any weakness to using a SHA-1 hash rather than for example SHA-256 in this scenario?

It's got smaller output and therefore less protection against brute force attacks, but HMAC in itself isn't vulnerable. SHA-1 is however under attack, with collision resistance the first to go. If you manage to muck up step 2 then you're likely in trouble. If you use HMAC then you may not be directly vulnerable to current known attacks. But attacks only get better.

  Does the use of SHA-1 make it easier to for example extract the secret key compared to SHA-256?

No, the fact that SHA-1 may be less collision resistant doesn't mean that the algorithm is reversible.

That said, unless there are pressing requirements to use SHA-1, e.g. backwards compatibility, I would rather choose SHA-256 or SHA-512/256.


Are there transitive ciphers (either symmetric and asymmetric)

Actually, there's the Pohlig-Hellman cipher (dating back to the 70's) that can do precisely this; it works like this:

There's a large public prime $p$ (for which the DLOG problem is hard)
The secret key is an integer $x$ that is relatively prime to $p-1$
To encrypt a message $M$ with key $x$, we compute $C = M^x \bmod p$
To decrypt a message $C$ with key $x$, we compute $M = C^{x^{-1} \bmod p-1} \bmod p$

It should be clear that the encryption and decryption processes (for a fixed key) are inverses of each other, and that this allows Alice and Bob to do precisely what you asked for; if Alice has $M^b$, she can give Bob , $(M^b)^a = M^{ab}$; Bob computes $(M^{ab})^{b^{-1}} = M^a$, and send that back to Alice, who can then recover $M$


Quantative criteria to measure confusion and diffusion property of encryption algorithm

Diffusion

Diffusion can be quantified by examining the branch number of the diffusion layer. The branch number indicates how much a difference in the input will spread around the rest of the state after the transformation has been applied.

The branch number can be used to prove lower bounds on the amount of diffusion that the permutation provides.

Measuring avalanche statistically can only tell you if your diffusion is awful, it can't really be used to prove that diffusion is complete and even throughout the state, or that one design is better then the other (assuming that both have decent diffusion).

Confusion

Confusion, or non-linearity, can be quantified by measuring stats such as differential and linear probability. For small enough mappings, it is easy to take these metrics by simply building a difference distribution table and linear approximation table and simply examining the results. For larger mappings this may prove challenging if not intractable.


First things first: Don't roll your own crypto.

As for your current approach: This is basically a vigenere cipher which is inherently broken, provides not integrity protection and wouldn't even encrypt known / predictable bit positions (where the ASCII code is constant zero or one).

As for an improved version:
Use a well-known encryption algorithm (e.g. AES-GCM) to encrypt and authenticate the key. Don't forget that you have to use a nonce (a number used only once) with it. Do not feed the user password directly into the cipher, but rather feed it into a proper password based key derivation function (PBKDF) (e.g. Argon2, scrypt, bcrypt, PBKDF2). Make sure you use a salt and that it is random and that the derivation parameters are so large that key access takes about 100ms of full CPU load on your system.


What is the NTRU parameter equivalent to security level 112, 128 and 192?

The answer is not easy. There is an estimator by  John Schanck. You can use this estimator to derive according to your requirements.
For example

NTRU
Core-SVP (tuple Sieving)
Hybrid

443
~93
~89

743
~176
~172

I've omitted the variant of the Core-SVP, for example, the core belongs to the Tuple lattice sieving. They are both used in the Core-SVP and in the Hybrid.


RSA: Is it secure to use the private key to encrypt and the public key to decrypt?

No, you generally cannot swap the public and private keys.

Your public key consists of a public exponent and a modulus. The modulus should be known to the person doing the encryption. The public exponent - in general - is a relatively small prime such as 3 or 65537 (Fourth number of Fermat). So given the modulus all an attacker has to do is guess the public key. It's very easy to factor pretty small exponents (I've written software to generate public keys given a private key). The exponent of the private key on the other hand consists of a number that is about as large as the modulus. It cannot be easily factored; the security of RSA relies on this fact.

Currently the majority of software uses RSA with a small public exponent. It is however possible to create an RSA exponent that is the same size as the private exponent. In that case you would have something close to two private keys. Note however that the public key is generally not required to be private. So software may not protect the public key as much as the private key (with regards to e.g. side channel analysis). Sometimes the software may also use padding required for signature generation instead of those for encryption if you present it a public key - mainly due to some weird signature functions required for SSLv3 and TLS 1.0.

So even if your software would accept the public key - RSA is modular exponentiation after all - then by all practical means it not going to be secure.


What data Certificate Authority encrypt for CSR?

In the X.509/PKIX certificates used for SSL/TLS as tagged, but not necessarily for (many) other types of certificates:

A CA doesn't encrypt anything; it signs certificates. Signing is not encryption, although some people are confused by the fact that for one algorithm (RSA) one part of signing is similar mathematically to one part of encryption. The certificate is not the same as the CSR and a certificate is not a signed CSR, although the certificate includes some important data from the CSR: always the public key and often the subject name and sometimes some extensions.
A party who uses a cert (in SSL/TLS usually the client using the server's cert) validates it partly by verifying the cert's signature using the CA's public key (for which the CA usually has and provides another cert, the CA cert). I'm not sure I understand the rest of your question; we need to validate any cert to be sure it's valid and not faked, and an SSL/TLS client needs to validate the server's cert in order to be sure it's communicating with the correct server and not an imposter.
"if it is replaced" -- what is "it"? Do you mean a 'Man-in-the-middle' changing the handshake to include some other cert (or chain) instead of the server's cert (or chain)? If so, see #2.
Yes, the certificate contains a field Issuer which identifies the CA that issued (signed) the cert, and the Issuer field is used to locate the CA cert containing the CA public key used to verify the cert. However, there are other related values that can be and usually are in the cert as well:

AuthorityKeyID (AKI) extension identifies either the signing key (by copying its SubjectKeyID/SKI) or the signing cert (by its issuer and serial)
CRLDistributionPoint extension identifies where the CA, or an agent of the CA, issues Certificate Revocation Lists (CRLs)
AuthorityInfoAccess.OCSP (Online Cert Status Protocol) extension identifies where the CA, or an agent of the CA, provides revocation information online
AuthorityInfoAccess.CAIssuer extension identifies where the CA cert is available online (although in SSL/TLS the prover = server is required to send it so this normally shouldn't be needed)


How do the following new (2013) ECC curves compare in security or efficiency?

Are there performance, size, or power efficiencies from one curve to another?

The larger the curve, the larger the keys and signatures, and likely the slower the computations. There are exceptions to the last one – curve parameters do affect how efficiently they can be implemented, so some curves with good parameters can be faster than slightly smaller curves.

  Perhaps more important, are there security improvements over a given curve?

All of them should be safe, but the larger curves have more security margin.

  If a new alt-coin (Bitcoin) were created today, which curve is ideal?

Since signatures and public keys appear in the blockchain, having them be small would be great. Having signature verifications take little time would also be good, since that's time wasted.

Curve25519 has 256-bit keys and 512-bit signatures, and is known to have a fast implementation (Ed25519 for signatures). Especially if it gets standardized, it would be a decent choice.

Unless there's some kind of a breakthrough, 256 bit curves with 128-bit security should be enough until/unless quantum computers break ECC. For a post-quantum altcoin, you could use e.g. hash signatures, but that would expand the blockchain quite a bit.


How to generate Multiple Encryption Keys for use in RSA polymorphic multiplication

Besides the answer Dimitree gave to himself, I' like to add something even if I am not sure whether I understand the original problem he wanted to solve.
You used the same message a and encrypted it with different values for e, but used the same modulus N. And you added the different exponents e.
As far as I know, the homomorphic multiplicative feature of RSA is defined in a way, that the same e and N are used, and you either want to get a multiple of m by just manipulating c or you want to multiply two c values.
Simple encryption and decryption of numbers in RSA is straightforward: To encrypt a number m, one computes c = m^e mod N. To decrypt a ciphertext c, one only needs to compute m' = c^d mod N = m^(e*d) mod N = m.
To see that RSA is partially homomorphic, consider two numbers m1 and m2 and their respective ciphertexts c1 and c2. To compute the product m1 * m2 homomorphically, one computes the product of the ciphertexts, c1 * c2. This then decrypts to m1 * m2: (c1 * c2)^d mod N = (c1^d) * (c2^d) mod N = (m1^(e * d)) * (m2^(e * d)) mod N = m1 * m2.
The RSA scheme is only partially homomorphic because one is only able to perform multiplications.
In a similar way you may build an attack modifying c to c' such that the receiver gets m' = k*m.
However, I might not have understand the problem and you are talking of another kind of multiparty communication. If so could you explain the scenario a bit more detailled.


Appropriate length of the challenge string for challenge-response authentication?

Standard approach:

$n=10^{12}$ challenges are drawn;
assume each challenge is $k$ unbiased independent random bits;
odds that there is a collision is less than $(n^2/2)\cdot2^{-k}$, by a first order approximation of the birthday problem, always erring on the safe side, and negligibly so for large $n$ and low odds of collision (our goal);
we want the odds to be less than some acceptable residual odds $\epsilon$ that the challenge will repeat (potentially allowing replay); like, $\epsilon=2^{-30}$ (less than one chance in a thousand million).

Now, solve for $k$. Mentally: 3 decimal digits are worth 10 binary orders of magnitude, thus (slightly erring on the safe side) $n$ is 40 BOMs, $n^2$ is twice that, $n^2/2$ is 1 less, dividing by $\epsilon$ adds 30 BOMs, thus we need 109 bits; rounding up to the next multiple of 8, we want at least 14 bytes.

Beware: it is uneasy to build a random generator that will generate independent random bits if power loss between uses or adversarial upset is a possibility.

If we want to reduce $k$ to the max in order to conserve bandwidth, and have secure remanent read/write memory for a counter, and an secret extra key, we can use a 40-bit counter (numbers of BOMs in $n$), encrypted with a 40-bit block cipher and the key (which needs to be known only by the entity generating the challenge).

Not only will the challenge be smaller, it is guaranteed to never repeat (this is part of the Format Preserving Encryption folklore).

Beware: a reliable counter is extremely hard to get right if power loss during uses or adversarial upset is a possibility; thus if possible, the prudent approach is to stick to pure random challenge.

I second the opinion voiced by @CodesInChaos that a challenge-response should be part of an overall protocol giving the required security insurance; and in particular that it should not be possible to hijack a channel after the challenge/response; or/and insert in there as a Man in the Middle.


Is it possible to reduce the size of an RSA key?

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align}
N&=p\cdot q\\
d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\
d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\
d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\
q_\text{inv}&=q^{-1}\bmod p
\end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

If we'll generate $k$ keys of a certain size, without salt, we want to use use a (truly random) seed of at least $n+\log_2(k)$ bits, where $n$ is the security level corresponding to the public key size (perhaps $n\approx 112$ for 2048-bit RSA): we need to guard against the adversary enumerating seeds, generating the corresponding public modulus, and testing if it matches one of the public keys, which is expected to succeed after enumerating about $1/k$ of the seeds.

We can also use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.


It seems to me that the answer to the question, as literally asked, is $0$.  This is because you're asking for the minimum advantage "for every adversary", and the set of possible adversaries includes e.g. the trivial adversary that simply always outputs an empty message and a random tag $t \in T$, and thus has a probability of exactly $1/|T|$ of successful forgery.

However, that's almost certainly not what the question is trying to ask, if only because the answer above doesn't actually make any use of the extra collision-finding algorithm.  What I suspect the question should ask is something like:

  Let $(S,V)$ be a MAC scheme (as defined above), and let $C$ be an efficient algorithm that will output a pair of distinct messages $m_1 \ne m_2$ such that $S(k, m_1) = S(k, m_2)$ for a randomly chosen key $k \in K$ with probability $1/10$.  Show that for any such triple $(S,V,C)$ there exists an adversary $A$ (with oracle access to $S(k,\cdot)$ and $C$) that can forge a message with advantage at least $a > 0$ independently of the security parameter, and determine the maximum value of $a$ for which this claim holds (assuming that secure MAC schemes exist).

As for solving this problem, consider an adversary $A$ that uses $C$ to generate a message pair $m_1, m_2$, queries the oracle for $t_1 = S(k,m_1)$ and outputs $(m_2, t_1)$.  What is the advantage of such an adversary?

For bonus points, show that, given a secure MAC scheme $(S^*,V^*)$ (i.e. one against which no adversary has more than a negligible advantage), we can construct a triple of efficient algorithms $(S,V,C)$ that has the property described in the question, and against which no adversary can have more than a negligibly higher advantage than the adversary $A$ described in the previous paragraph.


It is hard to have message authenticity without integrity. To authenticate the message you need to know what message is being authenticated. If you could change the message the authentication tag should become invalid. Message authenticity means that you can establish that the message originated from a trusted entity. For this reason message authenticity often implies integrity.

This doesn't go the other way around because of checksums. Checksums can be used to protect integrity of a message. Checksums however do not protect against active attacks as anybody is able to calculate a checksum. If you need to protect against active attacks then the message is usually authenticated as well.

I'm not sure that "data authenticity means that the initial message sender is who he/she claims to be" is a correct definition. That seems the definition for entity authentication. The data may not be an identifying aspect for the entity. I would rather say that message authenticity proves that the message originated from a specific entity. In that case - as explained in the first section - integrity is probably implied.

As an example, say we find a bunch of paintings all bearing the same signature. We however do not know who created the paintings. All we know is that there is some unknown painter that painted the messages - the identity of the painter is not really established. What we do know however is that all the paintings belong to a single painter. That says quite a lot about the paintings themselves.

If you look at entity authentication then no explicit message needs to be involved, so data integrity may not be required. So there you are: authentication without integrity.

Authenticity and integrity are different concepts, even if used in the context of data/messages. It doesn't make sense to mix those concepts even if one implies the other. So I try to write "message authentication and integrity" instead of just "message authenticity" or "message integrity".

In text you have to distinguish between message and entity authentication. If you have message authentication you know that integrity is very likely implied. This is not the case for entity authentication. So you do need to look at context to see if integrity is implied.


How to change the following commitment scheme to Pedersen commitment?

My answer one the other question assumed that you use elliptic curves as they usually are more common when it comes to ZKP because of their size and speed, however, you can easily change the notation since

$xG$ is equivalent to $g^x\ (mod\ p)$
$A+B$ is equivalent to $A\cdot B\ (mod\ p)$

I will not explicitly write $(mod\ p)$ from now on.

$P$ chooses a random $r$ and calculates $C=g^r h^{[age]}$.
$P$ signs $a$ with $r$ as private key.
$P \rightarrow T: C,a, signature_a$
$T$ looks up $P$'s age, calculates $R = C \cdot h^{-[age]} = g^rh^{[age]}h^{-[age]}=g^r$, verifies $signature_a$ against $R$ and signs $C$ using $T$'s private key.
$T \rightarrow P: signature_C$
$P \rightarrow V: C, signature_C, proof$


Hash functions operate on blocks like SHA-256 has 512-bit input block. In SHA-256, your data $m$ is divided into 512-bits blocks $m_1,\ldots,m_n$ where each entered into the hash function. The final block, $m_n$ is padded as

$$k=(447−l) \bmod 512$$ where data size is $l$ and $k$ is the number of zeros following the 1 after $m$ and finally the message size in 64 bits. The message size can also 128 which allows larger files to be hashed. So the input to SHA-256 is

$$m\|1\|0\ldots0\|\text{size_of(m)}.$$

Each other hash function defined in a similar way, an example from FRC4634

  The hash functions specified herein are used to compute a message
     digest for a message or data file that is provided as input.  The
     message or data file should be considered to be a bit string.  The
     length of the message is the number of bits in the message (the empty
     message has length 0).  If the number of bits in a message is a
     multiple of 8, for compactness we can represent the message in hex.
     The purpose of message padding is to make the total length of a
     padded message a multiple of 512 for SHA-224 and SHA-256 or a
     multiple of 1024 for SHA-384 and SHA-512.

Note: The 64-bit (or 128-bit) message size also determines the maximum input size for a SHA-256 hash.


Is it possible to derive the recipient's public key from libsodium's crypto_box?

You are given $E_{H([ab]P)}(n, m)$ and $[b]P$, where

$E$ is an authenticated encryption function,
$H$ is a hash function,
$a$ is the recipient's secret key and $[a]P$ is the recipient's public key,
$b$ is the sender's secret key and $[b]P$ is the sender's public key,
$P$ is the standard base point on the standard curve,
$n$ is a nonce, and
$m$ is a message.

Your task, as stated, is to find which of $[a_1]P, [a_2]P, \ldots, [a_k]P$ is $[a]P$.  Let's assume you already know $n$ and $m$; if you don't—if your knowledge about them has total min-entropy $e$ bits—then you'll probably have to iterate this process $2^e$ times.  Let's simplify it a little bit and say you only want to tell whether $[a]P = [a_1]P$ or not; you can repeat it $k$ times to find which key among the choices, if any.

Suppose you have a random algorithm $A(Q, R, c)$ that returns 1 with high probability for $A([a]P, [b]P, E_{H([ab]P)}(n, m))$ and returns 0 with high probability for any other inputs.  Then I can define an algorithm $A'(Q, R, S) = A(Q, R, E_{H(S)}(n, m))$ that serves as a distinguisher for the decisional Diffie–Hellman problem in the group generated by $P$, because it returns 1 for $A'([a]P, [b]P, [ab]P)$ with high probability and returns 0 for any other inputs with high probability.

So the answer is: No, Eve cannot even confirm the recipient just by examining the ciphertext.  This property is sometimes called key privacy or anonymity.  (The formulation in the paper is slightly different, but I think it is equivalent; if not, adapting the proof to the formulation in the paper is left as an exercise for the reader, since most DH-based schemes naturally exhibit key privacy, unlike RSA-based schemes.)


Is the 1st Encrypted Block Less Secure Than Subsequent Ones?

In the first block, the IV provides the "randomness", and in subsequent blocks you just use the previous block of ciphertext instead. Based on the assumption, that the cipher is not weak and behaves like a pseudorandom permutation, this is basically the same: You XOR something unpredictable on the plaintext, and then encrypt.

As long as the IV is chosen randomly (and therefore, it should never be the same), there is no weak beginning. If you disregard the randomness and always start with the same value for a new message, then yes, the first block can be considered weaker. Because then you can distinguish, if two messages have the same beginning.


How to generate a random polynomial of degree $m$?

I assume you're referring to section 5 of the paper you linked to, which reads:

5 An instance using polynomials
In this section, we describe an instance of the technique of
Section 4 using Shamir's secret sharing scheme [25]. In this
scheme, $\mathrm{hpwd}_a$ is shared by choosing a random polynomial
$f_a \in \mathbb Z_q[x]$ of degree $m - 1$ such that $f_a(0) = \mathrm{hpwd}_a$. The
shares are points on this polynomial. We present the method
in two steps, by first describing a simpler variation and then
extending it in Section 5.4 to be more secure against an
offline attack.

To choose a random polynomial $f(x) = c_k x^k + \dotsb + c_1 x + c_0$ of degree $k$ in the polynomial ring $\mathbb Z_q[x]$ simply means choosing $k+1$ random coefficients $c_0, c_1, \dotsb, c_k$ uniformly from the finite field $\mathbb Z_q$.  However, the additional constraint that $f(0) = c_0$ should take a particular fixed value means that, in fact, only the $k$ coefficients $c_1, \dotsc, c_k$ can be chosen randomly, while the constant coefficient $c_0$ is fixed.
(Note that, using this procedure, there's a one in $q$ chance that $f$ will actually be of a degree lower than $k$, because $c_k = 0$ by chance.  However, in the context of Shamir's secret sharing that's exactly what you want: the polynomial really should be randomly chosen from the set of polynomials of degree at most $k$ in $\mathbb Z_q[x]$ whose lowest coefficient has the desired secret value.)

Ps. A note on notation: $\mathbb Z_q$ here denotes the ring of integers modulo $q$, which is a field if and only if $q$ is prime.  However, Shamir's secret sharing actually works in any finite field $\mathbb F_q$, which exist for all prime powers $q = p^n$.  In particular, the characteristic-2 fields $\mathbb F_{2^n}$ are often convenient to work in, since their elements correspond naturally with $n$-bit bitstrings.  The downside, of course, is that multiplication in finite fields of non-prime order is slightly trickier to implement (or, rather, that you're somewhat less likely to find an existing built-in implementation of it). For more details, see e.g. Galois fields in cryptography.


Dangers of using CTR mode for encryption

From your question I'll assume that you do not plan to use strong means of authentication along with CTR encryption. If you do, the first point is invalid.

Never ever use CTR mode alone. If you use CTR mode alone (i.e. without authentication) you allow attackers bit level precision for changing files. This can result in very undesirable decryptions where important data was changed because the attacker knew the format, the position and the previous content.
Never ever re-use a nonce + key pair. If you do re-use a {nonce, counter} and key pair, you allow an attacker to perform a ciphertext only attack (the worst sort of attack imaginable) and the complete security of the system should break down. Note further that re-using the same counter at any space-time combination suffices.


Keys: Is This Way of Encryption Already Invented?

Maybe not the precise scheme, but having elements in the key select a particular cipher is pretty common - mainly by persons starting crypto. All in all they are generally not secure and end up discussing Kerckhoffs's principle.

It is not easy to create a modern, secure cipher by alternating between a lot of insecure classical ciphers. No doubt it can be done, but this scheme is not intricate enough for that; it will fail basic randomness tests and will probably fall to frequency analysis as well.


Is it necessary to encrypt nonce in cryptographic communication?

If your nonce is 16 bytes, and your message pre-nonce is a multiple of 16 bytes (i.e. no padding is needed), sending the nonce in the clear opens you up to replay-ish attacks. Specifically, if an attacker captures one exchange with nonce $N$ and response $R$ (with $b$ blocks $R_1$ through $R_b$), and then impersonates the server and the client sends them $N^\prime$ as nonce, they can create a new message with the correct nonce at the cost of scrambling the last block of $M$ (by XORing the second-last block of $R$ with $N\oplus N^\prime$). How this affects your system depends on the specific system, but this is generally not something you want to be possible.

The proper way to mitigate this isn't to send $N$ encrypted: it's to use authentication on the server's response. The client will already refuse a message that has a previously used nonce; it will also refuse a message that doesn't have the correct nonce value. That means that an attacker already can't do a straight replay attack, because a straight replay will be rejected. However, you should still worry about an attacker maliciously tweaking the message (that thing where if they know the contents of one block, they can change them at the cost of scrambling the previous one? That's true for all your blocks, and they can do it on the first block without scrambling any other blocks at all.) On the other hand, with a proper message authentication code, you can prevent any attacker who doesn't know the key from feasibly forging any message from the server; properly done authentication means that the only messages an attacker could send are exact replays, so if you can throw those out they can't do anything.

So the correct response is "use authentication, preferably with an AEAD mode like GCM, CCM, or EAX." (AEAD combines encryption and authentication in a secure way; it's fairly easy to screw up if trying it yourself). If you can't use AEAD, share a second key to use for a MAC algorithm and then use that MAC on the ciphertext to authenticate it (and do that before decrypting the ciphertext). Then you don't need to worry about encrypting $N$ or not, because the attacker can only pull off an exact replay and an exact replay is blocked by your challenge-response system.


What's the difference between DH and DHM?

Yes, it's the same.
Wikipedia writes on the subject:

In 2002, Hellman suggested the algorithm be called Diffie–Hellman–Merkle key exchange in recognition of Ralph Merkle's contribution to the invention of public-key cryptography (Hellman, 2002), writing:

The system...has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie–Hellman–Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography.[7]


Example of a problem for which Zero-Knowledge proof is not sequentially composable

The paper you cited gives that exact example. It shows that zero-knowledge that is NOT zero-knowledge for auxiliary input is not strong enough. The fact is that most known zero-knowledge proofs are secure for auxiliary input and thus are secure under sequential composition.


Why does openssl BN_generate_prime return only a fraction of the safe primes within the given bit range?

The smallest safe prime you got from OpenSSL was 3221226167 = 0xC00002B7.  The largest was 4294967087 = 0xFFFFFF2F.  This makes me hypothesize that OpenSSL is setting the two high bits to one, and choosing the rest of the bits randomly.  If that is accurate, that would explain the range of primes you did.

As far as why you found many more safe primes in the range between 0xC0000000 and 0xFFFFFFFF, I don't have a good explanation for that.  I would have predicted that your experiment with OpenSSL should turn up approximately 96.2% of all safe primes in that range.  I don't know why you only saw 89.1% of the safe primes in that range.  Is it possible that OpenSSL has a slightly different definition of safe prime than what you were using in your exhaustive prime sieve?

Oh, why 96.2%, you ask?  It has to do with the coupon collector's problem.  If you have $n$ different objects, and you randomly draw $n$ times (sampling with replacement), you don't expect to observe all possible objects.  Instead, some objects will have been chosen multiple times, and some will have been chosen only a few times.  In your case, there are apparently 3059799 different safe primes (objects).  You draw $10^7$ times (with replacement).  What fraction of safe primes will be missed?  Well, let's fix a single safe prime.  The probability that it is missed on any one draw is $1-1/3059799$.  The draws are independent, so the probability that it is missed on all of the draws is $(1-1/3059799)^{10^7}$, which is approximately $0.038$.  In other words, we'd expect that a $0.038$ fraction of safe primes will never have been output by OpenSSL, in your experiment, assuming OpenSSL samples uniformly at random from all possible safe primes.  This corresponds to covering 96.2% of the safe primes during the $10^7$ draws you did.

Another possible explanation for your observed data is that maybe OpenSSL does not choose uniformly at random from all possible safe primes in that range; maybe some safe primes are slightly more likely to be chosen than others.  For instance, one possible method for generating a prime number at random is to select an integer $m$ at random, test if it is prime; if not, test $m+1$ for primality; if that's not prime, test $m+2$; and so on, continuing until you find a number that is prime.  This procedure does not generate the uniform distribution on primes of a certain size: primes that are preceeded by a large gap (a long stretch of composite numbers) will be more likely to be drawn than others, and primes $p$ where $p-2$ is also prime will be less likely to be chosen.  It is possible that OpenSSL is using some sort of random prime generation strategy like this.  If it is, then this affects the coupon collector's calculation, and we'd expect to see somewhat more repeats.  So, your observed numbers are consistent with this hypothesis.  If this is how OpenSSL is generating primes, it is a deviation from the uniform distribution on safe primes, but this deviation is not believed to cause any security problems.  The number of possible safe primes is still ginormous (the entropy of the distribution is still plenty large), so there's no known way to take advantage of any non-uniformity that results.

This gives you some hypotheses and potential explanations you could test further.  An authoritative answer might require spelunking through the OpenSSL code (which is not much fun at all!).


what is the maximum size of the payload data when using ed25519

That depends really on which symmetric cipher and cipher mode is used. Basically, the strength provided by the secret is 128 bits, as indicated in the page you linked to.

Usually the secret is then converted into a key using a Key Derivation Function (KDF) or even into multiple keys, which will each have a security level of 128 bits (as long as the KDF is strong enough, but that's commonly the case).

After that it is up to the scheme used. Probably you don't want to go over $2^{128}$ blocks of encryption, but that's kind of nonsense in the first place.


How can a decryption program tell me that a private key is incorrect for RSA and ECC?

The answer is different for the schemes that are used. So there is no one answer for the simple reason that the different modes have different properties.

In general modes such as PKCS#1 v1.5 or OAEP encryption is used for RSA. These modes contain a specific padding that is performed before the modular exponentiation that is the backbone of RSA. Performing the modular exponentiation with the private key - possibly sped up using the Chinese Remainder Theorem or multi-prime calculations - will result in the padded message. Now the padding is checked before the message is returned. This means that using an invalid private key / ciphertext pair will result in a padding error. Note that padding errors may actually lead to attacks on the key.

It is not possible to perform encryption directly using ECC. Instead ECIES can be used to perform it indirectly. This is basically key agreement followed by encryption using a symmetric key. In this case the asymmetric key agreement may fail without error resulting in an incorrect symmetric key. Then the subsequent decryption may not cause an error either. This can be fixed by using an authenticated cipher such as GCM, which generates an error for any invalid secret key / ciphertext pair.

The same goes for RSA-KEM as for ECIES. So again: it depends on the scheme.

So the conclusion: use an authenticated encryption scheme for the symmetric cipher. And don't forget to protect against padding oracle attacks for RSA. PKCS#1 v1.5 padding should not be used anymore because of a specific padding oracle attacks called the Bleichenbacher attack. OAEP should be secure (if the implementation is secure, of course).

If you do that you can be sure that some kind of error is returned if you use an invalid private key / ciphertext pair.

Another option is to sign the plaintext message. In that case you can verify the authenticity of the message after decryption. This has the additional advantage that an adversary cannot simply encrypt a different message using the public key. In general this should be combined with the authenticated encryption option mentioned in the previous section.


Digital Signature Algorithm (DSA) with medium fields

The question deals with the finite field $\mathrm{GF}(p^n)$. It wants to study/attack a variant of DSA in (the multiplicative subgroup of) that field, rather than $\mathrm{GF}(p)$. Whatever that DSA variant is, it can be attacked by solving the Discrete Logarithm Problem in $\mathrm{GF}(p^n)$.

The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-1$, and the order of any element divides that. If the order of $a$ has no large prime factor, then the Pohlig-Hellman method allows reduction to easier subproblems, that a general DLP algorithm like Baby-Step Giant Step or Pollard's rho can solve. DSA blocks such attacks by working in a multiplicative subgroup of large prime order $q$ (e.g. at least 256-bit). That also keeps signature size to the minimum (twice the bitsize of $q$).

The parameters envisioned are $p\approx10^{10}$ and $n=17$, thus $p^n$ about 565-bit, making such subgroup plausible. If we want $p$ just below $2^{32}$ and $x^{17}-2$ irreducible modulo $p$ (which simplifies computations), we can use the 32-bit $p=\mathtt{ffe083f1}_\text{h}$, with $p^{17}-1$ having as highest prime factor the 262-bit $q=\mathtt{2a92bc16243adf3264304adf2adc292c32e64b569a5abfbd7be71d7a1816e3d8c1}_\text{h}$. To obtain an element of order $q$, we can select almost any arbitrary polynomial $u$; find the order $r$ of $u$ (we divide $p^{17}-1$ by primes in its factorization while raising $u$ to that power yields $1$); and use $g=u^{r/q}$ as the generator of a subgroup of order $q$.

Building a DSA analog from that and SHA-512 is easy. The only difficulty is when the original makes an exponentiation modulo $p$ followed by a reduction modulo $q$. Among many, one option to parallel this is to make the exponentiation modulo $x^{17}-2\pmod p$, then evaluate that polynomial in $\Bbb Z$ at the point $x=2^{32}$ (that is concatenate the coefficients expressed as 32-bit integers), then reduce modulo $q$.

That will make a working DSA, secure against all the aforementioned algorithms thanks to the large $q$. But that's nevertheless insecure, for other DLP methods are applicable to the case at hand. There's a summary of recent results in Razvan Barbulescu and Cécile Pierrot's The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields, in LMS Journal of Computation and Mathematics, 2014.

Tentatively: the algorithm of choice to attack that DSA analog could be Antoine Joux, Reynald Lercier, Nigel P. Smart, and Frederik Vercautere's The number field sieve in the medium prime case, in proceedings of Crypto 2006.

The musing with a small example at the end of the question attempts to work in $\mathrm{GF}(17^7)$, but uses a polynomial $m_1=x^7-2$ that is not irreducible modulo $p=17=m_2$, since$$(x+8)(x^6+9x^5+13x^4+15x^3+16x^2+8x+4)\\\quad\equiv x^7-2\pmod{17}$$

It follows that $(x+8)$ is not invertible, and we get a ring rather than a field.

If we change to $p=29$ that makes $x^7-2$ irreducible. I assume this in the following.

The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-1$, here $29^7-1$. This factors as $2^2\cdot7^2\cdot88009573$. The order of $a$ is bound to be a divisor of that. By computing $a^{(29^7-1)/2}=-1\ne1$, $a^{(29^7-1)/7}=-5\ne1$, and $a^{(29^7-1)/88009573}\ne1$, we get that $a$ is a generator of the full multiplicative group. $b\ne0$, therefore $a^e=b$ has a solution.


Can machine learning analyze random number generator?

The goal of an ideal cryptographically secure pseudo-random number generator (CSPRNG) is to produce a stream of numbers that no machine can distinguish from a truly random stream of numbers. Formally, it's impossible unknown whether it's possible to prove that a CSPRNG is truly random.

That being said, there exists a family of statistical tests that can measure whether a sequence of numbers appears to be uniformly random, and produce a probabilistic analysis as output. I'm not sure if these tests qualify as related to machine learning, but here are some examples:

Chi-squared distribution testing.
Statistical hypothesis testing.

If you are interested in trying out a CSPRNG, you can use:

AES-CTR with a random key acting as the seed.
Under Linux, Mac OS X, BSD, /dev/urandom.
window.crypto.getRandomValues() in your browser console (Chrome, Firefox).

Note that not all PRNGs are CSPRNGs.


Is Schannel supposed to use SHA1 for (EC)DHE params?

I'm led to believe the use of SHA-1 for the ECDHE parameters is not due to misconfiguration, but is rather the intended (albeit not ideal) behaviour of server-side Schannel. This behavior seems to be present in versions up to Windows Server 2012 R2 and even continues with Windows Server 2016 Technical Preview 5.

I've captured handshakes with many, many random servers that advertise they're using some version of IIS and the negotiated cipher suite uses ECDHE. In all cases, the signature algorithm chosen for ECDHE params is SHA-1. I couldn't find a single IIS server that used SHA-2.

If anyone has any evidence that IIS/Schannel is capable of using SHA-2 in this scenario, please post, otherwise for now I'm going to consider this answered as "by design".


Bitmasks or seed along with public key in WOTS+ post-quantum signatures

The XMSS Internet Draft actually does not implement the original XMSS scheme but XMSS-T as described in Mitigating Multi-Target Attacks in Hash-based Signatures, by Hülsing, Rijneveld, and Song (PKC 2016). There also a security reduction is given that shows that exactly this is ok (using a SEED instead of a list). It also introduces keying all hash function calls (which is also implemented in the Internet Draft) to prevent multi-target (second-)preimage attacks. The drawback of using a SEED is that this step requires a (Q)ROM proof. The reason is that the standard model PRF / PRG security properties all require the seed / PRF key to be kept secret (while it gets published in the given scenario).


Extract adversary's secret input in simulation based security proofs

@WYC, I suggest you take a look at the Lindell tutorial on https://eprint.iacr.org/2016/046.pdf

To answer you #1 question, I'll get from that tutorial the following requirements for the simulator:

It must generate a view for the real adversary that is indistinguishable from its real view;
It must extract the effective inputs used by the adversary in the execution; and
It must make the view generated be consistent with the output that is based on this input.

To answer your #2 question: the simulator is doing a mimic of the adversary. We can say it is a comparision: whatever the adversary do in the real world the (simulated) adversary must be able to do in the ideal world. Therefore, do not read this as a proof of the protocol's flaw. The point is: do you agree that the adversary chooses its inputs? So how simulate it in an indistinguishable way?


AES CTR with a non random and predictable nonce?

For CTR mode, a random IV is not needed. The only requirement be that the counter be unique in each block over all encryptions. (This is in contrast to CBC mode where unpredictability of the IV is essential.)


How to invalidate decryption key in multi user model?

Sure.  Encrypt John's private key under Adam, Emily, and Scott's public key.  When you revoke Emily and change John's keypair, encrypt John's new private key under Adam and Scott's public key.  If Adam or Scott need access, they can decrypt.  After the key change they will still have access and still be able to decrypt it, same as they were able to before.


How to devise cryptographic system with data-sharing ability and password reset

The phrase "password reset" is not applicable for encryption.
Password reset means that starting from some moment only a new password can be used and none of the previous passwords can be used any more. For encryption this is not possible, because if some password (key) can be used for decryption, it can still be used without any limits. For instance, if reset was possible and user reset password to a new one, then a few days later found the previous password, this password would obviously still be able to decrypt the same data.
Thus, we cannot call it "reset". The requirement to be able to decrypt the data in case user forgotten the password actually means:

either you may help user to restore the current password (decryption key)
or, if encryption scheme allows multiple decryption keys, you give user an additional password (key)

In both cases you as a developer can obtain a password (decryption key) not only when user asked you about this, but also on your own. Thus, the requirement 3 would be violated.
Any schemes with secret sharing don't fit these requirements as well. If you implement secret sharing where user has one part of the additional decryption key, this can also be lost. If you implement secret sharing where user has none of parts of shared secret, then the secret (decryption key) can be restored without the user knowing about that, thus the requirement 3 would be violated.
Briefly: There is no way to fulfill all your requirements simultaneously. This has nothing to do with cryptography, this is just a common sense.  Means, at least one of requirements need to be changed.


Why don't the TLS1.3 cipher suites mention the key exchange and digital signature algorithm in names?

Yes. TLS 1.3's cipher suites only specify its symmetric AEAD and hash algorithms. The signature algorithms are specified separately. Several (asymmetric) signature schemes can be used with the same cipher suite.


Pseudocode for constant time modular exponentiation

No.  If you don't have a strong math background, implementing RSA yourself is a  bad idea (and perhaps even if you do).  There are many ways to go wrong, which can open up subtle security weaknesses.

Instead, you should use a well-vetted RSA implementation from a standard crypto library, and a well-vetted protocol -- or hire a cryptographer who does understand the mathematics, if you don't think you can trust any existing implementation or need help selecting one that is suitable.


Symmetric key in homomorphic encryption over the integers

It turns out that just like the question linked to in the question, the key needs to be an odd number so that the encrypted number doesn't have the same parity (odd or even-ness) as the plain text value.  When it has the same parity, the encryption failed because you can tell exactly what the plaintext bit was!

As for why the high bit needs to be set, I'm going to just assume that it's to make sure the key is large, which helps security.  If someone knows differently, please inform me!


Can we use a Cryptographic hash function to generate infinite random numbers?

This construction gives you cryptographic-quality pseudorandom output, but it isn't as secure as it can be for a random generator.

With commonly used hash functions $H$ (such as any of the SHA2 and SHA3 family), as far as we know, the bits of $H(\textrm{seed}, n)$ are unpredictable if you only know $n$ and $H(\textrm{seed}, m_i)$ for any number of values $m_i \ne n$, but you don't know $\textrm{seed}$. This makes $D(n) = H(\textrm{seed}, n)$ a good key derivation function: its output is essentially indistinguishable from random.

A good random generator must have the property that a bit in the output is not predictable even if the adversary knows all the other bits of the output, but not the seed. The construction $H(\textrm{seed}, \textrm{counter})$ has this property. But a good random generator also has an additional property: backtracking resistance. Backtracking resistance means that if the adversary compromises the hash state at some point, then they can't recover past outputs. (Of course the adversary will know every future output, at least until the random generator is reseeded.) Your construction does not have this property since the original seed remains a part of the hash state.

A good random generator has a “ratcheting” step, which makes it impossible to recover the previous state from the current state when generating some output. It's easy to build ratcheting with a hash function: you basically just run the hash function on the hash state. Take a hash function with an $n$-bit output. Start with an $n$-bit secret seed; that's the original state of the random generator. To generate up to $n$ pseudorandom bits, calculate $H(0 || \textrm{state})$ and output that; also calculate $H(1 || \textrm{state})$ and use this as the next internal state. In pseudocode:

state = seed
while True:
    output(hash('0' + state))
    state = hash('1' + state)

Hash_DRBG specified in NIST SP 800-90A is a popular pseudorandom generator construction based on this principle.


When does a multiple Vignere cipher become intractable?

Yes, if you know the key lengths and have a sufficient amount of known plaintext, you can easily recover the keys (or at least something equivalent to them) using linear algebra.

How much is "a sufficient amount"?  Well, to fully recover all the key characters, you would need to solve as many linear equations as there are characters in all the keys combined, and would thus need at least that many ciphertext/plaintext character pairs to get a unique solution.

However, in general, some of those equations will be redundant, because multiple Vigenère encryption has equivalent key(set)s.  This implies that a) you cannot, in general, fully recover the original keys, but b) you can generally recover an equivalent set of keys with less known plaintext than the combined length of all the keys.

The exact amount of redundancy will depend on the key lengths.  As an extreme example, encrypting a message with two keys of length $a$ and $b$, where $a$ is an integer multiple of $a$, is obviously equivalent to encrypting it with a single key of length $a$.

More generally, adding a constant to all characters of one key and subtracting the same constant from all characters of another key obviously won't change the result of the encryption.  By choosing suitable constants, we can transform any set of keys to an equivalent one where (e.g.) the first character of each key except one is zero.  So, in general, a set of $n$ keys with total length $\ell$ can have at most $\ell - n + 1$ non-redundant characters, and thus finding an equivalent keyset requires at most that many known plaintext characters.

(Of course, that's assuming that each ciphertext/plaintext character pair actually contributes to the solution.  Depending on where the known pairs are located in the message, this may not always be the case, either.  For example, trivially, two ciphertext/plaintext character pairs separated by a distance that is divisible by the least common multiple of the key lengths will be encrypted with the same key characters, and thus knowing them both won't provide any more information about the key than just knowing one of them.  On the other hand, I would conjecture — but cannot prove off the top of my head — that a sequence of $\ell - n + 1$ consecutive ciphertext/plaintext character pairs should always be sufficient to find an equivalent keyset.)

If all the key lengths are coprime, I believe $\ell - n + 1$ ciphertext/plaintext character pairs is also the minimum number needed to fully determine the key set (up to equivalency).  Otherwise, fewer should be sufficient.

Also, yes, if the message is no longer than the longest key, and that key is fully random, independent of the other keys and used only for one message, then the system is equivalent to a one-time pad, and thus provides perfect secrecy.

Essentially, this is because just encrypting the message with that one key is sufficient to provide perfect secrecy, and anything else we do with the message cannot compromise that.

In fact, since Vigenère encryptions commute with each other, we can always arrange them so that the encryption with the long random one-time key happens last.  Thus, we can treat the result of all the other encryptions as the plaintext input to a one-time pad scheme, which of course perfectly conceals its input.  Thus, nothing about any of the other keys matters in any way, as long as at least one of the keys satisfies the criteria (randomness, independence, length, non-reuse) for being a secure one-time pad.


Zero-knowledge proofs vs. "Identification schemes"? (as in Katz--Lindell)

I think I'm qualified to answer this question :-). The approach of going via identification schemes suffices for constructing secure signature schemes. Since this is the aim of this part of the book, it is much simpler than doing full blown zero knowledge. However, if you are interested in looking at sigma protocols and compilation to non-interactive zero knowledge via Fiat-Shamir, then you are going to need the more complex definitions. So, in short, what we do in the book is not more general; on the contrary, it's more specific, but suffices for what we need.


Proof of shared secret through key derivation

HMAC nor a KDF is needed here. As long as you always use a constant size key and "tag" (generally called a nonce, as in number-used-once) you can simply use a secure hash function, like SHA-256.

My suggestion is to drop keeping track of the tags sent so far - this administration is bound to fail at some point. Instead, generate a 32 byte random number. This reduces the chance of collision to a neglegible amount.

So if you use my proposed scheme:

Alice sends a 32-byte random number $n$ to Bob.
Bob replies with $H(K || n)$.
Alice checks the result.

Then an eavesdropper or even a MITM attacker will never learn $K$ faster than bruteforce.


Why does ε-differential privacy protect the subset of 1/ε edges in terms of graphs?

I think this is a reference to group privacy. See Theorem 2.2 in the Dwork-Roth book.

If you have $(\varepsilon,0)$-differential privacy for changing 1 edge, then you have $(1,0)$-differential privacy for changing $1/\varepsilon$ edges.


Your solution is not resistant to a rainbow table attack. Furthermore, what if an adversary supposes your locality: ask you about your "private" location information, fake his/her one and tries to retrieve yours?

When you say "Anonymous location" and "without revealing the location" you are demanding a very difficult problem of Multiparty Computation: see MPC millionaire problem.

B.T.W, we can find more robust solutions that mix hash and location privacy: have you ever heard about "Spatial Bloom Filter"?


Is xgcd faster than Fermat for calculating $d$ in RSA?

The extended Euclidean algorithm ($\operatorname{xgcd}$), when applied to $p$ and $e<p$, uses at most $\lceil\log_\phi(\sqrt5(p+1))\rceil-2\in\mathcal O(\log p)$ divisions in $\mathbb Z$. (This is Knuth's corollary to Lamé's theorem.)
Using Fermat's little theorem and square-and-multiply exponentiation on $e$ modulo $p$ takes at most $2\cdot\lfloor\log_2(p-2)\rfloor\in\mathcal O(\log p)$ multiplications in $\mathbb F_p$.

Therefore, both methods are asymptotically equivalent. However, there are some practical benefits when using $\operatorname{xgcd}$:

The involved numbers' bit length decreases very quickly.
A division with remainder is generally cheaper than a multiplication followed by a modulo operation.


The strong authentication protocol referred to in the book is defined in the Annex N of "X.509 (10/16)" published by the ITU https://www.itu.int/rec/T-REC-X.509

Here is an excerpt of the standard for the two-way and strong three-way protocols:

  Annex N

  Considerations on strong authentication

  Strong authentication makes use of PKI as specified by this Specification, which
  provides the basic approach to authentication. However, many authentication procedures
  employing this approach are possible. In general, it is the business of a specific
  application to determine the appropriate procedures, so as to meet the security
  policy of the application.

  NOTE – This Specification does not specify the procedures in the detail required
  for implementation. However, additional standards could be envisaged that would do
  so, either in an application-specific or in a general-> purpose way.

  Two-way authentication, described in clause N.3, involves, in addition, a reply from
  B to A. It establishes, in addition, the following:

  that the authentication token generated in the reply actually was generated by
  B and was intended to be sent to A;
  the origin, integrity and timeliness of the authentication token sent in
  the reply;
  (optionally) the mutual confidentiality of part of the tokens.

  Three-way authentication, described in clause N.4, involves, in addition, a
  further transfer from A to B. It establishes the same properties as the two-way
  authentication, but does so without the need for association timestamp checking.


Changing password hash and iv on (successful) user login

the initialization vector for openssl is re-created
  1. generate 16 random bytes.
  2. Hash the bytes with SHA256.
  3. Store the hash in the database

if you generate 16 random bytes (128b), there is no reason to hash it

  password is stored as a SHA256 hash of the openssl output.
  How strong is this method?

you're encrypting the password what has a principial weakness - it is reversible. Once someone get access to your system (therefore all the code and configuration including your secret key), all user passwords are to be revealed. The user passwords should be stored as salted hash, so they are unrecoverable.

Seems you are effectively storing a salted hash of the password, that is good. However the sha256 is relatively fast function, you better to use PBKDF2 (slow hash) to mitigate dictionary or brute-force attack. There is a nice article how to do it properly

  Does updating the database user credentials increase or decrease the chances of a decryption in any event?

The problem is once someone get access to the database and  and all the configuration, the adversary will have all information needed to decrypt all the passwords.

Next - if the passwords won't change themselves, I see no reason for re-hashing the passwords, it just increases complexity of your application.


Role of Fermat's little theorem in the proof of correctness of ElGamal signature

Thanks to fgrieu's comment above and the following quote from here (PDF):

  Theorem:

  Let $p$ be a prime and let $a$ be a number not divisible by $p$. Then if
  $$ r \equiv s \pmod {p − 1} $$
  we have
  $$ a^r \equiv a^s \pmod p$$ In brief, when we work $\mod p$, exponents can be taken $\mod{p − 1}$.

I (think i) understood, how the first (implicit) step relies on Fermat's little theorem:
$$\begin{align}
g^{H(m) \pmod{p-1}} &= g^{xr+sk \pmod{p-1}} \\
g^{H(m)} &\equiv g^{xr+sk} \pmod p
\end{align}$$


How to model a miniature elliptic curve?

The curve parameters include:

$p$: The prime modulus of the underlying field

$a$ and $b$: These are used in the curve equation, $y^2 = x^3 + ax + b$

$G$: a point on the curve that generates a subgroup

$n$: the order (number of points) of that subgroup

Once you have decided on your $p$, the process is basically try different curve parameters and a point-counting algorithm to find a curve with a large, prime order subgroup.

You can do this all automatically using SageMath

Here is a script that will generate a curve for you with the given bit size: https://github.com/brichard19/ecdl/blob/master/scripts/gencurve.sage


There is really no need to go beyond 256 bit security. If you want to combine multiple keys - presumably because you are not sure they provide enough security regardless of the size - then you could concat them and use them as Input Keying Material to a KBKDF that provides extraction as well as expansion (e.g. HKDF). Then the output can be used to seed your PRNG.

It seems you are trying to build your own KDF using CTR mode. Such KDF's already exist, but they generally don't provide extraction of the entropy, just expansion of statically sized (128, 192 or 256 bit) keying material. Proving that your scheme does extract entropy well will be tough to accomplish.

The only drawback of using HKDF for this is that the keying material must be in memory to perform the calculations; you should make sure that this is (1) possible and (2) possible to secure. How big this drawback is depends on the situation.


In constraint systems for ZK proofs, why are multiplications counted but are additions not?

Your question seems to assume this is true for any constraint proof system. I'm quite confident that this property is on a case-by-case basis. Bulletproofs, for example, have this property: proof size is $\log(n)$, with $n$ the amount of multipliers in the arithmetic circuit. In the rest of my answer, I'll talk about how a bulletproof achieves this.

I'll give a very condensed sketch of how bulletproofs achieve this property. For a more in-depth explanation, I suggest to read the above paper, or the (in my opinion) simpler notes of the good folks at dalek-cryptography.

Bulletproofs writes their constraint system in a single vector equation like follows:

\begin{aligned}
\mathbf{W}_L \cdot \mathbf{a}_L +
\mathbf{W}_R \cdot \mathbf{a}_R +
\mathbf{W}_O \cdot \mathbf{a}_O =
\mathbf{W}_V \cdot \mathbf{v} +
\mathbf{c}
\end{aligned}

Here, the $\mathbf{W}_{\{L,R,O,V\}}$ are weight matrices: they map secrets from their right hand side to constraints. $\mathbf{v}$ are the input secrets. Note that this equation contains the linear constraints, not the multipliers. In what follows, they combine it with the multipliers ($\mathbf{a}_L\circ \mathbf{a}_R=\mathbf{a}_O$), and then this equation is molded into a form $t(x)=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle$, in which $x$ is a challenge of the verifier. Here's the first clue: $\mathbf{l}(x)$ and $\mathbf{r}(x)$ are of length $n$, the amount of multiplication gates.

The proof process links $t(x)$ and the two vectors $\mathbf{l}(x)$ and $\mathbf{r}(x)$ to the secret input commitments (in constant size), and then goes on to prove that their inner product relation holds: the inner product proof. This was introduced by Bootle et al., in Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting, and improved upon in the bulletproofs paper. This is your second clue: this inner product argument that proves something of the form $t=\langle \mathbf{l}, \mathbf{r}\rangle$ needs $\log(|l|)=\log(|r|)$ communication.


Short answer, before someone marks this as a duplicate or answers it with an essay or something:

You're exactly right. This was one of the biggest consequences of the infamous Heartbleed exploit in OpenSSL, which exposed the memory of processes using OpenSSL for TLS to anyone with an Internet connection. It's also significant for cold boot attacks, where someone with physical access to a computer shuts it down and boots a live CD or rips out the RAM and reads it before it loses all charge (moments, normally; much longer with enough refrigerant).

There are mitigations, including storing your keys in a hardware security module (HSM), a physical device designed to be difficult to attack. If your protocol uses forward secrecy -- such as TLS with DHE or ECDHE cipher suites -- new encryption keys are generated for each connection and thrown away relatively quickly (if they're properly erased from RAM, and not counting session caching and resumption mechanisms). In that case, your long-term RSA key would only be used for signatures. Exposing it would allow you to be impersonated and facilitate future MITM attacks, but would not allow decryption of past communications.