Generate 2 independent keys from a master key

The purpose of the salt is to limit the cost that an adversary can share between multiple targets.  The salt need not be random.  It need only be unique per user.

If two users share a salt (possibly an empty salt), then the work to find at least one of their keys can be shared with Oechslin's rainbow tables on a parallel machine so that the expected cost to find at least one of their keys in a batch multi-target attack is about half the expected cost of a single-target attack, and the expected time to find at least one of their keys is at most one eighth the expected time of a single-target attack.

In general, if there are $n$ possible keys, and $t$ targets, and you parallelize the computation about $p \geq t^2$, then the expected cost to find at least one is $n/t$ and the expected time to find the first one is $n/pt$, at most about $n/t^3$.

If you use 256-bit keys, then the number of users necessary to make this significant is impossibly high, so you can safely use an empty salt in that case.  The salt is important only for ≤128-bit keys.  (This is why AES-128 should already be considered to have a <128-bit security level, and why you should use AES-256 anyway.)

If you have a notion of a user id unique to a key, you could just concatenate it with the name of your application as the salt, with no need for storage.  If you don't have a notion of a unique user id, using a random salt reduces the probability that the adversary can share work between two attack targets.  The longer the salt, the lower the probability of a collision enabling the adversary can share work.  Use a 256-bit salt, and there will never be a collision unless your implementation is broken.
A secondary purpose of a KDF is to map a high-entropy but possibly nonuniform secret into a uniform secret.  If your master key came from a Diffie–Hellman key agreement and is the bit string encoding of some unique representative of a residue class modulo a large safe prime, or is the byte string encoding of a point on an elliptic curve, then the master key is not uniformly distributed among bit strings, but does have high entropy.  A KDF smooths out the distribution on bit strings so it is effectively uniform.
The purpose of a password hash (scrypt, argon2, etc.) is to use all your available resources to drive up the cost of a single evaluation of the hash, which a brute force attack must do repeatedly.  Willing to spend 1sec on hashing?  Force the adversary to compute two million (say) HMAC-SHA256 computations instead of one for each guess.  Willing to spend 1 GB RAM on hashing?  Force the adversary to commit the area of 1 GB RAM in each parallel hashing circuit—which otherwise could have been dedicated to many more parallel hashing circuits if it were not memory-hard, like PBKDF2—or spend double the time hashing if they can only fit 512 MB RAM, etc.  If you can't raise the number of possibilities for the secret, e.g. if your secret was chosen by a human, you can at least raise the cost of testing each possibility in a brute force attack.

These considerations apply independently:

Have a human-chosen password?  Probably has ≪128 bits entropy.  Use a password hash like argon2id with a salt to (a) drive up the cost of each guess, (b) map a nonuniform bit string into a uniform bit string, and (b) prevent the adversary from sharing work between multiple targets.  Make sure if the user ever changes the password, the salt changes too, so if it's deterministically chosen, it can't just be an application name and user id—it must also include, say, a revision number.
Have a machine-generated memorable diceware password chosen from ${\sim}2^{128}$ possibilities?  Use a KDF like HKDF with a salt to (a) turn a nonuniform bit string of 128 bits entropy into a uniform bit string, and (b) prevent the adversary from sharing work between multiple targets.  Using a password hash to drive up the cost of each guess doesn't hurt if this is only ever used in an interactive application, but it's not necessary.
Have a shared secret encoding of an $x$ coordinate on Curve25519 from an X25519 key agreement, so that $x^3 + 486662 x^2 + x$ is a quadratic residue modulo $2^{255} - 19$?  Use a KDF like HKDF to turn it into a uniform random bit string.  Salting doesn't hurt in this case, but it's not necessary.


Is this an example of a zero knowlege proof?

This has some issues, with both soundness and zero-knowledge.

The issue with zero-knowledge is that an eavesdropper who knows $L$ and overhears legitimate traffic can compromise the secret quite easily. While factoring is hard, taking a GCD is very efficient. That means that given $M=pr$ and $L=pq$, an eavesdropper Eve can efficiently compute $\gcd(M,L)=p$. That is a fatal flaw in this scheme as a ZKP -- an eavesdropper can compromise the secret. Where it gets interesting is that your idea of a simulator is correct -- Sam can simulate a valid transaction, which should be enough to guarantee zero-knowledge (Eve could simulate the valid Peggy-Victor transaction without knowing $p$, which would let her efficiently compute $p$ from scratch).

After thinking about this, I think the reason why you can simulate it but it leaks info is that it's unsound (i.e. a prover without the secret can successfully authenticate with 100% probability). When checking $pr$, you verify that $M\ne L$, and $M\ne C$, and $M\mid LC$. It's certainly true that $pr$ meets those conditions. But so does $r$! That's why the fact that a simulator could produce a legitimate-looking transcript doesn't imply zero-knowledge: the transcript only looks legitimate in the protocol because you don't do all the checks you should on it, and further checks on the actual simulated transcript could reveal that it's faked.

The reason simulators are often used to show zero-knowledge is that it means that someone can produce a transcript indistinguishable from a real one without knowing the secret. It's not enough that this transcript passes the tests in the protocol; it must be something that could actually have been produced by a legitimate prover/verifier combo (or computationally indistinguishable from it). If your scheme is unsound, this is certainly not necessarily the case -- an unsound scheme can let a class of transcripts through that are easily distinguishable from legitimate transcripts, which means the simulator might be generating transcripts from the former class.

So, the fatal issue is ultimately that you have $L=pq$ and $M=pr$ both known to an attacker, who can recover $p$. The only reason simulation worked is that you didn't check everything you could have checked; this lets a simulator work, but means that the simulator's transcripts couldn't have been real transcripts (and it's easy to tell that they couldn't have been real), so the simulator doesn't give you zero-knowledge.


Can we use Shamir secret sharing conversely?

No, if $n$ users have independently chosen secret random numbers $r_i$, and for any given $t\in[1,n)$, we can't use Shamir secret sharing to construct a secret dependent on $t$ out of $n$ of the $r_i$, and independent of which $r_i$ are picked. The critical issue is that what Shamir secret sharing assigns to a user is dependent on what the others get.

More generally, I think there is no function taking $t\in[1,n)$ pairs $(i,r_i)$ with distinct $i$ and producing something independent of the picks but dependent on each $r_i$. I'm trying to think of a proof, but nothing has happened yet.


Can Alice send Bob a secure message with only DSA and no key exchange?

Let me first answer your actual question (and then I'll proceed to answer something slightly different that I think will be informative and helpful). Your question asks whether it's possible to use only a DSA key. Technically speaking, this is of course possible. The reason is that a DSA key has exactly the same format as an ElGamal key. No one forces you to use the key with the proper algorithm. (I know that this is a bit stupid, but it will be more meaningful after what follows below.) Just note that if you use the key both for DSA signing and for ElGamal encryption then you may have security problems, and you need to formally prove that this combination is OK. (By the way, this is all OK since Alice already has Bob's public key, so there is no problem of authenticating the key, etc.)

Despite the above answer, I have a feeling that what you are really asking is whether or not it's possible to use signatures alone in order to securely encrypt (in the public key setting, without a shared symmetric key). I'll translate it to "is it possible to use signatures alone to get key exchange" since key exchange is more relaxed than public-key encryption.

This is an excellent question. The first problem with the question is "how to formalize using one primitive to get another". The naive way of doing this is saying that if A exists then B exists. So, your question would be: is the following statement true "if signatures exist then key exchange exists". However, we believe that both signatures exist and key exchange exists, which if true, makes the statement logically true irrespective of any connection between signatures and key exchange. This led Impagliazzo and Rudich in their groundbreaking work Limits on the Provable Consequences of One way Permutations to define that one primitive implies another if one can be constructed from the other using a black-box reduction (and in a world where no other crypto exists, which can be achieved by giving the adversary an NP-oracle to solve all NP problems, for example). Note that most (but not all) reductions in crypto are black box. It is beyond the scope here to define black box, but for here it suffices to say that the primitive is used based on its input/output functionality only, and the reduction uses the adversary in a black-box way as well.

Now, back to your question. The answer is no. Impagliazzo and Rudich proved that one-way functions do not imply key exchange in this setting. Stated differently, it is impossible to construct a black box reduction from one-way functions to key exchange. Noting now that signatures can be constructed from one-way functions only (One-Way Functions are Necessary and Sufficient for Secure Signatures, Rompel), this implies that there exists no black-box reduction from signatures to key exchange. I remark that this result by Impagliazzo and Rudich holds in the presence of an eavesdropping adversary only, so it has nothing to do with man-in-the-middle attacks or anything like that.

Let's conclude by going back to DSA. Note that it is possible to use a DSA key to get key exchange; as I said, just use it for El Gamal. However, this is exactly the difference. My use of DSA is not black box. Rather, I am utilizing the number-theoretic properties and the structure of the DSA key. Thus, this does not contradict the result of Impagliazzo and Rudich.


Traitor tracing - determining a set of codewords

Note that there are two words in $F$ which disagree on the $k^{th}$ coordinate if and only if  $|X(k)|>1.$

All three words in $F$ have $0$ as their first symbol so $X(1)=\{0\}.$

Thus all descendants have 0 in their first coordinate.

By definition of the direct product $\times,$ the descendants are formed by entering all elements of $X(1)$ in the first coordinate, those of $X(2)$ in the second coordinate, etc.


Practical uses of Manipulation Detection Code (MDC) and IGE

Don't believe every claim ever made in any paper ever written, particularly when the paper provides little or no justification for the claim; not everything you read reflects the cryptographic consensus.  This is particularly true for a paper written in 2002, which is a time our understanding of authenticated encryption and security engineering was still in flux.

Today, the conventional wisdom is: just use authenticated encryption, such as GCM, EAX, etc.  For most purposes, there's really no compelling reason to ever use a special MDC-based scheme.

Can there ever be any practical use to MDCs?  I don't know; that's too broad a question to answer.  I don't know if anyone can ever convincingly tell you "no, they will never ever be useful, I absolutely guarantee it".  But in general, I don't see much use to MDC-based schemes.  I find it hard to imagine practical situations where I'd want to use a special MDC-based scheme.  Standard authenticated encryption schemes are good enough.

I don't recommend use of IGE nor biIGE modes: if you have to ask, you shouldn't be using them.  (There may be some very special situations where one might use them -- see, e.g., this use of biIGE in Minx, a system for anonymous communication -- but those are the exception instead of the norm.)
For almost all ordinary real-world situations that you're likely to encounter, an authenticated encryption scheme is going to be adequate.  Researchers have invented tons of clever ideas ever invented, but that doesn't mean they're all useful; in practice, a handful of standard primitives will cover you for 99% of real-world situations.


How can a cryptosystem be unconditionally secure?

The term unconditional security was (as far as I know) coined by Diffie and Hellman in their seminal paper New Directions in Cryptography. Here is the snippet

  [... ] a system which can resist any cryptanalytic attack, no matter how much computation
  is allowed, is called unconditionally secure. Unconditionally secure systems are discussed in [3] and [4] and belong to that portion of information theory, called the Shannon theory, which is concerned with optimal performance obtainable with unlimited computation.

The reason why a perfect implementation of one time pad (OTP) can be considered to be unconditional secure is because of Shannon's insight which may be succinctly described by
$$
Pr_{\mathbf{k}\leftarrow \mathcal{K}}\left[\mathbf{c} = \mathcal{E}\left(\mathbf{m}_0,\mathbf{k}\right)\right] = Pr_{\mathbf{k}\leftarrow \mathcal{K}}\left[\mathbf{c} = \mathcal{E}\left(\mathbf{m}_1,\mathbf{k}\right)\right],
$$

i.e. given a ciphertext $\textbf{c}$, the probability that it was the encryption of some plaintext $\textbf{m}_0$ is equal to the probability that it was the encryption of another plaintext $\textbf{m}_1$; and this holds true for all possible plaintexts and ciphertexts.

Note that it does not say anything about how big or small the keyspace is; for OTP, the only requirement is that the key be at least as large as the message.

Thinking purely from an adversarial perspective, the content of the message can be ANYTHING but there is nothing in the ciphertext that makes one message seem more probable than the other. I have tried to explain this with a cartoon image. Exhaustively searching for the original plaintext (by brute-force cryptanalysis) is an exercise in vain because every plaintext is equally likely! The world war II pigeon discovery is a case study of this kind.

Of course, in case the adversary has some side information that makes the context more specific, the actual message (or parts of it) may be correctly guessed. But it is important to know that any such information is not leaked by the OTP at least.


As a caveat, I have never worked with Microsoft SEAL. But the following may still be useful.
The formula for the variance of a finite dataset $(x_1,\dots, x_n)$ can be written as:
$$\sigma^2 = \frac{1}{n}\sum_{i = 1}^n(x_i - \mu)^2$$
where:
$$\mu = \frac{1}{n}\sum_{i = 1}^n x_i$$
Note that $n\mu = \sum_{i = 1}^n x_i$ --- I will switch between these two expressions freely.
One can algebraically manipulate the expression for $\sigma^2$ to the following expression:
$$\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - \sum_{i = 1}^n x_i}{n^2}$$
(check that this is an identical formula)!
This expression can be computed more easily as follows. Let $\vec{x} = (x_1,x_2,\dots, x_n, 0,0,\dots,0)$ be your plaintext vector, where I assume $n$ is a secret parameter (things are easier if this is not the case, but not by much).
Let $c$ be the encryption of $\vec{x}$.

Compute the ciphertext vector $c_{n\mu} =(n\mu, n\mu,\dots, n\mu)$ via your rotation trick (you already do this)

Square $c$ coordinate-wise to get the vector $c_{x_i^2}$ with "slots" $(x_1^2,\dots, x_n^2, 0^2,\dots, 0^2)$

Apply your rotation trick to $c_{x_i^2}$ get the vector $c_{\sum_i x_i^2} = (\sum_i x_i^2, \sum_i x_i^2,\dots, \sum_i x_i^2)$

Now, any slot of $c_{n\mu}$ (they all take the value $n\mu$), any slot of $c_{\sum_i x_i^2}$ (they all take the value $\sum_{i = 1}^n x_i^2$), and $N$ are sufficient to compute the variance via the formula:
$$\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - n\mu}{n^2}$$
If you can defer this computation to decryption (even as $N\to\infty$ it should remain quite efficient, like 4 arithmetic operations) then you should do that (and the ciphertext can take the form $(c_{n\mu}[0], c_{\sum_i x_i^2}[0], c_N)$, where $c_N$ is a ciphertext encrypting $N$).
If not, the problem is reduced to being able to extract (any) "slot" of a SEAL ciphertext, which is likely quite possible without doing more multiplications.
This leads to a number of different situations:

