Is public key ever used to encrypt data directly?

TL,DR: It's technically possible, but not in well-designed systems.
No, public-key encryption is never used to encrypt end-user data directly, either in TLS or in any other sensible protocol. Public-key encryption has many drawbacks compared to symmetric encryption:

It's a lot slower. A lot slower.
It can only encrypt very small payloads (a few tens of bytes). To encrypt more data would require a mode of operation, which carries its own share of difficulty (modes for symmetric encryption don't necessarily work automatically with public-key encryption).
If done wrong (e.g. PKCS#1 v1.5), it's vulnerable to oracle attacks.
It's more complex to implement, and at more risk of side channel leaks.
A successful quantum computer as currently envisioned would break all current asymmetric cryptography, but would only have a minor effect on symmetric cryptography (requiring twice the key size).

Sensible protocols are hybrid: they use asymmetric cryptography to establish a session key, and then use symmetric cryptography with the session key. Encrypting the session key is not the best way to do this. Rather than generate a session key and use public-key encryption to encrypt it, it's better to use asymmetric cryptography to generate a random session key. This is usually called a key establishment method (KEM) (although terminology can vary). The basic type of two-party KEM is key agreement, where each side uses its own private key and the other side's public key to generate a session key, in such a way that both sides obtain the same session key. Diffie-Hellman is the classic key agreement protocol. There are also one-sided KEM, for example RSA-KEM has one side apply the public-key operation to a random number in the correct range, and the other side decrypts it with the private key.
Good protocols use signature and key establishment in preference to public-key encryption. Signature and key establishment use the public key in combination with data received from an untrusted peer and use the private key in combination with data produced locally. In contrast, public-key encryption uses the private key in combination with data received from an untrusted peer, which gives an attacker more direct access to the most sensitive part of the system.
TLS may or may not use public-key encryption, depending on the cipher suite.
Most TLS cipher suites use a key agreement method (Diffie-Hellman, usually on an elliptic curve nowadays) to allow the two parties to exchange a symmetric key, and the client checks a signature made by the server to make sure that it's connecting to the expected server. With ephemeral Diffie-Hellman (each side generates a new DH key on each connection), this has the benefit of providing forward secrecy: an attacker who records a TLS connection and later manages to compromise one of the parties will not be able to decrypt the connection, because that requires the knowledge of the ephemeral key.
There is a set of TLS cipher suites that use public-key encryption and not signature or
key agreement. You can spot them because they have “RSA” in their name, but not “(EC)DH(E)”. The client creates a symmetric key and encrypts it with the server's public key. In theory, this is secure: without the server's private key, an attacker cannot obtain the symmetric key. In practice, this method has historically been subject to many implementation flaws. And even with a perfect implementation, relying on public-key encryption lacks forward secrecy: if an attacker records traffic and later breaches a server, the attacker can use the server's private key to decrypt past connections. The most recent version of the TLS protocol (TLS 1.3) does not include any cipher suite based on public-key encryption.
RSA-KEM is not used in TLS.
Finally, to answer the literal question in the title, there are of course plenty of systems with badly designed cryptography out there. As we've seen, there are sensible (but not ideal) protocols that encrypt a session key. The asymmetric encryption mechanism doesn't care that what it's encrypting is a key, so it is possible to have a system that uses a public key to encrypt user data directly and that is functionally correct (i.e. what you decrypt with the private key is what was originally encrypted with the public key). If the size of the data to encrypt is small enough, the system even has a chance of being secure (i.e. the only way to decrypt data is to already have the private key). Due to the size limitation, this is effectively never done in sensible protocols.


Exchanging Keyspace and Message space in PRF

In general this is not the case. Consider a PRF F which ignores the first bit of the key. Then you can distinguish F'(k,.)=F(.,k) from a random function (and thus break its security as a PRF) by querying it on inputs x and x', where with x' we denote x with the first bit flipped. Note that the outputs of F'(k,.) will collide on inputs x and x' as F(x,k)=F(x',k).


Is there something like a secure hashmap?

where "1234" is the result of hashing "foo", and "6%!*3" is the encryption of "bar" using "foo" as encryption key (or something along those lines, I'm afraid I don't know much about encryption - what I mean is that it should be possible to use the string "foo" to decrypt "6%!*3").

So you want to encrypt the usernames, then use the username as an encryption key to the email address and other data?

This is doable and not difficult. If your usernames are unique, you can run the username through a PBKDF to generate a symmetric encryption key, then use it to encrypt the rest of the user's data. If they are non-unique, you need to concatenate the username with a salt first (a piece of non-secure data such as UserID).

My primary concern would rather be with whether the username can be used as a secret. If there is a public user profile, it can be trivially easy to obtain the complete list of usernames by querying the server for users with ?id=1, ?id=2, and so on. Many web applications, e.g. forums, outright offer a complete list of users.

Even if the username serves as a log-in only, and not for sharing anything, it's common practice to use the same username across multiple websites. Just trying each out of a few million usernames grabbed from various sites on the web, which don't make a secret out of them, could probably give one access to about half your entries. Large username dumps are publicly available.

It would be best to find something that is not publicly available to use as the encryption key. Unfortunately, mass dumps or email addresses are also readily available on the web.


Homomorphic & Functional encryption: Mapping unencrypted outputs to encrypted outputs using existing data

Actually, what you asked is not unusual, even more, it is always true.

Since $Eval(f, Enc(dA)) = Enc(f(dA))$ and $Eval(f, Enc(dU)) = Enc(f(dU))$, if $Eval(f, Enc(dA)) = Eval(f, Enc(dU))$, then $ Enc(f(dA)) =  Enc(f(dU))$.

Now, if you use the decryption algorithm in both sides, you get $f(dA) = f(dU)$.

The same argument applies if we use $Enc(f)$ instead of $f$.

The point now is whether this information is useful or not, because the probability that $Eval(f, Enc(dA)) = Eval(f, Enc(dU))$ is very small: even if $dA = dU$, you are supposed to have $Enc(dA) \not = Enc(dU)$, therefore, the evaluation algorithm is likely to give you different outputs.

So, you would probably never see this event and, consequently, you would not be able to use the conclusion (the right side of the implication).


How to evaluate the security of a certain encryption method?

How could I spot red flags?

The red flag is actually the entire red zone (like trees in the forrest...). If there is code for encryption at all, you better throw it away unless it's some proper library from a source with good reputation for exactly this kind of thing.

It is something different, if they use a cryptographic library properly, that can be achieved by non-experts. But implementation of actual encryption ... the chances of a crucial error are immense.

  For example, the Standard File protocol supports E2E ...

If you look at the homepage, the section developers is only listed in the menu, there is no matching content. However, on the positive site they don't actually implement encryption, they use CryptoJS as library.

  For example, is splitting a key in thirds a good idea?

In general: Actually it doesn't make any sense, because you should create keys fitting to their task and why would someoen want to split a key in a meaningless way? If the goal was to split it securely in the sense of a secret sharing scheme (e.g. that you can only reassemble any information with both halves), that's something totally different.

  Telegram did this with a $300k bounty.

The Telegram "challenge" is bogus anyway. It is basically "I think of a number, give you no information, and if you can guess it, you win".

That is not how cryptanalysis works, that is not how security works. By doing that, they already proved that they don't understand much about these fields.

Here are a few articles about that:

Why You Should Stop Using Telegram Right Now
Related is this older article by Bruce Schneier on crypto contests


Can you update a (k,n) scheme to a (k+t, n+t) scheme (assuming old keys can be deleted)?

You can use a variant of the standard "degree reduction" trick from secret-sharing-based MPC protocols, but use it to increase the degree instead.

You start out with a $(k,n)$-sharing of a value $s$. Denote the collective object by $[s]_k$, meaning that party $i$ has private value $p(i)$ where $\deg(p) < k$ and $p(0) = s$. Just so we're on the same page:

$s$ can be expressed as a linear combination of these shares via $s = p(0) = \sum_{i=1}^n c_i p(i)$. The coefficients $c_i$ in this case are public.
if everyone locally multiplies their share of a value $[v]_k$ by a public $\alpha$, the result is $[\alpha v]_k$ -- i.e., shares of $\alpha v$.
if everyone locally adds shares of $[v_1]_k$ and $[v_2]_k$ the result is $[v_1 + v_2]_k$.

Back to our $(k,n)$ sharing of $s$, we want to make it a $(k+t,n+t)$ sharing. To do this, let all of the original $n$ parties make shares of shares. Party $i$ acts as dealer, distributing $(k+t,n+t)$-shares of the value $p(i)$ to create the object $[p(i)]_{k+t}$. Using local computation, everyone computes the desired object $[s]_{k+t} = \sum_{i=1}^n c_i [p(i)]_{k+t}$. They can throw away the old shares of $[s]_k$ now.

Note: all of this assumes honest behavior by the parties. If some are corrupt, then verifiable secret sharing tricks would be needed.


Distinguishing joint probability distributions

Obviously not; one can easily define probability distributions $P$ and $P'$ such that $P(X,Y)=P'(X,Y)$ and $P(Y,Z)=P'(Y,Z)$, but $P(X,Y,Z) \ne P'(X,Y,Z)$

For one such example, take $P$ be the probability distinguish where $X$, $Y$ and $Z$ are uniformly and independently distributed boolean variables; and $P'$ be the probability distribution that $X$ and $Y$ are uniformly and independently distributed boolean variables, and $X=Z$ with probability 1.

Now, $P(X,Y)=P'(X,Y)$ (because, in both probability distributions, each possible combination of boolean variables will occur with probability 0.25), and similarly $P(Y,Z)=P'(Y,Z)$.

However, $P(X,Y,Z) \ne P'(X,Y,Z)$ in an computationally easy manner, because with a single sample of the probability distribution, we can check if $X = Z$ (can guess $P$ if it is false, and $P'$ if it is true); that gives us a distinguisher that succeeds with high probability.


What does the Double Ratchet algorithm need the Root Key for?

Introduction of Root key is a critical element in ensuring Break-in recovery. Below is my dig at explaining its necessity -

Why is DH ratchet used:
For argument's sake, if an attacker was able to compromise a given message key, he/she would be able to compute future chain keys and message keys if only Symmetric-key ratchet were used. DH ratchet is hence introduced to prevent this and ensure Break-in recovery.

Now to answer your question:

In DH ratchet, each party generates a new DH key pair and forwards the public key component over to the other party.

