Seed a PRNG with random data and a password

If your password has a low entropy (or "could have a low entropy") and the "key file" is assumed to be known to an attacker, you really need some key stretching like PBKDF-2, bcrypt or scrypt with a suitable work factor to detain possible attackers.

As these functions also have a salt input, and you actually have another entropy source (the key file), I would use the key file as the salt input and the password as the key input to these schemes, and produce an output of suitable size for your CSPRNG seed.

I suppose the same scheme is also secure when only the password is known (and not the keyfile used as salt), though this is not a direct design goal of these password hashing schemes.


What are the key differences between the draft SHA-3 standard and the Keccak submission?

No they did not, the internals and security levels have not been changed from the draft Keccak submission, only the padding rule has changed.
The padding change is the only difference, this allows future tree hashing modes as well as the current SHAKE outputs to generate different digests given the same security parameters and message inputs. Up to 4 additional bits are added, which keeps the full padding inside a byte boundary, making implementations with octet only input able to switch to SHA-3 from Keccak with change to only a single line of code.
The padding change has no negative impact on the security of SHA-3.


Recommendation of lightweight RNG for Miller-Rabin primality test

Secure embedded TRNGs are difficult
In an embedded system where the adversary is assumed to control the environment of the Target of Evaluation¹, like a Smart Card, making a TRNG is notoriously tricky. It's hard to ensure the output is truly unpredicatable.
When there is a hardware source, one line of attack freezes it, either literally (thru evaporation of a liquefied gas, lowering temperature thus reducing thermal noise and offsetting the comparator that translates noise to bits) or by other means (e.g. shorting the source's digital output line). A standard countermeasure tests if the source's output is "random enough", before feeding the output of that to a (CS)PRNG (it's pointless to test the output of a CSPRNG). It's difficult to make that test sensitive enough for security, satisfying evaluators, yet not degenerate into unacceptable field failure rate. And it might not be enough against more sophisticated attacks (I can vaguely imagine an adversary modulating the power supply to control the source's output, making it pass the source test, yet control the input of the CSPRNG, thus its output. And that naturally occurring conditions could have the same effect, perhaps explaining this embarrassing disaster).
For these reasons, only a fool, or one operating under pressure to deliver something good enough to pass a poorly designed test, would rely only on hardware source + source test + CSPRNG. It's best to add two ingredients to the mix:

A secret key, injected at manufacturing, that is fed into the CSPRNG. When that remains secret, and all else except the CSPRNG itself fails, at least the output of the CSPRNG is secret until it leaks by other means.
A counter in permanent memory, fed into the CSPRNG. When all else except the CSPRNG itself fails, at least the output of the CSPRNG is not reproducible from one power-on cycle to the next. Problem is making the counter demonstrably resisting power cut at that wrong moment (decided by the adversary, or it's common substitute Murphy). It's hard, or even impossible depending on hardware.

But do we need a TRNG for a Miller-Rabin primality test?
If we have to abide by some diktat standard mandating that a TRNG is used for the bases of the Miller-Rabin primality test, resistance is futile and we need a TRNG, see above. I disregard that in the rest of this answer.

what's the minimal set of requirements for an RNG for use in M-R test?

When we disregard the issue of side channels, it's sufficient that its output is unpredictable by whoever generates the candidate prime prior to that generation, and about uniform. That's not even necessary, see first bullet below.
We can do without a TRNG when at least one of the following holds:

We generated the candidate prime with a procedure we trust to produce random candidates, as must be the case for RSA key generation²: a fixed set of bases will do (under plausible mathematical conjectures). Yes, a 1024-bit integer known to have been generated at random in $[2^{1023.5},2^{1024}]$ that further passes MR to bases $\{2,3,5\}$ is prime with probability of the contrary less than $2^{-80}$, that is certainty in all except mathematical circles. And for added hope of getting rubber-stamped confidence, we can generate the bases with a public CSPRNG seeded with the prime tested.
We have a secret at hand: a CSPRNG seeded with that secret and the prime tested will demonstrably do, even if we are validating³ the primality of an externally supplied prime candidate intended for an RSA moduli.

Wrapping it up: for an MR-test built into the generator, using fixed bases $\{2,3,5\}$ is enough for 1024-bit or more; and using about any sound generator seeded by the integer tested (and negligible or zero probability that two bases are identical) is ample. For an independent MR test, use such generator seeded with a secret and the integer tested.

¹ I'm using Common Criteria vocabulary to make it look like I'm familiar with it. That's common trickery.
² In this case, we can do with a very small number of MR base. See FIPS 186‑4 appendix F.1, or earlier table C.1, which boils down to: 3 bases will do for primes at least 1024‑bit (when we disregard the issue of strong primes, which is common practice, and reasonable at least for two-factors RSA with primes at least 1024‑bit).
³ In this case we need more MR bases, and I know no much better bound than at least $k/2$ tests for $2^{-k}$ residual probability that a composite creeps.


Is this step necessary?

Yes. Assuming you don't want to adopt a RSA-KEM based approach, you need some form of padding to gain full IND-CCA2 security (textbook RSA even lacks the much weaker IND-CPA security!) and OAEP is the preferred such scheme, having a security reduction for IND-CCA2 (that is, it's IND-CCA2 as long as some reasonable assumptions hold).


The obvious way of implementing ChaCha20 involves nothing but additions, fixed rotations, and XORs.  All of these are constant time, so the obvious way of implementing ChaCha20 is secure against timing attacks.  The main way that ChaCha20 is made faster -- SIMD -- does not change this.

On the other hand, the obvious way of implementing AES uses table lookups for the S-boxes.  These are not constant time because of caching.  Avoiding this requires either:

Naive approaches with massive performance penalties.
A technique called bitslicing.  This uses the unlimited parallelism available in CTR mode to emulate a hardware AES implementation, but operating on many bits in parallel.  This only works in CTR mode (because other modes don't have the requisite parallelism) and is not easy to implement.


Can we prove $(a,b,c,d)$ is of form $(g,g^x,g^y,g^{xy})$ without knowing $\phi (N)$?

From the paper you linked in the comment:

Each of these $k$ proofs take four rounds and they can all be done in parallel. These proofs are based on a classic zero-knowledge proof that a tuple $( g, A, B, C)$ is a Diffie-Hellman tuple. [13]

That classic proof works as like this (ommitting the moduli, all calculations within the group structure):

The tuple $(g,A,B,C)$ is given
The prover additionally knows $x$, s.t. $B = g^x$ and $C = A^x$. This is the same as a DH tuple, where the prover just knows one of the exponents. If we define $y$ as solution to $B = g^y$, then the tuple has the standard form $(g,g^x,g^y,g^{xy})$.
In the ZK proof, the prover first chooses $r$ randomly, and then sends $(m_1,m_2) = (g^r,A^r)$ to the verifier.
The verifier chooses a bit $b$
The prover sends $r' = r + bx$
The verifier checks if $g^{r'} = m_1 B^b$ and $A^{r'} = m_2C^b$

Can we prove that the $(a,b,c,d)$ is a Diffe-Helman tuple without knowing $ϕ(N)$?

As you can see above, the zero knowledge proof does not require knowing $\phi(N)$, it doesn't require anything else than the normal group operation. So yes, that's possible.

Edit- Application:
Assume someone is given $(g,g^{2^3},g^{2^5})\mod N$. He wants to compute $g^{2^8}$ and prove that he has done the job correctly, but he does not know $ϕ(N)$.

Well, that does not work. Computing $g^{2^8}$ from the given values is an instance of the computational Diffie-Hellman problem. However, if it's possible to calculate that, then the DDH problem can't be hard either. And that means, it doesn't really make sense to create a ZK proof in the first place. If you want to prove that, I think this would contradict the strong RSA assumption.
Ah, as a final note: Knowing $\Phi(N)$ is equivalent to knowing the fatorization of $N$. However, that does not necessarily imply, that this knowledge allows the calculation of DLOGs (unless the modulus is constructed in a special way, e.g. $\phi(N)$ just has small factors). But what is gained is the ability to calculate discrete roots - in RSA the exponentiation by $d$ is just the calculation of the $e$th root.


What if the input $x$ is only one bit? Would not $G$ leak all of $x$?

In otherwords, the hiding property should work for all plaintext spaces, even if your plaintext space is $\{0,1\}$. $G$ is not hiding for that plaintext space.


Yes, it is possible.  You described how in your question.  I'm not sure what your remaining problem is.  You can think of this as two totally different, independent logical "users" -- or as two different OTP sequences -- with both of them assigned to the same person, using a different one for each channel.  If the OTP scheme is secure, then your approach will be secure too.

The difficult part will be the usability aspects: to convince the user to make to use the proper OTP sequence for the channel they are using.

Also, OTPs are not secure against man-in-the-middle attacks, so they are not a complete solution.

Lastly, one tip for how to get better answers here.  Try describing what you are trying to achieve (what your requirements are) and ask for how to achieve it.  You might get answers or approaches that you hadn't anticipated.


How to apply a block cipher to (large) packetized communication when packets can get lost/erased?

Is it really just a block cipher in ECB mode, so that each packet can be decoded without any prior packet⁰?

No. ECB is bad and creating a secure real-time channel (that can even handle packet loss) is a solved problem. It has been for years. There's no good excuse for using ECB here.

  Is it a block cipher in some non-ECB mode, but it gets reset at the start of a packet?

The usual approach would be to have some form of initialization vector for the encryption which is sent as cleartext with every packet and is used to re-synchronize the state between both endpoints if packet loss is expected. For some encryption schemes this can simply be the packet counter. Then once you have synchronized state for a packet, you use a stateful encryption scheme, like GCM or CTR + HMAC to encrypt the singular packet.

If you want to have a look at how this works out in practice, the three big secure channel standards are TLS (cannot handle lossy underlying layer), DTLS (adaption of TLS 1.2 for lossy contexts) and SRTP.


Searching for a dining cryptographers problem variant

I believe I found the reference I was looking for. I believe it's from the book 'Einführung in die Kryptographie' from Albrecht Beutelspacher, Jörg Schwenk and Klaus-Dieter Wolfenstetter, published by Springer. I read it back in college.

In chapter 5.2 on 'Multiparity Computations' they talk about 'Wer verdient mehr' ('who earns most'). The idea is that in a multi-party with >2 participents one of them (Alice) starts by adding their income, i_1, to a random number r, writes it down on a note and passes that note around. Everybody else then adds their income i_n to the number. Once the note arrives back at Alice, Alice then can subtract the random number r and is able to compute the average income of the round, so they can compare if their income is above or below average without exposing any other information. Of course this only works if all participents answers are trustworthy.

A interesting approach. But I was wrong with my assumtion that it had anything to do with the 'dining cryptographers' problem.


Does DDH hold in $Z_N^*$ where N is product of 2 large primes

The same attack doesn't work when we consider the group $Z_N^*$ where N is product of 2 large primes. This is because computing jacobi symbol without knowing factors of N is hard by Quadratic Residuocity assumption.

This is incorrect: computing the Jacobi symbol can always be done in polynomial time, and does not require knowing the factorization. You're confusing it with the hardness of computing residuosity (i.e., checking whether an element of $Z_N^*$ is a square). DDH does not hold over $Z_N^*$. It is however conjectured to hold over $J_N$, the subgroup of elements with Jacobi symbol 1, see pages 23-24 of my paper.

EDIT: a screenshot of some old slides of mine: each element of $Z_N^*$ can have Jacobi symbol 1 or -1, and if it has Jacobi symbol 1, be square or non-square.


What are the consequences if someone finds the accessible 1600-bit block $X$ and $R$-bit block $V$ such that $\text{Keccak-}f[1600](X \oplus V) = X$?

Then you've found a collision in SHA-3, and you get a prize.

There is a choice of prizes:

You could get your name on a virtual piece of paper that makes a lot of people excited and causes exceptionally insufferably tedious debates on Hacker News.
You could get a large number of unmarked bills in small denominations and possibly an unwanted piece of lead in your head by selling the collision on the black market.
You could get the fruit of exploiting the collision in real-world applications, with a lot more effort, and who has time for that kind of effort anyway?


The short answer is NO: you will not obtain identical ciphertexts from the same file encrypted using two different runs of a decent public key file-encryption software; their hash will not coincide.

The longer answer (in theory):

If you use a deterministic public key encryption scheme like textbook RSA, i.e., without randomized padding, then yes.

If you use a secure public key encryption scheme such as RSA OAEP (providing at least IND-CPA security), i.e., encrypting the same message twice with the same public key produces different ciphertexts with overwhelming probability, then no.

However, in the latter case your randomness used for encryption may be computed pseudorandomly from some known value (such as the message itself), as for instance used in message-locked encryption, then the answer turns to yes again.

Hybrid encryption:

If you encrypt larger files (larger then the supported message space of the public key encryption scheme) with a public key encryption scheme you should use hybrid encryption. This is also what will be used by a file-encryption software.

Let us denote the public key as $pk$ and the document as $m$.

Then encrypting the first time results in $(c_1,c_2)=(E_{pk}(k),E_k(m))$ for a random symmetric key $k$.
The second encryption will result in $(c_1',c_2')=(E_{pk}(k'),E_{k'}(m))$.

If you set $k=k'$, i.e., use the same symmetric key, then $c_2=c_2'$ (depending on the mode of operation used for the symmetric cipher you may also require to use the same IV/nonce). Otherwise, if $k\neq k'$ then $c_2\neq c_2'$ with overwhelming probability.

If you use a deterministic public key encryption scheme, then $c_1=c_1'$. If you use a probabilstic (secure) public key encryption scheme, then $c_1\neq c_1'$ with overwhelming probability (as said above, one however can turn probabilistic public key encryption deterministic public key encryption).

Hashing the ciphertext

Now, the first part of the answer only refered to deterministic/probabilistc encryption. It additionally depends on what you see as the hash of the ciphertext, or if you hash the file as it is, and what you want to guarantee in your application and what you want to store.

If you only store the hash of the second component $c_2$ when using hybrid encryption, then the hashes will be identical if you use the same symmetric key (as well as IV/nonce), i.e., $k=k'$, and the document does not change.
But why then use public key encryption? You could encrypt $k$ using $pk$ (store it with the encrypted file) and then decrypt and encrypt the file again and make the comparison.
Alternatively, you could in addition to the file store the encrypted hash of the file.
You could also simply store a hash of the unencrypted file.
You could also simply ignore hashing and compare the encrypted files.


Which risks are associated with deriving multiple keys from the same DH secret Z?

It depends on how you use HKDF to derive multiple keys.

Background: HKDF consists of two stages: first HKDF-Extract computes an intermediate value from the randomness source; then HKDF-Expand can be used to generate one or more session keys from the intermediate value.

The right way is to use HKDF-Extract once, and then call HKDF-Expand multiple times, with multiple different info strings.  In other words, to derive two session keys, you'd call HKDF-Extract once and HKDF-Expand twice.  If you do that, then this is a perfectly good practice -- it is exactly what HKDF was designed for.

The wrong way is to call the entire HKDF process twice, with two different salts.  Some implementations of HKDF might not separate out the two stages, and just combine them; if you used that, and performed the entire process twice (using HKDF-Extract twice and HKDF-Expand twice), then this is not the intended way to use HKDF.

Everything is fine if you use the "right" way, so for the rest of this question I assume you were asking about the "wrong" way.  There are two answers about whether this is a good idea: the "engineering" answer, and the "principled" answer.

The engineering answer is that, in practice, if you generate two keys using two different info strings, I suspect you'd probably get away with it without problems.  If we model the hash as a random oracle (admittedly a very strong "assumption"), then I suspect it might be possible to demonstrate that what you propose is OK.  Disclaimers: I haven't analyzed this, and I'm certainly not going to give you any guarantees -- if you do what you propose, cryptographers will wag their finger and say "tsk, tsk", and rightly so.  I suspect you'd probably get away with it (it's not the worst sin you could make), but if something does go wrong, cryptographers aren't going to take the blame -- it's all on you.

The more principled answer is that if you do what you propose, you are misusing the HKDF primitive.  The HKDF is only intended to be applied to a single $Z$ once.  It is intended to turn an unguessable value into something that looks uniformly random.  It has been analyzed for that use.  It was not designed to derive multiple keys from the same $Z$: it hasn't been analyzed for that kind of use case, since that's not what it was designed for.  So, you're throwing away the benefits you could get from the public analysis of HKDF if you use it in a way that it wasn't designed for.

Consequently, given that it is so easy to use HKDF the right way, you should probably do that.


Well, it sounds like you're close.

The multiplications implicit within the MixColumns operation are $GF(2^8)$ multiplication operations, using the same field representation as they use in the inverse within the sbox.

However, because they're multiplying by the fixed constants $\mathtt{1}$, $\mathtt{2}$ and $\mathtt{3}$, it's easier to implement than a general $GF(2^8)$ multiplication.

Multiplying by $\mathtt{1}$ is easy; it's exactly what you'd expect.

Multiplying by $\mathtt{2}$ is what your question is about: it is equivalent to shifting the number left by one, and then exclusiving-or'ing the value 0x1B if the high bit had been one (where, in case you're wondering, the value 0x1B came from the field representation).  And so, that is the answer to the question you asked; if the high bit was a zero, then you don't need to exclusive or anything (or equivalently, you exclusive-or in a 0x00 constant).

And, your next question would likely be "how do a multiply by $\mathtt{3}$"?  Well, you can do that by multiplying by $\mathtt{2}$ (see above), and then exclusive-or-ing that with the original value, since $\mathtt{3} = \mathtt{2} \oplus \mathtt{1}$.  Or, in other words:

$$\mathtt 3 \times x = ( \mathtt{2} \oplus \mathtt{1})\times x = (\mathtt 2 \times x) \oplus x $$

So, once we've gotten the multiplication by 2 operation solved, the multiplication by 3 is solved as well.

Once you've multiplied all the vector elements, then you need to add them.  Now, you might be tempted to add them modulo 256, but that'd be wrong.  This "addition" operation is actually "exclusive-or".  They've written it as $+$ because, in $GF(2^n)$ fields, exclusive-or is considered the addition operation; it acts an awful lot like an addition operation in conjunction with the multiplication operation.

So, if we look at the calculation:

$$(\mathtt{d4} \times \mathtt{02}) + (\mathtt{bf} \times \mathtt{03}) + (\mathtt{5d} \times \mathtt{01}) + (\mathtt{30} \times \mathtt{01})$$

$\mathtt{d4} \times \mathtt{02}$ is $\mathtt{d4} << 1$, exclusive-ored with $\mathtt{1b}$ (because the high bit of $\mathtt{d4}$ is set), giving $\mathtt{b3}$;
$\mathtt{bf} \times \mathtt{03}$ is $\mathtt{bf} << 1$ exclusive-ored with $\mathtt{1b}$ (because the high bit of $\mathtt{bf}$ is set) and $\mathtt{bf}$ (because we're multiplying by $\mathtt{3}$), giving us $\mathtt{da}$;
$\mathtt{5d} \times \mathtt{01}$ is $\mathtt{5d}$, and $\mathtt{30} \times \mathtt{01}$ is $\mathtt{30}$.

Now, we add (rather, exclusive or) $\mathtt{b3}$, $\mathtt{da}$, $\mathtt{5d}$ and $\mathtt{30}$ together, and that gives us $\mathtt{04}$.


CBC key lifetime, or, "how big is too big?"

as the previous comment said, due to the birthday paradox/problem, after 2^64 blocks (for block ciphers with 128 bits block size) collisions start to get very likely, the authors of cryptography engineering suggest for CBC "2^32 blocks or so", according to them that leaves a residual risk of 2^-64 that there will be leakage of a full block (when a collision happens in cbc, you leak 128 bits of information about the plaintext)

this is for CBC, of course, other modes of operation have other characteristics.


Lookup table for DSA/ECDSA/Schnorr multiplication

Actually, doing $k-1$ multiplications isn't all that much less than what can be achieved using a more sophisticated power algorithm (say, base $2^w$, for an appropriately chosen $w$) - and these algorithms don't need a precomputed table.

On the other hand, there are more sophisticated precomputational algorithms out there, which drastically reduce the number of multiplications (and sometimes also shrink the size of the table as well).

Now, I haven't seen this sort of optimization when dealing with finite field groups ($\mathbb{Z}_p^*$); in my experience, general power routines (or possibly optimizing for the case of $g=2$) appears to be the norm.

However, it is quite common when dealing with Elliptic Curve groups.

As for my speculations for why this is:

The $\mathbb{Z}_p^*$ routines tend to be older; perhaps no one considered it worth the bother to updating them to use precomputed tables.
The tables for $\mathbb{Z}_p^*$ would be larger (because each precomputed element would be larger).
With ECC, you can efficiently compute inverses - we can take advantage of this to improve our precomputation algorithms somewhat, making the precomputational advantage somewhat larger.


Questions regarding the one-wayness and collision-resistance of a hash function based on RSA-like problem

Knowing either $p$ or $q$ is sufficient to recover both of them (as $q = n/p$). So imagine we know all of $p, q$, and $n$.
The chinese remainder theorem can be phrased many different ways. In general, it states that when working mod $n$ (where $n$ is a product of distinct primes [1]), you can instead work mod each prime separately. In this particular setting, this means that instead of looking at the equation:
$$H(m) = m^2\bmod pq$$
We can look at the pair of equations:
$$H(m_q, m_p) = (m_q^2\bmod q, m_p^2\bmod p)$$
If we can "solve" one of the sets of equations ($\bmod n$ vs $(\bmod q,\bmod p)$), we can efficiently convert the solution into a solution of the other equation. The second equation will be easier to solve, so will be how we can perform a preimage attack.
In more detail, say you're given a "target" point $c = H(m)$ for some unknown $m$.
Then, we can apply the chinese remainder theorem to convert this into two points $(c_q, c_p)$ for the bottom equation (in particular, $c_q = c\bmod q, c_p= c\bmod p$).
How can we find $m_q$ such that $c_q = m_q^2\bmod q$?
There are known algorithms to do it (see Cipolla's algorithm) which do so efficiently (it looks like it is $O(\log q)$).
So, we can find $m_q, m_p$ that solve the bottom equation efficiently.
Then, we just convert $m_q, m_p$ back into $m$.
This can be computed efficiently, in particular by writing:
$$m = m_q(m_q^{-1}\bmod q) p + m_p(m_p^{-1}\bmod p)q$$
Where $m_q^{-1}\bmod q$ is the inverse of $m_q$ within $(\mathbb{Z}/q\mathbb{Z})^{\times}$, meaning is the modular multiplicative inverse.
So essentially, if we know $n$'s factorization, we can apply the chinese remainder theorem to reduce everything to the case of $\mod p$ where $p$ is prime.
Arithmetic behaves much better in this case, so we can efficiently solve the equation.

[1] One can even apply this to distinct prime powers, meaning an equation $\bmod p^2 q^3$ can be broken into two equations $\bmod p^2$ and $\bmod q^3$. It cannot be broken into 5 equations $(\bmod p, \bmod p, \bmod q, \bmod q,\bmod q)$ though.


How can a client privately query a subset of a database?

You're looking for PIR, Private Information Retrieval or OT, Oblivious Transfer and possibly also PSI, Private Set Intersection.

PIR enables a client to query a server for the $i$-th entry of a database without the server learning the query. However, the client may learn values for other indices too.

OT is a stronger PIR without this leak.

PSI enables a client to find the intersection of their secret set and the server's secret set. You might want to do PSI before PIR to filter out non-members before trying to look them up, to reduce communication costs. Possibly of interest RePSI, Reactive PSI reduces the ability for a malicious client to enumerate the server's set.

A much weaker alternative may be of interest too. If the database is large, but reasonably partitioned and the client is willing to reveal which region they are querying, then you can use k-anonymity.

Ex. Have I Been Pwned's password lookup works by taking the first 5 hex characters of the hash of your password to identify the partition of the large password hash database. Then, you filter the smaller but still large partition down to your exact hash/key and read its value.

Although the server does not learn the user's password, related queries can uniquely identify the user if they have multiple compromised passwords tied to a common username or email address. I.e. There may be only one user whose two password hashes start with "12345" and "abcde".

If the client searches for the information on "Bobby Smith" and "Carol Smith" and these two people exist in separate partitions, then the server may link the two queries to recover your query. Even if all queries are independent without any relation, k-anonymity still reveals the tiny subset of the large database, the client is interested in.


Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?

I'd say that the whole argument hinges around a "secret attack" that possibly the NSA may know of, enabling them to break some instances of elliptic curves that the rest of the World considers as safe, because the secret attack is, well, secret.

This yields to the only possible answer to your question: since secret attacks are secret, they are not known to people who are not in the know (duh), and thus there is no "openly known method making that feasible", by definition. Since we don't know, in a mathematically strong sense, whether such a thing as a "secure elliptic curve" can exist at all, "no known attack" is about the best kind of security assumption that you will ever get.

Now if we look closely, we may note that the NIST curves have been generated with a strong PRNG: given a seed value $s$, the curve is $y^2 = x^3 + ax + H(s)$ with $a = -3$ (a classic value for this parameter; it gives a slight performance improvement for point doubling in Jacobian coordinates) and $H$ a deterministic PRNG. Here, the PRNG is what is described in ANSI X9.62 (section A.3.3.1) and is based on an underlying hash function, SHA-1 in the case of the NIST curves. For practical purposes, we can consider this PRNG to act as a random oracle. What this means is that even if NSA knows of some secret method to break some elliptic curves, they would still have had to do quite some work in order to find a seed which yields a curve which "looks good" (in particular, a curve with a prime order) and yet is among the set of "breakable curves". For instance, if only one curve in $2^{100}$ is weak against this unknown attack, then NSA would have faced an average of $2^{100}$ SHA-1 invocations (at least), a ludicrously high number.

Therefore, unless we add to the speculation another "unknown attack", this time against SHA-1 (specifically, the PRNG of X9.62 A.3.3.1 with SHA-1 as hash function), we must assume that if the NSA knows of a secret breaking method for some elliptic curves and used it to rig the NIST curves, then that method must be able to break a non-trivial proportion of possible curves. So we are not talking about a handful of special-format weak curves, but something really devastating.

We have no proof that elliptic curves are inherently strong, however we have some "intuition" that the apparent strength of curves against discrete logarithm is linked to the notion of canonical height (see also this presentation). If that intuition is correct, then there cannot be more than a very small proportion of "weak curves" (e.g. the curve $y^2 = x^3 + ax$ is weak if the base field is a 256-bit field); chances of hitting a week curve with a randomly generated $b$ parameter would be extremely remote. In that sense, the postulated "unknown attack" of NSA, in order to be usable to rig generation of the NIST curves, would also have to prove wrong the intuition of many mathematicians specialized at elliptic curves.

I think that the paragraph above is the closest you can get to a mathematical rational argument about why the NIST curves are not rigged.

I do have a second argument, though, which I find rational, though it is from economics, not mathematics: we cannot measure how secret a secret attack can be. Remember that the primary users of US-government-specified cryptographic parameters are US corporations; a primary goal of NSA is to protect these corporations against foreign enemies (competitors). Purposely pushing the use of rigged curves, where the rigging uses the knowledge of some as yet unpublished attack, is very risky: this will hold only as long as some half-crazed mathematician from the deepest of Siberia does not find the same attack. As Leibniz explained, scientific discoveries seem to happen to the whole World at the same time; everybody thinks the same things simultaneously. That's a notion which is well-known to academics: publish fast or perish.

So if the NSA does its official job properly, then it must not promote the use by US businesses of tools which are known to be flaky and thus potentially exploitable by anybody. NSA cannot ensure that it has a monopoly on mathematics...

This contrasts with the DualEC_DRBG backdoor, where there is a known method to rig it (by careful choice of the two involved curve points), but, crucially, it is equally obvious that people who did not get to choose the curve points cannot exploit the backdoor. That is the kind of backdoor that NSA can safely promote, because they know they can keep it under their exclusive control.

This also contrasts with the 56-bit DES key, where the backdoor was obvious (key amenable to exhaustive search) but could be exploited only through accumulation of sheer processing power; in the 1970s, USA had a known big advantage over USSR in that field, and they knew it. When computing power became available too generally, they switched strategies and decided to promote strong encryption methods (3DES, then AES): they prefer it when their enemies cannot break encryption, even if that means that they cannot break it either.


Feistel cipher key generation and round function algorithms

In the best maths I can manage, Feistel ≠ DES but rather DES ∈ Feistel.  This is important as that's what's confusing you.  It's just that DES is extremely prominent in the literature so articles are drawn towards it.  The following is two  Feistel rounds (ostensibly just a single round as they have to be in LH and RH pairs):-

This is also important in that this is the super set.  And being so, there is no particular architecture for either the function or the key schedule that generates the round keys.  DES architecture is just what the designers thought up to create it.  Similarly, Blowfish ∈ Feistel, but you can come up with our own function and key schedule.  I'm just a country boy and not a cryptographer, but as I understand it the overall security of a Feistel network will be proportional to the security of the key schedule times the security of function.  Approximately, but you get the idea.  It is possible to use anything from a strong hash function to simple compression techniques for function  This will directly affect the security requirements for the key schedule.

It is interesting to note that whilst there are proven architectures for Feistel compression functions (and indeed native block ciphers like substitution and permutation), there are no equivalent standardised architectures for a key schedule.  You can have anything, ranging from Blowfish's computationally expensive method, through AES' to the dodgy striping technique of RC4.  The basic requirement of the key schedule (even more important than security) is that the key can be repetitively slotted into the main architecture at the correct bit width.  Otherwise, it won't even begin to work.

There are of course certain fundamental requirements for both, and these are too extensive to list here.  Now that you know the nature of these two fundamental components, you can do your own research.  Look at things like:-

Are there any specific requirements for the function FF in a Feistel cipher?

Questions about key schedules

Implementation detail of Feistel networks (featuring Blowfish)

So I'll end as I started, Feistel ≠ DES but rather DES ∈ Feistel.


Security of XORing hashes vs concatenating

The answer is (as always): It depends. If you want pseudorandomness, then XOR is a good combiner (actually even optimal). However, if you want collision resistance then XOR is a really bad combiner because afaik you cannot show that collision resistance of the two hash functions implies collision resistance of the combiner. If you think about it, a collision for that combiner does not imply a collision for either of the hash functions. The same argument applies to second-preimage resistance. On the contrary, for the concatenation combiner a collision of the combiner contains a collision for both hash functions.

For one-wayness the situation is a bit more complicated. However, you cannot use a preimage finder for the combiner to find preimages for one of the hash functions...


CBC Padding Oracle in SSL3. Why only in SSL3 not in TLS1,TLS1.1, etc

Essentially the reason is that in SSL3 the padding was not specified which was corrected in the specification of TLS. Here is a detailed and readable explanation of the attack.

However, there is a variant of the poodle attack that also works on TLS because the same procedure as for SSL3 could be used on TLS packets. While this was not standard-compliant it would work and some implementations are vulnerable.


How to correctly encrypt data with proper authentication using AES-256-CBC in php?

Basically you would be constructing an AEAD scheme. You will need to perform HMAC over the IV, the ciphertext and possibly over additional associated data (AAD). If you just need to authenticate the ciphertext then you may simply leave out (or leave empty) the AAD - but not the IV during the HMAC function.

Fortunately somebody already thought about standardizing this, so you may simply copy this draft RFC called " Authenticated Encryption with AES-CBC and HMAC-SHA". Obviously having a draft RFC is less optimal than a full RFC with a lot of research, but at least it has undergone some evaluation. It basically formalizes something that already existed in the first place.

Notes:

The RFC seems to have been written with TLS 1.3 in mind, but as TLS 1.3 deliberately leaves old style algorithms behind, it seems to have been mostly ignored;
This scheme uses encrypt-then-MAC, it doesn't hurt to understand the differences with MAC-then-encrypt and encrypt-and-MAC.


How NIST's ECC curves (P256 alias secp256r1 and friends) have been generated is public: that's in SEC2v1 (with reference to the "verifiably random" method of ANSI X9.62-1998, a draft of which is here), including the seed of the SHA-1-based PRNG used; however, how that seed was chosen is not public, and it's anyone's guess if that's just lost or if something nefarious was done (yet notably: we know no method to do something nefarious).

How Brainpool's ECC curves have been generated is public, and based on a nothing-up-my-sleeve number. All the details where formerly online there (pages 8 to 10), with copy at the Web Archive.

Disclaimer: I do not know who actually checked that the numbers match the methods listed above.

Bernstein's Curve25519 matches more security criteria (see there) and is designed to be easier to protect against side channel attacks, all things equal. But on the other hand:

It is not known any practical attack taking advantage of characteristics of Brainpool (or NIST) curves for ECDSA signature, and as far as I know for proper implementation of ECIES encryption.
Single-chip tamper-proof devices (including all those with a Common Criteria certification that I am aware of) currently tend to have a hardware accelerator that does not directly support Curve25519; thus secure implementations of Curve25519 on said devices would be slow, or at least not security evaluated. That's the argument given by nitrokey's support:

  Curve 25519 isn’t supported by the smart card chip we are using

The question echoes a common opinion:

  ECC seems more future-oriented than RSA

to which there are several counterarguments:

With key sizes giving comparable security against today's attacks, ECC might well turn out to be what gives the worst protection against hypothetical future quantum computers usable for cryptanalysis, because the current guess is that the larger keys would require quantum computers with about proportionally more coherent qubit, and scalability of that currently is the major hurdle in quantum computing.
For tasks using a securely generated private key (signing in particular), ECC is typically much more vulnerable than RSA is to failure of the random number generator, and that's a very practical line of attack.
For tasks performed with the public key (verification and encryption), RSA is faster, and simpler (thus safer) than ECC is.

Thus if we stick to what's available on secure hardware, target longer term security, do not dismiss quantum computers usable for cryptanalysis within a lifetime as pipedream, and RSA-4096 gives acceptable signature generation and decryption speed, it might be a good choice. See this for applications where RSA makes a lot sense.

Personally I'm far from paranoid on key size or imminent cryptopocalyse by quantum computers (on the grounds that practical attacks tend to be far more mundane, like penetration of the machine where the Smart Card stands, which might not allows private key extraction but allows rogue signature/decryption; side channel attacks; fault attacks), and I'd be happy with 256-bit ECC (or better) if RSA is unacceptably slow, as happens a lot on Smart Card CPUs at 3072-bit level or more: work for secret-key operation increases about with the cube of the key size for both RSA and ECC, and the smaller multiplicative constant for RSA far from offsets it all.


Clarification on the origin of `01` in this oracle padding attack?

Actually, we don't care about the amount of padding the original message had; we care whether the modified plaintext (that is, the result of the decryption of the modified ciphertext) has good padding or not.

The padding will be valid if the last block had one of these patterns:

  XX XX XX XX XX XX XX 01

  XX XX XX XX XX XX 02 02

  XX XX XX XX XX 03 03 03

  XX XX XX XX 04 04 04 04

  XX XX XX 05 05 05 05 05

  etc

(where XX is any byte value).  If we modify the ciphertext, and then the decryptor decrypts and packet and finds a valid padding, then we know that the value in that last block is one of those patterns.

Now, why do we initially consider one the first one, and essentially ignores the others?  Well, for a random change (that is, if the attacker is in the initial stages of that attack, and may have no information about the decryption), then the last block will have the last byte 01 with probability 1/256; the rest of the alternatives will, in aggregate, happen with probability less than 1/65280, hence with quite high probability, the ciphertext being accepted with indicate that the last byte of the plaintext was 01.


Does this use of hash provide anything over a nonce? HMAC instead?

the use of hash doesn't prevent forging. Does this provide much over just using a closely held nonce?

on the contrary, the use of hash described should prevent forging assuming the secret is kept .. well.. secret

  Does hash make it particularly difficult to derive the input? Since secret is not encrypted, this seems to assume that either

Indeed, it should be very hard to derive input (secret) from its hash. That's one of the mandatory properties of a hash function. The secret should stay secret on the server side (not revealed to the client)

  secret need not be secret or the token is closely held, which should be the case for a CSRF token.

if the secret is revealed, the client could forge a new valid CSRF token


Is this man in middle atack possible in quantum cryptography?

Is there something wrong it this scenario?

Obviously, yes.  Any such QKD system would require an authenticated channel back from Bob to Alice; that's to make sure that Bob is the one that's actually receiving the quantum signal, and not a man-in-the-middle.

More fundamentally, your system doesn't actually take advantage of any Quantum Effects; by measuring a particle, you can deduce its entire quantum state (or, at least, as much of the state that the protocol cares about); as such, it can be entirely described with classical physics.

There are actually several proposed QC systems; the simplest is probably the original BB84 system.  This system has the photon being in one of four quantum states, and takes advantage of the fact that a measurement will give only 1 bit (and this is the crucial quantum effect); using the authenticated channel, Alice and Bob can coordinate which of Bob's measurements gave answers consistent with what Alice sent; because the attacker cannot measure things without losing information, any attempt by him to measure and retransmit will introduce a measurable error rate.

  [Or] quantum cryptography is a big talk about nothing?

A number of people (including myself) are quite skeptical about quantum cryptography; however that doesn't have with us not thinking it doesn't work.  Instead, we look at the limitations (need for special quantum channel, cost of equipment, low data rate, low range, vulnerability to side channels), and ask "what advantage does it have compared with classical cryptography (either symmetric or asymmetric) to justify dealing with these limitations".


Cryptographically strong seeded pseudo random number generator

In your scheme, $R[0] = S[1]$, because hashing $S[0]$ always gives the same result.

So knowing the output $R[0]$, the attacker can predict the entire stream - he knows the complete internal state at the position of $S[1]$.


Can substrings of a long string be efficiently authenticated?

Here's a better solution, using a Merkle tree.

Suppose the string $S$ is $n$ letters long.  Build a binary tree with $n$ leaves, with each leaf corresponding to one letter in the string.  Then, each node corresponds to a substring: the $i$th leaf corresponds to the $i$th letter in the string, and an internal node $x$ corresponds to the substring obtained by concatenating all of the leaves that are descendants of $x$.  Now, you can store at each node of the tree the MAC of the substring it corresponds to.  This is all done in a precomputation.

Once you've precomputed the binary tree, you can authenticate any substring $T$ of $S$ as follows: $T$ can be written as the concatenation of the strings at $O(\lg n)$ nodes in the tree.  Therefore, to authenticate $T$, you send the MACs at those nodes.  In this way, the authenticator is $O(\lg n)$ in length.  This is better than your trivial solution, in terms of the length of the authenticator (as your trivial solution requires an authenticator that is $O(|T|)$ in length).  In your storage setting, the length of the authenticator corresponds to the amount of data that must be read from storage to authenticate a particular substring $T$.

If your goal is solely to optimize the length of the authenticator, You might be able to build an even shorter authenticator using set accumulators, though the performance cost would likely be much higher.  Given a string $S$, you construct a set of pairs $\langle i, S_i \rangle$, then use a set accumulator construction to sign that set; now it is possible to derive a signature on any subset, such as one corresponding to a substring of consecutive letters from $S$.

Another alternative might be to use hash chaining or MAC chaining.  For MAC chaining, you could do the following: let $Y_i = MAC(Y_{i-1} || S_i)$, for each $i$.  You can store all of the $Y_i$'s alongside the string.  Then, to authenticate a substring $S_{i..j}$ of $S$, you read $Y_{i-1}$, do $j-i$ MAC operations to run forward along the substring, and check that the result matches $Y_j$.  Of course, as an engineering optimization, it would be possible to store the $Y_i$ values for only every $k$th index $i$, for some $k$.  I don't know whether this will be better in any sense than the other schemes.

You might also be interested in the following research papers:

Homomorphic signature schemes.  Robert Johnson, David Molnar, Dawn Song, and David Wagner.  RSA 2002, Cryptographer's Track.  See particularly Section 4, redactable signatures.
Sanitizable Signatures.  Giuseppe Ateniese, Daniel H. Chou, Breno de Medeiros, and Gene Tsudik.  ESORICS 2005.

Given that you are focusing on stored data, you might also like to look at the line of research on memory integrity checkers, e.g.,

Checking the correctness of memories.  Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, and Moni Naor.  Algorithmica, 12(2/3):225–244, 1994.
The Complexity of Online Memory Checking.  Moni Naor, Guy N. Rothblum.  FOCS 2005.


What does the PFX file extension stand for

On my Windows 7 machine the .pfx file-type is called:

  Personal Information Exchange

I'm not sure why this turned into .pfx, but guess that they wanted to avoid .pix, because it sounds like an image format.

The acronym can also be found in MSDN where it describes a set of functions in an API for creating PFX files.


Calculation of AES encryption per second

Let us assume a few things:

10 gb/sec means Gb/s, the number of gigabits per second;
we use network notation for Gb/s, which means that 1 Gb consists of 1,000,000,000 bits;
we'll use the minimum of AES blocks to encrypt - this is true for most single pass modes of encryption such as CBC and CTR;
we only use the AES primitive for confidentiality, not message integrity or authenticity (this restriction is lifted in the second part of the answer).

In that case 10 Gb/s is 1.250 GB/s. And as AES encrypts 16 bytes per block, this comes down to 78,125,000 operations per second (ops/s). Depending on the protocol and mode a few operations may be required at the start or end but those are insignificant to the ~78M ops/s.

If AES is also used for message authentication, for instance using AES-CMAC then you should double the amount of ops required.

Authenticated encryption modes based (solely) on AES such as CCM mode and EAX mode are "double pass", which means that two AES block encrypts are required for each block of input.

AES-GCM uses 128 bit modular multiplication during GMAC calculation. It is likely faster than these double pass modes, especially on newer processors with instructions to accelerate the multiplication required for GCM.


Assuming:

the objective is to protect the confidentiality of the user names from an attacker having read access to the encrypted data, the ability to add usernames of her choice, and nothing else (in particular, no access to the key, even by proxy of a computer or device holding the key, or side channel);
the IV is randomly chosen for each individual username encrypted (or re-encrypted after an edit);
the key has been randomly chosen, is not compromised, and is used only for that usage;

then the system using CBC is safe, as far as we know (this follows from IND-CPA security of AES-256 in CBC mode). Notice this is highly theoretical. If an adversary can get remote access to a PC, and unless an HSM or Smart Card is used to hold the key, you have no strong argument that the key did not leak. Even if you use such tamper-resistant hardware to store the key, you have no argument that the adversary could not use that hardware, or otherwise access the plaintext.

Using ECB, the system would be unsafe even with the theoretical hypothesis given. In particular, it would be easy, from the ciphertext, to spot:

identical usernames:
usernames identical up to the first 16 characters bytes;
with high confidence, if a username uses more or less than 16 characters bytes (which in turn could be correlated with ethnic origin).

Update: Having the same IV for every user is a classical mistake, and brings back some (but not all) of the weaknesses of ECB. In particular, it is trivial to spot identical usernames; and thus to spot if a given username is present, for an attacker able to add a user with a given username. Depending on the number of usernames an adversary can realistically add, and on the encoding used for user names (which has considerable influence on the difficulty to exactly guess a 16-byte fragment of a username), it would be more or less easy to recover a fraction (or perhaps all) of the usernames.

IMHO, simply put, there is no proper way to encrypt usernames in an online database. Problem is, whoever can use the database to get the usernames will circumvent any crypto there might be; this is not a cryptographic problem. If you only want to give the illusion of security (or, equivalently, do the best you can in an implementation running in a nondescript environment), use CBC or CTR encryption with a random IV for each encryption of a record.


The mentioned approach of splitting the keys in pair as $(k1,k2)$ for first person, $(k1,k3)$ for second and $(k2,k3)$ for third person for the given situation is correct! And the PRF can be computed as follows:
First person computes: $F1((k1,k2),x)=F(k1,x)⊕F(k2,x)$
Send this F1 to the second person and compute F1⊕F2 where F2 is $F2(k3,x)=F(k3,x)$
$F1⊕F2 = F(k1,x)⊕F(k2,x)⊕F(k3,x) = F'((k1,k2,k3),x)$


Hash of multiset of values, which lets me compute the hash of the union

One solution is a group-based hash function.  Choose an abelian group $(G,+)$ and a conventional hash function $h:\{0,1\}^* \to G$.  Then, set

$$H(S) = \sum_{x \in S} h(x),$$

or in other words,

$$H(x_1,\dots,x_m) = h(x_1) + h(x_2) + \cdots + h(x_m),$$

where $+$ represents the group operation of $G$.  Notice that this is commutative.  It is also associative: given $H(S),H(T)$, it is easy to compute $H(S \cup T) = H(S) + H(T)$.

The security of this depends partially upon the choice of $G$.  Here are some sample instantiations:

If you choose $G=(\mathbb{Z}/p\mathbb{Z},+)$ where $p$ is a large prime, the resulting scheme has been proposed by Bellare et al. under the name AdHash.  I would expect this to provide approximately 80-bit security if you choose $p \approx 2^{1600}$.
If you choose $G=((\mathbb{Z}/p\mathbb{Z})^*,\times)$ where $p$ is a large prime, the resulting scheme has been proposed by Bellare et al. under the name MuHash.  I would expect this to provide approximately 80-bit security if you choose $p$ such that the discrete log problem modulo $p$ provides at least $2^{80}$ security.
If you choose $G=(GF(2^n),+)$ (i.e., the group operation is xor of $n$-bit strings), the resulting scheme is insecure: it can be broken using a simple linear algebra based attack.

See also https://crypto.stackexchange.com/a/5231/351


Security importance of Key Schedule in Block Cipher

If i use another Key schedule algorithm in AES, then security decreased or remain same?

This really requires a concrete proposal for an alternative key schedule in order to conclude whether or not it would constitute an improvement or a weakness.

The AES key schedule is not exactly ideal, but the rest of the design seems to be strong enough such that this does not really matter in practice. So the practical security would probably not be modified. The key schedule is almost surely the weakest part of the AES algorithm; The fact that it is secure as-is implies it probably would not make a gigantic difference to modify the key schedule.

I bet if we tried, we could come up with some kind of pathological example that would lead to a weakness, but I can't think of one offhand.

  Question 2. Why we expand key? brute force will take O(2^128) time regardless of the key schedule is strong or not. what is the advantage of making key expend?

This is a very good question that I have wondered about myself. I do not think I have ever seen explicit justification in a cipher proposal for why round keys are derived and applied exactly as they are - as in: "By deriving our keys this way and applying them at this specific interval, these attack(s) are prevented"

One thing that it accomplishes is that it makes each application of the round act differently. Symmetry of various kinds can be used in an attack against the algorithm.

I have seen a few papers that were specifically about the importance and design of key a schedule. Basically, they advocate ensuring full diffusion of the key and ensuring that, given one portion of a round key, it should be difficult to derive any other portions of the key.

So, hypothetically, if you used a fully diffusing, unpredictable, one way function as your key schedule, then recovery of one round key would not assist in recovery of other round keys.

Interestingly, I have found justification for NOT using a key schedule: The cipher LED utilizes no key schedule, and is resistant even to related key attacks because of it. It relies on the round constants to simulate independent round keys.

  I was curious about this when I was learned about 3DES. Which developed because the former DES has weak key length 56bit so vulnerable to brute force attack, i was wondering why doesn't they just remove key schedule process and use the whole round key as a key.

Since the DES key is only 56 bits, just using it directly would not be an improvement. Also, the DES key schedule pretty much does just use the key directly: It does pull from different bits over the course of different rounds, but it's really just re-ordering the bits of the key, and not really deriving a new/different one. Also note that 3DES utilizes more master key material then regular DES.


What is the sign bit for in Feige-Fiat-Shamir?

The original 1986 Fiat-Shamir paper can be found here. The subsequent Feige-Fiat-Shamir 1988 paper can be found here, and contains the answer (Section 3):

  The $S_j$ (which are witnesses to the quadratic residuosity character of the $I_j$) are effectively hidden by the
  difficulty of extracting square roots $\bmod n$, and thus A
  can establish his identity by proving that he knows these
  $S_j$. By allowing $I_j$ to be either plus or minus a square
  modulo a Blum integer, we make sure that $I_j$ can range
  over all the numbers with Jacobi symbol $+1 \bmod n$ and
  thus the $S_j$ exist (from B’s point of view) regardless of
  $I_j$’s character, as required in zero knowledge proofs of
  knowledge.


What happens if you multiply a point with its order on complete Edwards curves?

Actually multiplying an elliptic curve point $G$ by its order $q$ gets you to the neutral element of the group, i.e., the point $O$ such that $P+O=P$ for any point P.

In a generic elliptic curves this point is the point at infinity $O$. However on Edwards curves, this point is $(0,1)$, i.e., it can be represented by affine coordinates. This is also stated on wikipedia.

Therefore, multiplying a point by its order, on an Edwards curve, gets you the point $(0,1)$

This means that on Edwards curves: $P+(0,1)=P$ for any point $P$.


Usage of Zero-knowledge proofs for NP-complete languages

If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for.  In short, just put the OWF through the Cook-Levin reduction.

In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP witness-finding question "what is a 3-coloring of this graph $G$?", by converting $y$ into a graph $G$ such that any 3-coloring of $G$ can be efficiently converted back to a preimage of $y$ under $f$.


Does there exist a public database of RSA-2048 moduli and their factors?

TL;DR
It's not possible, because there are way too many prime numbers.
It's possible that there might be a database with some of these numbers, but not a database with all the possible numbers. There are just way too many prime numbers to fit them all in one database.

How many 1024-bit prime numbers are there?
To get a 2048-bit modulus you multiply two 1024-bit prime numbers together. Using $$\frac{n}{\ln(n)}$$ we can estimate the amount of prime numbers with the length of 1024-bits. The amount of 1024-bit numbers is $2^{1023} - 1$.
$$2^{1023} - 1 \approx 8.9 \times 10^{307}$$
We then apply the approximation:
$$\frac{8.9 \times 10^{307}}{\ln(8.9 \times 10^{307})} \approx 1.25 \times 10^{305}$$
We now have an approximation of how many 1024-bit prime numbers there are.

How large is the database?
If you want to put them all in a database you just have to calculate the number of these primes multiplied with their size (which is of course 1024-bits). That gives you the size of your database in bits:
$$1024 \times 1.25 \times 10^{305} \approx 1.28 \times 10^{308}$$
So as you can see this database would be way too large and it wouldn't be practical to even try to fit them in any database.


Simple digital signature example with number

I'll give a simple example with (textbook) RSA signing. I'm going to assume you understand RSA.

First key gen:
$p\gets 7,q\gets 13,n\gets pq=91, e\gets 5, d\gets 29$

Thus your public key is $(e,n)$ and your private key is $d$.

Say we want to sign the message $m=35$, we compute $s=m^d\bmod{n}$ which is $s\gets 42\equiv 35^{29}\bmod{n}$.

The message and signature get sent to the other party $(m,s)=(35,42)$. Who takes the signature and raises it to the $e$ modulo $n$, or $42^{5}\equiv 35 \bmod{n}$. Then makes sure that this value is equal to the message that was received, which it is, so the message is valid.


RSA encryption secure mode, plaintext length limit vs. key length

Lets assume Java here. In that case the ECB part of the name is a misnomer. ECB is the most simple mode for a block cipher. It means splitting up the plaintext message into multipe blocks and then encrypting them separately. Java's RSA implementation doesn't split anything up, you can only encrypt a single block of plaintext. They should have used "None" instead or have left it out altogether.

Yes, OAEP is secure, if implemented correctly. It requires a mask generation function parameterized with a cryptographically secure hash function. You can compare MGF1 with a key derivation function. For that kind of usages SHA-1 is still secure. I'd still prefer SHA-256 none-the-less, if just to avoid nasty questions on the protocol. It is plenty fast for this kind of use and new processors even contain instructions to speed up the algorithm.

For the maximum plaintext message I'll simply refer to a previous answer. It lists a payload size of 214 bytes for SHA-1 and 190 bytes for SHA-256 if OAEP is used.


What scalars produce the wrong values with X25519's montgomery ladder?

Actually, the answer is none. Everything works, and produces the correct results.

Potential problems arise when converting back to Twisted Edwards space, and that's a different question.


Re-using parts of a one time pad to encrypt a new one?

Let me get this straight; if you are sending a 256 bit message, and get a 256 bit reply, the obvious way using OTP would be the message to use up 256 bits of pad, and the reply to use up a separate 256 bits of pad, using a total of 512 bits.

Instead, you propose to use a total of 512 bits to send the message (and a temporary pad), the reply will then be encrypted using the temporary pad); this uses a total of ... 512 bits of pad.

Well, I don't see any reasons why this would be insecure (however, you appear to think you have a way to extend this to multiple messages; exactly how that would work is not obvious), however I also don't see any specific advantage over normal OTP; in both cases, you're using 512 bits of pad to transmit a total of 512 bits of message.


Is using HMAC signature as a long-term password secure?

As long as your master secret key is generated properly and protected properly, this should be fine. HMAC is widely believed to be a pseudorandom function. So, the output (i.e. the password = PRF(secret_master_key, username)) should be pseudorandom and has good entropy.


Does choosing N to be product of safe primes avoid William's p+1 factoring attack on RSA?

In this post, I found that choosing RSA modulus $N$ to be product of safe primes avoids Willam's $p + 1$ factoring attack.  But how can we guarantee that $p+1$ and $q+1$ are also not smooth? Why are they guaranteed to have large prime factors?

Actually, you're tripping over the various notions of "safe primes" vs "strong primes".

"Safe primes" are generally defined as you said, primes $p$ where $(p-1)/2$ is also prime.  As you note, it guarantees that $p-1$ has a large prime factor; however it gives no guarantee of $p+1$

"Strong primes" are more variously defined; one common one is a prime $p$ where $p-1$ and $p+1$ both have a known large (for example, > 100 bit) prime factor (and sometimes there are more conditions).  With this definition, both $p-1$ and $p+1$ are not smooth.

The ones arguing for more complex RSA key generation methods (the reasoning apparently being that adding complexity always adds to security) generally argue for "strong primes".

On the other hand, it's not at all clear that it adds any real security at all; if your primes $p$ and $q$ are small enough that a random prime has a nontrivial probability to be vulnerable to William's method, then with strong primes of the same size, you have a nontrivial probability of being vulnerable to ECM (and so the sizes of prime you picked as too small).

Here's how it works: William's method works this way: the attacker takes guesses at prime factors; if he guesses all the prime factors of $p+1$ or $q+1$, he can factor (and, other than time, there's no downside to incorrect guesses).  (And, Pollard's method works the same with $p-1$ and $q-1$).

ECM works this way: the attacker picks a pseudocurve, which fixes "small" values $\epsilon_p$ and $\epsilon_q$; then, he takes guesses at prime factors, and if he guesses all the prime factors of $p + \epsilon_p$ or $q + \epsilon_q$, he can factor (and, again, other than time, there's no downside to incorrect guesses). [1]

Each iteration of ECM (that is, a guess at a prime factor) does take more time than the corresponding iteration of William's, but only by a small constant factor; as we rarely have that precise an estimate on the attacker's capability, we can generally ignore this constant factor.

What does this mean?  We can certainly select $p$ to be a strong prime, where $p+1$ has a large prime factor (which is essentially unguessable), and so William's factoring method has no hope.  However, we cannot do the same for $p + \epsilon_p$, as that covers a range around $p$, and we cannot control which pseudocurve the attacker selects.

Hence, selecting strong primes doesn't, in practice, make the factoring any more difficult.

[1]: Real ECM implementations will select a number of pseudocurves, and run them in parallel.  They do this to take advantage of the possibility that one of the curves might have a $p + \epsilon_p$ which is exceptionally smooth; however the above argument holds even if the attacker doesn't do that.


Given the key, the plain text and the cipher text can I calculate the IV used in CBC mode?

It is simple.

Just decrypt first 8 bytes encrypted buffer(1 block) in ECB mode (You only need encrypted buffer and key to do so) and then xor the result with the input buffer. Result will be IV.

In decryption of CBC, IV just affect first block. That's why only first block is incorrect in your case.


Doubts about Authenticated Data Structures logic

One reason I see is that simple signatures only prove the data block was produced by you, but not that the block is what you queried for.

A simple example: suppose you have 4 data blocks $d_1,d_2,d_3,d_4$ which you can query by index, i.e. on query = 1, the server should return $d_1$.

Now when using a signature scheme, you store $(d_1,d_2,d_3,d_4)$ as well as their signatures $(s_1,s_2,s_3,s_4)$. Later you query 3, and the server returns $(d_{x},s_{x})$. At this point, you can verify that $s_x$ is indeed a signature of $d_x$. But how can you be sure $d_x$ is $d_3$ you asked for? What you have got can be $(d_1,s_1)$ for example, which will pass the check. Remember that the main spirit of using a cloud is that you store your data in the cloud without having to keep a local copy. Now you won't be able to tell whether you get the right answer.

If you use a Merkle tree, then you will get a tree like this:

Now when you query 3, you will get $(d_3',h0',h11')$. You can hash $H(h0'||H(H(d_3')||h11'))$. If the result is the same as the root you saved, you must have got $d_3$ as you requested, as the path is unique for this item.

A similar issue when using signatures is that what if the server returns an old version of the data item? There is no way to tell because the signature does not prove freshness. When using a Merkle tree, the root is updated every time you update the data, so it gives you freshness guarantee.


What are the properties of secure Elliptic Curves?

For typical protocols like Diffie–Hellman key agreement and Schnorr-type signature,* SafeCurves surveys the modern security criteria for elliptic curve choice.  In these protocols, the adversary is assumed to know the choice of curve; the security comes from criteria of the curve, not of secrecy of the curve.†

The basic criterion is that computing ‘discrete logs’—that is, given a scalar multiple $[n]P = P + \dots + P$ of a known point $P$ on the curve by a secret integer $n$, computing $n$—costs well above $2^{100}$ curve additions.  But there are many other criteria, like twist security, that are not as obvious to an untrained observer, and were not considered in the design of historical standard curves like NIST P-224.

Certain criteria are not about secure vs. insecure curves per se, but rather about fast and secure vs. fast or secure implementations: for example, NIST P-256 does not admit the Montgomery ladder, which is a fast way to compute $x$-restricted scalar multiplication in constant time.  In NIST P-256, you can compute scalar multiplication fast, or in constant time, but not both—so it is tempting to sacrifice security in pursuit of performance when implementing NIST P-256 or choosing an implementation of it, whereas with Curve25519 you can attain both simultaneously using the Montgomery ladder and there is no temptation to sacrifice security that way.

Some of the criteria are relevant to some protocols but not others, for instance because DH key agreement is subject to active attacks that are not relevant in the security model of signatures.  Fortunately, some curves satisfy all the criteria, such as Curve25519, Ed448-Goldilocks, and E-521.  The first two of those are standardized in RFC 7748, which also prescribes a rigid procedure for selecting a curve for a given prime field satisfying all the security criteria and optimizing performance by certain easy heuristics—a procedure which, incidentally, also generates E-521.‡

* SafeCurves does not address more exotic applications like pairing-based cryptography, which necessarily use a different class of curves.

† In the various proposed post-quantum isogeny-based cryptosystems, choices of curves are secret positions in an isogeny graph of curves, but this is a rather different scenario from what is usually known as elliptic curve cryptography today, and as such seems unlikely to be relevant to your question.

‡ The IETF chose to endorse Ed448-Goldilocks rather than E-521 because Ed448-Goldilocks performs better, and even though the theoretical attack costs on E-521 are higher than on Ed448-Goldilocks, the two both have a meaninglessly high ‘security level’ that only serves as a hedge against minor cryptanalytic advances, not to raise actual costs on what is an impossibly expensive attack to begin with.


Key Scheduling of International Data Encryption Algorithm (IDEA)

Have a look at the corresponding paper.

The key is a 128-bit string $K$. The round keys for round $r=1,...,8$ are derived as follows:

take the version of $K$ cyclically rotated to the left $25\cdot r$ times;
split the string obtained into eight substrings and call them $Z_1^{(r)}$, ..., $Z_8^{(r)}$.

The keys $Z_7^{(r)}$ and $Z_8^{(r)}$ are never used. The subkeys $Z_1^{(9)}$, ..., $Z_4^{(9)}$ are used to mask the output.


Why must we generate the signature before any compression being done at PGP?

As for the first reason: in the future you probably need the decompressed form of the message. There won't be much you can do with the compressed message. But PGP is application level; you may want to verify that message at any time. Now you may want to verify the signature over that decompressed data without compressing it first. E.g. it's a good use case to allow compression over the network and then store the uncompressed message on disk.

As for the second reason: compression works with heuristics and levels of compression. Those levels are hints to the system how much work (CPU cycles mostly) it needs to put in to compress data. Different implementations may make different choices. The compressed format itself will indicate how the compression took place - otherwise you wouldn't be able to decompress of course. So if you decompress on system 2 (using the stored methodology of system 1) and compress it again (using the heuristics of system 2) you are likely to get a different result. Different outputs will result in different signatures, so it makes more sense to sign the uncompressed plaintext.

Semantically it also makes slightly more sense; you wanted to sign the message, right? Not some special compressed representation of it.

Obviously the compression should be completely loss-less for this to work; one bit wrong in the resulting message or a different order of the plaintext and the signature won't verify.


Password protection in ARJ: 3 characters of password are retrievable

More info on the ARJ format with international (i.e. extremely weak) encryption can be found here at cpsr.org:

A = password
B = compressed text to be encrypted
A' = permuted password
B' = encrypted compressed text
C = constant
^ = XOR

A' = A ^ C
B' = B ^ A'

This is performed character by character.

So if you know the constant (from the application code) and the input and output character then you've got just one variable left: A, the password character:

A = B ^ B' ^ C.

However, the header contains at least 3 static bytes: the header ID and the archiver version number. So for these bytes / characters you don't need to test anything.

There are many other semi known values in the header, but you will need some additional information such as the length of the password to use them to crask the password.


how much is secure to encrypt a password using itself (as encryption key) for storing it on an insecure media?

I think what you are looking for is a Password-Based Key Derivation Function (PBKDF).

You can take a moderately strong password, like 12-14 random letters and numbers (no dictionary words though!), and throw it into the PBKDF function together with some other parameters, e.g. salt, number of iterations and the desired key length.

After that you have a reasonably strong - say 128 bit key - for the real AES encryption/decryption.

For more info, see http://en.wikipedia.org/wiki/PBKDF2

One more thing. To prevent brute forcing of your key you should experiment with the number of iterations for the key derivation. As a good rule of thumb, choose a number that makes the algorithm run for approximately 1 second on the target machine.


Can j-invariants be used to decide which elliptic curves are suiteable for cryptography?

Giving the j-invariant is basically equivalent to giving a curve equation (up to quadratic twist) (over $\mathbb F_p$ for $p > 3$) : to each j-invariant you can attach a pair of curves $(E, \widetilde E)$. You can easily compute the curve equations of $E$ and $\widetilde E$ from $j$:

$$E: y^2 = x^3 + a x + 2a, \qquad a = -\frac{27j}{j-1728}$$

Now the $j$-invariant is "suitable for crypto" if both curves above are suitable, which you can check using the usual algorithms (SEA, etc.).
Since it is easy to go from “curve equation” to “j-invariant” and back, it is also easy to conclude that the j-invariant does not contain anything particularly useful for cryptography.


To be DHKE group, there are five properties to be held,

This is true; however, to be a secure DHKE group, there has to be an additional property:

The "discrete log problem" needs to be hard; that is, given a public value $xG$ (where $G$ is the public group identifier, $x$ is your private value, and $xG$ is the generator acted upon itself $x$ times), it is hard to recover $x$.

In the addition case, we have $xG = \underbrace{G + G + … + G}_{x \text{ times}} = x \times G$., where $\times$ is integer multiplication.
If we know $x \times G$ and we know $G$, then it is easy to recover $x$ by doing a simple division (modular division if we're doing the addition modulo $p$, which isn't much harder), and hence the Diffie-Hellman would be trivially insecure.
Actually, just having a secure discrete log problem is not sufficient; the "Diffie-Hellman" problem also needs to be hard, that is, given $G$, $xG$ and $yG$, it should be hard to recover $xyG$ (this is known as the computational Diffie Hellman problem), or given $G$, $xG$, $yG$, $zG$, it should be hard to determine whether $xy = z$ (this is known as the decisional Diffie Hellman problem).  Either of these problems may be easier than the "discrete log problem" for any group; however, for addition, none of these problems are hard.


Collecting entropy: can I use timing of reading as a separate source from the reading itself?

The values of these timestamps  appear to be determined by two components:

when your code decides to sample the GPIO inputs; and
whether a bit is to be discarded or not.

The first component is not proven to be random (and if you assume it is, you would not need to add complexity to this RNG; just create a second RNG based on CPU execution jitter).

The second component is the same information that you have already used in the whitener.
In other words, if an attacker can make some (partial) predictions about the raw GPIO inputs, then the timestamps are predictable, too.

Please note that the Wikipedia page you linked is not a complete description of the von Neumann algorithm; if you click through to Von Neumann extractor, you see that this algorithm requires that the source is a Bernoulli sequence.
Almost all physical noise sources fail this because their output values are correlated.


In RSA, what's the risk of revealing $p^e\bmod N$?

Does revealing $p^e\bmod N$ (in addition to the public key) allow factorization of $N$

Yes, with that extra information, $N$ is easy to factor.  A computation of $\gcd( N, p^e \bmod N )$ gives the factor $p$ (because $p$ is the only prime the two integers $N$ and $p^e \bmod N$ have in common, it is a factor of both integers, while $q$ is not a factor of $p^e \bmod N$)


First of all, The Montgomery's Reduction algorithm requires that $\operatorname{GCD}(n,R)=1$ .
This requirement is satisfied iff $n$ is odd.

The $R$ is chosen as $2^l$ where $ 2^{l-1} \leq n < 2^{l}$.

For $x < n$  the $n$-residue with respect to $R$ is defined as;

$$ x' = x \cdot r \bmod n$$ than the set

$$\{i \cdot R \bmod n\;|\; 0 \leq i \leq n-1 \}$$ is a complete residue system, that is, it contains all the numbers between $0$ and $n-1$.

The selection of $R$ is the smallest bound.

  Why should the choice of $R$ be $2^l$ where $l$ is the length of $N$ to the base $2$?

Montgomery Reduction converts arbitrary division into shift operations. Therefore  $2^l$  is a good choice for computers, we have to shift $l$ bits.

  Why cannot we have a larger $R$?

It won't be effective since you will have more unnecessary shiftings due to a larger $R$.

note: if $R<n$ than this will not work.


Help defining a shift cipher mathematically

My understanding is given that $E_K(x)=(x+K)~mod~26$ is the character by character encryption of a shift cipher, you want to extend it to words as the function $E'$ given by
$$E'_K(x_1,\ldots,x_m)=(E_K(x_1),E_K(x_m)).$$
If you intended the key $K$ to change per character you can modify.


Identification Schemes and Internet of Things

All that this part in the introduction is really saying is that identification is important to IoT. Much as we can say that, for electronic banking transactions, privacy is important (because otherwise people could read your financial transactions) but authentication is more important (because otherwise people could actually steal your money, which is worse), this introduction claims that identification is the most important security objective for many areas, including IoT. It's not saying other objectives are not important, and whether or not you can objectively rank these criteria and agree that identification comes out on top isn't really the point - it's just saying that identification is an important objective for IoT.
As for why it's important, suppose you have an IoT device that unlocks the door to your car, or to your house. Before unlocking the door in response to a request, it's really important that the system is able to determine that the request came from your unlocking device, and not from someone else's unlocking device - i.e. it's important that it identifies your device. It may be that you couldn't care less about privacy - if "unlock my door" were the only message that's capable of being understood by the system, for example, then even if you encrypt it any eavesdropper will still know what the message is, so you gain nothing by concealing it.


Is there any functional encryption scheme whose key generation circuit is in NC1?

Attribute-Based Encryption schemes (ABE) are definitionally a sub-category of FE. Furthermore, non-monotonic ABEs (NM-ABE) can encode decisions from $NC^1$, so yes, there are FE-schemes that are restricted to $NC^1$.

There are both ciphertext-policy ABEs (CP-ABE), key-policy ABEs (KP-ABE) and mixtures of them (dual-policy, or DP-ABEs), so it is possible to embed the circuit of desired complexity into both ciphertext and key (or key generation).

The most general FE schemes can encode decisions from the whole of $NC$, so they are also able to encode circuits in $NC^1$. FE-schemes also exist in both KP- and CP-flavors.


The mathematical similarity and difference between code-based PKE and multivariate DSS

Multivariate schemes tipically work with a central polynomial map $\mathcal{F}(X) : F_2^n \mapsto F_2^m$ which is a quadratic map that defines $m$ quadratic equations on $n$ variables. Then select $T,S$ as invertible affine transformations. The public key $P(X) = T \circ F \circ S(X)$ is written as $m$ quadratic forms in $n$ variables over $F_2$.
However, as every Quadratic Form $q_i(X)=X^T Q_i X$ can be linearised using Tensors, this is, a dot product of $\overline{q_i}(x \otimes x)$ where $\overline{q_i}$ is the $n^2$ vector reshape of the matrix $q_i$.
Then rewrite the public key as a $m \times n^2$ matrix $\overline{P}$ where the $i$th row encodes the $i$-th columns of the quadratic forms. This is a rectangular matrix which doesn't allow an attacker to compute the input value $X$ from the output $Y$. From here the goal is to either attempt to solve by obtaining the affine transformations $(T,S)$ which we refer to the Isomorphism of Polynomials ($\mathcal{IP}$), solving the underlying non-linear quadratic system over $F_2$, which is a subinstance of the PoSSo problem, called the $\mathcal{MQ}$ problem or studying the MinRank $\mathcal{MR}$ problem.
For example, an HFE public key can be computed using pure Linear Algebra, without working in Polynomial Rings and Finite Fields. Either deriving the Quadratic Forms as I did here or using Tensors. But you still need to apply Berlekamp's to find roots over $F_q$.


Are two keys derived from the same password vulnerable to a related key attack?

Unless the key derivation function you use is specifically designed to exploit related-key attacks, then no, it will not result in a vulnerable related-key pair. It is true that XSalsa20 is not designed with related-key attack resistance in mind, but a key put through any decent KDF will not lead to exploitable weakness.

This answer explains the kind of effort that can go into creating a pair of related keys. Suffice it to say, there is absolutely no reason to worry that a KDF will produce such keys. The only other kind of attacks occur for certain ciphers when keys are extremely similar. An example of this is RC4, where encrypting known-plaintext with multiple keys that differ in only a few bits can lead to complete key recovery.

Note: I have not analyzed your overall password management scheme, just your direct question about related keys.


a doubt in Rijndael's key expansion sizes

AES-128 takes a 128-bit key, produces 11 128-bit subkeys out of it with a cryptographically weak function, and uses them in 10 internal rounds. It can be said that the full key is reused 10 times.

AES-192 takes a 192-bit key, produces 13 128-bit subkeys out of it (or, equivalently, 9 192-bit subkeys), and uses them in 12 rounds. The full key is reused 8 times.

AES-256 takes a 256-bit key, produces 15 128-bit subkeys (or 8 256-bit ones) and uses them in 14 rounds. The full key is reused 7 times.

Therefore, AES-128 uses its key more intensively, and AES-192 and AES-256 -- less intensively.  However, only very specific cryptanalytic attacks may exploit this property. For example, related-key attack can break the entire AES-256, but can not break the full AES-128. By ''break'' we mean that it is possible to produce ``similar'' ciphertexts from ''similar'' plaintexts on some particular key pairs. However, the related keys are rarely seen in practice, so this property is not much relevant to the actual security of AES.

To conclude, AES-256 can be considered weaker than AES-128 in a very specific setting only, and this setting is unlikely to occur in practice.


Authentication and encryption using a simplex communication channel

Sure. For instance:

Use PKI, register client public key (or self signed certificate) on the server and consider any registered public keys as trusted. You should understand also all drawbacks that it has, like dealing with validity period (how are you going to check if some PKs are still valid / trusted or not and should you remove them from your server PK store or not?), dealing with compromized private keys (instead of revocation list of CA), etc.
Use shared secret. Again, be prepared to the drawbacks. For instance, in such case not only the user, but also you on the server side will be responsible for keeping user authentication material safe.
One time passwords.


What is the importance of 1 < d < φ(n) and 0 ≤ m < n in RSA?

From the algorithm stated on Wikipedia:
"4) Choose an integer d such that 1 < d < φ(n) and gcd(d, φ(n)) = 1; i.e., d and φ(n) are coprime. 5) Determine e as e ≡ d−1 (mod φ(n)); i.e., e is the modular multiplicative inverse of d (modulo φ(n))"
I don't understand the importance of 1 < d < φ(n).

You can use a d greater than φ(n), but it needs more computation time than a d less than φ(n).
Also, d and e in 4) and 5) should be swapped. You may see 8.2.1 Handbook of Applied Cryptography

Also why must the message M to be encrypted be an integer m such that 0 ≤ m < n
(Here n is the product of two distinct primes p and q)

If m is less than 0 or not less than n, you can not recover m; since decryption gives you a number(m') 0 ≤ m' < n.


Does $(u_1=r_1\cdot x,\ \ w_1=r_1\cdot z, \ \ u_2=r_2\cdot x,\ \ w_2=r_2\cdot z)$ Leak Information?

Yes, this does leak some information.  In fact, just knowing $u_1$ and $w_1$ will allow the attacker to calculate $u_1^{-1} w_1 = x^{-1} z$.*  In particular, knowing this value will let the attacker calculate $x$ if they know $z$, or vice versa.

Similarly, knowing $u_1$ and $u_2$ will let the attacker calculate $u_1^{-1} u_2 = r_1^{-1} r_2$.  With $u_1$, $w_1$ and $u_2$, they can calculate both of these.  (Knowing $w_2$ will not actually add any further information, since it can be calculated from the other values as $u_2 u_1^{-1} w_1 = u_2 x^{-1} z = r_2 z = w_2$.)

Without additional information, however, you cannot work out the exact value of any single parameter.  In particular, given any (non-zero) $x$, we can choose $r_1$ and $r_2$ so that $u_1 = r_1x$ and $u_2 = r_2x$ take any values we like, and then further choose $z$ so that $w_1 = r_1z$ takes any value we like; $w_2 = r_2z$ will then equal $u_2 u_1^{-1} w_1$, as it always must.

*) I'm assuming here that all the values are non-zero, and therefore invertible, which they most likely are if they're chosen at random modulo a large prime.  You can work out the special cases where some of the values are zero as an exercise yourself, if you like.


Is there any implementation of threshold BGN homomorphic encryption?

Here are two implementations, I haven't used any of them though.

https://github.com/baonq-me/bgn
https://github.com/nasimmaleki/Cryptography


Minimum Nonlinearity of boolean function

You can give a boolean function by it's truth table.
For example if $f(x, y, z) = x + z$ you have the following truth table:

  x   y   z   f(x, y, z) = x + z
 ----------------------
  0   0   0     0
  0   0   1     1
  0   1   0     0
  0   1   1     1
  1   0   0     1
  1   0   1     0
  1   1   0     1
  1   1   1     0

just enumerating the last columns gives you $(0, 1, 0, 1, 1, 0, 1, 0)$. This $f$ is by its definition clearly a linear function. If you want to enumerate all linear functions you can look at the Hadamard matrix and Hadamard transform.

To calculate the linearity of a boolean function $g$ as explained in this question you take the minimum Hamming distance between the output vector of $g$ and all linear functions.

So if your function would for example be $g = (1, 0, 0, 0, 1, 1, 0, 1)$ the Hamming distance to $f$ would be.

g: 1 0 0 0 1 1 0 1
f: 0 1 0 1 1 0 1 0
------------------
   1 1 0 1 0 1 1 1 => HD 6 => non-linearity at most 6

In fact if you where to try all linear functions you would find $h = (0, 0, 0, 0, 1, 1, 1, 1)$ with

g: 1 0 0 0 1 1 0 1
h: 0 0 0 0 1 1 1 1
------------------
   1 0 0 0 0 0 1 0 => HD 2

and this is the lowest value so the non-linearity of $g$ is 2.

I hope this answers your second question.

Now we can answer your first question simply by finding examples.
Here are two 4-bit functions with different non-linearity:

[1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
Non-linearity here is 2. It cannot be more than 2 because the middle two bits are swapped from

[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
which is clearly linear (depends only on highest value bit). And it cannot be less than 2 because the function is non-linear and balanced.
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0] has non-linearity 4.

This, I hope answers your first questions negatively. Not all functions have the same non-linearity.


What is the Discrete Logarithm Problem in (Z/Zp) in the DSA?

There is actually only one DLP in DSA. There are multiple approaches to solve it, that can be classified in two categories.

The security of DSA (as defined in FIPS 186-4 section 4) is no better (and equivalent under some models) to the difficulty of the Discrete Logarithm Problem in some Schnorr group. The problem is finding an integer $x$ solution of the equation $y=g^x\bmod p$ for given $p$ defining the group, $g$ in the group, and public key $y$ in the group.

More precisely, that group is a subgroup of $\mathbb Z_p^*$, or equivalently $(\mathbb Z/p\mathbb Z)^*$, for some prime $p$, under modular multiplication, with the subgroup generated by $g$, having as order some randomly seeded prime $q$, and as a consequence $q$ dividing $p-1$. When following FIPS 186-4, $p$ is of L bits and $q$ is of N bits, for one of of these parameters sets:

L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256

This DLP problem can be solved by two classes of algorithms:

Generic algorithms applicable to the DLP in any group of prime order $q$; this includes Pollard's rho and baby-step/giant-step; the cost of the algorithms depends mostly on parameter N (exponentially so, but only polynomialy on L).
Specialized algorithms for subgroups of $\mathbb Z_p^*$, including index calculus and the DLP variant of the General Number Field Sieve; the cost of the algorithms depends nearly only on parameter L (less than exponentially so, but more than polynomialy).


AES is a block cipher and is supposed to be a pseudorandom permutation. It can achieve IND-CPA or IND-CCA or authenticated encryption by using the appropriate mode of operation together with AES. Let see what can be achieved or not.

Has AES been fully (10-rounds) broken? by what means? (commercial? supercomputer?)

Direct brute-forcing

The total BitCoin miners reached $\approx 2^{92}$ double SHA-256 calculations in a year. So you need on average

$2^{35}$ multiple power of this monstrous computing power to break AES-128
or wait for $2^{35}$ years.

The Summit in Oak Ridge can reach $2^{71}$ SHA-1 in a year so no threat there.

In short, there is no threat from here.

Best Known Cryptographic Attacks
The key of AES-128 can be recovered with a computational complexity of $2^{126.1}$ shown in Biclique Cryptanalysis of the Full AES by Bogdanov et. al, using the biclique attack, achieved in 2016. Note this is not the related-key-recovery attack from the same authors and that such attacks are not practical since we are generating the keys randomly. The attack requires $2^{88}$ data complexity and $2^8$ memory complexity.

In short, theoretically, one can say it is broken since the attack requires less than the brute force. However, the attack time and data complexity are not practical, either. From the paper; As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.
The other theoretical attacks on AES-128 are based on the Biclique Cryptanalysis;

Biclique Cryptanalysis of the Full AES, Bogdanov et al.
Better than Brute-Force - Optimized Hardware Architecture for Efficient Biclique Attacks on AES-128, Bogdanov et al.
Sieve-in-the-Middle: Improved MITM Attacks,  Canteaut et al.
A Framework for Automated Independent-Biclique Cryptanalysis, Abed et al.
Bicliques with Minimal Data and Time Complexity for AES, Bogdanov et al.
Improving the Biclique Cryptanalysis of AES Tao et al.

\begin{array}{|c|c|c|c|c|r|}\hline
\text{data} & \text{w/o SIM} & \text{Mem. Bytes} & \text{with SIM} & \text{Mem. Bytes} & \text{reference} \\ \hline
2^{88}& 2^{126.21}& 2^{14.32}& - & - &  \text{Bogdanov et al. 2011}\\ \hline
2^{4}& 2^{126.89}& 2^{14.32}& - & - &  \text{Bogdanov et al. 2012}\\ \hline
- & - & - & 2^{126.01} & 2^{64} &  \text{Canteaut et al. 2013}\\ \hline
2^{72}& 2^{126.72}& 2^{14.32}& - & - &  \text{ Abed et al. 2014}\\ \hline
2 & 2^{126.67} & 2^{14.32} & 2^{126.59} & 2^{64} &  \text{Bogdanov et al. 2015}\\ \hline
2^{64} & 2^{126.16} & 2^{14.32} & 2^{126.01} & 2^{64} &  \text{" "}\\ \hline
2^{56} & 2^{126.13} & 2^{22.07} & 2^{125.99} & 2^{64} &  \text{Tao et al. 2016}\\ \hline
2^{72} & 2^{126.01} & 2^{26.14} & 2^{125.87} & 2^{64} &  \text{Tao et al. 2016}\\ \hline
\end{array}
Where SIM is Sieve-In-the-Middle technique

Multi-Target attack
If you had plaintext-ciphertext pairs with different encryption keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ targets is $2^{128}/t$. If you have a billion targets that you will be able to find the first key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This applies not only to AES but all block ciphers.

Post-Quantum Crypto
Due to Grover et. al's seminal work we know that the security of any block-cipher is halved in key size and it is shown to be asymptotically optimal.
Thus, AES-128 will have 64, and AES-256 will have 128-bit security if someone can build the QC. If you consider your assets valuable, the reasonable choice is to double the key size.
One can also use Grover's algorithm in parallel like in classical parallelization. One, however, will get $\sqrt{K}$ speed gain with $K$ copies.

why has 256 bit key based encryption is used so much to replace it?

Therefore, to mitigate the attacks that exist now or in a possible future, you need to double the key size. In AES, this makes AES-256. If you consider the overhead of using the AES with 256-bit key, in which we need 14 rounds, in CPU this makes around 40% percentage overhead. So, as stated in comments by Prof. Lindell, in marketing AES-256 sounds better, and becomes the standard.
The 256-bit marketing also may come from the US/NATO military regulations which use several distinct security levels (e.g. confidential =128, secret =192, top-secret =256). The 17 years old document from June 2003 states top-secret must be used 192 or 256 bits keys;

The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use

In a side note, according to leaked documents by Snowden, NSA looking for tau statics to break AES. After this revelation, consistent and strong encryption is required from governments. After 5 years, nothing has been related to tau statics and AES appeared in academics area.
Current Nist Recommendation NIST as of March 2019 disallows less than 112-bit security for block cipher in SP 800-131A Rev. 2:

The use of keys that provide less than 112 bits of security strength for key
agreement is now disallowed.

Validation of the 40% overhead of AES-256 with AES-NI
The below numbers are from a laptop with a i7-6700HQ CPU to validate the performance overhead with AES-NI.
$openssl speed -evp aes-128-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-128-ctr     509191.01k  1592361.66k  3090684.67k  4237894.66k  4708169.05k  4763506.01k

$openssl speed -evp aes-256-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-256-ctr     439608.45k  1479537.77k  2478394.14k  3129161.54k  3255877.41k  3396628.62k


Should I use “modes of operation” for a single block of data?

Even though you are only encrypting one block at a time, think about what would happen if your input data happens to be the same as a previous encryption.  Even though you are encrypting the blocks days or weeks apart, plain encryption (aka ECB mode) would have the same problems as usual.  Counter/CBC/... are designed to avoid that problem.  If you know the input data won't repeat (sequence number, etc. as part of your data) then you won't have the repeating blocks problem of ECB where identical plaintext, when encrypted with the same key, always outputs the same ciphertext.