If $N$ must be kept secret and you cannot defer this computation, you then must clearly compute the multiplications $c_N\times c_N$, $c_N\times c_{\sum_i x_i^2}$ (which can be done in parallel, increasing multiplicative depth by 1), and the division by $c_N\times c_N$, leading to a computation of multiplicative depth 3 (the same complexity as your "bad" situation of zeroing things by multiplying by the ciphertext encryption $(1,1,\dots,1,0,0,\dots,0)$.)

If $N$ can be public, you only have to compute scalar multiplications, so can be done in (total) multiplicative depth 1

If you can defer the computation to decryption, you can do the entire computation in total multiplicative depth 1 again (even while keeping $N$ secret).

All of this discussion is assuming that you want to minimize multiplicative depth. It looks like you are using CKKS as your underlying scheme, and I can't remember if its complexity is controlled by multiplicative depth or something more esoteric (such as GSW's way of computing the complexity of multiplications). Still, the two points of:

Rewriting computations to be algebraically identical, while (hopefully) simpler to compute homomorphically
Deferring (small) parts of the computation for execution on the client when possible

are worth keeping in mind as generic ways to optimize things.


Collusion resistance in proxy re-encryption scheme depending on bilinear map rules

A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegating party.

Are you sure that definition makes sense?  After all, if proxy has the Alice->Bob reencryption key, and Bob has his private key, then the two of them can jointly decrypt any message encrypted by Alice's public key.  And, the point of a private key is to be able to decrypt messages, so (no matter what we do) the proxy and Bob effectively have the private key (even if they might come up with the same bit pattern).

So, what does collusion resistance mean in this context?  If the requirement is that they cannot determine the bit pattern of Alice's key, well, we can easily do that by using a scheme with multiple equivalent keys (and so even if they can come up with 'a' key, it is unlikely to be Alice's bit pattern).  However, that doesn't sound very useful...


CBC-MAC 8 octet ICV compatable with 16 octet block size?

In general the authentication tag size is indeed generated by simply using the first (leftmost, in most byte array representation) bits. In general Tlen - the length of the tag - is supposed to be a multiple of eight, so a tag size of 64 bits results in the leftmost 8 bytes.

You cannot just change the block size of a block cipher. AES is only supporting a 128 bit / 16 byte block size (although Rijndael supports any block size between 128 and 256 bits inclusive using 32 bit increments). So changing the block size of a cipher is generally out of the question.

The usage of just the first/leftmost bytes out of the full MAC output is so widespread that an AEAD API interface that I wrote based the method signatures on the fact. Note that the output of a MAC is indistinguishable from random anyway, so in principle you can use any bits of the result; using the first/leftmost bytes is however the commonly agreed default.

If unsure: read the standard, NIST SP-800 38C:

  Set $T=\operatorname{MSB}_{Tlen}(Y_r)$

and

  $\operatorname{MSB}_s(X)$ : The bit string consisting of the $s$ left-most bits of the bit string $X$.


What key length is required to keep simple keyed "hash" secure?

What you want is a pseudo-random function family from the set of 5-digit numbers to itself. As you found out, the total number of such functions is $10000^{10000}$, which is quite a lot.

Contrary to what Thomas said, most of them are not "crap" – a randomly selected function from this space is as secure as we can have. Unfortunately this would mean a key of size 10000 · 5 decimal digits (i.e. around 166096 bits, i.e. 20 KB), which is a bit impractical.

So we need a smaller key, and still a secure selection from the whole space, which just looks like a random selection. That is known as a pseudo-random function family (PRF) ("indexed" by the key). The "looks like random" can be formalized with some indistinguishability criterion, but from that your two criteria follow (each of them allows an easy distinguisher).

The key size should still be big enough to not enable brute-forcing – this nowadays practically means a 128 bit key.

Smaller key sizes might be possible, if you limit the number of queries an adversary can make, but I would not build my security on this – there shouldn't be a problem to store an 128 bit key per device (if one can store secrets there at all).

Of course, the construction of your PRF should be done in a way that doesn't have any inherent weaknesses, like the crap which was used in the example of your previous question.

Using $HMAC(key, input)$ with a secure hash function (like SHA-2), followed by an output transformation which produces five decimal digits, looks like a secure way to build this. As the input has a fixed length and actually fits together with the key in one input block of the hash function (for most crypto hashes), using a simple $H(key || input)$ should work, too.


Why is it inadvisable to increase the number of rounds or using a larger block size to a published(standardized) block cipher such as AES?

Just in general messing with well studied cryptographic standards is inadvisable. Especially if there is no clear benefit.

Adding rounds to AES is fairly safe, before it became AES the number of rounds in Rijndael was discussed. You need to make sure you continue to use a reasonable key schedule.
This may have even some value, as we have seen attacks on reduced round AES making the safety margin smaller than originally believed.

Changing block size is far from trivial. It is not all obvious how to change AES block size while preserving it's desired properties. This is far more likely to end up in a weak slow cipher.


Elliptic curve over prime field with high order roots of unity

My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?

Not particularly; the factorization of $p-1$ is not specifically relevant to the strength of a curve over $\operatorname{GF}(p)$.

Now, it is quite relevant to the strength of the group $\mathbb{Z}_p^*$; however that's because the order of the group is always $p-1$ (assuming $p$ is prime), and the factorization of the group order is quite relevant.  However, the elliptic curve (in general) doesn't have order $p-1$; instead, it is $p + \delta$ for some $|\delta| < 2\sqrt{p}$ (the exact value of $\delta$ depends on the precise curve you pick), and it is the factorization of $p + \delta$ which is important.


Can an encryption key be inferred by knowing the plaintext and the corresponding ciphertext?

Good thinking!
The good news is that, when you use authenticated encryption, there's no need to keep such "dummy" plaintext-ciphertext pair.
In a typical authenticated encryption, a tag is computed based on the key, the plaintext, and possibly additional data (e.g. AAD, Initialization Vector), so that upon decryption, the tag is verified for correctness. Typically, the tag is 128-bit as is the case with GCM-AES and ChaCha20-Poly1305.
Successful decryption of an authenticated ciphertext indicates that if the correct key had been used then the ciphertext along with other inputs to the encryption algorithm are correct and had not be modified by any man-in-the-middle.


Maximum length in bits of the product n=pq

If $p$ and $q$ are 1024-bit primes, then by definition of the bit size of an integer (at least, a prime in a cryptographic context with glimpses of RSA), $2^{1023}\le p<2^{1024}$ and $2^{1023}\le q<2^{1024}$. Thus their product $n=pq$ verifies $2^{2046}\le n<2^{2048}$, and $n$ is a 2047-bit or 2048-bit integer. We show by exhibition that both cases are possible, with $p=q=2^{1023}+1155$ for the first case, and $p=q=2^{1024}-105$ for the second.

Hence the maximum length in bits of the product $n=pq$ is $2048=2\cdot1024$.