Let us go by the assumption that an attacker was able to compromise the chain key at a given point when party A is sending a new DH public key to the party B. Provided that the attacker has the ability to intercept the channel, it would be trivial for him to replace A's DH public key with self generated public DH key and forward the message over to B. In doing so, the attacker can conveniently remain to be an MITM between A and B even with the DH ratchet, unless ---- the DH ratchet were to use an additional secret known only to A and B to derive the chain keys. No points for guessing what the secret is - root key.

Recall that the Root key was bootstrapped at the beginning of establishing the communication between A and B. Since this initialization used pure DH mechanism using Identity keys, there is really no way the attacker could have compromised the root key.

Continuing the narrative - So, when B makes use of attacker introduced public DH key in combination with the root key, B generates a "receiving chain key" and sends along a new public DH key. Our attacker who is intercepting the channel, now attempts to replace B's public DH key with a new self-generated DH public key and sends to A.

The attacker's intention being to to build the corresponding chains to match up to A's sending chain and B' receiving chain to successfully establish a working MITM.

But due to the introduction of 'root key' (or an updated version of it) in the DH ratchet, the attacker will not be able to generate corresponding chain that can quite match up to B's sending chain. The same holds true on the other side with A's receiving chain.

Hence, at this point when B sends a message encrypted using 'message key' derived from B's "sending chain key", the attacker  would not be able to make sense of it. Note also that, at this point A and B would have to re-establish trust because the message keys/chain keys don't match up at either ends.

This way, an attacker's window of interception after a chance compromise of a 'message key' is limited until the next opportunistic 'DH ratchet' cycle.

Note that the root key also gets updated with each DH ratchet but there is no way the attacker can influence the root key or glean its contents.


AES-128-CTR message integrity: Construction of HMAC

In effect, does this mean that a separate HMAC must be created for every single message, i.e. all 16 bytes?

No, you can use HMAC over the whole message with all its blocks.

Of course, that means you can't localize corruption/tampering, so if you were sending a huge message you might want HMAC smaller parts (but longer than 16 bytes or you are transmitting more hash than message), so that you can retransmit only the incorrect part.

  And at last, going even further, what would be the weaknesses of using merely the encrypted message (and the key, for sure) for the HMAC calculation, thus leaving out the initialization vector?

If you received a message $n||E_{k,n}(m)||H_k(E_{k,n}(m))$, you would only be able to authenticate the ciphertext. If an attacker had tampered with the nonce $n$, AES CTR would happily decrypt your message but give you random data.


Is Diffie-Hellman mathematically the same as RSA?

Both RSA and Diffie-Hellman work with modular exponentiation. But they work in a different way:

In RSA, there are two exponentiations which invert each other, i.e. we have $e$ and $d$ such that $(x^e)^d \equiv x$ for all $x$. E.g. if $\square^e$ is the encryption, $\square^d$ is the corresponding decryption. To create this pair of $e$ and $d$ (or derive one from the other), we need the prime factorization of the modulus $m$ (which thus should be private).

In Diffie-Hellman, both the basis $g$ and the modulus $m$ of the exponentiation is fixed. The exponents $x$ and $y$ are randomly chosen private keys, and we use the fact that $(g^x)^y \equiv g^{x\cdot y} \equiv (g^y)^x$, where $g^x$ and $g^y$ are public, while $x$ and $y$ are (and stay) private, and $g^{x·y}$ is the shared secret.

To break RSA, we would have to get $x$ from $x^d$, $m$ and $d$ - this could be called the discrete $d$-th root problem. (The best known way to do this is to factor $m$ to get $e$ ... and if you have $e$, this also can be used to factor $m$).

To break Diffie-Hellman, we have to get $g^{x·y}$ from $g^x$, $g^y$, $m$ and $g$. The best known way to do this would be to get $x$ from $g^x$ or $y$ from $g^y$ (and $m$ and $g$), the so-called discrete logarithm problem.  (Incidentially, it is not proven that this is really the best way, i.e. that there is not a faster way to do this.)


It mainly depends on how the algorithm was selected. If it was selected by a public competition like for AES, then it is likely to be secure. If it was forced in by the NSA such as Dual-EC random number generator, then you may have some doubts.

Other questions you may want to ask yourself are:

Is this an "original" algorithm or was the problem that it relies on already known?
Is there a formal proof (often not possible), checked by independent persons or organizations?

In the end you will always have a grey area here. Some things like AES are probably secure, Dual-EC certainly is not. But for the (NIST/SECP) ECC parameters it's a lot harder to say.

Saying that Suite B is safe or not is a blanket statement that oversimplifies what is happening in the field of cryptography.

As it is highly visible, it will be highly scrutinized by the cryptographic community. But as Dual-EC proves nothing is to be fully trusted.


You can use those values more than once and there isn't much of a reason to choose another pair – except longer values for a cipher with a larger block size.

The only real requirement for the values is that they differ. However, if someone found a fixed point or other cycle for MDC-2 with a given block cipher, they could choose that point as an IV and be able to generate collisions for any string. That's why using a pair of non-suspicious nothing-up-my-sleeve numbers is better.


Effective period of Mersenne Twister generator output

The Mersenne Twister algorithm is not a cryptographically secure algorithm. The state can be revealed if enough output is available.

However, if the internal state will repeat after $2^{19937}-1$ then obviously this is also the period of the output, even if the output is just 32 bits.

With a period it's not about when a certain output repeats once, but if the output is repeated indefinitely - in other words, you get into a cycle. Because of this the output size doesn't really matter: the repetition is on all the output put together. You can have a large period even if the algorithm outputs single bits at a time.

Note that the internal state of the Mersenne twister is not 32 bits, it's a whopping 2.5KiB. So the state is (necessarily) large.


Why is sharing the seed and using SecureRandom "deterministically" so bad?

Both determinism and non-determinism are useful. The question is which one you use for which purpose.

Determinism is generally useful for expanding a short secret to a long one. For example, you may keep a short random secret and use it to generate a long keystream that you can XOR against messages for encryption and decryption (such as described in the RFC quote). When one string is generated deterministically from another, then the derived string is considered no more secure than the original since knowing the original allows the derived one to be calculated.

Non-determinism is generally used to generate a random value that no one else knows (yet). If you need to generate a key and don't want someone else to guess it, you need a non-deterministic (or at least something that we feel is close enough to non-deterministic) process. If you instead used a deterministic one, then the output no stronger than input and the problem hasn't been solved since you need an strong input. Somewhere in the derivation chain you need something strongly non-deterministic so that the output can't be guessed.

Generally, cryptographic keys are derived non-deterministically and then the cryptographic operation (such as encryption or signing) performed by them is deterministic. (At least, you can think of it as being deterministic, technically it's still supposed to be randomized in some way.)

One last piece of the puzzle: In practice, non-deterministic random number generators accumulate non-deterministic entropy and use that to seed a deterministic process that generates output. This is because non-deterministic entropy is relatively hard to come by and it generally needs to be compressed/whitened before being output. The output was generated deterministically from a non-deterministic source, so it is considered non-deterministic itself.

All of that is a very high overview and is light on details, but the concepts are necessary to understand recent issues on SecureRandom.

So what happened with SecureRandom?

SecureRandom provides random output for things like key generation, so it needs to be non-deterministic. SecureRandom keeps an internal random state that it deterministically generates output from, and that internal state is supposed to be non-deterministic. So although the output is deterministically derived from an internal seed, when the seed is non-determinstic we consider the SecureRandom output to be non-deterministic. SecureRandom also allows the user to provide their own input seed as well.

SecureRandom had a bug where the internal state, if not seed was provided by a user, was automatically filled from a random source like /dev/urandom, but it was done improperly. The amount of random data actually used was much smaller than it should have been. Not having enough random input lead to cryptographic problems.
Another problem was that when a seed was provided by the user to SecureRandom, that seed would override the existing internal state. This meant that if the user called SecureRandom without seeding it they got deterministic output from a non-deterministic source, but if they provided a seed then they got deterministic output from their own input and their input (very likely) wasn't strong enough to be cryptographically strong itself. I don't think this behavior was a bug, but it was changed anyway to prevent innocent misuse. The fix was to add the seed to the internal state, rather than to use it to replacing the state.

Summary: When SecureRandom was used without a seed, the output was supposed to be non-deterministic, but it was based on too few non-deterministic bytes to be secure. When a seed was provided, the output only depended on the seed which was behavior that might confuse developers who thought a custom seed would add to the internal state rather than replace it.


What are the major differences between SET and SSL?

TLS

TLS (SSL) is a general, not payment-specific protocol. Most important in the context of this question, it is current best practice.

SET

SET was introduced around 1996 and declared dead around 2003.


Proper way of encrypting large files with AES-256-GCM

No, the way that it is described, the solution is insecure.
The chunks themselves are of course secure. That is: as long as you verify the authentication tag and if the IV is indeed unique, i.e. a nonce as required by GCM.
However, an adversary can simply switch around the chunks in the file, including the IV and authentication tag. That way the file can be rearranged. Similarly, whole chunks can be removed without issue. If you use the same key for multiple files, you can replace one file with another, or even move chunks between files.
The way around this is to verify that all the authentication tags are in the correct order, e.g. by using HMAC or even by using them as Additional Authenticated Data (AD or AAD) in a separate call to GCM. Then add the final authentication tag to the start or end of the ciphertext of the chunks.
As GCM is insecure for large amounts of data, I'd use a separate data key for each file. You can generate one using a key based key derivation function (KBKDF such as HKDF) from the master key and a 256 bit random salt (the salt needs to be included with the ciphertext, of course). Then you can use a zero based 12 byte statically sized counter as nonce.
That will still leave the issue of being able to switch files. That could be avoided by including the file path into the calculation of the keys and saving it in the file, but beware that this will break any file that is renamed. This is a pretty tricky issue that will require domain specific solution. Similarly, changes to files are as tricky to handle. Some kind of separate register / third party may be required.

Note that in principle GCM uses CTR mode and can be made an online capable cipher. Such a cipher directly converts plaintext to ciphertext and vice versa. That way you can have, say, 1 GiB chunks while using a buffer size of 1 MiB or less (or even no application specific buffer at all).
Problem is that many implementations of GCM do away with this property. Some do allow incremental "update" calls, but even then the decryption specifically may not be fully online. An example of this is Java where you have calls to update methods, but since the authentication tag is considered part of the ciphertext the online property during decryption is lost (i.e. it has to buffer as many bytes as the authentication tag, because it cannot distinguish between the two until all the bytes are updated).


What's the difference between AES and earlier block ciphers?

From a user's point of view, AES improves on DES and 3DES in at least two important aspects beyond speed and key length:

AES is a 128-bit block cipher, which makes it more secure for huge volume of data than a 64-bit block cipher is. For example, any 64-bit block cipher in CBC mode is vulnerable to a simple distinguisher attack: the adversary has a chance to recognize plaintext with all identical blocks (e.g. unused portion of a file), because the corresponding ciphertext is more unlikely to contain collisions than it is for random plaintext. That makes 3DES-CBC quite practically unsafe for 32 GiB enciphered; for 8 MiB enciphered, the advantage is already like $2^{-25}$ (fixed).
AES does not have the complementation property of DES (and 3DES), which is that $\forall K, \forall X, \overline{\operatorname{DES}(K,X)}= \operatorname{DES}(\overline K,\overline X)$; that property, while occasionally useful, is undesirable in some protocols, and from a theoretical standpoint makes DES and 3DES trivially distinguishable from a random encryption oracle.


How do I compare three cryptographic schemes with respect to security?

This examines prerequisites; it's not a comprehensive answer, but outgrew a comment.

It's necessary to define if one wants to evaluate the security of the homomorphic scheme(s) implemented by SEAL, HElib and libScarab; or/and the security of the implementations of such scheme(s) that these libraries provide.

It's necessary to define the legitimate user's goals; the assets to be protected. These can usually be discovered by writing down the use cases.

One must define the threat model: assumed goals and capabilities of adversaries; in particular, exactly what data (including, keys) they can read, write or otherwise alter. If implementation is in scope, what's the level of access they have to the computers running the code and holding the data: can they run code on the same CPU as the implementations? With what accuracy can they time the execution result? What resources can it be expected that the adversary use (computing power, available thru funding or otherwise; that might influence a choice of key size, and some libraries might not be flexible on that)?

Note: some fine-grained security analysis, especially of physical devices, consider the level of expertise/knowledge of adversaries. But that's against Kerckhoffs principle and should be avoided from a pure cryptographic standpoint. Plus, digital attacks can relatively easily be commoditized: script kiddies can mount complex (but generic) attacks.

Credit to Maarten Bodewes for large portions borrowed from his comment.


Is it possible: Derived key based on variable number of private keys?

Yes it is possible and already in use in multiple way (LUKS for example). The way it works:

Have a master key that encrypts the whole data
Append a header in front that contains the master key encrypted by the password you want
To add a password add a keyslot (master key encrypted by another password)
To revoke a password remove said keyslot (the user cannot decrypt the master key anymore)

A crude implementation could be that your put your db in a LUKS partition (it could be a file) and add or remove password as wanted.


Show G is insecure against adaptive adversaries

(a) Adaptive case: To show that the adversary can get a very large advantage, send an arbitrary query $x$ to the oracle. The left part of the response is the input of the second query. If the oracle is a PRF, the left part of the second response equals the right part of the first response. If the oracle is a random oracle the two parts are not equal with a very high probability $p \rightarrow 1$ for $n \rightarrow \infty$.

Let $$L: \{0,1\}^{2n} \rightarrow \{0,1\}^n, ~L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_1, \ldots, x_n)$$ and $$R: \{0,1\}^{2n} \rightarrow \{0,1\}^n, L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_{n+1}, \ldots, x_{2n})$$ be the projection to the left and right $n$ Bits, respectively.