This generalizes to: for odd primes $p$ and $q$, the maximum length in bits of the product $n=pq$ is the sum of the bit length of primes $p$ and $q$; proof that this bound is tight can be obtained from the observation that $\forall k>1,\exists p\text{ prime with }2^{k-1/2}<p<2^k$, which itself follows from stronger versions of Bertrand's postulate.

Since $p$ and $q$ are large primes, they are odd, hence $pq$ is odd, hence the least significant bit of $n=pq$ is 1.

Addition: in common RSA key generation standards FIPS 186-4 appendix B.3 and ancestor ANSI X9.31-1998, it is chosen primes $p$ and $q$ with $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$, which insures that $pq$ is exactly $2k$ bits.


Showing a CBC-MAC is not preimage resistant with a proof

According to wikipedia's page on CBC-MAC:

If the block cipher used is secure (meaning that it is a pseudorandom permutation), then CBC-MAC is secure for fixed-length messages.[1] However, by itself, it is not secure for variable-length messages. Thus, any single key must only be used for messages of a fixed and known length.

Your case presents no such vulnerability, since you're hashing a fixed number of blocks ($1$, to be exact). If you were to compute the CBC-MAC of a variable-length message you could perform such a preimage attack.


Secure against what and for what purpose?

MD5 remains too fast for most human typed passwords.  You should use something like bcrypt or PBKDF or sha256crypt where there are a tunable amount of thousands to millions (or more) rounds of hashing to generate each hash.  You really don't want to allow users to try several billion hashes per second per GPU.

f(x) := md5(x) ++ md5('abc' ++ x) will be just as vulnerable to preimage attacks as md5 -- that is given some hash f(x) = 5d41402abc4b2a76b9719d911017c592d76051e1dae76d1f309598102df58d84 find x.  You simply truncate look at the first 128-bits of the 256-bit hash and it reduces to the problem of md5(x)=5d41402abc4b2a76b9719d911017c592, which you can type into several online md5 reverse lookups (the second half reversed too without me adding it).  So you can see this method will not be secure for user chosen passwords (at least for typical users).

Luckily, last I checked (and according to wikipedia), there are no practical publicly known preimage attacks on MD5 for high-entropy strings.  There is a MD5 preimage attack that takes 2123.4 instead of the full expected complexity of 2128 for a 128-bit hash, but it will not be practical (about 24 times faster than brute force).

Now md5 is not collision resistant.  It is possible to construct pairs of text such that m1 != m2, while md5(m1) == md5(m2).  Granted if you found a collision in md5, this collision would not work immediately for f(x) as in general md5('abc' ++ m1) != md5('abc' ++ m2) when md5(m1) == md5(m2).  However, the underlying flaws of md5 is that is built on the Merkle-Damgård construction will still be present and probably could still be exploited (things like how md5(m1++x) == md5(m2++x) will always be true if md5(m1) == md5(m2)) and could probably still be exploited (even if its not immediately obvious and would be more complicated than simply combining existing attacks).


This is problematic as stated. You need to specify a probability distribution for that complex matrix, but the complex field is infinite. This then implies that you need to also carefully define some detection/quantization mechanism.
So, why complex numbers?


Private set intersection, using a semi-trusted server

Your simple approach is not bad, but you might consider these modifications:

First, you don't need a PRF, any form of hashed key or a simple hash over the concatenation of a key and the element should be enough. Basically any one-way function over elements and some sort of key should do the trick, and you can optimize for speed.
The key is not chosen by Trend but Alice and Bob run a key exchange. There is no need for Trend to know the key at all. That means he can determine if two elements are equal but not get the element itself. With a keyed hash, even knowledge of the possible elements does not help if the server is compromised.
Both Alice and Bob send the hashed set to Trend, preferably already ordered to reduce the complexity of finding all equal hash values.
Trend sends the list of equal hash values back to both of them.
In a second step you can either use Trend again or leave it up to Alice and bob to make sure that they really have the same elements and not just the same hash value (different elements might have the same hash value). If you use Trend, Alice and Bob can run another key exchange and this time use symmetric encryption with this key and send the elements to Trend.


Non-interactive Zero-knowledge proof signature validation without public key

First, before I answer your questions: Money rewards are not forbidden, as far as I know, but that's not how it goes here. Feel free to check out the according question on crypto-meta.

I think, there are few conceptual misunderstandings in your scenario.

First, a signature scheme uses the private key (also called signing key) to sign messages, and it uses the public key (aka verification key) to verify, that a signature matches to a given message (under consideration of this verification key).

Then, you also want to use the public key as address set a limit of ~800 bit, which is a bad idea, because common schemes based on RSA or Schnorr groups (like ElGamal signatures, DSA, etc.) are recommended to be larger (1240 bit at least).

And then, your scenario is quite weird, or maybe you used the wrong expressions. But if A broadcasts a message, he can not sign this message for B (signing requires the private key). If you meant "encrypt the message with the public key $B_{pub}$", it would make sense, but why would B send a request if this message was meant for him?And why would C not know the public key of B, if this was also used as address?

Maybe you should clarify your scenario, because right know I tend to the answer "no, it's not possible".


With OpenSSL and ECDHE, how to show the actual curve being used?

You can make OpenSSL print out the handshake messages with the -msg parameter:

openssl s_client -msg -connect myserver.net:443

Then look for the ServerKeyExchange message. Here is an example:

<<< TLS 1.2 Handshake [length 014d], ServerKeyExchange
    0c 00 01 49 03 00 17 41 04 6b d8 6e 14 1c 9b 12
    4d 58 29 20 e8 e2 1a 24 0d da 8f 38 1a 5d 85 2b
    2b 70 61 97 3b a7 5b fd b6 14 b3 5d f0 dd ea 7b
    68 d9 eb bc b2 59 32 52 9d 8e 9c 97 c0 d4 45 4c
    (...)

This can be analyzed, using RFC 5246 and RFC 4492 as references. In this case:

0c: this is a ServerKeyExchange message (described in section 5.4 of RFC 4492)
00 01 49: of length 0x000149 bytes (329 bytes)
03: the curve type is "named_curve"
00 17: the curve is secp256r1 (curve identifiers are in section 5.1.1, identifier 0x0017 is 23 in decimal).

secp256r1 is also known as P-256, one of the 15 curves standardized by NIST in FIPS 186-4. In fact this is the curve that almost everybody uses.


AES ECB deterministic encryption to perform Private set intersection

Yes, there is a more secure way to achieve your goal. For uniqueness you can use SIV mode with a static nonce. SIV mode first calculates a MAC over the plaintext and then uses that as IV to the mode of operation. This means that identical plaintext will result in identical ciphertext, but that plaintext that only differ by a single bit will result unrelated ciphertext. That way the leakage when identical blocks are used in the plaintext is avoided. SIV has the advantage that integrity / authenticity of the message is protected as well.

SIV has the disadvantage that it requires an authentication tag to be included, to achieve the aforementioned integrity / authenticity. This authentication tag then doubles as IV vector for the internal cipher (hence the name: synthetic IV). If you for some reason does not have the space to store the authentication tag then you may need to look at Form Preserving Encryption of FPE.


I think the very first question before diving into designing the protocol would be to ask yourself what kind of secure communication do you want? Namely, there are two options to consider when it comes to communication between the IM users:

For the client-server secure communication, there are two directions to consider:

From “sender to server”, you would have to encrypt the message with the public key of the server (assuming using public key encryption).
From “sender to recipients”, the server would encrypt each message with the respective recipients' public key (assuming using public key encryption). However, if you are consider using symmetric encryption, a good reference for protocol would be the SSL/TLS protocol that is used widely.

For the end-to-end secure communication, it would be difficult to implement for group message but simpler for individual message. It means that the sender will encrypt the message with a predefined encryption key, and only people who know the encryption key is able to decrypt the message. Sharing the predefined encryption with a group might compromise on the overall security.

Once decided on the framework type, you can add additional information to the payload (i.e. message) to ensure there is authentication, non-repudiation, data integrity, etc. A good reference would be the SSL/TLS protocol.


Why do new versions of TLS use an explicit IV for CBC suites?

TLS 1.0 uses initialization vector (IV) to refer to two different processes. TLS 1.1 introduces a new type of IV that causes an entire block to be discarded and isn't directly comparable to the old series of IVs based on CBC residue. By simply changing an operation at the beginning of a record, the hope was apparently to make implementations easy to patch and prevent strain on some systems.

Overview

IVs attempt to prevent any (key, message) pair from producing the same ciphertext on retransmission. They generally need to be unique, preferably random, but shouldn't need to be secret. (A shared secret IV is really just more key.)

There are many ways to try to use an IV. Let's start with ECB (no IV), then examine TLS 1.0 first, then examine how TLS 1.1/1.2 uses its new IV.

I. ECB

If you just broke up a plaintext into chunks and encrypted each chunk, you're going to risk retransmission of the same block if the plaintext repeats. So the way CBC improves on ECB is to XOR the previous block's ciphertext into the current block's plaintext before encryption. That's sufficient to lower the likelihood of retransmission on every block but the first, which aren't XOR'd with anything yet. So you toss in an explicit IV to the first round to get CBC.

II. TLS 1.0 with CBC

In TLS 1.0, each party might like to be able to ensure this first IV is random. So each party proposes an IV. The two IVs are then mixed together through a pseudo-random function.

  Initialization Vector (IV)
  When a block cipher is used in CBC mode, the initialization
  vector is exclusive-ORed with the first plaintext block prior to
  encryption.
  --RFC 2246

The sender then takes the IV and XORs it with the first block of plaintext. This will propagate through the block chain, it should be sufficient to ensure no repeated ciphertext blocks (at least not corresponding to repeated plaintext blocks).

While an IV proper shouldn't need to be secret, BEAST showed it isn't wise to let your attacker anticipate your next IV and also be able to shape your next chunk of plaintext.

III. BEAST

So in the BEAST attack, the attacker gets the IV for the next message, and then tricks the sender into sending some message of the form (not IV xor CPT).

Once the IV (aka 'mask') is XOR'd in before encryption, it cancels (NOT IV). CPT is now some chosen plaintext that will be encrypted (sans any mask). That's bad.

In version 1.1 of TLS, the big change was providing a fresh IV at the start of each record (every 16k bytes).

The TLS 1.0 "IV" for each block is just called a mask in 1.1. The TLS 1.0 IV for the first block can even be optionally kept. So the new IV doesn't actually replace (either of) the old IVs directly, they serve slightly different purposes and are implemented in slightly different ways.

Per RFC 4346, one of the following two algorithms SHOULD be used to generate the per-record IV:

  Generate a cryptographically strong random string R for the IV. Mask the data with R. The first cipher block will be encrypted as:

  E(R XOR Data).
  Generate a cryptographically strong random R and prepend to the plaintext prior to encryption.  In this case the mask can be fixed, or
  the CBC residue from the previous record may be used as the mask.
  Using the residue preserves maximum code compatibility with TLS 1.0
  and SSL 3.  It also has the advantage that it does not require the
  ability to quickly reset the IV, which is known to be a problem on
  some systems.

  The decryption operation for all alternatives is the same: The
  receiver decrypts the entire structure but discards the first cipher
  block, corresponding to the IV component.

The priorities were to preserve as much of the existing spec as possible, making implementation easier.

In TLS 1.1 and 1.2, they're encrypting the IV in the first block, which will be discarded by the sender. The TLS 1.0 IV is now called a "mask." By keeping the old IV as a mask, but introducing a new IV that makes a disposable block, they leave the algorithm changed as little as possible.

The parties no longer cooperate on this new, more frequently generated IV, meaning fewer code changes, and less strain on some systems.

Further reading

Tor on the BEAST attack
Slaying BEAST
Beauty and the BEAST
Security impact of Rizzo/Duong
RFC 2246 (TLS 1.0), RFC 4346 (TLS 1.1)
Block cipher modes of operation


What you need to know is that all equations in this context are, implicitly, understood to be modulo n. That information alone should answer all of your questions, starting with the equation k = (z1 - z2) / (s1 - s2) (modulo N), which hence means k = ((z1-z2) * modular_inverse_mod_n(s1-s2)) % n, where I tried to copy your modulus (%) operator. Specifically:

Why not 1/k? k^-1 is the way the modular inverse of k is written in your equations, as is the (1/k) which you seem to misunderstand the way a C compiler might.
Why doesn't 1/k work? It would if you teach the audience (interpreter/compiler?) to treat it as modular division or modular inverse.
Is there another way? I'm not aware of a simple other way; however, one can make use of even very small information leakage (i.e. both k values have the same initial bit) to reduce the search space if you really insist on making it hard for yourself.


A missing step in ECDSA signature verification implementation

A lot of libraries will define the point at infinity as $\mathcal{O} = (0, 1, 0)$ (or as $(0, 1)$ if using affine coordinates). Note that the Wikipedia article you link states:

  Verify that $r$ and $s$ are integers in $[1,n-1]$. If not, the signature is invalid.

And a little further down:

  The signature is valid if $r\equiv x_1 \pmod{n}$, invalid otherwise.

So if we represent the point of infinity as having an x-coordinate of zero then we see that $r$ can never be equal to $x_1$ as $r$ must be explicitly checked to be in the range $[1, n-1]$ which implies $r > 0$.

python-ecdsa performs the checks from step 1 in lines 132-135. It does not, however, represent $\mathcal{O}$ as mentioned above, but rather sets INFINITY = Point(None, None, None). So If we get xy = INFINITY in the verification call the method will throw an exception as the modulo operator in v = xy.x() % n will be called on None.

It's not clear if this exception is caught or expected by the calling code, but in any case the verification call will not return that the signature is valid when this happens.


Simple explanation of sliding-window and wNAF methods of elliptic curve point multiplication

Suppose for simplicity we have an 4-bit key $k= (k_0,k_1,k_2,k_3)$, where each $k_i$ is a bit. To compute $kP$, we find
$$k_0P + k_1(2P)+k_2(4P)+k_3(8P)$$
But we could instead write $k=(k_{01},k_{23})$, where we separate it into 2-bit windows. Then we can write
$$ kP = (k_0+2k_1)P + (k_2+2k_3)(4P) = k_{01}P + k_{23}(4P)$$
Then one way to actually compute this is to compute $k_{23}P$, then double it twice to get $4(k_{23}P)=k_{23}(4P)$. Then we add $k_{01}P$ to this.
Extending the pattern, this is the same as double-and-add, except (1) we're doubling multiple times between each add; (2) in the add step, we don't just add $P$ or $0$, but a value in $\{0,P,2P,3P\}$.
For a window size of $w$, we split the key into $(k_0,\dots, k_{n/w})$, where each $k_i$ has $w$ bits. We start with $Q=0$, then repeat for $i=0$ to $i=n/w$:

$Q \leftarrow 2^w Q$
$Q\leftarrow Q + 2^{k_i}P$

In regular double-and-add for an $n$-bit key, we need $n$ doublings and $n$ additions. With this windowed method, we still need $n$ doublings, but only $n/w$ additions, plus whatever it costs to compute each value of $2^{k_i}P$.
If you just compute $2^{k_i}P$ with regular double-and-add, then there is no point to this windowed method -- it will cost more! But if you pre-compute a table of all the values of $\{0,P,\dots, (2^w - 1)P\}$, then you can look up the value in the table, which (depending on your cost model) is probably much cheaper. But the size of this table is exponential in $w$, so you save a factor of $w$ additions at the expense of an exponential amount of precomputation.
I haven't heard of the sliding window before, but it looks like it's exactly the same except you start your pre-computed table at $2^{w-1}P$, and then you don't bother adding a multiple of $P$ if the leading bit $k_i$ is 0 -- you just double $Q$ until the leading bit is 1, which shifts all the windows by the number of doublings.
Wikipedia says "In effect, there is little reason to use the windowed method over this approach, except that the former can be implemented in constant time" which to me seems like saying "there is little reason to use an elevator to get to the bottom floor of a building, instead of jumping out of the window, except that the former can be done without breaking your legs".
Edit: For wNAF, the main idea is that if you precompute $\{0,P,\dots, (2^w-1)P\}$, then you have $\{-(2^w-1)P,\dots,-P,0,P,\dots,(2^w-1)P\}$ almost for free, because you can just flip the sign of the $y$-coordinate (in Weierstrass form at least).
If you're careful about how you represent a number, then you should be able  to do something almost identical to windowed multiplication, except you use these negative multiples of $P$ and thus use fewer additions with the same amount of precomputation.
I am fairly sure (but not certain!) that you can represent a number $k$ by $(k_0,0,k_1,0,\dots, 0, k_{n/w})$, where each $k_i$ is in $\{-2^{w-1},\dots,2^{w-1} -1 \}$. That is, by using negative values, you can fit a 0 between each word (hence "non-adjacent form").
What the wNAF algorithm on Wikipedia is doing is similar to the sliding window: Rather than double exactly $w$ times between each addition, it checks whether the remaining value is even, and if it does, it does another doubling before the addition. This ensures it only ever adds odd multiples of $P$, which saves half the precomputation cost.
An important paragraph is:

One property of the NAF is that we are guaranteed that every non-zero element ${\displaystyle \scriptstyle d_{i}}$ is followed by at least ${\displaystyle \scriptstyle w\,-\,1}$ additional zeroes. This is because the algorithm clears out the lower $\scriptstyle w$ bits of $\scriptstyle d $ with every subtraction of the output of the mods function.

EDIT: It looks like the issue is that $0,1,2,\dots, 2^w-1$ is ambiguous notation. The pre-computed values are actually $0,1,2,3,4,\dots, 2^w-1$. That is, they are just incremented by 1 instead of doubling each time.
In your example, this means the precomputed values are $\{P,2P,3P,4P,5P,6P,7P,8P,9P,10P,11P,12P,13P,14P,15P\}$ (since $w=4$). Then the $d_i$ would actually be $d_1=9$, $d2=1$, and $d_3=9$ (that is, exclude the powers of 2), and so $d_iP$ is in the table for all $i$.
When you start the algorithm, $m=3$ and $Q=0$, and you add $d_3P=9P$ to $Q$ to get $Q=9P$. $9P$ should be in your table. Then you move to the next iteration of the loop, and double $Q$ for $w$ iterations. Since $w=4$, this means we get
$$(2^4)Q = (9\cdot 2^4)P$$
Then $m=2$, and you add $d_2P = 1P$, to get $Q=(9\cdot 2^4 + 1)P$. Then in the next iteration of the loop, double $Q$ another four times to get:
$$(2^4)Q = (2^4)(9\cdot 2^4 + 1)P=(9\cdot 2^8 + 1\cdot 2^4)P$$
Finally, $m=1$, and and so we add $d_1P=9P$ to $Q$ to get $(9\cdot 2^8 + 1\cdot 2^4 + 9)P = 2329P$.


Is there a way to bruteforce the private key of this cryptocurrency altcoin?

First up: APC != APW. The later is a different fork, which you missed to follow… costing you cash. Besides that my research showed that the original APC coin site is down, 99.9% of its block explorers are down, and only the most exotic exchanges list APC (naming it AppleCoin, AppeCoin, AlphaCoin, etc. all using the same APC short notation) which are clear warning signs that the 2013 APC AppleCoin currency is down and out ever since they forked it into APW.

Answering the core of your question

Having said that, cryptographically the wallet recovery based only on public key(s) and wallet password is infeasible as it would mean brute-forcing your public keys to recover private keys. This is much harder (from a time & resources perspective) than mining cryptocurrency, so thinking about brute-forcing is a futile effort.

The password you've got protected the database your wallet used. That's not helpful when trying to recover your private keys… unless you have a backup the wallet database — which you stated not to be available.

My advise: learn from the experience and move on… while constantly reminding yourself that regular backups of important data (all data, not only financial data) can save you from a lot of frustration and from losing money.


Diffie-Hellman: *assumed* largest prime factor of order of $g$?

I've read in several places that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that?