Query $$G_k(x) = F_K(x) \parallel F_K(F_K(x))$$
Query $$G_k(L(G_k(x))) = F_K(L(G_k(x))) \parallel F_K(F_K(L(G_k(x)))) =
 F_K(F_K(x)) \parallel F_K(F_K(F_K(x)))$$

And hence $$R(G_k(x)) = L(G_k(L(G_k(x))))$$

(b) Non-adaptive case: Since $F$ is a PRF both $F_K(x)$ and $F_K(F_K(x))$, and hence $G_k(x)$ cannot be distinguished from random output. Since the inputs in a sequence of queries are chosen beforehand, their responses appear completely unrelated and do not provide any information about the nature of the oracle.


Let me preface this by saying that I am not a lawyer and if you are planning on using ECC in a system you sell, you should hire a lawyer.

There are a number of ECC related patents. However "in all of these cases, it is the implementation technique that is patented, not the prime or representation, and there are alternative, compatible implementation techniques that are not covered by the patents" (src). That said, the patents last 20 years, the implementation techniques that are patented might be freely usable (I say might because I believe there are other legal mechanisms to protect IP) 20 years after the patent was applied for. A very quick survey showed that many of the patents on the Wikipedia page were applied for in the late 80's to late 90's. Thus, by 2020 the currently existing patents should expire.

ECC can presumably be used without infringing on the patents. So, the patents themselves are not necessarily inhibiting widespread use. There are some who would argue that the real reason ECC isn't widely used is due to it's age and the fact that RSA came first. Age lends credibility (the longer it has been around w/o a break the more the community trusts it).


means that $X$ and $X'$ have $\ell$ bits[...]?

Yes.

  means that [...] $\Delta X=X-X'$[...]?

Yes and no. Fundamentally what $x-y$ means is $x+(-y)$, but for bit-strings over $\mathbb F_2$ this becomes $x+(-y)\bmod 2$ for each bit, and $-y\equiv y\pmod 2$, i.e. $y$ and $-y$ behave the same. As this means that addition is just XOR, we write $x\oplus y$ to indicate this.

Also note that $\Delta X=X\oplus X'$ is the bitstring that has a bit set iff $X$ and $X'$ differ in that bit position and so it's the "difference" ($\Delta$) between the strings.


Derandomization for asymmetric encryption is a bad idea. Main reason for that is that if an asymmetric encryption mechanism is deterministic, then it allows a brute force attack on the plaintext: the attacker tries possible plaintext messages and encrypts them, and tries to see if it yields the same encrypted message as the one which was observed. Real-world plaintexts usually have much less entropy than cryptographic keys.

Some extra notes:

You could use asymmetric encryption only to convey a fully random symmetric key, in which case brute force on the key is not feasible. But then, this means that you have a random source at hand, so OAEP should not be an issue.
You could imagine a deterministic process that feeds on an extra secret value, thus not reproducible by attackers. But then, this would not really be "derandomization"; that process and the source secret value would better be described as a custom PRNG, i.e. you are just using normal RSA-OAEP.


Small complex multiplication field discriminant for solving ECDLP

I first recall some basics on the discrete logarithm problem and the Pollard-rho algorithm before answering you question.

The discrete logarithm problem

Given a point $P$ of prime order $q$ on an elliptic curve, and $Q$ a point in the subgroup generated by $P$, then there exists $k$ such that $Q = kP$ where $0\leq k < q$.

The discrete logarithm of $Q$ in base $P$ is $k$, and the discrete logarithm problem is finding $k$ knowing $P$ and $Q$

The Pollard-rho algorithm

The Pollard-rho algorithm on a generic group of prime order $q$ has a complexity of $\sqrt{\pi q/2}$.

The principle of it is to construct a sequence of points by posing $R_0 = a_0P+b_0Q$ with random integers $a_0$ and $b_0$, then using a function $f$ that acts as a pseudo-random walk to obtain the sequence of points:
$$
R_{i+1} = f(R_i) = a_{i+1} P + b_{i+1} Q.
$$
Eventually, there will be will a point $R_j$ that is equal to a previous point $R_i$ in the sequence. Then, we deduce that:
$$
k \equiv (a_i - a_j)(b_j-b_i)^{-1} \mod q,
$$
if, of course, $(b_j-b_i)$ is invertible (but that will be the case with a high probability).

Now, the birthday paradox gives the aforementioned complexity.

Speeding-up rho

On elliptic curves, it is easy to compute $-P$ from $P=(x,y)$ since $-P=(x,-y)$. Then, we can regroup all the points of the curve by pairs $\{P,-P\}$.

Instead of looking for a collision between a point $R_i$ and $R_j$ in the sequence,
we look for a collision on their $x$-coordinate. The discrete logarithm will be found if we have $R_i = \pm R_j$.

It is as if the search has not been done on all the points, but only on half of them. Then the value $q$ in the complexity is replaced by $q/2$, which gives the complexity of $\sqrt{q\pi/4}$ (which you will find the corresponding page on the website SafeCurves).

Speeding-up rho further

What we did above is possible because we have the map (called endomorphism) $[-1]$:
$$
\begin{array}{rrcl}
[-1]: & E & \longrightarrow & E \\
     & (x,y) & \longmapsto & (x,-y)
\end{array}
$$
that sends a point of the elliptic curve $E$ to its opposite. We can see that if we apply it twice, we go back to the original point. We say this map has order $2$, and that is why we could grouped by pairs. And it is easy to compute.

Now the question is: does there exist other such maps easy to compute that could be used to speed-up rho by a greated factor?

The answer is yes. For instance, the curve secp256k1 has the following endomorphism:
$$
\begin{array}{rrcl}
\phi: & \texttt{secp256k1} & \longrightarrow & \texttt{secp256k1} \\
     & (x,y) & \longmapsto & (\beta x,y)
\end{array}
$$
where $\beta$ is an element of order $3$ (it satisfies $\beta^3=1$ with $\beta \neq 1$) in the finite field of the curve. Then we have:
$$
(x,y) \mapsto (\beta x, y) \mapsto (\beta^2 x, y) \mapsto (\beta^3 x, y) = (x,y),
$$
which means the order of $\phi$ is $3$.

Then we can group the points of the curve by group of three: $\{ P, \phi(P), \phi^2(P)\}$. We choose one of three points as a representant (such as the point that has the smallest $x$-coordinate viewed as an integer). Instead of searching a collision in Pollard-rho on $q$ points, we search a collision on $q/3$ representants. From this, we deduce that on this curve we can divide by a factor $\sqrt 3$ the complexity of Pollard-rho. Combined with the previous speed-up, this gives a complexity of $\sqrt{q\pi/12}$.

Relation with the CM-field discriminant

The key is that we want an endomorphism easy to compute, otherwise it would not be useful to speed-up Pollard-rho. As we can see, those two examples given above are pretty simple. It is because their degree is $1$, which means the rational functions to compute the coordinates of $\phi(P)$ are polynomials of degree $1$.

There is a relation between the CM-field discriminant the existence of an endomorphism of small degree. In the case of the curve secp256k1, the fact that this discriminant is $-3$ is directly related to the endomorphism $\phi$ with this formula:
$$
\left(\frac{1+i\sqrt 3}{2}\right)\left(\frac{1 - i\sqrt 3}{2}\right) = 1,
$$
which means that there is a non-trivial endomorphism of degree $1$, that is the one given above.

I hope I gave some elements to answer your question. I will try to expand and correct some points later.


There is no need to manually add padding to the RSA public key.

Normally we'd expect the library to do whatever is needed to make key generation secure.  You shouldn't need to do manual tweaks to the public key it produces.  If the library doesn't do that, the library sucks; throw it away and get a better one.

And, for this specific case, no padding is needed during RSA key generation.  There's no need to add any padding to the RSA public key.  Depending upon how the private key is represented, the private key will often be of different length than the public key, so this is not something to worry about.


What happens when a root CA has its private key compromised?

A lot of sleepless nights for the CA, their customers, web browser and OS developers, and Slashdot users, that's what.
I don't know if a CA has ever had their private keys compromised, but there have been incidents where their systems were broken into and fraudulent certificates were issued. (There's a difference between a private key actually being taken, and an attacker just being able to feed bogus certificates into the system and get them falsely signed -- though both are quite bad enough.)
In 2011, a reseller for Comodo (later renamed to Sectigo, and still one of the largest CAs in existence) was compromised and used to issue several fraudulent certificates for google.com and other major domains. Comodo quickly revoked the certificates and disabled the reseller's account, and as a bonus (since online OCSP and CRL checks can be blocked) web browsers and OSes released updates specifically banning those certs.
Comodo was "encouraged" to be more careful -- indeed, another reseller account was compromised less than two weeks later but the attacker was unable to accomplish anything with it -- but their roots were not revoked and they suffered no major consequences. (The reseller is still around, too.) There was a great deal of handwringing around the Internet about whether this was an appropriate response to a limited breach or whether Comodo had made an unforgivable mistake but received "too big to fail" special treatment.
Later in 2011 (bad year), a CA called DigiNotar was compromised, and hundreds of fake certificates were issued, for Google and all sorts of other domains (again). When web browser and OS companies were eventually informed, they revoked DigiNotar's roots from their certificate stores -- defanging the fraudulent certs but breaking many (largely Dutch) websites in the process.
DigiNotar avoided informing anyone of the incident for more than a month, and were unable to produce a complete list of fraudulent certs. Mozilla, for one, lost confidence in them, and DigiNotar was bankrupt in weeks.


A DES cracker just tries out keys until a matching key is found.

So, with Verilog, you design a circuit which includes:

a counter, which enumerates possible keys in a fixed order;
a DES encryption engine, which, given a plaintext block and a key, computes the corresponding ciphertext block;
a comparison engine, which compares the ciphertext block obtained from the DES engine with the expected ciphertext block, and raises a flag if a match is found.

The outer system (say, the PC which controls the experiment) just has to measure the exact time at which the flag is raised, to infer the counter value at that time -- depending on the precision of the measure, this will narrow down the set of possible keys down to a few millions at most, and the PC can finish the work in a fraction of a second.

Of course, there are $2^{56}$ possible DES keys, which is a quite huge number. A complete DES cracking engine will include many copies of the DES encryption and ciphertext comparison engines, each engine exploring a given fraction of the set of possible keys (to some extent, counters may be shared).

If you read French, my PhD thesis contains a description of a DES-cracking engine with FPGA.


Parameter choice Supersingular Isogeny DH

Found the answer:

The $l$-torsion subgroup is isomorphic to a direct sum of two quotient groups:
$E[l] \simeq \mathbb{Z}_n \oplus \mathbb{Z}_n$, hence the basis requires two points and the elements of $E[l]$ are represented by linear combinations of such a basis.
[Reference: Elliptic Curves, Washington, section 3.1]


Weak and strong uniformity of cryptographic hash functions