Actually, both references talk about the behavior of the TLS client when negotiating a DHE-based ciphersuite.  The server proposes $p$ and $g$ as a part of the exchange, and hence the client doesn't know $q$.  This doesn't mean that $q$ is unknown, only that the client must trust that the server generated the group properly (which isn't totally unreasonable, as the client needs to trust the server to do other things properly as well).  Now, it would have been reasonable for the server to include the value $q$ as well (so a paranoid client could check it); they didn't include that in the protocol.

  The only method I'm aware of is to start with a large enough prime $q$ and search for prime $p=nq+1$...

That is certainly one method which is used in practice.  An alternative method would be to search for a Sophie-Germaine prime, that is, two values $p$ and $q = (p-1)/2$ which are prime simultaneously; in this case, any quadratic residue (other than 1, of course) would work as a generator.  This takes a bit of more work than the method you listed; however if you're generating a group once, this is irrelevant.


What happens when cbc+hmac get a replay attack?

Rejecting replays is the duty of a higher level protocol. Simple authenticated encryption will accept any message with a valid MAC, even if you receive it several times. Decryption is a stateless process, but you need state to keep track of messages you already received.

For example you could associate an increasing counter with each message you send. The recipient then keeps track of the highest counter they have received so far and rejects any lower counters. You could send that counter in plaintext alongside the ciphertext, but make sure to include it in the data you MAC.

For other modes of encryption the IV/nonce can double as counter. This is the case for AES-GCM or XSalsa20Poly1305.


Points 3 and 4 are a secure way of storing the input to bcrypt (with appropriate choice of parameters for bcrypt).

Points 1 and 2 aren't necessary but don't harm:

they would add a small amount of extra computation for an attacker is possession of the password database that wants to do a dictionary attack;
the attacker wouldn't be able to straight-out use a standard cracking tool as it is a custom scheme, they would need to modify existing tools or develop their own.


How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher?

One option would be to get them to select a one-time MAC of the form:

$mac(m,k_0, k_1) = (k_0 \times m + k_1) \mod p$

You would select $p$ to be something like 29. $k_0$ and $k_1$ would be chosen at random from the values 0-29. $k_0$ has the additional restriction that it can't be 0.

You can aid the computation by giving them a 29x29 matrix of all multiplications mod 29 and a similar table for all additions mod 29.

You'd then work through the message a letter at the time. Suppose these were the letters were numbered: $m_0 \dots m_i$. You'd start at $m_0$, computing the mac equation above. Then you'd feed the mac output in to the $k_1$ position for the next message block:

$mac(m_1, k_0, mac(m_0, k_0, k_1))$

and so on and so on:

$mac(m_i, k_0, mac(m_{i-1}, k_0, \dots))$

The final result is simply the output of the MAC.

Even though it isn't secure it demonstrates at least the idea of a MAC. It also gives them a design that can be trivially extended in to a secure MAC with small alterations.


Is AES secure for java application licensing?

To begin with, let's assume that the attacker cannot extract the AES key from your software.  That means the best they can do is a chosen-plaintext attack on AES: choose a block $Y$, request its encryption $Z$, repeat as many times as desired and try to use the results to figure out something useful about the encryption of other plaintext blocks.

Since AES is believed to be IND-CPA secure, i.e. indistinguishable from a random permutation under chosen plaintext attacks, this is not likely to work.  If the attacker cannot somehow distinguish AES from a random permutation (which, if AES is as secure as it's assumed to be, they shouldn't be able to do), all they can do is try to compile a long list of plaintext/ciphertext pairs and hope that the key they want to crack is found in the list.  But as long as you don't truncate the inputs too much, that isn't likely to happen either.  (You don't specify what you mean by a "digit", but as long as one digit contains at least 4 bits, 16 digits amounts to at least 64 bits, which should be sufficient.)

However, that's all assuming that the attacker cannot just extract the AES key from the software.  If they can, then creating their own license key generator will be trivial.  Note that, from the attacker's perspective, extracting the AES key is much more useful than just modifying the software to disable the key check: knowing the AES key allows them to create valid license keys for any copy of the software on any platform, including future upgrades.

Extracting the key is also likely to be easier than modifying the code, especially if you use the standard system crypto library for your AES implementation.  (As CodesInChaos notes, the attacker can just run the code under a debugger and log all system library calls it makes; the call to AESEncrypt() or whatever ought to stand out as a good target for a breakpoint.)  Using your own obfuscated AES implementation could make it a bit harder, but that's not really guaranteed to work either: crypto code tends to look fairly distinctive when decompiled, and even if the attacker fails to realize that they're looking at AES, they could still just lift the code and its inputs wholesale.

Thus, if you don't want anyone to be able to write key generators for your software, I'd strongly suggest using digital signatures instead.  If you don't want to do that, your other option is to just obfuscate the heck out of your code and accept the fact that a skilled and determined attacker will be able to reverse engineer it and write a license key generator.  Or, you know, consider whether you really even need a license key in the first place.


Is encrypting a file with AES-CTR and then encrypting the AES key with RSA-4096 secure?

First of all, CTR mode is an archaic mode of operation that only provides you confidentiality. In modern standards, we use Authenticated Encryption (AE) modes like AES-GCM or ChaCha20-Poly1305. AE provides you confidentiality, Integrity, and authentication in a bundle.

There is no need to encrypt the IV. They are never designed to be encrypted. They provide probabilistic encryption that is very useful if a key is used more than once.

To encrypt with RSA-4096 you need a proper padding scheme like PKCS#1.5 or OAEP. The latter, OAEP, is better since the former has more issues. Once you use proper padding you are fine (not exactly). Note that RSA is totally broken if someone is able to build Shor's algorithm with enough Q-bits.

It is not clear how are you going to keep your RSA-private keys safely. Is it turning into a chicken-egg problem? Another problem is what if someone plays with the key.txt file. Alas, you can no longer access your files! You need backups.

In these kinds of problems, we prefer passwords based key derivation function like PBKDF2 or Argon2id. Have a good password and derive the encryption key with good parameters and from there encrypt with a AES-256-GCM [*]. It actually uses CTR mode inside. You will only get an additional tag this is up to 128-bit storage overhead and this is nothing compared to your file size. The speed lost, see yourself below from the OpenSSL speed tool.

$openssl speed -evp aes-256-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-256-ctr     474901.33k  1490379.07k  2337490.52k  3131689.64k  3592602.97k  3086712.83k

$openssl speed -evp aes-128-gcm
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-256-gcm     435559.37k  1178543.34k  2184926.89k  3160146.94k  3705495.55k  3713903.27k

In the end, a Veracrypt may be good for you. Have a good password, generate it with diceware or Bip39 then you will have a good entropy. Use it while creating your volume.

Diceware passphrase has an entropy around

A five-word  has 64.6 bits
six words have 77.5 bits
seven words 90.4 bits
eight words 103 bits
nine words 116 bits
ten words 129 bits.

Bip39 creates $\approx 2^{263}$ with 256 coins tossing and selecting 24 words.

And, don't forget to back up your files.

[*] Since we talked about Shor, we have to consider Grover, too.


PKCS#11: Can C_GetMechanismInfo() return CKR_OK on a disabled mechanism?

The caller may invoke C_GetMechanismInfo for a mechanism that does not appear in the list returned by C_GetMechanisList, where the latter "... is used to obtain a list of mechanism types supported by a token".

I believe that's the reason they added the adverb possibly.

I am not sure what you refer to as "temporary disabled". To me, if the token is not in a state that allows a certain mechanism (temporarilly or permanently), C_GetMechanismInfo should return CKR_MECHANISM_INVALID or at the very least not CKR_OK.


Securely send public key from client to server in RSA?

In this protocol:

client draws a random AES key $K_\text{SES}$ (I'll make it 128-bit);
client enciphers $K_\text{SES}$ using the server's RSA publickey $K_\text{PUB}$, and sends the result $\text{RSAES}_{K_\text{PUB}}(K_\text{SES})$ (note: RSAES designates RSA encryption with some unspecified padding e.g. per one of the two fine encryption schemes defined in PKCS#1);
server receives the alleged $\text{RSAES}_{K_\text{PUB}}(K_\text{SES})$ and deciphers it into the alleged $K_\text{SES}$, using the server's RSA private key $K_\text{PRI}$; servers stops if that fail;
server enciphers $K_\text{SES}$ using AES key $K_\text{SES}$, and sends the result $\text{AESENC}_{K_\text{SES}}(K_\text{SES})$;
client receives the alleged $X=\text{AESENC}_{K_\text{SES}}(K_\text{SES})$, deciphers it using the original AES key $K_\text{SES}$, and aborts if $\text{AESDEC}_{K_\text{SES}}(X)\ne K_\text{SES}$;
presumably, $K_\text{SES}$ is then used as a session key; I'll assume as key to some unspecified mode of AES for confidentiality, and perhaps something (not even suggested) for authentication; at least the client's public key is sent using that encrypted channel.

A 5-minute non-exhaustive analysis reveals various serious issues, limitations, and risks with this protocol:

there is no explicit protection against replay of a session to the server; in many circumstances this is a gapping hole!! (clarification: replay to the server is simply sending the messages sent by a genuine client and recorded in an earlier session, including any IV, and would work in the absence of some challenge-response from the server, which is currently not described);
it was imprecisely specified (it still is, in particular regarding error handling and time-outs), making a detailed analysis impossible;
it is not peer-reviewed, thus must be presumed unsafe;
as any protocol starting without secret credentials on the client side, it can not authenticate the client;
as any known non-quantum protocol, it can not prevent Eve-in-the-middle from intercepting or/and relaying the messages, but that is not by itself a security issue;
there is no protection against denial of service of the server by multiple connections, replayed or not;
there are Bleichenbacher padding oracle attacks on some bad implementations of step 3. on the server side (typically when using RSAES-PKCS1-V1_5), that in the worst case could leak $K_\text{SES}$, and then the sky is the limit;
if somewhat Eve-in-the-middle manage to abuse the implementation of step 6. on either the client or server side as a decryption oracle, then the possibility exists that she can obtain the decryption of $X=\text{AESENC}_{K_\text{SES}}(K_\text{SES})$ using the active key $K_\text{SES}$, giving her $K_\text{SES}$, with similarly devastating effect (clarification: if the encryption uses CBC, the attack could consist is replacing one genuine ciphertext block with with $X$ obtained from step 4. and somehow obtain the corresponding plaintext block, that would yield $K_\text{SES}$ after an exclusive-or with the previous ciphertext block ; that should not be possible in an authenticated link, but not enough details about that are given);
if $K_\text{PRI}$ ever leaks, the protocol is entirely insecure after the leak with no stated provision to recover from that;
if $K_\text{PRI}$ ever leaks, the confidentiality of past recorded communications is compromised; contrast that with protocols offering forward secrecy;
update: there is no stated safeguard to reduce the risks resulting from a poorly seeded or otherwise bad RNG being used at step 1., which times and times has occurred on the field;
update: at step 6. the client's public key is sent enciphered, when we really need authentication, not really described.


The differential privacy book is the typical reference for the area, and it is quite useful here. Since this answer essentially amounts to quoting from that book, I'll walk through how to find the right things to quote.
Ctrl+F-ing "Laplace", we find Theorem 3.6, which states that the Laplace mechanism is $(\epsilon,0)$-differentially private.
This mechanism adds i.i.d. $\mathsf{Lap}(\Delta f/\epsilon)$ noise to the output, where (as you mention):
$$\Delta f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_1$$
So this is the $\ell_1$ version of sensitivity.
Ctrl+F-ing "Gaussian", we see that it works for sensitivity defined via:
$$\Delta_2 f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_2$$
This is an $\ell_2$ notion of sensitivity (although note that "neighboring datasets" $x, y$ are still within 1 of eachother in the $\ell_1$ norm, meaning they still differ in at most one row).
Theorem 3.22 then shows that to be $(\epsilon, \delta)$ differentially private, the Gaussian mechanism adds i.i.d. noise $\mathcal{N}(0, 2\ln(1.25/\delta) \Delta_2(f)^2/\epsilon^2)$ to the output of the function.


Why authors of bcrypt have chosen blowfish and not some hash function like SHA-1?

The bcrypt KDF does not use the entire block cipher as-is. It relies on a modified version of its key schedule. This is important because blowfish, unlike many other ciphers, has an extremely expensive key schedule. It requires about four kilobytes of fast memory, compared with SHA-1 which is so light that it can almost be computed entirely in x86 registers. Although bcrypt is not nearly as memory-hard as other, modern KDFs like Argon2, it was still quite good at the time and is still better in many ways than PBKDF2, which internally uses a hash function like SHA-1 or the SHA-2 family.

See Why can't one implement bcrypt in Cuda? for more information on why memory hardness is good. It explains why you can't get as much out of the massive parallelism of a GPU with bcrypt. There's also the wonderful answer by Thomas Pornin elsewhere which goes into more detail about bcrypt's security.


Since you already know $K$, you just need to know the length of $H$ based on the hash algorithm you are using, which should be constant, then simply split the output of $D_k$ into the 2 parts of appropriate length.

You can then perform the keyed hash on the first part and match it against the last part, which will match if the decryption was successful.

It should be noted that your method is not aligned with best practices, such as NOT hashing using key prefixing (unless you are using Keccak or other sponge based hash), and NOT hashing the plaintext, but rather the ciphertext, as attacks are possible, especially with RC4. Also it is not recommended to use the same key for both encryption and authentication as per your example.

A better option is:

$C'$ = $E_k (M)$

$C$ = $C'$ $||$ $HMAC_{k'} (C')$

Where $C$ is the final transmitted message, and the hash is checked prior to decryption of the message, and $k'$ is a separate or derived key just for authentication.


Using HMAC as a nonce with AES-CTR encrypt-and-MAC

What you're describing is pretty similar to the SIV block cipher mode. It also uses a deterministic function of the message to derive the nonce for CTR encryption. Under some pretty widely accepted assumptions about HMAC-SHA256 this is a perfectly fine way of achieving deterministic authenticated encryption. It doesn't meet IND-CPA (as you pointed out) but if this is acceptable for your application, you should be fine.

Disadvantages are mostly in terms of efficiency. The mode you propose requires two passes of the plaintext to generate a ciphertext, but GCM only requires one. A mode like OCB also only requires one pass for authenticated encryption, but is parallelizable as well. The impact of this is, again, dependent on your application.


Is this a secure implementation of password reset email?

What you describe looks secure to me, but excessively complicated.  The following simpler procedure should suffice:

When a password reset token is requested:

Generate a secure random token and save it (or a cryptographic hash of it) in the database, along with a timestamp.  Overwrite the previous token, if any.
Send the token to the user by e-mail (suitably encoded).

When the user submits a token:

Check that it matches the token in the database, and that the corresponding timestamp is not too old.

The only part of the process which needs to involve any cryptography at all is generating the random token, and optionally hashing it.  You can usually offload the former task to the OS; on Unixish systems, for example, you can read the token from /dev/urandom.  Alternatively, if you're using a decent crypto library, it should provide a routine for generating secure random numbers (which may call the OS random number generator internally).

Ps. The one situation where you might want to go with a more crypto-heavy solution would be if you didn't have access to a convenient database for storing the tokens.  In that case, you could, for example, compute the token as MACK(userid || timestamp), where MACK is a message authentication code keyed by the secret key K, and have the user submit the timestamp along with the token.  (You could also include a random number in the MAC input, but that's not really necessary — without the key K, an attacker won't be able to forge the MAC.)  However, since you do have a database available, this doesn't really apply.


Is double SHA-256 the best choice for Bitcoin?

Since the initial release of Bitcoin is  9 January 2009,  the designer had these NIST hash functions (NIST-FIPS 180-4) as available options: SHA-1( 1995), SHA-256 (2001), SHA-512 (2001), and some more.
The main difference between SHA-256 and SHA-512 is the target CPU. SHA-256 is designed for 32-bit CPUs and SHA-512 is designed for 64-bit CPUs. That makes a huge difference in the target CPUs.
One can argue that the designer wanted protection against the length extension attacks. However, SHA-512/256, which has the same pre-image, secondary-preimage, and collision resistance as SHA256, is secure against length extension attacks. Though not officially available at that time, simply trimming the 256 bit from the output of SHA-512 is the countermeasure. The knowledge was there since SHA-384 (2001) was available and it is trimmed from SHA-512 with different initial values for domain seperation *.
The obvious choice can be considered as the speed. SHA512, according to the Blake2 site, is 50% faster than SHA-256. SHA-1 is 2-times faster than SHA-256. However, the output size of SHA-1 is 160 bit and can be considered small for security during 2009 and for the mining space.
Another parameter for the choice of 256-bit is that Bitcoin used ECDSA-SHA-256 signatures. The obvious choice for hashing the message is using SHA-256.
Therefore, we can conclude that the designer didn't want fast mining, compatible with the ECDSA-SHA-256 signature so choose the $\operatorname{SHA-256}$ and, to prevent length extension attacks, selected double hashing. The double hashing is invented by Ferguson and Schneier in their book Practical Cryptography to countermeasure against length extension attacks.

As a side note, double-hashing doesn't prevent collision attacks since any collision $\operatorname{SHA256}(x)=\operatorname{SHA256}(y)$ is also a collision for  $$\operatorname{SHA256}(\operatorname{SHA256}(x))=\operatorname{SHA256}(\operatorname{SHA256}(y)).$$

*In academics, the first occurence the trimming as a countermeasure againt the length extension attack goes back to 1995


The symbol of the circle with the + in it is one of many symbols for exclusive-or. XOR, EOR, EXOR, ⊻, ⊕, ↮, and ≢. Binary OR is true when either input is true; binary XOR is true when exactly one input is true. If both inputs are true, the XOR result is false.

One property of this is that if either input bit flips, the output bit will also flip. That's sort of the definition of XOR, so you'll have to figure out how to reword that for your stream cipher question.

A XOR B Truth Table
Input   | Output
A   B   |
________|_______
0   0   | 0
0   1   | 1
1   0   | 1
1   1   | 0

0 = FALSE
1 = TRUE


Differential privacy noise that scales with $L_p$-sensitivity with $p>2$?

You can measure your sensitivity in an arbitrary norm. The exponential mechanism, that samples from the distribution proportional to $\exp(-\epsilon |z-f(x)|_p / 2)$ will give pure DP. This is more general, and the K-norm mechanism will allow you handle sensitivity measured in norms other than some p-norm. For pure DP, these p-norm mechanisms are optimal. In particular, when sensitivity is measured in the $\ell_2$ norm, the optimal mechanism adds noise from the Gamma distribution.
How then does the Gaussian noise mechanism do better? It gives you $(\epsilon, \delta)$-DP instead of pure DP. It is natural to ask what the optimal approximate DP mechanism is for other sensitivity measures. It turns out that for approximate DP, the right Gaussian mechanism is always optimal. You just convert your $\ell_p$ sensitivity bound into an $\ell_2$ sensitivity bound (by finding the smallest $\ell_2$ ball that contains your $\ell_p$ ball) and add Gaussian noise based on that. Here again, there are analogous results for sensitivity being measured in non-p-norms.
Some caveats are in order. Optimal above is for your error being measured in the Euclidean distance. Some of the results are optimal only up to logarithmic factors. When you care about error in other norms (say $\ell_\infty$), there can be other more interesting mechanisms.
References:
The upper bounds for $\ell_p$ balls are straightforward. The lower bounds are in
https://arxiv.org/abs/0907.3754, and https://arxiv.org/abs/1212.0297. Simpler lower bounds for CDP/RDP are in https://arxiv.org/abs/1911.08339.


Knowing SHA256(m) and k, is it possible to calculate HMAC-SHA256(k,m)?

No, knowing the SHA-256 hash of an arbitrary message, and a key, it is not possible to compute the HMAC-SHA-256 for that message and key; that's because in HMAC, something dependent on the key is put in front of the message before hashing the message.

Addition: if what's asked was possible, then a break of SHA-256 allowing to find collisions would be a death blow for HMAC-SHA-256 (the HMAC for messages colliding per SHA-256 would be identical for any key). By contrast, we have excellent hope that the HMAC construction would provide enough protection to keep HMAC-SHA-256 practically safe. There's the precedent of HMAC-MD5, which remains unbroken even though MD5's collision resistance is trounced; and the theoretical security argument made by  Mihir Bellare in New Proofs for NMAC and HMAC: Security without Collision-Resistance.

Independently, on the same line: knowing the SHA-256 hash of an arbitrary key of more than 64 bytes, and a message, it is possible to compute the HMAC-SHA-256 for that message and key; that's because by definition of HMAC, for keys larger than the message block size (64 bytes for SHA-256), the first operation made with the key is to replace it by its hash.

Note: in this answer, arbitrary excludes guessing a low-entropy value from its hash.


Why isn't outputting only a portion of the hash state a simple defense against length extension attacks?

Contrary to your assumption, this is done, and it is secure: For instance, the hash functions SHA-224 and SHA-384 are basically the same algorithms as SHA-256 and SHA-512! The only differences are in the initial values for the Merkle-Damgård construction used internally and, of course, in that only the first $224$ or $384$ bits of the resulting hash are output. These hash functions are resistant against length-extension attacks since an attacker would have to guess the remaining (too many) bits of the internal state. (Note that the choice of different initial values is irrelevant to this issue, so just truncating SHA-256 or SHA-512 also yields length-extension-resistant hashes.)

As another almost-example: In some sense, Keccak/SHA3's first $r$ output bits are simply a prefix of the internal state after consumption of the last block, while the rest of the state is kept secret (and possibly used to compute more output bits, which are again prefixes of the internal state, through repeated application of a so-called "sponge function"). With this construction one can argue, and in fact this is advertised as a feature of Keccak, that the keyed hash $\operatorname{Keccak}(\mathit{key}\mathbin\Vert\mathit{data})$ yields a secure MAC, while the same construction for Merkle-Damgård hashes is vulnerable to length-extension attacks.


What is the difference between a stream cipher and a one-time-pad?

There is no universally accepted definition of the expression "stream cipher"; but the one I most often encounter is the following: a stream cipher is a symmetric encryption algorithm which accepts as inputs arbitrary sequences of bits (or bytes) such that:

the length of the output is equal to the length of the input (no padding);
for any $n$ (possibly any $n$ which is a multiple of 8 if we restrict ourself to bytes), the first $n$ output bits depend only on the key and the first $n$ input bits, regardless of the value of the subsequent input bits.

In that sense, the One-Time Pad is a stream cipher. A block cipher used in CTR mode or CFB mode is also a stream cipher. Note that the latter is not of the kind "XOR with a stream generated from the key independently of the input data". The Wikipedia page you link to talks about "synchronous stream ciphers" and "self-synchronzing stream ciphers".

However, the ultimate security of the One-Time Pad comes from the key size: it is unbreakable because it assumes that the key is as long as the message and was generated by an unpredictable mechanism. If you generate the pad with a more conventional stream cipher, working over a small fixed-size key, then it is no longer a One-Time Pad, just a "regular" stream cipher. The expression "One-Time Pad" refers to, exclusively, the mythical scheme which uses truly random long keys. So while One-Time Pad is a stream ciphers, stream ciphers are not One-Time Pads.


A zero-knowledge algorithm for proving inequality of two discrete logarithms was given e.g. by Camenisch and Shoup in Section 6 of Practical Verifiable Encryption and Decryption of Discrete Logarithms (CRYPTO'03).

Quoting  from the paper:

  Let $G=\langle g \rangle$ be a group of prime order $q$. The prover
  and verifier have common inputs $g, h, y, z \in G$ where $g, h$ are
  generators of $G$ and $log_g y \neq log_h z$. The prover has the
  additional input $x = log_g y$. The prover and the verifier then
  engage in the following protocol.

  The prover randomly chooses $r \in Z_q$, computes the auxiliary commitment $C = (h ^x/z)^r$, and sends $C$ to the verifier.
  The prover executes the protocol denoted $PK\left\{(\alpha, \beta) : C = h^\alpha (\frac{1}{z})^\beta \wedge 1 = g^\alpha (\frac{1}{y})^\beta \right\}$ with the verifier. (Note that this is a
  proof of equality, so we know how to do this).
  The verifier accepts if it accepts in Step 2, and if $C \neq 1$; otherwise, the verifier rejects.

  This constitutes an honest-verifier proof system for proving that
  $log_g y \neq hog_h z$.


Trustless exchange without a third party

No, without some kind of trusted information there is no way of identifying the parties, so Alice and Bob are never able to trust that they have transferred the data to the right party.

Even if they meet in person they need to have some trusted data (such as facial features of a person, remembered from when they met before) otherwise they may confer data to an imposter.

I'm assuming here that you need to keep the data confidential. That is not apparent from your question. If this isn't the case Alice and Bob could simply publish the information for all to see.

Of course, Alice and Bob would still not be confident that the right entity posted the data, i.e. the authenticity of the data cannot be proved.


Pairing — Finding points which are depicted in different cyclic subgroups?

With a very small field (here, $q = 11$, i.e. there are only eleven elements in the base field), the number of points on the curve is small enough to enumerate them all, even by hand.

Elements in $\mathbb{F}_q$ are integers from $0$ to $10$. The field extension $\mathbb{F}_{q^2}$ is defined by using a formal extra element $i$ such that $i^2 = -1 = 10 \bmod q$ (there is no such element in $\mathbb{F}_q$, so $i$ is really a "new element"). All elements of $\mathbb{F}_{q^2}$ are then written as $a+ib$ for two values $a,b \in \mathbb{F}_q$. This is basically the same way that complex numbers ($\mathbb{C}$) are defined with regards to real numbers ($\mathbb{R}$).
There are $q^2 = 121$ elements in $\mathbb{F}_{q^2}$.

The C program below just enumerates all points $(x,y)$ such that $x$ and $y$ are elements of $\mathbb{F}_{q^2}$; there are $121^2 = 14641$ such points. Out of these, $143$ match the curve equation ($y^2 = x^3 + 4$)
 (total curve order is $144$ since there is also the "point at infinity", which has no $x$ and $y$ coordinates). For each such point, we apply the point addition law repeatedly to work out the point order (for a point $P$, we add $P$ repeatedly until we reach the "point at infinity"). For points of order $3$, we print out the points $P$ and $P+P$. Here is the code:

#include <stdio.h>

typedef struct {
        unsigned re, im;
} mq2;

static mq2
mq2_sub(mq2 x, mq2 y)
{
        mq2 z;

        z.re = (11 + x.re - y.re) % 11;
        z.im = (11 + x.im - y.im) % 11;
        return z;
}

static mq2
mq2_mul(mq2 x, mq2 y)
{
        mq2 z;

        z.re = (121 + x.re * y.re - x.im * y.im) % 11;
        z.im = (x.re * y.im + x.im * y.re) % 11;
        return z;
}

static mq2
mq2_mul_int(mq2 x, unsigned f)
{
        mq2 z;

        z.re = (x.re * f) % 11;
        z.im = (x.im * f) % 11;
        return z;
}

static mq2
mq2_inv(mq2 x)
{
        unsigned d, d0;
        mq2 z;

        d0 = (x.re * x.re + x.im * x.im) % 11;
        d = (d0 * d0 * d0 * d0) % 11;
        d = (d * d * d0) % 11;
        z.re = (x.re * d) % 11;
        z.im = (121 - x.im * d) % 11;
        return z;
}

static mq2
mq2_div(mq2 x, mq2 y)
{
        return mq2_mul(x, mq2_inv(y));
}

static int
mq2_eq(mq2 x, mq2 y)
{
        return x.re == y.re && x.im == y.im;
}

static int
mq2_eq0(mq2 x)
{
        return x.re == 0 && x.im == 0;
}

static void
mq2_print(mq2 x)
{
        if (x.im == 0) {
                printf("%u", x.re);
        } else if (x.im == 1) {
                if (x.re == 0) {
                        printf("i");
                } else {
                        printf("i+%u", x.re);
                }
        } else {
                if (x.re == 0) {
                        printf("%ui", x.im);
                } else {
                        printf("%ui+%u", x.im, x.re);
                }
        }
}

typedef struct {
        mq2 x, y;
        int zero;
} point;

static const point Z = { { 0, 0 }, { 0, 0 }, 1 };

static int
point_is_on_curve(point P)
{
        mq2 x, y;

        x = mq2_mul(P.x, mq2_mul(P.x, P.x));
        x.re = (x.re + 4) % 11;
        y = mq2_mul(P.y, P.y);
        return mq2_eq(x, y);
}

static void
point_print(point P)
{
        if (P.zero) {
                printf("inf");
        } else {
                printf("(");
                mq2_print(P.x);
                printf(",");
                mq2_print(P.y);
                printf(")");
        }
}

static point
point_add(point P, point Q)
{
        mq2 lambda;
        point R;

        if (P.zero) {
                return Q;
        }
        if (Q.zero) {
                return P;
        }
        if (mq2_eq(P.x, Q.x)) {
                if (mq2_eq(P.y, Q.y)) {
                        if (mq2_eq0(P.y)) {
                                return Z;
                        }
                        lambda = mq2_div(
                                mq2_mul_int(mq2_mul(P.x, P.x), 3),
                                mq2_mul_int(P.y, 2));
                } else {
                        return Z;
                }
        } else {
                lambda = mq2_div(mq2_sub(Q.y, P.y), mq2_sub(Q.x, P.x));
        }

        R.x = mq2_sub(mq2_sub(mq2_mul(lambda, lambda), P.x), Q.x);
        R.y = mq2_sub(mq2_mul(lambda, mq2_sub(P.x, R.x)), P.y);
        R.zero = 0;
        return R;
}

static unsigned
point_order(point P)
{
        point Q;
        unsigned order;

        order = 1;
        Q = P;
        while (!Q.zero) {
                Q = point_add(Q, P);
                order ++;
        }
        return order;
}

int
main(void)
{
        int i, j;
        unsigned num;

        num = 1;
        for (i = 0; i < 121; i ++) {
                for (j = 0; j < 121; j ++) {
                        point P, Q;

                        P.x.re = i % 11;
                        P.x.im = i / 11;
                        P.y.re = j % 11;
                        P.y.im = j / 11;
                        P.zero = 0;
                        if (!point_is_on_curve(P)) {
                                continue;
                        }
                        num ++;
                        if (point_order(P) == 3) {
                                point_print(P);
                                Q = P;
                                while (!Q.zero) {
                                        Q = point_add(Q, P);
                                        printf(" -> ");
                                        point_print(Q);
                                }
                                printf("\n");
                        }
                }
        }
        printf("curve order: %u\n", num);
        return 0;
}

This code is gloriously inefficient, with all its integer divisions and use of affine coordinates; it still completes in less than a hundredth of a second on my laptop computer.

When run, it shows the points of order $3$, as expected:

(0,2) -> (0,9) -> inf
(0,9) -> (0,2) -> inf
(8,i) -> (8,10i) -> inf
(8,10i) -> (8,i) -> inf
(2i+7,i) -> (2i+7,10i) -> inf
(2i+7,10i) -> (2i+7,i) -> inf
(9i+7,i) -> (9i+7,10i) -> inf
(9i+7,10i) -> (9i+7,i) -> inf
curve order: 144

Note that this includes the point $(2i+7,10i)$ which is missing on the screenshot in your question (but it is present on page 52 of the PDF).

Notes:

I wrote that code just for that answer; it's not an extract from anything else.
The mq2 structure represents an element of $\mathbb{F}_{q^2}$. The two fields re and im are named by analogy with complex numbers ("real part" and "imaginary part").
The mq2_inv() function computes the inverse of an element. In $\mathbb{F}_{q^2}$, the inverse of $a+ib$ is:
$$ (a+ib)^{-1} = \frac{a-ib}{a^2+b^2} $$
To compute the inverse of $d = (a^2+b^2)$, Fermat's little theorem is used: $d^{-1} = d^{q-2} \bmod q$. Note that the inverse will silently return $0$ if asked to invert $0$ (which is nominally not defined).
A curve point is a pair of coordinates $(x,y)$ in $\mathbb{F}_{q^2}$, or the special "point at infinity" (which is not in the plane). The point structure contains the coordinates $x$ and $y$, and a flag (zero) for the point at infinity. The point addition function must filter out the special cases:

When one of the operands is the point at infinity, then the sum is the other operand (this also handles the case of adding the point at infinity to itself).
When both operands have the same coordinate $x$, then this is either a doubling (operands are equal); or the operands are opposite to each other, and their sum is the point at infinity. There is a special-special case when we double a point whose coordinate $y = 0$, in which case the result is the point at infinity.
In all other cases, this is a normal point addition, which we compute with the group law formulas.

I cannot prove that the book author (Craig Costello) computed the points with a crude program such as this one, but it is certainly a possibility, and it's not that hard. It's a matter of one hour of work at most, and the code does not need to be efficient since there are so few elements to check.

When studying elliptic curves, and especially pairings, it is very useful to write some customary implementation like that one, that allows fiddling with values and check examples.


ENC(M) || SignA(ENC(M))
  Have confidentiality (from ENC), and authenticity from signature, but no integrity because i have the signature of ENC (so someone can use forgery on my signature) and non-reputation i don't think (but i m not sure).

Confidentiality is yes because of ENC, correct.

The other's are all linked to each other. They are present if the receiver only accepts signed messages and the verification is performed with the trusted public key of Alice. If a public key of an adversary is accepted then any random ciphertext can be created and signed.

Non-repudiation is not accomplished because the secret key is not signed together with the message. If the receiver uses a different key you'd get a different message after decryption, even though the signature over the ciphertext verifies. So it is NO for non-repudiation and YES for confidentiality and message integrity / authenticity.

  ENC(M || SignA(M))
  This have all property, because ENC give confidentiality, signature authenticity e non repudation and integrity because i have message and his signature for verify.

But yes, basically right. Note that if the encryption scheme is vulnerable against e.g. plaintext / padding oracle attacks that the confidentiality breaks down. This scheme is what we usually do.

  SignA(ENC(M))
  In this schema i have confidentiality and authenticity , but no integrity. I m not sure about non-repudation.

The message is not send (!), so it is kept very confidential. You cannot even guess it, because the signature is over encrypted data. Integrity / authenticity are then of course nonsense. Non-repudiation is also not possible.

Unless somebody is able to get the original message and encrypt it again anyway. But usually only the given message are allowed (or you'd have issues with DoS and replay attacks and whatnot).

  ENC(M) || SignA(M)
  With this schema i have confidentiality, integrity and authenticity. I have again doubt about non-repudation.

Wrong! You can guess the data and verify the signature. If it verifies, you've found the data. We commonly assume that the public key is known to all.

Once you've decrypted you have M, SignA(M) so there is your non-repudiation - and therefore integrity & authenticity.

Again: if the encryption scheme is vulnerable against e.g. plaintext / padding oracle attacks that the confidentiality breaks down (even more significantly for complex messages).

Beware that generally these kind of questions are debated for "perfect" schemes, where E is perfect cipher and SignA cannot be broken. Furthermore, no other communication or actions are allowed other than the one specified.

I've already mentioned the oracle attacks and what could happen if the message was send afterwards. Those situations can and should be disregarded when answering the questions, even if they are definitely worth considering when implementing such a scheme in practice.

The reason is that you first need to get down the security of perfect schemes and can then on designing or analyzing systems based on the security claims. Then the next thing to do is to consider the practical systems. I'm however already very much rooted in practical application, so my brain starts to automatically insert warnings when looking at the schemes.


AES key length greater than 256 bits - is it dangerous to do an implementation outside of the standard?

There is no obvious extension of AES for larger key sizes. At best, AS3Crypto may be hashing the key to 256-bits for you, but the risk that AS3Crypto is doing something horribly insecure in that case is astronomically larger than any benefit that you could gain by having a larger key size.

$2^{256}$ is so huge that the only way that it could ever be brute-forced is by finding a significant AES weakness that would likely make all AES key sizes vulnerable in any case.

Even though you currently don't have any need to use anything other than AS3Crypto, that might change and it would be nice not to have a non-standard cipher in place.

Lastly, if you really do want to exceed AES-256 security (and you are probably fooling yourself, as I think you know), you would be better off XORing with a completely different cipher like Salsa20. Tahoe-LAFS (which is written by people who know what they are doing, crypto-wise) has taken this approach as they are aiming for 100 year security: https://tahoe-lafs.org/trac/tahoe-lafs/wiki/OneHundredYearCryptography.


J-PAKE : About Schnorr NIZK proof for ephemeral private keys

No. The whole point of doing a zero knowledge proof (in this case, a non-interactive zero knowledge proof) is that the verifier does not learn any additional information besides the statement that is intended to be proved.

The Schnorr protocol allows to prove knowledge of the discrete logarithm without revealing the exponent. On top of that, the Fiat-Shamir heuristic can be applied to the protocol to produce a non-interactive version of the proof, still without revealing the exponent.


What are the benefits of lattice based cryptography?

Post-quantum security:  As you note, quantum attacks are not known to break lattice-based cryptosystems.  But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer.
Security from worst case assumptions:  In security proofs for cryptosystems we typically assume that some problem is hard on average or more precisely hard to solve for random instances drawn from some particular distribution.  For example, we may assume that factoring a product of two random primes cannot be done by a poly-time algorithm.  While this is usually safe, it is in principle possible that someone will find an efficient factoring algorithm that works often on random instances but not on all instances.  Lattice-based cryptography does not suffer from this drawback:  Those schemes are proven secure assuming that lattice problems are hard in the worst case, meaning they are secure as long as no one can find, say, a poly-time algorithm for approximating shortest vectors in every lattice, not just random ones.  This is a huge theoretical advance, but determining exactly what it will mean in practice is difficult for me to say.
Efficiency improvements:  I'll be a little sheepish on this point, but it's often noted that lattice-based schemes have a parallelizable structure that may make them faster in certain contexts.  This is because the algorithms involved are usually simple matrix multiplication with relatively small modular arithmetic (i.e., not cryptographic-sized numbers).  However, my understanding is that implementations of lattice-based schemes would have larger keys, and I'm also not aware of any studies that definitively compare lattice based schemes to traditional schemes.
New primitives:  We only know how to build fully homomorphic encryption from lattices or from very similar techniques.  There is a ton of potential here, and we have no idea how to build such things from factoring or other traditional assumptions.


How to generate tokens from a secret key?

Digital Signatures are the solution.

A very simple algorithm is

Just like RSA, generate a public key $(N, e)$ for everyone, and a private key $d$.
Whatever message $m$ you post, also post a digital signature $\sigma = m^d ~(mod ~ N)$
People can verify the post is by you by checking that $\sigma^e = m ~ (mod ~ N)$

For more rigorous schemes, see Digital Signature and Digital Signature Algorithm


Is there a way of increasing the time to brute force a cipher, but by increasing the ciphertext size instead of the key size?

Is there a way to greatly increase the time a brute force attack would require to decrypt the message without increasing the key size?

Something tells me you haven't understood what "brute force attack" means. In short, it boils down to: "try every possible key until you guess the correct one".

As a logic consequence, enlarging plaintext or ciphertext does not add anything to the security of a cipher when it comes to brute force attacks. Your cipher would still rely on the security of that

  …small key size (say 40-bits)…

which is definitely too short to make brute-force attacks unfeasible.

Now, instead of thinking about increasing plaintext and/or ciphertext message sizes (which might even introduce additional attack vectors which could void the need for a brute force attack), we usually fall back on KDFs (key derivation functions) to get a stronger key.

Differently worded: instead of trying to make the "message" stronger (which doesn't really make sense), we make the "secret" stronger as that actually adds to security… thanks to the algorithm design of KDFs (with tweakable parameters et al).

Think of it this way — a burglar (read: attacker) doesn't care how big or small your house (read: message) is. All that counts is the strength of the lock (read: cryptographic algorithm) and the strength of the key. A good lock and key can keep a small toolshed in your backyard safe, while a bad lock with an easy to reproduce key can make a military bunker as accessible as a public park bench.

To wrap it up, the security of a cipher mainly* comes from:

the individual cryptographic algorithm used, and
the key, which should be strong/large enough to make it unfeasible to simply "walk all keys until you stumble upon the correct one" (which is what we call a "brute force attack")

When not enough key material is available, KDFs come handy. And in case the cryptographic algorithm doesn't support an accordingly strong key size, you should switch the algorithm for a stronger one. There are ample, well-vetted algos availabe.

* Nota bene: Surely there are some additional nit-bits like initialisation vectors etc that also add to the security of modern ciphers, but I've bluntly skipped all that to keep this answer short and simple.


Besides the ones mentioned in the already existing Q&A "Examples of modern, widely used ciphers that suddenly fell?", the following major code breaks have been notable in history:

The break of the German Enigma based codes in the second world war by the team led by Alan Turing;
Project Magic / Purple;
Crypto AG's Hagelin C(X)-52, which can be regarded as a break from an operational standpoint;
The Zimmermann Telegram;
Break of Lorenz cipher;
Halske T52;
Project Venona;
Break of JN-25.


Is my understanding of CPA indistinguishability experiment correct?

There are a surprisingly large number of subtly different definitions of CPA indistinguishability.  What you describe in points 1 through 5 is one that I have heard of, though at the end of your post you make it 'iterative', in the sense that $\mathcal{A}$ can play the game over and over with $\mathcal{E}$ using the same secret key but fresh, independently-random values for $b$ for each game.  I have not heard of the IND game being set up iteratively like that -- usually $\mathcal{A}$ only gets one bite at the apple in terms of guessing $b$. Are you sure you meant to define it that way?

You also don't really define what it means for $\mathcal{A}$ to "continue to have access to the oracle" in point 4.  Do you mean $\mathcal{A}$ can make more chosen plaintext queries before it has to guess $b$?  If so, do they have to be of the form $(m_0, m_1)$ where only the encryption of $m_b$ is returned to it, or can they be individual messages?

Granting $\mathcal{A}$ up to $q_e$ queries of the form $(m_0, m_1)$ (i.e. so that every query is a 'challenge') before it has to make its guess for the value of $b$ is the more common Left Or Right (LOR) notion of IND-CPA.  BDJR'97 defines LOR IND-CPA (as well as several other notions of CPA security):
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.4734


Is it possible to perfom quadratic residues attack on elgamal cryptosystem?

First, some background on Quadratic Residues:

A Quadratic Residue (QR) is a number $x$ such that there exists some number $y$ with $x \equiv y^2 \pmod p$ (where $p$ is the modulus we're talking about - I'll make it implicit here on out), and it doesn't matter what $y$ is, only that whether such a $y$ exists.
There exists an efficient test where we can determine whether any value $x$ is a QR or not.
The value $x \times y$ is q QR if either both $x, y$ are QRs, or neither is.  If one is a QR and the other is not, then $x \times y$ will not be.
The value $x^n$ is QR if either $x$ is a QR or $n$ is even (or both) - if $x$ is not a QR and $n$ is odd, then $x^n$ will not be a QR either.

With that in mind, the El Gamal encryption of a message $m$ is the pair:

$$(g^r, h^r \times m)$$

where $g$ is publicly known generator, $h$ is the public key (which we assume that the attacker knows, and which will be $g$ raised to some unknown power), and $r$ is a random number selected by the encryptor (and hence unknown).

What we do is determine whether $h^r$ is a QR or not (which might sound a bit tricky, as we don't know the value of $h^r$, and so we can't use our efficient test).  However, we can deduce it based on the following cases:

If $h$ is a QR, then $h^r$ will be as well.
If $h$ is not a QR, that implies $g$ is not a QR either (because $h$ is $g$ raised to some power).  In this case, we check if $g^r$ is a QR or not - if it is, then $r$ is even (and so $h^r$ is a QR).  If $g^r$ is not a QR, then $r$ is odd (and so $h^r$ is not a QR).

Once we have determined that, we then check if $h^r \times m$ is a QR.  If the QR-ness of $h^r$ and $h^r \times m$ are the same (that is, both are a QR, or neither is), then $m$ must be a QR.  If they differ, $m$ must not be a QR.

Hence, in all cases, we can determine whether $m$ is a QR or not, by examining the ciphertext and the public key.