For the usual suspects (MD family, SHA family etc.) none are known to be weakly uniform (to be picky, they also aren't known to be cryptographically secure). To demonstrate uniformity in a constructive way would give a collision attack; to do it in a non-constructive way would be an existence proof that would generally use some sort of mathematical structure and the functions are not really designed in that way.
If we look at more mathematically structured hash functions which use ideas from public key cryptography such as the Chaum-van Heijst-Pfitzmann Hash Function (see section 7.4 of Stinson Cryptography: Theory and Practice), we can reduce the output modulo $2^n$ and have weak uniformity by the surjectivity of powers of primitive roots. Moreover, if $p-1$ is divisible by $2^n$ then we will have strong uniformity.
Note that the cost of collision finding in Chaim-van Heijst-Pfitzmann is the same as the cost of solving a discrete logarithm which is below the birthday bound and so larger parameters are required for collision resistance.


Can public key cryptography survive quantum computers?

Current commonly used public key cryptography systems are based on the hardness assumption of factorization and/or discrete lograrithm.

Both these problems are solved efficiently using Shor's algorithm using a quantum computer.

Should someone build a quantum computer capable of running the algorithm with thousands of qbits and the ability to apply enough operations on them without decoherence, then it would break RSA and diffie-hellman including elliptic curvre variants.

This breaks all commonly used public key cryptography but does not break all known public key cryptography. There are other asymmetirc algorithms, for example those based on lattice problems which are currently believed to be secure even in the face of quantum computers.


Signing data packets increases data size too large for packet to contain

How is this avoided??

Well, if it add any sort of integrity check to the data (be it a signature or a more sensible MAC), well, that increases the size of the data (packet), and so can potentially push the packet to be larger than the MTU size (assuming the inbound and outbound MTU sizes are the same).

However, the TCP/IP protocol has mechanisms to deal with this.  The details depend somewhat on whether you're encrypting as an end host, or you're a security gateway - since you talk about encrypting traffic from a website, I'll assume you are (at least partially) talking about a security gateway (that is, something that sits between the two end points).

The most obvious one is to advertise a smaller MTU size; that is, if you get a packet that (after encapsulation) would be too big, you reject it with the appropriate ICMP message (giving the largest MTU size that you could process).

This works; however IPv6 doesn't allow you to advertise an MTU size smaller than 1280; if the path that handles the encrypted traffic is close to that size, this doesn't work.

The fallback is to do packet fragmentation yourself; you divide the packet into two (along with some notation to the decryptor about what you did), and encapsulate each packet separately.  This is uglier, however it does work.

The IPsec RFC (4301) goes through this rather explicitly...


Algorithm: How to use x and y mouse movement co-ordinates to generate random data?

The PuTTYgen program, which is open source, contains the following comment in WINPGEN.C where it collects mouse movement for key generation:

/*
* My brief statistical tests on mouse movements
* suggest that there are about 2.5 bits of
* randomness in the x position, 2.5 in the y
* position, and 1.7 in the message time, making
* 5.7 bits of unpredictability per mouse movement.
* However, other people have told me it's far less
* than that, so I'm going to be stupidly cautious
* and knock that down to a nice round 2. With this
* method, we require two words per mouse movement,
* so with 2 bits per mouse movement we expect 2
* bits every 2 words.
*/

I don't know how accurate this information is. I just remembered seeing it and though it was worth sharing.


You can do ECDH with more than two parties. See the below adaptation of the wikipedia example for an EC group -

The parties agree on the algorithm parameters, a curve over $E(\mathbb{F}_p)$ and base point $G$.
The parties generate their private keys, named $a$, $b$, and $c$ (these are integers).
Alice computes $aG$ and sends it to Bob.
Bob computes $(aG)b = (ab)G$ and sends it to Carol.
Carol computes $(abG)c = (abc)G$ and uses the x coordinate as her secret.
Bob computes $bG$ and sends it to Carol.
Carol computes $(bG)c = (bc)G$ and sends it to Alice.
Alice computes $(bcG)a = (bca)G = (abc)G$ and uses the x coordinate as her secret.
Carol computes $cG$ and sends it to Alice.
Alice computes $(cG)a = (ca)G$ and sends it to Bob.
Bob computes $(caG)b = (cab)G = (abc)G$ and uses the x coordinate as his secret.

A note about your concern with Montgomery curves (such as curve25519). Montgomery curves indeed only return the x coordinate but point multiplication only requires the x coordinate as input. Said another way, the Montgomery ladder which is used for point multiplication does not use the y coordinate in the algorithm. So the doing e.g. $(aG)b$ is fine since $aG$ will return an x coordinate, and we can use the Montgomery ladder to multiply that by $b$.

In fact, multi party DH will work for any group that has a "combine" and a "scale" operations for its elements.


When/why is RSA (hybrid) encryption used rather than alternatives?

The Integrated Encryption Scheme offers no qualitative advantage (in term of cryptographic service offered) compared to hybrid encryption using RSA. In particular, neither provides Forward Secrecy: if the private key of the recipient leaks, past cyphertexts can be deciphered. All there is to do is apply the decryption algorithm.

This contrasts with Diffie-Hellman key exchange followed by symmetric encryption with the session key, which can provide Forward Secrecy because the seeds used to generate the session key are never available to an adversary.

Asymmetric encryption protocols allowing forward secrecy (like authenticated DH combined with symmetric encryption) tend to require two-way communication (I know no exception), and thus are not universally usable. Public key encryption schemes (like IES/ECIES, and RSA combined with symmetric encryption for large messages) are the only common option for one-way communication, including email and enciphered backup (communication from past to future, thus one-way, from a cryptographer's perspective).

The rest of this answer compares advantages of the two encryption schemes discussed in the question.

The main advantages of RSA (with hybrid encryption, for all except very small messages) are that

it was first there;
it allows for very significantly more efficient asymmetric encryption (not decryption); this is an important feature in some applications where messages are of moderate size, and the enciphering party has limited computing power, or decryption seldom occurs.

The main advantage of IES is that it allows to perform asymmetric encryption based on the difficulty of solving a problem related to the Discrete Logarithm in a finite group (when RSA relies on solving a problem related to factoring). In turn, this allows:

more efficient decryption, because smaller exponents are involved;
and when using a finite group based on an Elliptic Curve, that is ECIES:

yet more efficient decryption because elementary operations can involve smaller values for conjectured equivalent security;
slightly smaller cryptograms when compared to straight hybrid encryption (this advantage all but disappears, except for very small messages, when we take the mildly unusual step of embedding part of the message into the RSA cryptogram).

Per request: such embedding could be as follows. Assume a 3072-bit (384-byte) public RSA modulus, and some 256-bit (32-byte) hash function $H()$. RSAES-OAEP of PKCS#1v2 allows to encipher any message $M$ from 0 to 318 bytes into a 384-byte cryptogram, by

padding $M$ into $\widetilde M$

where

seed is a fresh random value as wide as a hash;
lHash is the hash of some public constant;
PS is filler bytes with value zero;
the Mask Generating Function is some PRF, usually built from the hash.

then applying the raw RSA public-key transformation $\widetilde M\to C=\widetilde M^e\bmod N$.

This is reversible by applying the raw RSA private-key transformation $C\to \widetilde M=C^d\bmod N$, followed by un-padding.

For $M$ above 318 bytes, we can encipher the message portion past that limit using AES-256 in CTR mode, using the 32-byte seed as key (the IV can be all-zero, or the low 128-bit of $C$). The overhead for encryption is 66 bytes (2 hashes plus 2 bytes), comparable to that of ECIES with affine coordinates on a 256-bit curve (64-byte).

Note: this simplified scheme does NOT provide message integrity; breaks the security argument of RSAES-OAEP by reusing seed; and for that reason is not easily implementable on top of usual RSAES-OAEP APIs, which tend to give no access to seed.


In RSA, how to make sure that $p-1$ and $q-1$ are still hard to factorize?

The procedure to do this is:

Find a large prime factor $r$
When searching for the prime $p$, look among numbers of the form $rk+1$

When we find our prime $p$, we know that $p-1$ will have $r$ as a factor.

Step 1 is comparatively cheap compared to original search from the prime $p$; we select an $r$ which is large (as far as factors of $p-1$ go), but is small compared to $p$.

Step 2 is the original prime search, with an additional condition.  That additional condition doesn't actually slow it down; it doesn't make checking a candidate any more expensive, nor does it make it less likely that a candidate is actually prime.

Hence, the has little extra effort; step 1 is fairly cheap, and step 2 has no additional cost.


How are messages larger than 512 bits padded in SHA-256?

You're close; for a message of 550 bits, k=409; remember, k doesn't include the fixed 1 bit that you initially append.

In general, $k=512i + 447 - m$, where $m$ is the length of the message (in bits), and $i$ is the integer value that yields $0 \le k < 512$.  In your example, $m=550$, and $i=1$; this gives us $k=512\times 1 + 447 - 550$


RSA padding: what is it and how does that work?

Padding in cryptography means adding a (mostly secret) random set of data to the cryptographic functionality.

In practice and when done correctly, cryptographic padding adds a cryptographic problem and thereby reduces attack vectors because (theoretically) it reduces the success in “guessing” intermediate or final states of the encryption and/or decryption functionality.

Two notes:

The reason why I wrote “when done correctly” is that one of the disadvantages of cryptographic padding is that it could make the plain text of the message susceptible to padding oracle attacks.
Note that I wrote "(theoretically)" as some algorithms were weakened and even broken due to incorrect or missing implementations of cryptographic padding, but there are also ample cryptographic algorithms that can do without cryptographic padding as they use cryptographic approaches that differ from RSA's.

If you want to dive deeper into RSA-related cryptographic padding, take a look at this question and especially it's accepted answer which dives into the practice a bit more.

EDIT

Note that there's also a nice and more broad description of cryptographic padding available at
http://en.wikipedia.org/wiki/Padding_%28cryptography%29


How to generate a distributed private key?

Here's a paper that talks about a pre-commit DKG in detail https://eprint.iacr.org/2019/114.pdf.   It also includes some repudiation and decommitment features.

As a summary, each party does these steps:

roll a random number
publish the hash of (some dlp-hard-group-generator to the power of that random number)
after you get everyone's hashes, publish g to the power of that random number along with a signature, using g, proving ownership of that same random number
as long as everyone's hashes match up, compute the LagrangeSum(g) for the group
now you have a distributed M-Of-M key, and a public key corresponding to it, and a proof-of-secret key too.  any dishonest players result in the whole protocol failing
you can redistribute this key to M-Of-N players using VSSS.

A more broadly referenced solution is the ECDKG here:

https://pdfs.semanticscholar.org/3c52/35523be1d305de6dbf3433965c99d9fe4aea.pdf

Which relies on publishing and verifying commitments to polynomial coefficients, and secret communications between parties to ensure sharing was done correctly.   It is more robust to dishonest players, and ultimately works in 2 rounds for M of N instead of the 3 rounds (above).

IMO, the pre-commitment scheme is both easier to understand and easier to get right.


How to decode a caesar that goes to transposed plaintext?

The most frequent letter will probably still be e or t, this uniquely determines the ceasar shift, this leaves maybe a few options. You can also do a $\chi^2$ test to match the alphabet in the subcipher with the standard one, or use bigram frequencies to rate combine shifts in adjacent alphabets.

If all alphabets are mixed, not shifted standard alphabets, it's quite a different story, and will depend on the exact method of keying and square construction.


Securing content and login with "same" password

If you want to keep the crypto simple and mostly on the server side (which may be a good choice e.g. if you're developing a web service), you could use the following scheme:

To log in, the client sends the password $P$ to the server in clear, preferably over a secure channel (e.g. HTTPS).
The server derives a "master key" $K_0$ from $P$ using a key-stretching KDF (e.g. PBKDF2 or scrypt) and a salt $S$ stored in the database.  The length of $K_0$ should ideally match the natural output length of the KDF (e.g. 256 bits for scrypt or PBKDF2-HMAC-SHA256), and should be at least 128 bits.
The server uses a fast KDF (such as HKDF; note that extraction part of HKDF can be safely skipped, since $K_0$ is already a PRK suitable for direct expansion) to derive a verification key (i.e. a "password hash") $V$ of, say, 128 bits, which is compared against the corresponding value in the database to tell if the password is correct.  If it is, the server can use the same KDF to also derive additional key material, such as any number of file encryption keys $K_i$, from $K_0$.  After all necessary keys are derived, $K_0$ can and should be discarded.

Where desired and practical, the computationally intensive part of deriving $K_0$ from $P$ may equally well be performed on the client side.  However, $K_0$ should still be transmitted to the server over a secure channel, since under such a protocol it is still effectively a "password-equivalent authenticator".

Under this scheme, the server only stores $S$ and $V$ (and, of course, the encrypted files and any associated material such as IVs), which are not sufficient to recover $K_0$ or any of the file encryption keys.  A brute force attack on $P$ should be impractical due to the slow KDF used to derive $K_0$ from it; a similar attack on $K_0$ itself is infeasible due to the size of the keyspace.

The major and obvious weakness of this scheme, of course, is that a malicious or compromised server can still obtain $K_0$, and thus also any file encryption keys, when the user logs in.  Thus, while the user is safe from server compromises as long as they don't actively use the service, they do need to trust that the server is not currently compromised at the moment when they log in.

As long as the actual file encryption is done on the server, the weakness described above is unavoidable.  If this is not required, the obvious alternative is to perform the file encryption entirely on the client side (for which essentially the same key derivation process as described above may be used, just all done on the client) and in full control of the client (i.e. no running server-supplied crypto code on the client), and simply treating the server as a dumb file storage device.  The user can then be securely authenticated to the server using an augmented PAKE protocol such as SRP, possibly (but not necessarily) using the same password as for deriving the encryption keys.

Edit: ps. Even if the server can't be made to support SRP or some other augmented PAKE protocol (e.g. if the server runs some pre-existing software that you can't modify), a custom client could still securely store encrypted files on it by deriving both the file encryption keys and the server "password" (e.g. a 128-bit key, ASCII85 encoded for interoperability) from the user's actual password using a KDF as described above.  No matter how insecure the server may be, a compromise of the derived password will, at worst, allow an attacker to log into the server as the user, but it won't compromise the user's actual password or file encryption keys.

One difficulty here is that, without help from the server, there may not be any convenient place to store a salt for PBKDF2 / scrypt.  One way to work around that issue could be to derive the salt e.g. from the username and the server name; this is not ideal, but it's good enough for most purposes, especially if you also use a random per-file salt (stored as part of the encrypted file) when deriving each file encryption key from the master key.

In fact, even if you do store the salt on the server, it may still be a good idea to append the username and server name to it, since it can protect against some theoretical attacks (where a compromised server lies about the salt to find out if two users have the same password) as well as, more practically, against poorly implemented salt generation.


Smart Card - Entropy during on-board public key generation

In short, they retrieve the entropy directly from a source on the chip.

From Wikipedia:

  In computing, a hardware random number generator (TRNG, True Random Number Generator) is an apparatus that generates random numbers from a physical process, rather than a computer program. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, and other quantum phenomena

All reasonably secure smart cards contain a hardware source of entropy. In that way they are not dependable on entropy from the outside. This is of course highly important for smart cards as they should consider any outside information as possibly tainted.

Often these sources of random entropy are post-processed by some form of whitening. And often they are fed into a Deterministic Random Number Generator before the data is used by an application or send to the outside world. On less secure cards this is often a LSFR, but on higher-end cards NIST modes such as CTR_DRBG are used. This is therefore somewhat similar to how RD_RAND operates on modern Intel CPU's.

Beware to check if on card key generation is actually certified in the field for the particular smart card. Even if the key generation is supported, it may not contain enough protection against side channel attacks in the field. In that case you should only use the on board key generation within a secure environment. This is particularly true for RSA key pair generation.

Just like all the other parts of a smart card processor, the entropy source as well as the post processing can come under attack. Furthermore there have been (many) mistakes in the implementation of random generation in smart cards. Some of these can be contributed to the sometimes extreme limitation of resources on smart cards chips (over-optimization).


If you aren't worried about collusion or dynamic group membership, then a very simple solution is to simply have one key for encrypting the messages and another for signing them.  The encryption key gives someone read access and the signing key gives them write access.  Only nodes with the encryption key will be able to successfully decrypt the messages and read them, and only nodes with the signing key will be able to produce "valid" messages that have correct signatures.  The encryption key would be a symmetric key and the signing key would be a private key.  Everyone would have access to the public key to verify that messages were constructed by an authorized node.

If you need more complicated logic or a more flexible system, you can use cryptographic role-based access control, which usually makes use of attribute-based encryption.  But that solution will be very, very complicated.


How to combine a PRG and a non-PRG to design a PRG?

I agree that indeed $G^*(s_1, s_2) = G_1(s_1) \oplus G_2(s_2)$ should be a valid PRG if one of $G_1$ or $G_2$ is a PRG.
The common definition of a PRG requires two properties: being expanding and pseudorandom.
Expanding: $G^*$ is expanding if $l > \lambda$ because then $\lambda + l > 2 \lambda$.
The more interesting part is whether $G^*$ is pseudorandom. Depending on how narrow your definition of a reduction proof is the following might fit it or not.
Pseudorandom: We know that at least either $G_1$ or $G_2$ is a PRG. Call the secure one $G_i$, we don't need to know which one because this will work in both cases.
The pseudorandom property of $G_i$ says that its output on uniform random input is computationally indistinguishable from random.
This means that we could replace the output of $G_i$ by a uniform random string and call the resulting PRG $G^{**}$
$$G^{**} = u \oplus G_{1-i}(s_{1-i}), u \leftarrow_{\\\$} \{0,1\}^{\lambda+l} $$
No (computationally bounded) adversary can distinguish this new $G^{**}$ from $G^{*}$ by pseudorandomness of $G_i$. The formalization of this step actually requires a reduction.
After this you can apply can use an OTP like argument and conclude the proof.
We use techniques reminiscent of game hopping proofs here. Game hopping is pretty common in cryptography proofs. For further reference: A good survey that helped me understand it is this paper


Is there any Information on the "Modular Approximate Greatest Divisor" problem?

Specifically: is the problem of obtaining $\ p\ $ from samples of $\ pq_i + e_i \bmod x$ with secret $\ p, q_i, e_i$ and public $x$ equivalent in hardness to the previously mentioned variant of the problem that operates over integers?

Actually, if $p$ is relatively prime to $x$, and the $q_i$ values are uniformly distributed over $[0, x-1]$, then it is strictly harder than the AGCD problem, in that it is informationally secure (rather than computationally secure), that is, even if we assume that attacker has unbounded computational capabilities, he still cannot recover $p$.

The demonstration is actually fairly simple; even if we assume that attacker knows $e_i$, then for any sample value $s = pq_i + e_i \bmod x$, for any potential value $p'$, there exists a unique $q'_i$ value, namely, $p'^{-1}(s - e_i) \bmod x$ that would yield the observed sample $s$, hence the attacker gains no information about the relative probability of any candidate value $p$ (except for whether it's relatively prime to $x$)


You could protect the ECIES ciphertext with a superencipherment of DLIES, and you would not be weakening your security unless you slipped up and reused keys or used related keys.  That means each step should be done carefully and thoughtfully as if it was the only protection step you would be taking.  For example, when generating the cryptographically random value to serve as the session key protecting your data it's not the time to use a SHA-1 hash of "password1".  Don't use one algorithm to protect both the key and the data of the next algorithm.  Don't use ECB mode encryption.  Simple, but important steps.

The key protection algorithms chosen don't necessarily all have to be asymmetric unless that best meets your business needs.  The threat you're trying to guard against is that of a break in one of the algorithms, so the defense your building should include choosing each algorithm from different algorithmic families.  The first algorithm protecting the data should be something venerable and trusted, such as TDEA (3DES).  TDEA is used by IBM mainframes and cryptographic co-processors to encrypt their databases of keys - if it's good enough for IBM and their giant corporate customers, that's a good sign.  To protect the TDEA key as a session key, choose a non-Feistel algorithm, such as AES, to superencrypt it.  Then, choose your asymmetric algorithm such as RSA or ECC to encrypt the AES superencrypted data.

Is this much security necessary to last 30 years?  The idea is that if a class of algorithms suffers a massive failure that you've other algorithms that haven't also fallen remaining in place.  Let's say someone comes up with an instant factoring algorithm, suddenly rendering every RSA encryption ineffective.  If RSA was the only algorithm protecting your AES key, you're at risk.  Using RSA to encrypt the AES encrypted TDEA key would mean that both RSA and AES would have to fail before the attacker could get to your data.

Given that you're talking about a 30 year life span, it sounds like an application that will not be seeing daily use, so I am assuming performance isn't a concern.  What should be a bigger concern is that you or your heirs will have the software, computing equipment, uncorrupted media, and knowledge available 30 years from now to decrypt it (or at least have enough money to hire an expert in ancient cryptographic data recovery.)  The media is important.  If you burn it to DVD, do you know the DVD's inks will last 30 years?  If you print it on a barcode, will they still have a barcode scanner that can read those olde-timey QR codes?  Those are real questions: if my father's will had been encrypted and stored on 96-column punch cards in his safety deposit box, or on a ZIP drive, or an old 9 track tape, or an 8-1/4" floppy, or even printed on cheap fading greenbar, I know I wouldn't have a reader for any of them today.  That suggests you create a test plan that can be periodically executed to ensure future decryption will be successful.  The test doesn't have to decrypt the actual sensitive data, but it has to prove the hardware and software required for the decryption still works, and that the media is still viable.

Regarding the software, you have choices to make there, too.  You need to have faith that if you write a complex unchaining decryption application in .Net that there will be a .Net runtime environment available on Windows 15.1.  Will tiny 64-bit CPUs still be infesting the planet for any purpose other than cell phone CPUs?  Will Microsoft even exist?  If you get 15 years down the path and .Net has evaporated from the face of the earth, what will you do?

And where are you going to store the keys for 30 years?  Are you going to split them, keeping the RSA private key in one place, and the AES key in another?  Are you going to commit one to memory?  If so, are you going to be around in 30 years, or are you OK if the data is lost forever?

Finally, I come back to what should be your first step:  go over your business requirements again and determine if you really need this much over-the-top protection, especially considering the costs of developing and maintaining some non-standard forms of encryption.  Who are the attackers and what is their motivation?  What's the value of the data you're protecting?  How badly will someone really need it in 30 years?  This kind of long term storage is very, very expensive.  Are you willing to commit someone to 30 years of babysitting these secrets?  Let's say the secrets are guarding an account number in an overseas bank.  What happens to the protected assets if your heirs can't peel this onion apart?


Authenticated encryption using libsodium's crypto_box_curve25519xsalsa20poly1305

crypto_box_easy() doesn't generate a random nonce. But as documented, using a random nonce is safe, and can be done using randombytes_buf(nonce, sizeof nonce);. It's still the application's responsibility to include that nonce in the payload.

Alternatively, the more recent secretstream API automatically creates and attaches a nonce, and can encrypt a sequence of messages without having to care about the nonce at all.

(that being said, this is a programming question, so cryptography.stackexchange may not be the best place for it)


How fast a middle-class computer can verify assymetric signatures (like ECDSA, RSA etc.)?

According to the SUPERCOP measurements, an Intel Xeon E3-1220v6 ("Kaby Lake", roughly comparable to a low end 7000 series i7) with 4 cores at 3GHz achieves 311689 cycles for one verification of an P-256 ECDSA signature and 51093 cycles for one verification of an RSA signature (presumably with $e=65537$). This means this machine can verify $4\times 3\cdot10^{9}/311689\approx 38500$ ECDSA signatures per second and $4\times 3\cdot10^{9}/51093\approx234866$ RSA signatures (lower exponents or using Rabin-Williams will be faster) per second.

Ed25519 instead of ECDSA-with-P256 will be about twice as fast. Using Rabin-Williams instead of RSA will be about 3.75x as fast (assuming the speedup from RSA-1024 to RW-1024 is the same for RSA-2048 and RW-2048, as there is no RW-2048 data).

It seems like a speed-up of about 2x can be gained for generic ECDSA using batch-verification. A similar (slightly better speedup?) can be achieved for Ed25519. Using RSA-3072 as opposed to RSA-2048 (to obtain a security level comparable to P-256) will bring a slow-down of 1.66, so 84746 cycles or about 141600 verifications per second.


How safe is XOR with multiple independent but non random keys?

How safe is the resulting code? Can I store it online?

Very unsafe. No matter how you come up with these keys (passphrases, really), it will have extreme biases. These biases are going to be enough to make some pretty good guesses about your plaintext. This is what makes RC4 insecure in the WEP protocol, and RC4's biases are comparatively minor.

This also has the problem that passwords in general have, which is that you as a human can't accurately remember complex passwords. You'll have to either write them all down (in which case they can be discovered) or use some scheme which actually lowers their strength (your keys 1 through 3).

  Can security hold if 1 or 2 keys (but no more) are compromised?

For every key that is discovered, the biases of the other keys become more apparent. If 2 keys are discovered (particularly keys 2 and 4) it becomes pretty much a puzzle you find in a newspaper to solve.

My advice is to stick to known algorithms. If you need to encrypt something with a password, use something like bcrypt to expand your password into a high-entropy key, then use that key to encrypt with something like AES in a good mode like CTR.


You need to prove that there does not exist a way of finding $x$ and $y$ so that $plaintext \oplus x$ and $H(plaintext) \oplus y = H(plaintext \oplus x)$. The problem is that the attacker is unlimited in time, so the above may actually be possible. (It suffices to prove that there exist messages for which this can be done.)

In addition, in order for this to be secure, it has to behave as a secure MAC, even known the plaintext. So, saying that you don't care about known-plaintext attacks doesn't make sense. I'll explain. Assume that the distribution over the plaintext is that with probability $0.7$ the plaintext is "attack today" and with probability $0.3$ it is "don't attack". Then, an attacker can assume that the message is "attack today" and modify it to "don't attack" (by XORing in "attack today XOR don't attack" to the first part, and XORing in "H(attack today) XOR H(don't attack)" in the second part. The result will be that with probability $0.7$ the message will be changed to "don't attack" and with probability $0.3$ an invalid message will be received. This should not be allowed under any reasonable definition of security.


The M-209 cipher machine cannot be expressed as an LFSR because it is not LFSR-based. It is its own construction, using six adjustable key wheels whose initial positions acted as the key for ciphering. Its operation is vaguely similar to a standard substitution cipher, but the substitution positions would change for each letter, making cryptanalysis more difficult. It had a period length of 101,405,850.

See also https://en.wikipedia.org/wiki/M-209


Do I have to have a different salt for each password?

"In my system, there are no user names, only passwords."

This is the real problem.  Using the same value for both identification and authorization is usually a bad idea, for several reasons:

Two accounts cannot have the same password.
An on-line attacker needs only a single query to determine if any password in the system matches their guess; thus, they can attack all accounts in your system simultaneously with no more effort than attacking a just single account would take.
Since you cannot use per-account salts, an off-line attacker has the same advantage: they can hash each guessed password and then quickly match it against the table of valid hashes.

About the only time when using a single combined identifier/authenticator may be valid is when this identifier is randomly generated and known to have very high entropy (say, 128 bits or more).  With that much entropy, even the odds of guessing just one identifier out of millions of valid ones are acceptably low.  However, such long random tokens are generally impractical for humans to enter or memorize, so they're usually only practical in low-level automated protocols, e.g. as session identifiers.

You also write that:

  "When a user logins in, he types in one or more passwords [...]. Each password might unlock some subset of functions."

So it seems that, instead of the passwords being associated with user accounts, they're associated with some kind of roles.  That's a pretty interesting design, but I won't argue about its merits as such, compared to more traditional user account schemes; presumably you have some reason for designing your system like this.

However, what you could do is give names (or at least some kind of identifiers) to the roles, and have the users enter both the name as well as the password for each role they want to use.  That way, you can use the name to look up the relevant authentication record — which can then include a per-role salt — in the database.

In any case, naming your roles sounds like a good idea for other reasons too: surely there are times when you'd like to be able to refer to a particular role without divulging its password?


Signal protocol, how is Signed PreKey created?

Signed Prekey is one of the long-term prekeys which is used in X3DH. The public component of Signed Prekey is signed by the Identity private key and sent to the Key Distribution Server as part of key bundle. To make sure that the server doesn't tamper with key bundle, Signed Prekey is signed by the Identity key and Identity key is verified using out of band authentication with the help of safety numbers at some time in future.

One-time prekeys are disposable and deleted from the server every time a contact requests public key bundle from the server. Unlike one-time prekeys, Signed Prekey is not disposable but it is not permanent either. Signed Prekey gets expired in 48 hours and needs to be updated by the client whereas Identity key is permanent until app reinstall or change in device.

X3DH can still be initialised without one-time prekey if all the one-time prekeys are used up which can rarely happen. State of one-time prekeys are checked every 12 hours and if approximately 2/3 of 100 one-time prekeys are used up, they are replenished again. Expiry time of Signed Prekey can be extended to reuse it in future X3DH. The purpose of Signed PreKey is to provide some protection if no one time pre key was given, if a device was taken after the interval the initial shared secret still couldn't be calculated.


Include TSA Certificate in Timestamp Request

The behavior turned out to be a vulnerability. Details about it can be found here https://about.signpath.io/blog/2020/08/26/on-the-importance-of-trust-validation.html.


Bulletproofs with ranges not in power of two

You can use an AND statement to do this.

To prove that x is between a and b , you can prove that (x-a) > 0 AND (b-x) > 0


Is it right that the Bomba can halt, but give you a different settings other than the one Germans really used for encryption using an Enigma?

Not sure I follow your question and example.
For a start, the Bombe did not look for the correct key settings, it excluded impossible/wrong key settings. Since it exclude wrong setting then when it stops it might be a good stop or a false stop. They did calculate the number of stops they expected in a complete run (don't remember exact but <10) and later that calculation prove to be correct.

The groundsettings you show seems to be related to the repeated key that was used in the beginning. For that they used Zygalski/Jeffrey sheets to find wheels and key settings, that has nothing to do with the Bombe.


Can I compress $192$ byte key into $16$ or $32$ bytes which can be later used in KDF to recover full key

No, there is no way (secure or otherwise) to compress a random $192$ byte value into something smaller; it is impossible to encode $2^{8 \times 192}$ bit possible settings in only 32 bytes (or $191$ bytes, for that matter...)
Some exceptions:

If those 192 bytes were nonrandom, that is, the vast majority of those 192 bit settings were impossible, you may be able to encode which possible setting into 32 bytes; this would imply that, out of the $2^{1536}$ possible values of those 192 bytes, only $2^{256}$ were possible, then you could do it.  The only plausible way I can think of where this might happen is if the 192 bytes were some sort of public or private key, derived from a much smaller 32 byte seed (and you just store the 32 byte seed, and rederive as necessary).

If you don't mind a large probability of failure; if you don't mind a failure $99.6\%$ of the time, you could trim it down to $191$ bytes.  However, this really doesn't scale to getting things down to the $32$ byte level you're interested in.

If you don't care about the specific value of the $192$ bytes key (only that it was generated 'securely'), then what you can do is pick a $32$ byte secret seed, and use a KDF to expand it into the full $192$ bytes.  This would work; however from your question, it doesn't sound like that's what you're asking about.

BTW: if you ask about a 'secure' method, you need to define what you mean by that.  What operation(s) to do need to be difficult for an adversary?  In this case, there is no method (and so the question is moot), however in other contexts, it would matter.


Purpose of leading zero in PKCS1-v1_5 padding

The first byte is 0x00, because some standards allow RSA key sizes $8b+1, b \in \Bbb Z_+$. Such key would have 0x01 at the first bit, but it is possible for almost all other bits to be zero. Thus, 0x00 as the first byte allows interoperability with all possible RSA key sizes.

NIST's recommendations and few other standards actually recommend only few specific key sizes, where usually the most significant bit is set so technically it would be possible to use shorter encoding.

The 0x02 is simply number describing what encoding and how RSA was used. Currently there are two commonly used choices: 0x01 (private-key operations [commonly signing]), 0x02 public key encryption. (In addition, 0x00 used to exists, but it is not in common use anymore.)

You may also take a look at http://tools.ietf.org/html/rfc2313 (PKCS#1v1.5) [especially section 8.1] for details, or one of later RFC's for PKCS#1v2.x.


A decision problem is to decide if something is true or not (typically phrased in terms of membership of a language). In complexity theory, decision problems are useful for understanding, and most problems can be reduced to a decision problem of some form.

However, in everyday life we are usually not trying to solve decision problems. The algorithms in a public key cryptosystem aren't trying to solve decision problems, so you cannot use the language of decision problems. It just doesn't make sense, as you have discovered.

The notion of polynomial time still makes sense, though.


Is there an authenticated encryption scheme where the recipient can attribute the message to a single sender?

To get non-repudiation, you must have a "proof" which can be used against the signer himself. Symmetric cryptography, by itself, will not help you there, because a cryptographic proof can only come from some "secret" which is under exclusive control of the signer, and the symmetric model assumes that there is a shared secret between two entities. The concept of non-repudiation makes sense if the signer wants to default on his signature, and the receiver of the signature sues him and wants to convince a third party (the judge) that the signature is genuine and binding. This is a scenario where both parties are adversaries with each other. In that context, there is very little provability that can be extracted from a secret value that they both know.

There are systems which provide non-repudiation and still use symmetric cryptography. That's what happens (happened ?) in payment smart cards: the cards "signs" the transaction by computing a MAC over it, with symmetric cryptography; the MAC key is user-specific, but known to both the card and the bank. Such transactions are binding in a legal way (so there is "non-repudiation") because the Law says so; but the system works in practice because it is not easy to circumvent. In particular, the bank is assumed to be honest and not to frame its customers; this assumption is not free, because it comes at the price of very heavy controls and auditing systems on the bank side.

One cornerstone of non-repudiation, as existing laws on digital signatures put it, is the notion of exclusive control. What the signer uses to sign must be proven to be usable by the signer only. In the banking smart card example, this is obtained through several mechanisms, including the inherent robustness of the card, the PIN code handling, and the expensive verifications and safeguards which are performed on the bank side of the transaction. These verifications can be made cheaper if the whole system uses asymmetric cryptography, because maintaining exclusive control of an asymmetric private key is easier than doing the same with a shared secret. For instance, in an asymmetric system, you can arrange for the private key never to leave the device on which it was generated, which makes device initialization easier, especially when already deployed in the field.

(Note that "easier" does not mean "easy".)

Anyway, non-repudiation is about people or at least legal entities; cryptography sees keys. Binding entities to key control is a complex business; one way to do it is PKI. People involved in PKI know that PKI is 5% asymmetric cryptography, 95% procedures. Getting the crypto right is the easy part. Asymmetric cryptography is not sufficient to achieve non-repudiation; and it is not strictly necessary either, but, in the current legal context, you will find that obtaining non-repudiation is even harder if your toolbox does not include asymmetric cryptography.

To say it differently, you can get non-repudiation out of an AE mode, under the same conditions that you would get non-repudiation out of a MAC. This is doable, in fact it has been done, but in a heavyweight framework of procedures, laws, controls, and a lot of money thrown at it. Banks did it with symmetric cryptography because when such systems began to be deployed (in the late 1980s in France), cards which could do asymmetric cryptography were very expensive.


Statistical tests have no value to evaluate randomness in a cryptographic sense, because an attacker is not required to use any specific test. The fact that a stream passes some set of predetermined tests tells you nothing about how it fares against tests which are not in the set.


Addressing the first point, then no.  Min entropy is the smallest estimate of all ways of measuring entropy.  If you consider a string for cryptographic purposes, it's traditional to take the most conservative approach of entropy estimation.  That's the safest way if you wear a tin foil hat.

Min entropy is:-

If s (or X) is random, the individual byte probabilities will be uniformly distributed.  Some Pr(x) will be higher than others.  This range may actually be quite large because randomness can be quite pesky.  Since min entropy takes the max Pr(x) of the range, min entropy will always be lower.  In practice, it may only be 1 - 2% lower for random data.  It will be much lower though for non random data like language.

As a picture, this is a histogram of 1MB of really random data:-

We can assume that this is unbiased. Yet there is significant variation in the individual byte probabilities (the random thing). Ergo there must be a max probability.  This leads to a min entropy value of 7.93 bits /byte. So for an output of 1MB, you can only count on 992000 bytes of entropy for cryptographic purposes.  That's 0.9% less than you might naively expect.  Incidentally the chi for this gives p = 0.15.

As to your second point, I don't think that there is any consensus on this site.  Some say that a hash entropy extractor can only extract half of the original entropy.  Most of this work is highly theoretical though and I am  unconvinced of it's applicability to reality.  On the other hand there are commercial devices that can extract more than half.  I personally believe now that an extractor can extract all source entropy.


In 1985, Montgomery introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the modular multiplications become easier.

Peter L. Montgomery; Modular multiplication without trial division ,1985

We need the modulus $n$ we are working and an integer $r$ such that $\gcd(r,n) =1$ and $r>n$
Definition: The Montgomery representation of $x \in [0,n-1]$ is $\bar{x} = (xr) \bmod n$
Definition: The Montgomery reduction of $u \in [0,rn-1]$ is $Redc(u) = (ur^{-1}) \bmod n$. This is also called $n$-residue with respect to $r$. Indeed, one can show that this set $$\{i\cdot r \bmod n | 0 \leq i \leq n\}$$ is a complete residue system.
In Cryptography, we usually work with prime modulus therefore we can chose $r = 2^k$. In this case the  $\gcd(r,n) = \gcd(2^k,n) = 1$ is satisfied.

Fact 1 :

Since we are working modulo $n$, this is an elementary result.

Fact 2: If $x$ is even, then performing a division by two in $\mathbb{Z}$ is congruent to $x\cdot 2^{−1} \bmod n$. Actually, this is an application of the fact that if $x$ is evenly divisible by any $k \in \mathbb{Z}$, then division in $\mathbb{Z}$ will be congruent to multiplication by $k^{−1} \bmod n$.

What they try to say is

Let $k$ divides $x$ then $u \cdot k = x$ take the modulus $n$ on both sides.  $$u \cdot k = x \bmod n$$ Since $n$ is prime than $k^{-1}$ exist in modulo $n$ and that can be found with the Extended Euclidean Algorithm. For Montgomery this is required only once for $r$. Now we have;

$$u \cdot k \cdot k^{-1} = x \cdot k^{-1} \bmod n$$
$$u = x \cdot k^{-1} \bmod n$$

1.2 x <- x/2

When the $r = 2^k$ this is usually performed by shift operations. This is a trick of the Montgomery. The trial division is transferred into shifts.
x = x >> 2

What are the solid principles behind Montgomery multiplication with reduction?

Montgomery Reduction This is the Wikipedia version.
input: Integers r and n with gcd(r, n) = 1,
       Integer n′ in [0, r − 1] such that nn′ ≡ −1 mod r,
       Integer T in the range [0, rn − 1]
output: Integer s in the range [0, n − 1] such that s ≡ Tr^−1 mod n

m = ((T mod r)n′) mod r
t = (T + mn) / r
if t ≥ n then
    return t − n
else
    return t

Now, the advantage is clear. Since $r= 2^{k}$ the division and $\bmod$ operations are cheap by shifting or masking.
The $n'$ is defined as  $rr^{-1} -n n' =1$
The correctness can be seen by

observe that if $m = (( T \bmod r )n^{'}) \bmod r$ then $T + mn$ is divisible by $r$.

$$T + mn \equiv T + (((T \bmod r)n') \bmod r)n \equiv T + T n' n \equiv T - T \equiv 0 \pmod{R}$$ There for the $t$ is integer, not a floating point.
The output then is either $y$ or $t-n$ ( remember the fact 1). Now let see why the output is $Tr^{-1}$. We again use what we know
$$t \equiv ( T + mn )r^{-1} \equiv Tr^{-1} + (mr^{-1})n \equiv Tr^{-1} \pmod{n)}$$
Therefore the output has the correct residue as we wanted.
Why the substruction? We need to keep track of the $t$'s size.

$m \in [0,r-1]$
$T+mn$ then lies between $0$ and $(rn-1) + (r-1)n < 2rn$. Since the divived by $r$ then $0 \leq t \leq 2n-1$. A single substraction can reduce the $t$ into the desired range.

Montgomery Product
We are going to define a function that is going to be very powerful. Remember $\bar{a} = ar \bmod n$

$MonPro(\bar{a},\bar{b},r,n)$
//outputs $t = MonPro(\bar{a},\bar{b},r,n) = \bar{a}\bar{b}r^{-1} \pmod{n}$

$ T = \bar{a}\bar{b}$
$m = T n' \bmod r$
$t = (T+mn)/r$
if $t \geq n$ $\text{return}(t-n)$
$\text{return}(t)$

Let us simplify the $MonPro(\bar{a},\bar{b},r,n)$ to $MonPro(\bar{a},\bar{b})$ since we keep them constant and $r^{}$ can be calculated as constant before the operations.

What will happen if we call : $MonPro(\bar{a},1)$?

$$MonPro(\bar{a},1) = (a r) \cdot 1 \cdot r^{-1} = a \pmod{n}$$

What will happen if we call : $MonPro(\bar{a},b)$?

$$MonPro(\bar{a},b) = (a r) \cdot b \cdot r^{-1} = a \cdot b\pmod{n}$$

What will happen if we call : $MonPro(a,r)$?

$$MonPro(a,1) = a \cdot 1 \cdot r^{-1} = a r^{-1} \pmod{n}$$


Actually, for CFB mode, the IV is the same size as the block size, 16 bytes.

As for your question "does keeping the IV secret help security", the answer is "not really".

CFB mode processes the message in blocks, and for each block of plaintext, combines that with the previous block of ciphertext to generate the next block of ciphertext.  What the IV is used for is for the initial block of plaintext; there is obviously no previous ciphertext block, and so you use the IV instead.

What this means that if you keep the IV secret, it doesn't really hinder any particular attack in any way.  One way to see that is to assume the contrary; let us assume that, if we expose the IV to the attacker, that he can exploit some weakness.  If we assume that, then the attacker can use that weakness to attack a CFB mode encrypted text without the IV; what he does is take the ciphertext (without the IV), and treat the initial ciphertext block as the IV, and the rest of the ciphertext as the "real" ciphertext; the plaintext this corresponds to is the normal plaintext with the initial block omitted.

Because of this, if exposing the IV with CFB mode lead to a weakness, CFB mode in general is weak.  Now, written this way, this might not sound very comforting; however athat statement is logically equivalent to "if CFB mode is strong, then CFB mode with the IV mode exposed is strong", which is really what we want to show.

In addition, you ask whether:

  It's preferred to make IV constant in my application code

It is absolutely a bad idea to have a constant IV with CFB mode; he's why: the initial ciphertext block is:

$C_0 = P_0 \oplus AES( IV )$

What this means is that if an attacker sees two encrypted messages with the same IV and key, then he knows the above and also knows:

$C'_0 = P'_0 \oplus AES( IV )$

Even though is might not know what the IV is, he can combine the two equations to form:

$C_0 \oplus C'_0 = P_0 \oplus P'_0$

In other words, by examining the bit differences between the two initial ciphertext blocks, he can deduce the bit differences between the two initial plaintext blocks; that is far more information than we want an attacker to know.

Instead, you are far better off either using random IVs or possibly using a counter (if randomness is a problem for you).


Does selecting a set of random numbers for the key and IV insure security?

So your question has some holes in them but I will try to fill as much in as possible. If anyone were to see a mistake in my explanation, I would be more than happy if they pointed it out or edited this solution.

AES is a block cipher that has many modes namely: ECB, CBC, OFB etc. each of these have slightly different properties (both cryptographic and non cryptographic) and benefits. That being said, AES-256 is secure (apart from ECB, and I will not dive into different different definitions of security. If interested look into CPA Secure and CCA secure). The matter now becomes which mode to use, for which there is a better explanation explained here

Hopefully that answers your question. Let me know if there is something I missed.

As for your second question you would want to use a public key exchange protocol. I would suggest using Diffie-Hellman Key Exchange


How to select $g$ in Paillier Cryptosystem

The requirement is that your element $g$ is in $\mathbb{Z}_{n^2}^*$ and not in $(\mathbb{Z}_{n}^*)^2$.

The set $\mathbb{Z}_{n^2}^*$ is the set of integers smaller than $n^2$ that are relatively prime to $n^2$, i.e., you require an element $g$ from $\mathbb{Z}_{n^2}$ such that $\gcd(g,n^2)=1$.

$(\mathbb{Z}_{n}^*)^2$ on the other hand is the set of pairs $(a,b)$ such that $a$ and $b$ are from $\mathbb{Z}_n^*$.

You compute $\lambda=lcm(p-1,q-1)$ where $lcm$ is the least common multiple. Then for your chosen $g$ you have to check whether $a=L(g^\lambda \bmod n^2)$ (where $L(u)=\frac{u-1}{n}$ ) has a multiplicative inverse modulo $n$ (is an element in $\mathbb{Z}_n^*$), i.e., you have to check whether $\gcd(a,n)=1$. If this is the case, then compute $\mu$ as $a^{-1} \bmod n$. Otherwise, try with another $g$ until this condition is satisfied.


Suppose given a DSSP instance $\phi$, $(E_1,E_2,\phi')$ as defined in the paper. The goal is to use a DSSI oracle to decide if $\phi'$ is "parallel" to $\phi$ with "distance" $\ell_B^{e_B}$, that is, whether there exist $\ell_B^{e_B}$-isogenies $\psi,\psi'$ that make the following diagram commute.

$$\require{AMScd}\begin{CD}
E_0 @>\phi>> E_3\\
@V\psi VV @VV \psi'V\\
E_1 @>>\phi'> E_2
\end{CD}$$

By definition of the DSSP problem, we are in one of two worlds:

$(E_1,E_2)$ were chosen by picking an $\ell_B^{e_B}$-isogeny $\psi$ and computing $(E_1,E_2,\phi')$ to satisfy the diagram; in particular, $E_1$ is $\ell_B^{e_B}$-isogenous to $E_0$.
$(E_1,E_2)$ were chosen randomly among all pairs of $\ell_A^{e_A}$-isogenous supersingular curves over $\mathbb F_{p^2}$; in particular, $E_1$ is random.

Hence by applying the DSSI oracle with respect to $\ell_B^{e_B}$-isogenies to $E_1$, we may distinguish between those two worlds with high probability.

There is a chance of false positives: A random curve $E_1$ may still be $\ell_B^{e_B}$-isogenous to $E_0$ by chance, and it's unlikely that $E_2$ would be $\ell_B^{e_B}$-isogenous to $E_3$ in that case. However, it is not hard to show that the advantage of our constructed DSSP oracle is at least $1-\varepsilon$ times that of the DSSI oracle, where $\varepsilon$ is the proportion of curves $\ell_B^{e_B}$-isogenous to $E_0$ within the set of all supersingular elliptic curves over $\mathbb F_{p^2}$.
Typically, parameters are chosen such that $\ell_B^{e_B}\approx\sqrt p$, hence since the number of supersingular elliptic curves over $\mathbb F_{p^2}$ is lower bounded by $p/12$ we have $\varepsilon\leq (\ell_B+1)\ell_B^{e_B-1}\cdot 12/p\approx1/\sqrt p$ which is exponentially small in $\log p$. Therefore our DSSP oracle has non-negligible advantage assuming the DSSI oracle does.

Note that the DSSI problem is only stated for $\ell_A^{e_A}$-isogenies in the paper. I assume the intention was to leave the degree variable, or at least (by symmetry) also allow Bob's degree $\ell_B^{e_B}$, which I used above.