Fake non-membership proof in RSA accumulator As explained in this answer, if one knows the trapdoor (factorization of modulus $N$) in an RSA accumulator, one can generate fake membership proofs. Does the same apply to non-membership proofs? More specifically:
Given $A$ is the value of an RSA accumulator and $x$ is a value present in $A$, if I know $p$ and $q$, where $N = p \cdot q$, could I generate a non-membership proof saying that $x$ is not in $A$?

Yes. More generally, suppose you know the size of the group $\mathbb{G}$ you are working in (RSA, class group etc).
Let $A = g^n$ where $n$ is the product of the elements in the committed set. Assuming $n$ is co-prime to $|\mathbb{G}|$, you can compute integers $a_1$, $a_2$ such that $$a_1 x + a_2 n \equiv 1 \pmod{|\mathbb{G}|}\;\;,\;\; |a_2| < |x|.$$ Setting $w:= g^{a_1}$ yields $w^{x}A^{a_2} = g$ and hence, the pair $(w, a_2) \in \mathbb{G} \times \mathbb{Z}$ works as a fake non-membership proof.
This is a fake non-membership proof for a single element. But with a little more work, you can also create a fake constant-sized proof for an arbitrarily large subset as in the BBF19 paper (https://eprint.iacr.org/2018/1188). The PoKE protocol in the paper (which is necessary for non-membership proofs) depends on the strong-RSA and adaptive root assumptions, both of which assume the group order is unknown.


Is there a method to combine encryption and ring signing? There's the well-known question on whether to sign or encrypt first. However, if instead a message is to be ring-signed such that either recipient could be the actual signer, is there any scheme that combines signing and encrypting in one "atomic" step?

Yes, like there are conventional signcryption schemes combining digital signatures with encryption into a single primitive, there are also ring signcryption schemes that realize the same for ring signatures and encryption. Look for instance here or just ask Google scholar.


Why does TWINKLE use light instead of current? TWINKLE is a device devised by Adi Shamir to optimize the sieving step of GNFS. It consists of a cylinder, at the bottom of which are LEDs corresponding to factor base primes which blink with frequency 1/p. If more than a certain number of the LEDs blink at the same clock tick, you've found a GNFS relation (smooth integer pair). This is measured by a brightness sensor at the top of the cylinder: if the light level is above some threshold, the necessary number of LEDs must be lit.

My question is: why use LEDs instead of just measuring current? You could replace the LEDs with transistors that alternate current instead of blinking, and if the current sums to a certain level you have a hit. Why wouldn't this worK?

TWINKLE  uses LEDs as their output is easy to sum.  Simply put, the overall light level measured by a photo detector in the top of the tube is the (rough - important) sum of the individual LED emissions. I say important as the overall sum does not have to be accurate. It only has to exceed a threshold level when TWINKLE notifies the controlling PC of the current integer. This ambiguity mitigates   the practical issues of light travel distances /times, variations in individual LED emission levels and geometric imperfections of the photo detector's lens.

It's really quite clever.  This guy's going to do well for himself.  You can add up the output of the device's 100,000 processing cells with a single detector that has clear sight of all of the emitters. The innovation here is that each cell can operate totally independently and an overall 100,000 input   adder is not required.  It also allows the outputs in the form of light to be send at 10GHz, whereas that's getting ridiculously fast for circa 1999 technology distributed across a 6" wafer.

Your suggestion of adding the currents /measuring the total resistance  would require something like this arrangement:-

A long chain of 100,000 resistors would have to run between all of the computation cells. To make the maths easy for a sanity check, assume that the wafer is actually square with a grid of 316 x 316 cells. That makes the resistor chain approximately 42m long.  The reasons  that this can't possibly work are entirely off topic for this site, so here they are:-

You cannot guarantee that any circuit produced on a wafer is viable. In 1999 manufacturers would have been using a ~200nm lithographic process to make this stuff.  Adi himself suggests a device yield of 80%.  That means it's highly improbable that the resistor chain would be intact without any break or significant thinning. Surprisingly, the yield rate is dropping as technology improves(?) and may be down to 30% today.
It's impossible to measure resistance. You can only detect a voltage or voltage driven current. And any changes in current or voltage have consequences especially if the rate of change is fast.
Contrary to what people think, unfortunately there is no such thing as digital electronics.  There is only fast analogue electronics. The implication of this is that electricity can't even travel at light speed, and can be considerably slower (50%c - 80%c). The resistor chain couldn't be longer than ~5mm for transmission line effects to start clobbering the signal at 10GHz.
The same pesky transmission line effects make it impossible to synchronise all the cells to within 10ps - 20ps that Adi requires. Hence the light sensor on each cell.

It's worth noting that TWINKLE's successor, TWIRL, does not use opto summation techniques.  This may be an indication of the designer's lack of confidence in the benefits of optical /analogue methods for modern computing


Why is the discrete log problem easy when the exponent comes from a binomial distribution? I read in http://epubs.surrey.ac.uk/7219/2/esorics06.pdf that in exponential El Gamal the discrete log problem for recovering $m$ from $g^m$ can be made tractable when $m$ is drawn from a binomial distribution. Why is this?

Here's the deal.  The discrete log problem is feasible in the special case where the exponent is known to come from a small range of possibilities (e.g., the exponent is not too large).
Suppose we are given $y=g^m$, and we want to find $m$.  Suppose moreover we know that $m$ is small: $0 \le m < 2^{30}$, say.  Then it turns out it is easy to recover $m$, without too much computation time.

One very simple approach is to simply try all possible values for $m$: we compute $g^0$, $g^1$, $g^2$, \dots, $g^{2^{30}-1}$ and see which one of them matches $y$.  This will always find $m$, and it takes about $2^{30}$ computations.  It's feasible, but not super-fast: a few hours of computation, maybe.

A smarter approach is to use a square-root algorithm.  It turns out there are ways to solve this problem with about $2^{15}$ computations.  (Here $2^{15} = \sqrt{2^{30}}$, which is why this is known as a square-root method.  If we knew $0 \le m < M$, then these methods would require about $\sqrt{M}$ computations.)  This is eminently feasible, and very fast: perhaps a few minutes of computation.
There are several square-root methods that achieve this running time, including the baby-step giant-step algorithm (sometimes also known as Shanks' method) or Pollard's kangaroo algorithm (sometimes also known as Pollard's lambda method).

For more on efficient discrete log algorithms when the exponent is known to be chosen from a small range of possibilities, see Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset.
What does this have to do with your question?  Well, suppose we know that the exponent $m$ was drawn from a Binomial$(2^{30},1/2)$ distribution.  Then we know that $0 \le m \le 2^{30}$, so we $m$ comes from a small range of possibilities, and we can recover $m$ using the methods above.  Thus, it's not that there is anything particularly special about the binomial distribution, except that the binomial distribution is known to be bounded, and if this bound is small enough, then that lets us apply the methods above.

This situation often comes up in electronic voting.  Suppose there are $N$ different voters.  Let me sketch an approach for secure electronic voting using homomorphic cryptography.
We're going to have each voter encrypt their vote and published the resulting ciphertext somewhere for all to see.
Each voter's ballot will be encrypted as follows: for some particular candidate (say, Smith), we encrypt $m_i$ using a suitable public-key encryption scheme, where $m_i=0$ if the $i$th voter did not vote for Smith and $m_i=1$ if the $i$th voter did vote for Smith.  A voter's encrypted ballot is the concatenation of all of these ciphertexts, one per candidate, but for now let's focus on the part for Smith.  Each of the $N$ voters does this and publishes the resulting ciphertexts.
We choose a suitable homomorphic public-key encryption algorithm such that $E(m_1) \times E(m_2) = E(m_1 + m_2)$.  One standard way to achieve this is by encrypting $g^{m_i}$ using El Gamal encryption, so $E(m_i) = (g^{r_i}, h^{r_i} g^{m_i})$, where $r_i$ is random and chosen by voter $i$.  Each voter publishes their encrypted vote; thus, for voter $i$, $E(m_i)$ is published.
Since the encryption scheme is homomorphic, everyone is able to compute an encryption of $m_1+\dots+m_N$, using the relation $E(m_1+\cdots +m_N) = E(m_1) \times \cdots \times E(m_N)$.  Notice that $m_1+\dots+m_N$ is a tally of the total number of voters who have voted for candidate Smith, which is what we want to recover; and we have a public copy of an encryption of this.
Let $m=m_1+\dots+m_N$, so we have $E(m)$ and we want to recover $m$ to complete the tabulation of the votes.  During tabulation, the authorities (who have a copy of the private key, shared in threshold form) will use threshold El Gamal decryption to decrypt $E(m)$, which yields the value $g^m$.  Finally the authorities need to recover $m$.  Fortunately, they can do this by taking the discrete log of $g^m$.  This is feasible since we know that $m$ is in the range $0 \le m \le N$, and the number $N$ of voters can't be too large (e.g., we won't have more than a billion voters), so the above methods can be applied to compute this discrete log in this particular case.  I hope that makes sense.


Are all possible EC private keys valid? I usually generate a key pair using OpenSSL or Bouncy Castle.

I'm using curve secp256k1.

The 256bit private keys look fairly random.

Do all values of "private key" have a corresponding public key?

If so, can the public key be found for all arbitrary 256bit values, when treated as if they were private keys?

If not, is there a way to tell whether a 256bit value could be a private key?

I'll consider that you are using a 256-bit curve per ANS X9.62:2005.

Not all 256-bit bitstrings are a formally valid private key; when using big-endian conventions, these must represent a positive integer less than $n$, the order of the largest prime order subgroup. Quoting the normative A.4.1 Preliminaries in the standard:

  An elliptic curve key pair for given elliptic curve domain parameters is a pair $(d, Q)$, where $d$ is an integer in $[1, n – 1]$, and Q is a point on the curve such that $Q = d\,G$.

For the Koblitz curve secp256k1 of SEC 2,
$n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf}_{16}$.
For P-256 (also known as secp256r1),
$n=2^{256}-2^{224}+2^{192}-\mathtt{4319055258e8617b0c46353d039cdaaf}_{16}$.

The all-zero bitstring, and the bitstrings representing $n$ or more in big-endian convention, have no corresponding public key per the standard. They are in a proportion about $2^{-128}$ for secp256k1, $2^{-32}$ for P-256.

Note: we could reduce modulo $n$ bitstrings representing more then $n$, but that would be non-standard, and would still leave two bitstrings (corresponding to $0$ and $n$) without a public key.

Note: This answer disregards the ASN.1 representation of a private key.


Given a message and signature, find a public key that makes the signature valid Given a message $M$ and a signature $S$, is it feasible to find a RSA public key $(n,e)$ such that $S$ verifies as a valid signature on $M$ (using this public key)?

What if we're given one public key $(n,e)$ where the signature verifies (presumably, the public key of the original signer), and we want to find a second public key $(n',e')$ that also makes $S$ verify as a valid signature on $M$?  Is there an efficient algorithm to construct such a public key, and if so, how would you do it?  (We'll probably want $n'$ to be the same length, in bytes, as $n$.  Assume the RSA signature algorithm is using proper padding, e.g., PKCS #1.)

Actually, it does appear to be feasible to construct such a public key, with the caveats that:

the public exponent $e$ will be large.  While this is legal, most public keys have a small $e$
the modulus may be more vulnerable than usual to a specific (normally nonoptimal) factorization method.  However, how vulnerable it is can be controlled.

(Note: I'll use $N$ to designate the modulus; I want to use $n$ to mean 'the number of bits within the modulus).

Now, the problem can be summarized as: given values $S$ and $M$ (and $n$, which is the size of the representation of $S$), find a value $N$ and a value $e$ such that $Pad(M) = S^e \bmod N$ and $S < N < 2^n$

The reason for the upper bound on $N$ is how RSA signature verification works; they expect $S$ to be a bytevector the same length as the modulus; if we introduce a modulus which is larger than the signature, the verification process will fail, even if the math would happen to work out.

One obvious way to do this is to find a two primes $p, q$ and odd exponents $e_p, e_q$ such that:

$Pad(M) \equiv S^{e_p} \bmod p$
$Pad(M) \equiv S^{e_q} \bmod q$
$S < pq < 2^n$
There exists a value $e$ such that $e \equiv e_p \mod p - 1$ and $e \equiv e_q \mod q-1$

The last is a nontrivial condition, because $p-1, q-1$ are not relatively prime.  And, this generalizes in an obvious way to more than two primes; it turns out that two primes works for us.

Now, if we pick our primes $p, q$ first, we're stuck with solving discrete log problems to find $e_p, e_q$.  You might assume this is difficult; however, it turns out that discrete logs modulo a large prime can be easy, if the prime is properly chosen; in this case, we get to pick the primes.

If $p-1$ has $k$ prime factors, the largest of which is $r$, then a discrete log problem modulo $p$ can be solved in $O(k \sqrt{r})$ time.

We take advantage of this by doing the following:

Select a set of moderate sized prime values $p_1, p_2, ..., p_i$ and compute $p = 2 \prod p_i + 1$, and make sure that $p$ is prime
Also make sure that $Pad(M)$ and $S$ are either both quadratic residues, or both quadratic nonresidues modulo $p$; if they differ, then either $e_p$ will not exist, or it will be even, neither of which works for us.
Use the $O(k\sqrt{r})$ algorithm to find $e_p$
If $e_p$ happens to be even (which can happen if both $Pad(M)$ and $S$ are quadratic residues), then add $\prod p_i$ to it; this will make it odd, and also preserve the relation $Pad(M) \equiv S^{e_p} \bmod p$

We then do the same procedure to find $q, e_q$, noting that we need to look for values $q$ of the right size (to make $pq$ be within the range $S < pq < 2^N$), and that there are no common primes in the sets $p_i$ and $q_i$; this will likely prevent $e$ from existing.

If we follow these steps, then $e$ will exist, and we've solved the problem.

The only thing left to note is the size of the subprimes $p_i, q_i$.  That turns out to be a bit of a balancing act; if these subprimes are $m$ bits long, then the above procedure takes around $O(2^{m/2})$ time; however, it turns out that the Pollard's p-1 method can factor modulii of this form in $O(2^m)$ time. If we are concerned about someone applying this specific factorization method, then we need to select $m$ carefully.  If we select $m=80$ (that is, our subprimes are 80 bits), then we'll be taking around $2^{40}$ computations, which is probably on the hairy edge of "feasible", while Pollard's method would take around $2^{80}$ time (and it appears unlikely to me that anyone would invest that kind of time).


What does the term “nontrivial rotation” mean? The paper “Gimli: a cross-platform permutation” contains the following information:

  Occasionally (after rounds 24, 20, 16, etc.) Gimli adds an asymmetric constant to entry 0 of the first row. This constant has many bits set (it is essentially the golden ratio 0x9e3779b9, as used in TEA), and is not close to any of its nontrivial rotations (never fewer than 12 bits different)

What does the term “nontrivial rotation” mean? How to distinguish a “nontrivial” rotation from a “trivial” one?

A trivial rotation is one where the input to the rotation is equal to the output (hence the rotation is equal to the identity function). Rotating by a multiple of $n$ is a trivial rotation for all $n$ bit values. Note that for certain values other trivial rotations may exist. See below for the values of the (right) rotations of 0x9e3779b9 ($n = 32$) and the amount of different bits for each:

0:  0x9e3779b9 (0  bits different)
1:  0xcf1bbcdc (14 bits different)
2:  0x678dde6e (22 bits different)
3:  0x33c6ef37 (18 bits different)
4:  0x99e3779b (12 bits different)
5:  0xccf1bbcd (14 bits different)
6:  0xe678dde6 (18 bits different)
7:  0x733c6ef3 (16 bits different)
8:  0xb99e3779 (14 bits different)
9:  0xdccf1bbc (12 bits different)
10: 0x6e678dde (16 bits different)
11: 0x3733c6ef (16 bits different)
12: 0x9b99e377 (16 bits different)
13: 0xcdccf1bb (14 bits different)
14: 0xe6e678dd (12 bits different)
15: 0xf3733c6e (16 bits different)
16: 0x79b99e37 (20 bits different)
17: 0xbcdccf1b (16 bits different)
18: 0xde6e678d (12 bits different)
19: 0xef3733c6 (14 bits different)
20: 0x779b99e3 (16 bits different)
21: 0xbbcdccf1 (16 bits different)
22: 0xdde6e678 (16 bits different)
23: 0x6ef3733c (12 bits different)
24: 0x3779b99e (14 bits different)
25: 0x1bbcdccf (16 bits different)
26: 0x8dde6e67 (18 bits different)
27: 0xc6ef3733 (14 bits different)
28: 0xe3779b99 (12 bits different)
29: 0xf1bbcdcc (18 bits different)
30: 0x78dde6e6 (22 bits different)
31: 0x3c6ef373 (14 bits different)


Using keys as Additional Authentication Data in GCM In my opinion, it's not a good idea to use (symmetric/asymmetric) keys as Additional Authentication Data (AAD) in GCM as AAD is only authenticated but not encrypted. The key will be protected from modification but will not be confidential anymore. Is my understanding correct? (But maybe using a public key as AAD would be okay?)
Another side question is that, could the output of GCM, authentication tags, be referred to as digest?

Yes, we don't send the keys directly. One must keep the keys secret, all the time!
Instead, we send the key with a public key cryptosystem like RSA-KEM or better apply key agreement like Diffie-Hellman Key Exchange (DHKE) and better use Elliptic Curve version (ECDH). If you looking at some existing libraries look at libsodium or the age libraries for existing good implementations.
AAD is not mean to be secret, rather open and can be a part of the protocol like the record number, etc. It is additional information incorporated into the authentication tag calculation. Thus any change in AAD will be detected.
Digest commonly referred to as keyless hash, the GHASH, on the other hand, uses a 128-bit key to derive the authentication tag. If you insist, you can use it as a keyed hash function, too. But rather prefer HMAC instead of GHASH.


How secure is the knapsack? Can the knapsack be used in cryptography in a secure sense (described below)?

Knapsack problem: Given some number $X$ and a set $W$ of weights $w_1, w_2, ... w_n$, find a subset $S$ of $W$ (if it exists) whose weights sum to $X$.

Even though this problem is NP hard, there exist "pseudo-polynomial-time" algorithms for it and the average case hardness is questionable. So I am not sure how secure the knapsack is in reality.

I want to use the knapsack in a symmetric key sense (like a hash function), and NOT in a public key scheme, so there are no restrictions on  $X$ and $W$. Uniqueness of solution is also not required. The only requirement is that finding any such $S$ should be hard.
So my qustions are:

Is there a strategy for choosing $W$ and $X$ that makes the problem hard?
What are the practical values of $W$ and $X$ that make the problem hard?

EDIT: I don't need the strategy to also give me a solution $S$. The solution is never needed. The use-case requires finding any solution to be hard. The person generating the problem need not know the solution. Additionally, given the problem, it should not be easy for anyone to decide if a solution exists or not.

It may be possible to use the knapsack problem to build a secure cryptosystem, though experience suggests it is tricky and delicate.  There are many known algorithms for attacking the knapsack problem, which may or may not work, depending upon the specific parameters you choose.  Therefore, the security of the scheme will depend on the specific parameter values you use (e.g., the exact strategy you use for choosing all values, and the sizes of each value).

If you choose the weights $w_1,\dots,w_n$ independently and uniformly at random from a large enough space, and if $n$ is large enough, and if $S$ is chosen at random, then I suspect this should be secure (it'll probably be computationally infeasible to find $S$).  But I couldn't tell you exactly what parameter choices you'd need to make.  You'd need to read up on all known attacks on knapsack problems, including LLL-based algorithms and generalized birthday-based methods.  At minimum, I expect you need the weights to be (say) at least 256 bits long and $n \ge 160$, but I don't know if that is sufficient for security.

Are you using this only for one-wayness?  Can you use a standard one-way function (e.g., SHA256) instead, in lieu of the knapsack problem?  Or are you taking advantage of the special structure of the knapsack problem?


Trying multiple private keys against a pcap I have 1000's of Private Key files "f0167f3d025582d6bb65d5ca501a50eb.key" etc to use against a PCAP file.

Only one of those private keys are valid and I am wondering what would be the easiest way to test against them and pull out the valid one?

Example of the key -

-----BEGIN PRIVATE KEY-----
MIIEvQIBADANBgkqhkiG9w0BAQEFAASCBKcwggSjAgEAAoIBAQDjQfT7Awy8J44B
h1lddhMT8lN68Gg8xHyssIV2O9eO2g96RuBuhxOtbaNm2LvJe512vrrX1sL8LqJV
KZdAmR2SzVgnMc7oNcs+ZHOPIAZFrCL/m1RnnohA+1RFKm3LSH4eP8rvt6vZa2dZ
A8y8QZl9psnW5T84KWrWPSnuZDirBUehfWtRBdBJLlJkmUSu1+hr3BDq0pT1MnXO
8ZOX+FIb7yYCWWWGr4PH3IIokPm5sODbHB69RCMMLzpHXxR7dgnZycrz0SC+fMb1
moG/94XCDk3naQt48warHARno2rQ85ebIJDVEuIzmRmVqzt60gu7OFMxmr1f9n78
PEquGYmNAgMBAAECggEADuy1+gYpP/IZEWCiLdEjT5wKf3hqYBNHXM/689jaPzdy
7MTa2Gdmk20v3gE90+2aWcIM4z/nbkhhwNYKaOOlXY6+y1QqEnX18xMFw9CGmOzF
H6RD1spCiIH49tHihAcuwS3PVg7p6k1zbBUjzPlB606Y0tQbYsTVj1xU9KMAVbrT
VbIOijg30rwJiSyGPxntOj/bNoiOpyLEf6NEJ6xzUF+cHe2a2BJxvyZE8Jn25flu
qzRvjCz8r54dNCbj3wnO3+hvFyE62d4LEEYrgRIMZsI5gLX1eunS0LPaLtpjHgk0
FouzYHDdw2PhMRWicmUm4qYq0BGzNJGokraM8BViAQKBgQD6JzM8vYzuzRwrX48D
rtpWrEVl+6kVaIoalU18HihYPEpFCuWeG26+B1yhHzVTGIvUIwjy+uzVCh7laRvF
-----END PRIVATE KEY-----

The key is longer but i removed some

META: this is really tool use not crypto and probably should be on superuser.

Open the PCAP file in Wireshark. Find the/a desired handshake; expand the handshake message containing the (server) Certificate message, the Certificates element, the first (EE) Certificate and the signedCertificate; click subjectPublicKeyInfo and rightclick,ExportSelected to a file, for example pubkeyfile.

Write a shell script (or CMD or PS or whatever) to run openssl pkey -in privkeyfile -pubout -outform der and compare the result to pubkeyfile; in Bourne-type shell this could be:

 for p in privkey*; do
     if openssl pkey -in $p -pubout -outform der | cmp -s - pubkeyfile
     then echo FOUND $p; fi; done


What is this problem called and is it hard? given $g^x$ output ($g^y, xy$) Assume that $G$ is any cyclic group where the discrete log problem is hard, such as the elliptic curve group. Let $g$ be some generator of $G$.
The problem is as follows:
Given $(g, g^x)$ for unknown $x$, output any pair of the form $(g^y, xy)$ for $y \neq 0$.
This seems awfully close to the discrete log problem but I could not find any reference for it, nor prove the equivalence myself.
Some things are clear: That algorithm cannot know $y$, since it cannot know $x$ (because the discrete log problem is hard). Also, the algorithm cannot use the same $y$ for different $x$, since that would also reveal $y$, and thereby, $x$.
For this case, we may assume that the Decision Diffie-Hellman problem in $G$ is hard.
However, a hardness proof for non-DDH-hard groups will be nicer.

This problem is equivalent to the CDH problem:
Here is how to solve CDH given an Oracle that solves this problem:

Given $g, g^x$, we can compute $g^{x^{-1}}$ (which is equivalent to the CDH problem) by doing the following:

Call the Oracle with $g, g^x$; the Oracle gives us a pair $g^{y}, xy$

We compute $(g^{y})^{(xy)^{-1}} = g^{x^{-1}}$, hence showing one side of the equivalence

And, repeating my comment, here is how to solve this problem given a CDH Oracle:

Given $g, g^x$, we select an arbitrary value $z = xy$, and compute $(g^x)^{z^{-1}} = g^{y^{-1}}$.

We then invoke the CDH Oracle with $g, g^{y^{-1}}$ to recover the value $g^y$

We then return the values $g^y, z$, which shows the other side of the equivalence.


In the Quadratic Sieve, why restrict the factor base? In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having Legendre symbol $\left({N\over p_j}\right)=+1$.

Why this restriction of the factor base to primes $p_j$ such that $N$ is a quadratic residue modulo $p_j$? I wonder, because:

Wikipedia's introductory description of the Quadratic Sieve does not use such restriction, and works; the restriction is introduced in an example, without justification (in the article as it stands now).
Such restriction considerably lowers the density of integers having all factors in the factor base, arguably making it harder to find $x$ such that  $x^2\bmod N$ has all factors in the factor base (or more generally to find $(x,k)$ with $x^2-k\cdot N$ smooth).
A find including a factor not matching the restriction can help a successful factorization; borrowing the example in Introduction to Mathematical Cryptography section 3.6, trying to factor $N=9788111$ (by sieving $x^2\bmod N$ for $x$ starting at $\lceil\sqrt N\rceil$, by the same algorithm as in Wikipedia), it is found 20 smooths values of $x^2\bmod N$ for $x>\sqrt N$ among which it is selected (by Gaussian elimination)
$$\begin{align}
3129^2\bmod N&=2\cdot5\cdot11\cdot23\\
3313^2\bmod N&=2\cdot7^2\cdot17\cdot23\cdot31\\
3449^2\bmod N&=2\cdot5\cdot7^2\cdot11\cdot17\cdot23\\
4426^2\bmod N&=2\cdot3\cdot47^2\\
4651^2\bmod N&=3\cdot23\cdot31^3
\end{align}$$
where the last two relations would have been eliminated by the restriction of the factor base, since $\left({N\over 3}\right)=-1$; however, by taking the product of these relations, it is found that
$$(3129\cdot3313\cdot3449\cdot4426\cdot4651)^2-(2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47)^2$$
is a multiple of $N$, from it is found $2741$, a nontrivial factor of $N$, by computing
$$\gcd(N,3129\cdot3313\cdot3449\cdot4426\cdot4651-2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47)$$

Note: For the purpose of the question, please disregard the improvements of including $-1$ in the factor base; or/and allowing use of one or a few primes larger than the bound $B$; or/and (unless relevant) electing to factor $m\cdot N$ for a small multiplier $m$.

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


Cryptographic system with double keys with reversible order While reading Shamir, Rivest and Adleman's paper on "Mental Poker", I've met a mention of system such that $E_a(E_b(x)) = E_b(E_a(x))$, without however disclosing details on it, with $E_a(x)$ being “encrypt plaintext $x$ with key $a$”.

Do any existing secure modern cryptosystems have this property, and how is it called for later reference?

First, remark that the desired commutativity is incompatible with security under Chosen Plaintext Attack, which (under the name IND-CPA) is considered a requirement for modern encryption systems. Proof, expanded following tylo's comment, using the IND-CPA game as played for symmetric encryption (see the CPA indistinguishability experiment in section 3.5 of Katz and Lindell's Introduction to modern cryptography, also here on page 4):

We assume a cipher $E$:

commutative as in the question, that is: $\forall a,\forall b,\forall x, E_a(E_b(x))=E_b(E_a(x))$;
injective: $\forall a,\forall x,\forall y, E_a(x)=E_a(y)\implies x=y$ (a necessity for reliable decryption);
$E$ can be deterministic or probabilistic; in the later case $E$ has some randomness source as a hidden input beyond key (the subscript) and data (the explicit parameter), and the above properties hold for all values of the random inputs in each instance of $E$;
the cipher has a public definition (except for its randomness soure if any) allowing its practical implementation by the adversary (an algorithm with time and space complexity polynomial in the size of the parameters);

the game starts with the referee choosing and announcing the size of parameters;
the referee secretly chooses a random key $k$;
the adversary chooses a random key $r$, a random plaintext $X$, and computes $M_0=E_r(X)$ using the cipher's definition, until $M_0\ne X$ (which holds with high odds for any secure cipher);
in a training phase, the adversary submits $X$ for encryption and obtains $Y=E_k(X)$;
in the challenge phase

the adversary submits $M_0$, and any $M_1$ that is neither $M_0$ nor $X$ (submitting $M_1=M_0$ would be poor strategy; submitting $M_0$ or $M_1$ that was submitted in the training phase would be against the rules of the game played for deterministic encryption);
the referee secretly chooses $i$ randomly in $\{0,1\}$ by fair coin toss, and returns $C=E_k(M_b)$;

(here the rule of the game allows the adversary to make other queries for encryption under key $k$, bound to be for messages different from $M_0$ and $M_1$ in the game played for deterministic encryption);
the adversary returns $i'=0$ if $C=E_r(Y)$, which is computable using the cipher's definition, or $i'=1$ otherwise;
the adversary wins if $i'=i$ (and we want the odds of that, which should be better than $1/2$ by some $\epsilon>0$ independent of the size of the parameters);

if the referee picked $i=0$: $C=E_k(M_0)=E_k(E_r(X))$, and applying the commutativity property of the cipher we get $C=E_r(E_k(X))=E_r(Y)$, thus $i'=0$;
if the referee picked $i=1$: since $M_1\ne M_0$, and because the cipher is injective, $C=E_k(M_1)$ must be different from whatever $E_k(M_0)$ would have been, which (as shown above) is bound to match $E_r(Y)$ that was computed by the adversary and used to find $i'$, thus $i'=1$ (note: in the case of a probabilistic algorithm, one could think there potentially could be several $E_k(M_0)$, but the commutativity property makes it necessary that they all match $E_r(Y)$ as computed by the adversary: in order to be commutative, the cipher is bound to be deterministic for inputs $M_0$ and $Y$ given how these have been generated);
thus with certainty, $i'=i$ (this is a perfect distinguisher).

As remarked by figlesquidge, XOR with a One Time Pad has the desired commutativity property, in some sense. That's also true for any Stream Cipher with an out-of-band method for synchronization (including a block cipher such as AES in OFB or CTR mode, with out-of-band IV); by out-of-band I mean: not part of the ciphertext for which the commutativity property is thought.

However the OTP or other out-of-band data is often impractical (in particular it won't work in use cases where several ciphertexts are shuffled but out-of-band data has not, which is the situation in Mental Poker), and do not match the definition of a cipher (which requires reusable key and no out-of-band data).

We study the simplest commutative cipher in the cryptographic folklore, sometime used for Mental Poker:

The Pohlig-Hellman Exponentiation Cipher

For a given public odd prime $p$, let $K$ be the set of $k\in\mathbb N$ with $0<k<p$ that are coprime with $p-1$, and $*$ multiplication modulo $p-1$, so that $(K,*)$ is a commutative group with $k=1$ the neutral element.

The Pohlig-Hellman Exponentiation Cipher over $\mathbb Z_p$ with key in $k$ is
$$\begin{align}
E:K\times\mathbb Z_p&\mapsto \mathbb Z_p\\
(k,x)&\mapsto E(k,x)=x^k\bmod p=E_k(x)
\end{align}$$

Encryption with key $k$ is $E_k: x\mapsto E_k(x)$ and is a permutation of $\mathbb Z_p$. The set of the permutations obtained form a group under function composition (noted $\circ$), isomorphic to $(K,*)$:
$$\forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p,E_b(E_a(x))=(E_b\circ E_a)(x)=E_{b*a}(x)$$
As a consequence, decryption is $D_k=E_\overline k$, with $\overline k=k^{-1}\bmod(p-1)$ the inverse of $k$ in group $(K,*)$; and the desired commutativity property holds:
$$\forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p, E_a(E_b(x))=E_b(E_a(x))$$

For appropriate $p$ (making the Discrete Logarithm Problem hard), the cipher is conjectured secure for multiple random plaintexts related to the same random key [that's stated before (15) in the original article, linked to the title of this section; and justified by an argument I do not get]. However, it has a number of other properties that a random commutative cipher would not obviously have, including the multiplicative property $\pmod p$:

$$\forall k\in K,\forall x\in \mathbb Z_p,\forall y\in \mathbb Z_p, E_k(x\cdot y\bmod p)=E_k(x)\cdot E_k(y)\bmod p$$

There are a number of other undesirable properties:

Three fixed points: $\forall x\in\{0,1,p-1\},\forall k\in K,E_k(x)=x$
A symmetry in the message space: $\forall x\in \mathbb Z_p,\forall k\in K,E_k(p-x\bmod p)=\big(p-E_k(x)\big)\bmod p$
The isomorphism with $(K,*)$ allows some related-key attacks, and implies a weak key ($k=1$).
The keyspace is not an interval of $\mathbb N$, which is inconvenient.

A variant

We can fix these 4 issues. Let $p$ be a large public prime with $(p-1)/2$ prime, such as $p=\lfloor\pi\cdot2^{2046}\rfloor+3,617,739$. Let $P$ be the set of $(p-3)/2$ integers $\{2,3\dots,(p-3)/2,(p-1)/2\}$. For key $k$ of 256 bits and data $x\in P$, define
$$\begin{align}
k_E&=2^{320}\cdot\small\text{SHA-256}(k)+2^{64}\cdot k+1\\
k_D&=\overline{k_E}={k_E}^{-1}\bmod (p-1)\\
\mathbf E_k(x)&=\min\big(x^{k_E}\bmod p,p-(x^{k_E}\bmod p)\big)\\
\mathbf D_k(x)&=\min\big(x^{k_D}\bmod p,p-(x^{k_D}\bmod p)\big)
\end{align}$$
Fixed points and symmetry are removed by the definition of $P$ and the use of $\min$. The construction of the exponent $k_E$ makes it coprime with $p-1$ (since $k_E$ is odd and too small to divide the single odd divisor of $p-1$), ensures that any 256-bit $k$ makes a fine key, and provides fair protection against related-key attacks. The construction of $k_D$ ensures that $\forall k,\forall x,\mathbf D_k(\mathbf E_k(x))=x$.

The desired commutativity property still holds, as well as the multiplicative property (be it wanted or not). We can artificially get rid of the multiplicative property by inserting a pseudo-random permutation $M$ of the set $P$ before encryption, and its reverse afterwards: $x\mapsto (M^{-1}\circ\mathbf E_k\circ M)(x)$ still has the commutativity property, but not the multiplicative property; however an adversary knowing $M$ can still potentially get advantage of the multiplicative property.

Using RSA encryption padding

If $\small\text{OAEP}(x)$ designates the padding used for RSA-OAEP with a modulus of $\lceil\log_2(p)\rceil$ bits, then $x\mapsto E(\small\text{OAEP}(x))$ seems to be IND-CPA-secure, and decipherable (the desired commutativity property is lost: that padding must be external to whatever step of the protocol requires commutativity). As pointed by Ricky Demer, OAEP+ is preferable to OAEP.

Both paddings hide the multiplicative property, by means including making the cipher probabilistic.


Advantages of group signature schemes without encryption over with encryption Many group signature schemes follow sign-encrypt then prove paradigm, where a membership certificate, is encrypted using some public-key encryption scheme. There are some encryption free group signature schemes.

What is the advantage of group signature scheme without encryption over the group signature scheme with encryption?

Usually the schemes without encryption are more efficient in terms of computational and size complexity. This owes to the fact that encrypting a membership certificate and proving the consistency is typically more expensive than simply randomising some signature and proving a simpler statement.

It should be noted, however, that some schemes following the without encryption paradigm are secure in a weaker model than the schemes which use sign-encrypt-proof. For example, in the scheme in this paper, the anonymity guarantees are lost upon leakage of a user key. It was only recently shown that one can actually construct highly efficient schemes following the without encryption paradigm which achieve security in the strongest model for dynamic group signatures.

Also see the introduction of this paper for an in depth discussion of the pros and cons (the term sign-randomize-proof is used there to describe the paradigm used by without encryption schemes, as this captures the essence of the without encryption paradigm more appropriately).


Give a CPA-attack on Elgamal when used with $\mathbb{Z}_p^*$ We know that if the decisional Diffie-Hellmann problem is hard then the Elgamal encryption is CPA-secure. One show that if the chosen group is $\mathbb{Z}_p^*$ then the decisional Diffie-Hellman problem is not hard. For instance, one realizes that $g^{ab}$ is a square with probability $3/4$ with an argument based on the parity of $a,b$. Therefore, it makes self to ask the following question:

  Is there a CPA-attack on Elgamal when used with $\mathbb{Z}_p^*$?

I need some help on the way to go here. Should I try to build a distinguisher using the above fact about the Diffie-Hellman problem? Or does is just come from the algebraic structure of the group?

HINT

You already have a hint given in the problem statement:

  $g^{ab}$ is a square with probability $3/4$ with an argument based on the parity of $a,b$.

You should start by making sure you understand why is this the case. Then, once you do that, think about what it means to break DDH: it means distinguishing things that look like $g^c$ for a random $c$ from things of the form $g^{ab}$ for random $a,b$. Given the hint above, can you find a feature that differs between these two?


SHA-1 – Would using a SHA-1 CSR be a risk? If someone would generate a SHA1 CSR and submit it to an CA to receive a SHA2 certificate, would the process as a whole be at risk because the CSR could be malicious?

Assumption:

In this case, the “data” (as used in Q2) is the public key of the end user certificate.  In practice the CA could still generate a SHA2 certificate, even when a SHA1 CSR is being submitted. However, the CSR itself would be vulnerable in theory. So if an attacker would get in between he could put another name on the certificate. However, a proper RA would validate the CN and discover the forgery.

So basically a collision at the CSR would be possible but the validation process around it would keep it safe. However, submitting a SHA-2 CSR would be safer.

Would this even be a real life attack scenario?

No, it is not. The SHA-1 attack requires pre-computation. It is basically not possible to get a hash collision for data that is not controlled by the attacker. You'd need the attacker and the submitter of the certificate signing request to cooperate to create two different CSR's that have the same hash value within the signature calculation / verification.

Even then, it makes no sense to do this. As you correctly identified the RA would validate the CN. So you would not have achieved anything (if the wrong CN is accepted then the RA code itself is at risk, and this would have nothing to do with the certificate request itself).

It may be good to note that the main reason for signing the CSR is for the CA to validate that the entity filing the request and the entity holding the private key are the same entity.

Regardless, using SHA-2 for CSR's should of course be preferred over using a broken hash such as SHA-1.


How does the security parameter within a digital locker help prove that it unlocked correctly? I refer to Canetti et all, "Reusable Fuzzy Extractors for Low-Entropy Distributions", available here.

Paraphrasing the relevant part from §3:-

  The locking algorithm $lock(key,val)$ outputs the pair $nonce,H(nonce,key) \oplus (val||0^s)$, where H is a cryptographic hash function, nonce is a nonce, ||denotes concatenation, and s is a security parameter.

s creates a certainty of $1−2^{−s}$ that the unlocking was successful.  Surely there must be some  relationship omitted from the paper between s, |(nonce,key)| and  |val| for the XOR operation to be useful.  It has the smell of HMAC about it.

How can what appears to be padding with s zeros help prove that the locker was correctly opened? Is it some strange mathematical way to simply guarantee the bit length of (nonce + key)?

Note.  My confusion is increased by the fact that the nonce output from the lock function does not seem to be an input for the unlock function.

They mention $H(nonce, key)$ is modeled as a random oracle.
Then, $H(nonce, key) \oplus M\cong U\oplus M$ where $U$ is uniformly random, so the encryption scheme (essentially) becomes the one time pad.
This is a fairly standard construction.

One "flaw" with the one-time pad is that everything has a valid decryption.
Given that this is the case, how can you be sure you have the "right" key for some ciphertext?
The solution they mention is looking for the string $0^s$ at the end of your plaintext.
This will:

Always appear if you have the correct key for some ciphertext
Almost never appear if you have the incorrect key for some ciphertext (specifically, it will appear with probability $2^{-s}$, so you'll detect the incorrect key was used with probability $1-2^{-s}$).

This is morally equivalent to something like a checksum, and can probably be formalized using the terminology of error-correcting codes (but I won't attempt to).


Can a QR code be scanned if split using visual cryptography? I'm trying to get a python script to work such a way that it takes a QR code (a jpeg or a png) splits the jpeg into two images as shown here
https://github.com/LessonStudio/VisualCryptography

I'm not sure if the code can be scanned. I know we can get the image back, but what about the information stored ?

Any help would be appreciated.

A typical problem with the images regenerated by visual cryptography is that they have low contrast: when using superposed transparency, the white in the original image tends to become grey (or more precisely, 50% dithering of black and white, which is even worse from a 2D-code scanner's perspective); and there might be some white that creep in the black areas due to misalignment. This will be tolerated by some scanners, but will mess others. Scanning will be more difficult that with the original.

The classical scheme in figure 2 there will I guess not work reliably if each block on the original QR-code is split in two rectangles, as shown in that figure.

What would work better is to subdivide each block of the QR-code into a finer matrix, e.g 8x8: each block of the QR-code is turned to either X= or Y=, where white is actually transparent:

A black block in the QR-code is, with odds 50%, turned to X in the first transparency and Y in the second transparency, or Y in the first and X in the second; so that the superposition of the transparencies will be essentially black.
A white block in the QR-code is, with odds 50%, turned to X in both transparencies, or Y in both transparencies; so that the superposition of the transparencies will be essentially grey (50% dithering of black and transparent).

No information can be extracted from a single transparency.

It might help to encode specially the blocks that convey only structure: Finder Pattern, Separator, Quiet Zone, Timing Pattern (if any), Alignment Pattern (if any). For these I suggest, in order to help determining orientation and putting the transparencies with the same side up:

A black block in the QR-code is represented as black in both transparencies.
A white block in the QR-code is represented as X or Y in both transparencies, according to $(h+\lfloor v/2\rfloor)\bmod 2$ where $h$ and $v$ are the block's coordinate as integers.

The above does not solve determining from which side the transparencies shall be scanned: not all scanners accept mirror images. But it would not be a good idea to solve this by replacing one transparency by a white sheet, as it could tend to worsen alignment problems: different materials react differently to humidity and aging. This side up probably will do (and be the simplest for orientation).

Choice of the appropriate block subdivision is a compromise: too coarse, and the scanner might consider the pixels of the block as the grid of the 2D barcode; too fine, and alignment of transparencies will become infeasible.

If one used polarizing filters with orientation of X and Y different by 90°, there would be no need for subdivision of QR-code blocks into smaller pixels, truer white (assuming a non-polarized light source behind the aligned transparencies), and no dithering for grey, thus easier reading. However, I know no automated way to prepare the transparencies; closest to a workable idea is to start from transparent polarized squares the size of a QR-code block, and glue them in the appropriate orientation on some grid.


Which method to generate one time password? I'm looking for a concrete algorithm to generate one time passwords. The situation is as follows:

Alice and Bob exchanged a passphrase over a secure channel in the beginning. They want to symetrically encrypt data in the future, and every consecutive enryption/decryption process should use a one-time password.

For every single data exchange process it is considered that they remember the initial passphrase, but nothing else. It is possible to exchange additional metadata in cleartext alongside with the payload.

I looked at hash chains, but the problem with that is that they need to ensure that never use the same number of iterations twice and decrease it everytime. As I said above, they can't remember anything but the initial passphrase.

Second thought was to use a key derivation function, for example PBKDF2. The number of iterations could be statically (high enough), and the salt could be exchanged with the payload. But as a cryptography novice, I'm not sure if this is secury enough, because it wasn't made for that purpose, as far as I understand this. Or was it?

Are there alternatives? Or would it be sufficient to use a KDF in my case?

Yes, your best choice is indeed to use a key derivation function.
However you should consider using the TLS-PSK set of cipher suites for your needs. If you use the variant with DHE / ECDHE key exchange (recommended) included you don't have to rely on your passphrase being strong for security, both the password and the discrete logarithm have to be disclosed in order to recover the message.
In both cases (with and without additional key exchange) the TLS nonces will be used to aid master secret derivation, meaning you get unique master secrets even if re-use the static passphrase without additional key-exchange.

As for the cipher suites something like TLS_DHE_PSK_WITH_AES_128_GCM_SHA256 seems like the best choice at the moment or TLS_PSK_WITH_AES_128_GCM_SHA256 if you want to solely rely on your passphrase. As for what to input as PSK, either a hash of the passphrase directly (high entropy case) or a master secret like constructed in the next paragraph(s) is fine (in the low entropy case).

If you're only relying on your passphrase for confidentiality and your passphrase may have low entropy, you should use a password-based key derivation function (PBKDF), for which you can negotiate a key as follows:

$$A\rightarrow B: R_A$$
$$A\leftarrow B: R_B,C_B$$
$$A\rightarrow B: C_A$$

with $R_A,R_B$ being random 128 bit strings and $C_A,C_B$ being key-confirmation values. The 128/256-bit master secret $MS$ is calculated via $MS=PBKDF(PW,R_A||R_B)$ with the second input being the salt. From this you can derive as many keys as you want via HKDF-Expand and you can calculate the $C_A=HMAC_{MS}(R_A||R_B),C_B=HMAC_{MS}(R_B||R_A)$, note that the order matters or replay attacks apply.

As for the algorithmic choices for this and the following approach you should use SHA-256 or SHA-3-256 as your hash functions and Argon2 as your PBKDF.

If you're only relying on your passphrase for confidentiality and your passphrase has high entropy, you should use a key-based key derivation function (KBKDF). More concretely you want to use HKDF with a salt that you exchanged just-in-time via the above protocol with HKDF-Extract replacing the PBKDF.

TL;DR: Use TLS-PSK with strong cipher suites and / or apply a strong PBKDF (like Argon2) using a negotiated salt for key derivation.


Is a PRG concatenation using the same input still a PRG? Suppose we have a secure PRG $G: \{0,1\}^s→ \{0,1\}^n$ and we define a $G'(k)$ as:

$$
G'(k) = G(k) \| G(k)
$$

So if $G(k)=\mathbf{i}$, $G'(k) = \mathbf{i} \| \mathbf{i}$

Is $G'$ still a secure PRG?

Based on my own understanding it should be, because the statistical distinguishers will produce the same analogy of zeros and ones, therefore $G'$ should be a secure PRG too.

Is there any other principle about PRGs that $G'$ does not satisfy?

Refering to THIS post

If we call $U_k$ the random variable uniformly distributed over bit strings of length $k$, then a function $g: \{0,1\}^k \to \{0,1\}^m$ is called pseudo-random generator if no feasible(poly-time if you want) algorithm can distinguish $g(U_k)$ and $U_m$ with non-negligible probability.

More formally let $U'_m = g(U_k)$ then the distinguishing advantage of any distinguisher efficient $D$ that we denote as $\Delta^D(U'_m, U_m) = \Pr^{DU_m}[Z = 1] - \Pr^{DU'_m}[Z = 1]$ is negligible.

Here $Z$ is the output of the distinguisher, and negligible is any suitable notion of "really small"; same for efficient.

Now my ability to distinguish between $U_k$ from your PRNG $g: \{0,1\}^k \to \{0,1\}^m \mathbin\| \{0,1\}^m$ is obviously more than negligible. Because any OUTPUT from your generator has symmetry and if I see this symmetry the generator being used is most probably your generator.


Shamir's Secret Sharing vs. Asmuth-Bloom scheme I need to make use of a secret sharing scheme and I don't really know how to decide which one to use, Shamir's or Asmuth-Bloom (using CRT).

The complexity for recovering the secret seems to be linear in both cases and both schemes are perfectly secure.

Can anyone give arguments why we should opt for one over the other?

There is one theoretical difference between Shamir's scheme and Asmuth and Bloom's scheme.

Shamir can be done in an informationally secure manner; specifically, if the nonconstant polynomial coefficients were chosen in a random manner (that is, from a uniform probability distribution that's uncorrelated to anything else the attacker can see), then someone with a number of shares that's less than the threshold gains no information about the shared secret.  This is because, for any potential value of the shared secret, there is the same number of possible secret coefficients that is consistent with that secret value - if we assume that those coefficients were chosen uniformly, the attacker has no criteria to say that one set of coefficients is any more likely that the other.

In contrast, Asmuth and Bloom's scheme does leak some probabilistitic information.  Now, any particular value of the shared secret is possible; however different values of the shared secret have different numbers of possible secret value $\alpha$.  Assuming that the attacker knows the probability distribution that $\alpha$ was drawn from, he can then assign different probabilities to the values of the shared secret, should he choose to.

As Asmuth and Bloom's scheme does leak some probabilistic information, while Shamir's does not, well, that seems like a good reason to prefer Shamir's (especially since, as Louis says, Shamir's is actually easier from a practical standpoint)


Managing data access through asymmetric cryptography I want to manage authorization, as 3rd-party permissions, through asymmetric cryptography.

I'm concerned about how it is possible to share access of encrypted data with N entities, be able to revoke any of them at anytime, and do this securely.

I've thought about a cryptography function that I'm asking here some help to build.

Let's imagine I have a public data base encrypted with my public key.

I want:

to share some data from my encrypted DB (my email address for example) to 3 different entities (applications)
these 3 applications and only these to be able to read the data
to be able as a user to revoke their access to this data at any time.

I have a private/public key and these applications' owners too have a private/public key on the network.

I use a function to encrypt my email with my public key as:

Encrypt(Email, MyPublicKey)

At this point, only I with my private Key can read the data.

If I give access to a 3rd-party application to it, then I would re-encrypt my email with a new function, using my public key and the application's, so both my private key and the application private key are solution and can decrypt the data:

Encrypt(Email, (MyPublicKey, AppPublicKey))

So, now, only me and the application could read the data with our private key because each  of our private keys would be a solution of this encryption algorithm.

If I add a 2nd application access to this data, I would then re-encrypt the data through a new function:

Encrypt(Email, (MyPublicKey, AppPublicKey, 2ndAppPublicKey))

Now the 2nd application has the same access as me and the first application to this data.

Then if I want to revoke the 1st application's access, I would re-encrypt the data excluding the 1st application private key as solution of the function as:

Encrypt(Email, (MyPublicKey, 2ndAppPublicKey))

So, the 1st application cannot access to the data anymore as its private Key is not solution anymore of the encryption function.

Is it a known cryptographic scheme (like custom shared secret)? Does such mathematical function exist? What it would look like? Maybe there is a simpler solution I didn't see...

This is simple to do by combining symmetric and asymmetric encryption.

For example:

Generate data encryption key $s$.
Encrypt the data $d$ using symmetric algorithm $A$: $A_s(d)$.
Encrypt the symmetric key with the relevant parties public keys: $E_i(s)$.

The key can be per data field, or shared by various fields with equivalent permission requirements. When authorized requests access to the data, they would receive the encrypted symmetric key, be able to decrypt it and thus the data itself.

When you revoke access you have two options:

Only delete the encrypted symmetric key corresponding to that party.
Re-encrypt everything under a new symmetric key.

In the latter case you also prevent someone who has looked at the data earlier (and saved the symmetric key) from being able to decrypt the current version later. However, it can require more computation if the data is large.

As a compromise you could mark the data for re-encryption when next modified, under the assumption that since they had access they could already know the current value and must only be prevented from knowing future values.


Role of AND operation in FHE, MPC and ZK Going through LowMC, one of the main advantage of it seems to be useful in Fully Homomorphic Encryption (FHE), Multi-party Computation (MPC) and Zero Knowledge (ZK) proofs. I have no idea about any of these, but it seems lowering the number of AND gates is a big deal. Similar claim is made for the Kreyvium cipher as well.
Could anyone explain it to me, how having a low number of AND gates help in those 3 cases? Mainly, how come a private key cryptographic algorithm helps in those areas which are not at all related? Also, does it mean the cost for linear operation (Exclusive-OR gates) is zero in FHE/MPC/ZK?

In general, AND gates are no big deal. In practice however, many zero-knowledge systems are based on rank-1-constraint systems (R1CS, often "arithmetic circuits" in folklore), and the concern that LowMC tries to address is linked to this practicality.  Note that I'm talking from the perspective of ZK, although the principles probably carry over to FHE and MPC.
In R1CS, you declare constraints between inputs and outputs, and these constraints are of arithmetic form. For instance, you would write "(input[0] + 1)*secret[0] = output[0]".  In most R1CS systems (read: all that I know of), it is the multiplication gates that weigh heavy in the prove/verify functions, and the additions mostly come for free.
Now, most encryption/decryption functions are defined in terms of bitwise operations, not in terms of + and *.
To prove that you know the decryption of a certain value and its associated key, you would thus need to convert all those bitwise operators into arithmetic operations.  You can imagine these equations become quite large. The main operations in this context are, as you correctly identified, AND, OR and XOR.  Depending on the convention you use, you will encode True as 1 and False as 0, or vice versa.  It is then relatively easy to see that x AND y becomes $x * y$ and x XOR y becomes $x + y - 2 * x * y$, and x OR y becomes $x + y - x * y$.
Now, there are quite some optimizations that you can carry out here. For example, if you would use a stream cipher to show decryption, then you have to XOR your cipher stream $s[..]$ with the cipher text $c[..]$.  The former is a result of your circuit, but often the latter is a public value.  If this is the case, you can make that specific XOR more efficient by doing something like
let xor = if c[i] == 0 {
    s[i]
} else {
    1 - s[i]
};

which requires no multiplications for this specific XOR.
A related optimization exists for OR: if you take the convention False as 0, True as anything else, then x OR y just becomes $x + y$, as long as your field is large enough.
TL;DR: AND becomes multiplication, multiplication costs processing time.  XOR can sometimes be optimized out a bit.  By the way, if you're interested in low-multiplier-count symmetric crypto, have a look at Poseidon too!


ECIES: key derivation function and symmetric encryption scheme I am using an elliptic curve library which provided me with a shared secret using my secret key and a foreign public key. Unfortunately an ECIES is not available in the programming language.

I would like to implement an ECIES as follows.

Use the shared secret as a seed for a random number generator
Create an xor key with the random number generator
Compute $cipher = message \oplus key$
Transmit $cipher$ and a signature of $cipher$ using my private key

Is this approach correct and safe?

What you are describing is a stream cipher created from a generic PRNG. However, an actual stream cipher should be used instead. PRNG's are dangerous in the sense that they are sometimes pre-seeded or re-seeded by the system. If there is no mandated algorithm then the underlying implementation may change as well. Otherwise: yes, a stream cipher can of course be used to obtain confidentiality of the messages if used correctly.

AES in CTR (counter) mode is a pretty safe bet.

You seem to be using encrypt-then-sign. Usually sign-then-encrypt is used. The issue with encrypt-then-sign is that somebody can re-sign the ciphertext and claim ownership of it. The other aspect is that after decryption the signature is lost.

Therefore, usually sign-then-encrypt is used for asymmetric primitives such as ECIES and ECDSA. This may not be a problem in your specific protocol however; you could just want to allow only signatures from one specific private / public key and you could be fine with protecting the ciphertext in transit.

Once you have established a key and authenticated the exchange then you could also use AES-GCM or another authenticated cipher to send messages providing integrity, authenticity and of course confidentiality of the messages.

Note that there is a lot to do if you want to create a transport protocol. In place encryption is a bit easier wrt to possible attack vectors. If the system is secure in the end depends if the possible threats to the system are thwarted.

We can therefore not tell you if your approach is safe; we can tell if it is unsafe though :)


Bitwise operations in FHE Im reading about FHE and the libraries implementing it (SEAL, HELib).
I saw that SEAL doesn't support bitwise operations but I wondered if its theoretically feasible.
For example, bitwise-ing XOR an encrypted value with itself, gets us an encrypted 0. Bitwise it with the not of itself to get an encrypted 1. Using shifts with the computed two I would then be able to extract the encrypted number.
Shift right/left can be made using multiplication or division by (powers of) 2.
But XOR-ing is the main problem.
Is it theoretically possible under any FHE/HE scheme? What are the limitations?
Thanks

The answer to the GitHub issue specifically mentions what you're looking for

The reason why SEAL does not support bit operations is that bit operations require a non-power-of-two polynomial ring degree which leads to much less efficient polynomial arithmetic and hurts the performance of either homomorphic evaluation or encryption or both.

This states that with a non-power of 2 ring degree they could implement bitwise arithmetic, but it would hurt the performance of the algorithm.

We are evaluating the necessity and feasibility of adding support for bit operations. Perhaps we will adopt a different HE scheme for that rather than using BFV (definitely not CKKS).

This second quote states that, to avoid the efficiency issue, they would use a different homomorphic encryption scheme.
It seems to me you have your answer right there: they're confirming it's possible, and that they know how to do it. They're also confirming it wouldn't require changing the homomorphic encryption scheme. But since it would affect performance they're choosing not to.


Recommended way of adding a pepper/secret key to password before hashing? There have been several questions regarding password hashing here and on Security.SE.

A "pepper" is sometimes mentioned – an application-specific secret key. The canonical answer on password hashing implies that a adding pepper brings the composition close to a MAC, and that cryptographic MAC function should be used rather than concatenating a pepper together with the salt and password.

My question is: Where applicable, what would be a generally recommendable, sound, well understood way to MAC a user password and a secret key, in the context of password hashing?

I want to MAC the password using a secret key, then feed the output of the MAC to a slow hash function (like bcrypt, scrypt, or PBKDF2).  I want to know what kind of MAC to use.
To represent the MAC, I'm using this notation

HMAC-SHA256secretkey(message) and HKDFsalt(password)
password is the low-entropy user password
key is the high entropy secret key (the "pepper")
salt is a per-password random value, optionally reused by the subsequent computationally expensive hash such as bcrypt, PBKDF2, or scrypt

Would any of these constructs be more recommendable? Or is there an even better way? And if so, briefly why?

HMAC-SHA256 key(password)
HMAC-SHA256password(key)
HKDFpassword(salt)

NB: This question is in relation to the "pepper" section near the end of the accepted answer to "How to securely hash passwords". Thus the output of the MAC will be fed to a slow, computationally expensive KDF like bcrypt, PBKDF2, or scrypt.

Given the clarified answer, I suggest you do the following:

$T = F_k(\text{password})$

$Y = H(T, \text{salt})$

where $F$ is a PRF (pseudorandom function) and $H$ is a slow hash.  Here $k$ is the secret key (the "pepper").

You can instantiate $F$ with AES-CMAC or SHA256-HMAC (or any other good PRF).
When you use $F$, feed the secret key $k$ (the pepper) into the key input of the PRF, and feed the password into the message input for the PRF.  (This corresponds to your option 1.  I do not recommend using your option 2, and definitely not option 3.)

You can instantiate $H$ with a slow hash like bcrypt, scrypt, or PBKDF2.
When you use $H$, feed $T$ into the password input for the slow hash, and feed the salt into the salt input for the slow hash.

Finally, store $Y$ and the salt in your database of hashed passwords.

This scheme ensures that if the key $k$ (the "pepper") is kept secret and is not known to the adversary, then the adversary will not be able to recover any of the passwords.  It also ensures that if the key $k$ does become known to the adversary, the best the adversary can do is a dictionary attack on the passwords -- but this will be slowed down because of the slow hash.  Consequently, if $k$ does become known to the adversary, this scheme should be no worse than just using scrypt/bcrypt/PBKDF2 without a pepper.


Using "Additional Authenticated Data" as a secondary key In implementing a cipher in GCM or CCM mode, you are provided the option to add "Additional Authenticated Data" (AAD). This AAD is required for decrypting the cipher text, and seems to be used when data is crucially specific to a label.

EDIT: to clarify, an example of when it might be used that I have seen is if you want to encrypt the number of shares of a stock that has been purchased, but need to make sure that that number corresponds to the correct stock you would use an AAD containing the name of the stock.

What I am wondering is, could you use this AAD as a secondary key and simply keep it secret?

Thanks

You certainly could keep the AAD secret; however, for GCM, it wouldn't provide any additional security beyond what the secret key already provides; for CCM, it does still provide some limited authentication protection (but probably not enough).

The bottom line: if you can't trust that your key is secret, well, keeping the AAD secret (or have a secret portion) won't help you.

Details:

If the attacker has a guess for the secret key, he can still verify it, by using that key to decrypt the data, and seeing if the decryption makes sense.  He can do this because for both GCM and CCM, the AAD affects only the tag, it does not modify how the ciphertext is converted into plaintext.
If the attacker has the secret key, he can decrypt ciphertext (just as above).
If the attacker has the GCM secret key, and has seen one valid encrypted message, he can encrypt any plaintext of his own choosing.  This is because the GCM tag can be expressed as $F( Key, Nonce, Plaintext ) \oplus (G( Key, AAD ) \otimes H( Key, Plaintext))$ (where $\otimes$ is multiplication in $GF(2^{128})$).  If he has the key, he can compute $F$ and $H$; if he has seen a valid packet, he can solve the above for the value of $G( Key, AAD )$, even if he doesn't know the value of $AAD$.
If the attacker has the CCM secret key, and has seen one valid encrypted message with a specific nonce, he can encrypt any plaintext of the same length of his choosing with the same nonce.  That's because the CCM tag can be expressed as $F_{K, Plaintext}( G(Key, Nonce, AAD, PlaintextLen) )$, where $F_{K, Plaintext}$ is an invertible function; hence, given a valid message, the attacker can recover $G(Key, Nonce, AAD, PlaintextLen)$, and use that to generate a tag for another message with the same length.

The above assumes you transmit the entire 16-byte tag in both cases; if you truncate the tag to $n$ bits, this actually adds some additional protection to CCM (as inverting the $F_{K, Plaintext}$ function does require all 128 bits; if the attacker isn't given all 128 bits, he'll end up having to search for them).


Two or more initialization vectors with the same key I'm studying about WEP and I'm in doubt.

It seems that because it uses a initialization vector of 24 bits, which is relatively short, is easy to determine which key was used to encrypt the data.

But I don't understand why, for example, 24-bit initialization vector is short ok, and probably we will have 2 or more equal initialization vectors. But I don't understand why if we have similar initialization vectors, it will be easier to find the encryption key.

It seems that because it uses a initialization vector of 24 bits, which is relatively short, is easy to determine which key was used to encrypt the data.

Actually, it's not the shortness of the IV that does cause the key leakage (although it does cause other problems).

Instead, it's due to how WEP combines the IV and the key, and then how the RC4 key initialization algorithm takes the combination, and generates a biased permutation.  Depending on the IV, this permutation may make the first byte of the RC4 keystream (and, it turns out, later bytes as well) to be correlated to bytes within the key; this allows someone listening in (who knows the first byte of the plaintext; with WEP, that's constant) to deduce the key.

The bias isn't extremely strong, and so we do need multiple IVs to fully leak the key.

To go into more details than that fairly high level description, you need to start looking into the RC4 KSA and keystream generation; that's where the weaknesses lie.


Two plaintexts map to the same ciphertext in fully homomorphic encryption? In standard symmetric encryption, we can create an encryption scheme, in which two plaintexts $x_1, x_2$ map to the same ciphertext $y$, by choosing appropriate keys $k_1,k_2$ (!).
The most simple example is the one-time pad: For any plaintext $x$ and any ciphertext $y$, we can choose a one-time pad key $k$ such that $E(x,k)=y$. Therefore,

  (*)  we can for any $x_1,x_2$ choose two one-time pad keys $k_1,k_2$ such that $E(x_1,k_1)=E(x_2,k_2)$.

(Note, I'm not claiming that finding $k_1,k_2$ is computationally tractable!)

This in itself is not interesting, but now consider fully homomorphic encryption.

In a fully homomorphic encryption scheme, we have a plaintext $x$ and key $k$, and an encrpytion function $E(x,k)=y$, but where it is now possible for an (untrusted) party for a given arbitrary computation $f$, to do computations $\tilde f$ on ciphertext $y$ without knowing the plaintext $x$, such that by decrypting $\tilde f(y)$, we get $f(x)$.

I am wondering, whether there is a similar result as (*) for fully homomorphic encryption. That is, does there exist some fully homomorphic encryption scheme that has the following property:

  given two plaintexts $x_1,x_2$, there exists two keys $k_1,k_2$, such that $E(x_1,k_1)=E(x_2,k_2)=y$, and where this encryption is fully homomorphic, i.e. we can do any arbitrary computation $f$ (actually I only care about invertible computations) on $y$, and then decrypt this such that $D(f(y),k_1)=f(x_1)$ and $D(f(y),k_2)=f(x_2)$.

Note:

I am not claiming that this is practically useful in any way.
It is ok if actually finding these keys $k_1,k_2$ is computationally intractable.
I am interested in this for theoretical purposes only.

EDIT: random (and based-on-nothing) thought: If such an encryption scheme exists, then P=NP?

EDIT2: Here is an informal argument for why it shouldn't be possible:

a fully homomorphic scheme can by definition compute any computable function $f$. so it should also be able to compute a famliy of functions $f(x,n)$ where $x$ is the plaintext, and $f$ has EXPTIME complexity w.r.t. $n\in \mathbb N$.
Denote by $T(f(x,n))$ the amount of computational steps required to compute $f(x,n)$, and by $T(key)$ the amount of steps to find the right key $k$ for $x$ such that $Enc(x,k)=y$.
Then if we want to compute $T(f(x_i,n))$ "directly" for a set $X=\{x_i\}$, then it will take $T(f(x_i,n))\cdot |X|$ steps (simply the time required to compute an instance, multiplied by the amount of instances).
But if we want to compute it by using homomorphic encryption, then it will take $T(f(x_i,n)) + T(key)\cdot |X|$.
Therefore, as we increase $n$, the computation time of the first method (direct computation) increases faster by a factor of $|X|$. We, therefore, get "free computation" in the fully homomorphic case.
Therefore, no matter what the computational complexity is of computing the keys for the $x_i$'s, there always exists a $n$ such that computing it with the fully homomorphic method is more efficient.

This conclusion does not seem to follow the "laws of computer science", (though I haven't proved it's impossible), because it seems like a general-purpose method of improving the efficiency of such problems.

Same ciphertext from different keys

Since deterministic Homomorphic encryption schemes are insecure, all the proposed HE schemes randomize the ciphertexts in some way, i.e., during the encryption, some random value $r$ is sampled and combined with the ciphertext.

Hence, given two different keys $k_1$ and $k_2$ and two messages $m_1$ and $m_2$, we usually can find two possible random values $r_1$ and $r_2$ that make $Enc(m_1, k_1; r_1) = Enc(m_2, k_2; r_2)$, therefore, the answer for your question is yes.

For example, in schemes based on the Approximate-GCD problem, such as DGHV10, a message $m_i$ is encrypted as $pq_i + r_i + m_i$, where $p \in \mathbb{Z}$ is the secret key and $q_i$ and $r_i$ are random integers.

So, given two keys $p_1$ and $p_2$ and two messages $m_1$ and $m_2$, it is sufficient to take $q_1 = p_2k$, $q_2 = p_1k$ (for any $k$) and $r_1 = r_2 + m_2 - m_1$.

Then we see that
$$Enc(m_1, p_1; q_1, r_1) = p_1q_1 + r_1 + m_1 = p_1p_2k + r_2 + m_2 = p_2q_2 + r_2 + m_2$$
which corresponds to $Enc(m_2, p_2; q_2, r_2)$.

For the BGV scheme, it is a bit more complicated, but you can still choose keys such that it holds. Namely, let $s_1, s_2 \in R := \mathbb{Z}[x]/\langle f(x) \rangle$ be two secret keys and use the same $\vec e$ in the corresponding public keys. Than, we can set

$$m_1 + s_1\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle = m_2 + s_2\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle \mod q$$
where $\langle \vec a, \vec r \rangle $ denotes the inner-product and it is a polynomial in $R$.

This equality is satisfied if $s_1 = m_2\langle \vec a, \vec r \rangle^{-1} + s_2 \mod q$.

Computational "paradox"

First of all, you are not modeling the running times correctly, because finding four keys that produce the same ciphertext is more than two times slower than finding two keys, that is, you cannot simply use $T(key)\cdot|X|$, you should use $T(key, n)$ and $T$ is most probably not linear in $n$, since you have to solve systems with more than $n$ variables to find the keys.

Furthermore, that apparent contradiction with the "laws" of computation is not implied by the ability of finding such keys. Actually, what you need is not only to create equal ciphertexts but also two find a way that their evaluation yield the same ciphertext. It might be the case that $c_1 := Enc(x_1, k_1) = c_2 := Enc(x_2, k_2)$, but $Eval_1(f, c_1) \not = Eval_2(f, c_2)$, and therefore, you could not evaluate $f$ homomorphically a single time and decrypt it with two different keys.


Importance of round complexity in determining the efficiency of an MPC protocol Literature has different ways of specifying complexity of an MPC protocol:

computation complexity that measures the number of (assumed primitive) operations performed by all the parties;
communication complexity, which measures the number of bits communicated between parties during the protocol;
round complexity that measures the number of sequential steps in the algorithm (discounting on operations that can be done in parallel).

I feel that all the above parameters are important, to be discussed, when analyzing the efficiency of any proposed MPC protocol. However, I observed that round complexity is discussed in only few of the works. Hence I wanted to know, how important a role does the round complexity play in determining the efficiency of any proposed protocol. That is, when is considering round complexity of a protocol important?

It would be helpful if you could point me to literature that discusses the nature of functions that can be achieved, using MPC, in constant round and those that cannot.

First note that all polynomial-time functions can be securely computed with a constant number of rounds (Yao and BMR families) and all can be securely computed with protocols that have rounds dependent on the depth of the circuit computing the function (GMW families). The question is when is one type better than another.

The answer to this question is not straightforward, and depends on many parameters. Clearly, if you are on a slow network (Internet with 30ms round-trip time), then any protocol that has many rounds will be very very slow. However, if you are on a fast network, then many rounds has less of an influence (except in very extreme circumstances of incredibly deep circuits). It turns out that the constant-round protocols that we know of have much higher bandwidth than those that have complexity that depends on the depth of the circuit. Thus, in a very fast network, many-round protocols often out-perform constant round ones. As I mentioned, this is NOT the case in a slow network.

There isn't too much published that directly relates to this question. However, for semi-honest adversaries there is one paper that comes to mind by Schneider and Zohner, titled: GMW vs. Yao? Efficient secure two-party computation with low depth circuits that appeared at Financial Crypto 2013. This is a good place to start reading.


Break double encryption Let $E_k$ : {0,1}$^l$ be a block cipher encryption function with block-size $l$ and key-length $n$.

In class, we saw that a double encryption with two independent keys $E{}'_{k_1k_2}(x)$ = $E_{k_1}(E_{k_2}(x))$,

can be brute-forced in $O(2^n)$ time and $O((l + n)2^n)$ space using the meet-in-the-middle attack:

create a table with $2^n$ entries mapping
keys of length $l$ to entries of length n by encrypting the known plain text $x$ with all possible keys $k_2$,
then search the table by decrypting the corresponding cipher text $c$ using all possible keys $k_1$.

Suppose you only have $O((l + m)2^m)$ space (where $m < n$),
Give an algorithm to break the double
encryption in time $O(2^{2n-m})$.

I am stuck for days, can't figure out the trick that will allow such an efficient algorithm.

Any ideas? Tips? Hints?

This is homework of course.

ADDED:

Is it sufficient to show that if we choose smaller $n$ the encryption will be broken with non neglect-able probability? Or I must show an algorithm that ALWAYS brake the encryption?

Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?


Can TLS be used simply to exchange keys using the handshake protocol? From what I understand, in general, TLS consists of two protocols:
1 - Handshake protocol: uses public-key cryptography (ECDH, DH) to establish a shared secret between the client and server.
2 - Record protocol: uses the shared secret established in the handshake protocol to protect communication or application data between the client and server
Let's say I want to encrypt data and then use steganography to hide the encrypted data in an image, then I want to exchange the key used with the server using the handshake protocol BUT I do not want to send the steganographic image using the record protocol because it would defeat the purpose.
So, can I simply complete the handshake protocol and then drop the connection?

1 - Handshake protocol: uses public-key cryptography (ECDH, DH) to establish a shared secret between the client and server.

The handshake protocol is also used to establish a cipher suite, some configuration parameters and (usually) to perform entity authentication, amongst others.

So, can I simply complete the handshake protocol and then drop the connection?

The shared secret is only used to establish the session keys and might be destroyed after they've been established.
If you drop the connection the shared key should be destroyed by the implementation as well.
The session keys are TLS specific, and they are often not available from an TLS API for that reason.

So you could use part of the TLS handshake to establish a shared secret, but you'd go outside protocol specs if you use the session keys for anything else. If you use a TLS implementation you'd probably need to alter it to get to the right key material.
In your case it might be better to simply lift the relevant bits from the protocol and use that to define your own. Of course that would go against not using DIY cryptography, but I guess you've gone over that dangerous threshold already...


Algorithm to generate ECDSA keys with random number generator I have a certified random number generator (TRNG, it does not matter what it is for the question).

I would like to use it as a source to generate secp384r1 ECDSA keys. What is the algorithm I should use? Is it possible?

I know that it is generally not a good idea to implement one's own cryptographic algorithms, so is there any library that can be used for this? (something like Bouncy Castle?)

Many libraries allow you to specify your own random number generator. In BouncyCastle, for example, you can specify a SecureRandom in the initialize method of the KeyPairGenerator class; while in Go you can specify a io.Reader to the GenerateKey function.

Therefore, you would need to write a class that implements SecureRandom or io.Reader and reads the specified number of bytes from your TRNG, assuming your TRNG actually produces uniformly distributed random output.  Be careful though, if you mess it up, the whole security of your system is compromised.

(A safer approach would be to make a program that reads from the TRNG and writes to /dev/random, mixing up the system PRNG, assuming it's Linux)


Is this a peculiarity of the bytes of the underlying AES ciphertext, or of the way Ansible/Python represents the binary ciphertext as a digit string?

It's an artifact of how it represents a binary ciphertext.
What it does it first converts the binary into an ASCII representation of the hex, that is, converting it into the digits '0' through '9' and 'a' through 'f'.  Then, it converts each hex digit into its two digit hex representation, that is, the values '30' through '39' and '61' through '66'.
Back translating the first 16 characters of your quoted string:
6531333066306133

when converted back into ASCII, those are the 8 characters e130f0a3, which is the hex representation of the actual binary value.
As for why the character distribution you saw:

The character 3 is the first digit of 62.5% of the encoded bytes and is the second digit of 12.5% of the encoded bytes; hence it is expected to occur 37.5% of the time in aggregate

The character 6 is the first digit of 37.5% of the encoded bytes and is the second digit of 12.5% of the encoded bytes; hence it is expected to occur 25% of the time.

Any of the characters 1,2,4,5 is the second digit of 12.5% of the encoded bytes, hence it is expected to occur 6.25% of the time.

Any of the characters 0,7,8,9 is the second digit of 6.25% of the encoded bytes, hence they are expected to occur 3.125% of the time.

Those are roughly what you've seen (although the second example doesn't hold that close to these expected statistics; I'm not certain why that would be)


ECIES for encrypting ECDH key exchange I started studying Elliptic Curve Cryptography, and I do not know if I understand the difference between ECDH and ECIES (even with the other posts here on stackexchange).
I'm wondering if ECIES can be used to encrypt the ECDH key exchange to guarantee that it does not exist a man-in-the-middle. I'm thinking about this like TLS, where there is an asymmetric encryption before symmetric keys are exchanged.
In brief, something like:
Use ECIES to establish a secure client-server session and ECDH to generate the shared key to exchange information securely over the established secured session between server and client. In the Asymmetric Encryption Algorithm, the sender needs a Public key to encrypt the message, and the receiver need a Private Key to decrypt the message, while in Symmetric Encryption Algorithm, Both sender and receiver need single Symmetric session key to encrypt and decrypt data.
This make sense? If not, please help me understand the difference between ECIES and ECDH and if ECDH has some authentication.

Elliptic Curve Integrated Encryption Scheme (ECIES) is a type of Integrated Encryption Scheme (IES) that uses Elliptic-Curve Diffie-Hellman (ECDH) key agreement to establish an ephemeral data key (rather than a session key) which is then used to encrypt data using a symmetric scheme. It uses an ephemeral key during the creation of the ciphertext, for which the public key is stored with the ciphertext. Usually, the receiver / decrypting entity has got a static key pair for which the public key needs to be trusted by the sender / encrypting entity.
ECIES can of course be used for authentication of the receiver: you could encrypt an ephemeral key using the data key, send it over, and if the other party is able to decrypt then you have authenticated the receiver. Of course, the receiver must still show that it now has the authentication key to e.g. create a MAC over a message known by both parties. In the case of TLS you would basically be replacing RSA_ ciphersuites that perform RSA encryption with ECIES_ ciphersuites that perform Elliptic Curve encryption.
That sounds great, but hold on: both parties now first have to establish an ephemeral data key, to encrypt an ephemeral authentication key. It would be much easier to simply use the data key for authentication. If you'd do that then you're back to Diffie-Hellman key agreement. So basically it would only be useful if normal DH key agreement can - for some reason or other - not be directly integrated in the protocol.
This is an explanation by example that differs from an earlier, more concise one given here. That one focuses on the session key derivation, this one is more about the possible entity authentication.

There are several versions of the DH key agreement that allow authentication. Most possible schemes are documented in NIST SP 800-56A Revision 3: "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography", chapter 6.
Basically you need a static DH key to perform authentication which then can be performed by validating a MAC created using the derived key. So the "1S" scheme (S for Static) is able to authenticate one entity, and 2S schemes are able to authenticate both entities (I'll skip over multi-entity key agreement, for now, keeping it at a single pair).


How can a hash function that implements random oracle model have collision resistance? ROM is considered to be collision resistant. Does ROM assume there is an infinite set of outputs, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM is guaranteed a collision given a large enough set of input, even when the output is generated randomly.

As Ella Rose points out in a comment, it is not that there are no collisions; rather, one can prove that the probability of encountering a collision is small in the random oracle model.

The random oracle model posits a finite domain and a finite codomain; otherwise the space of functions would be infinite and there could not be a uniform distribution on them.  If $f\colon A \to S$ is a uniform random function into a set $S$ of $n$ elements (e.g., $S$ is the set of $t$-bit strings, so that $n = 2^t$), then $f(x)$ is independent for each distinct $x$, and $\Pr[f(x) = h] = 1/n$ for each $x$ and $h$.

When we combine these two properties—$x \ne x'$ implies $f(x)$ and $f(x')$ are independent, and $\Pr[f(x) = h] = 1/n$—we can conclude from a standard birthday argument that any algorithm making $q$ queries to a random oracle has probability at most $q^2/n$ encountering a collision.  Following Ramanujan, Knuth, etc., the expected number of queries before a collision is $$1 + \sum_{k=0}^{n - 1} \prod_{i=1}^k \biggl(1 - \frac i n \biggr) = 1 + \sum_{k=1}^n \frac{n!}{(n - k)! \, n^k} \approx \sqrt{n \pi/2}.$$   Consequently, the expected query cost of any algorithm to break a cryptosystem like RSASSA-PSS signature by finding a collision in a $t$-bit random oracle is about $2^{t/2}$—which for typical values of $t$ like 256 is far beyond the capacity of humanity to carry out.

Of course, it is possible that we will learn something about SHA-256 that enables finding collisions more cheaply than generic collision searches, like we did with MD5 and SHA-1.  But this is how the random oracle model works.


Hashing a password before using for online accounts I don't actually know what I'm talking about, so apologies if I get anything wrong. At the moment I have a password naming system for most of my online accounts that looks something like this: masterpassword + appname, where appname is the name of whatever service the password is for. ex. $sickpass123$_SoundCloud and $sickpass123$_Gmail. The idea is to have an easy to remember master password combined with the app name so every password is unique. I am worried though, because if a proactive individual manages to figure out one of my passwords, it would be easy for them to figure out the other passwords since they all contain the same master password.

I thought of running each password through a hash function (every time need to enter it) as this would ensure that each password is unique. ex. 8d9f24e142b33c2f7f3d59fc7c6043a7 and 84e08387ef918182154713d388f5ea62. In addition, I could encode the hash output in base64 or ascii85 to fulfill the capital letter/number/symbol requirements for passwords in online services. ex. OGQ5ZjI0ZTE0MmIzM2MyZjdmM2Q1OWZjN2M2MDQzYTc= and ODRlMDgzODdlZjkxODE4MjE1NDcxM2QzODhmNWVhNjI=.

I am also aware of password generators, but they generate a random string each time rather than a predictable output. I would rather have the same output be generated every time I enter my password. That way, it will be easy to remember every password, but the hash function will make each one virtually unique. Also, if only the hash output is given to websites, rather than the original password, the sites themselves will not know my pattern.

Is there any problems from using the approach I am suggesting?
Would it actually be less secure if the server encrypted my already encrypted password?
Should I encode the output in base64 or ascii85, or something similar?
Which algorithm would be best suited to this task? Do I need something more secure like SHA-1 or will the more primal MD5 be adequate (would anyone care enough to try to break the hash)?

EDIT: Thanks for all the answers. They were all very informative. I think I might try a password manager, perhaps MasterPasswordApp as @Matty suggested, as it'll be easier to manage.

Is there any problems from using the approach I am suggesting?

Yes, there are several.

First of all, some sites generate first time passwords, or even long time passwords. You may want to store those too. What if a site requires frequent updates?

If one password is reversed, you'd still loose confidentiality.

  Would it actually be less secure if the server encrypted my already encrypted password?

No, usually not. If you don't know the server's key then using encrypted input will not change encryption. Same goes for password hashing basically. If you don't operate with the same parameters (e.g. salt), then you are unlikely to be vulnerable.

  Should I encode the output in base64 or ascii85, or something similar?

Anything the target site accepts. This points to another issue since the sites may require passwords in a specific format. Both the alphabet (character input) of the password and the size may be restricted. So some sites would be better off with base64, some with base 85 and others with neither of the above. E.g. an 8 character base 64 string only has 48 bits of security, allowing brute force attacks. How are you going to remember which format is best for specific sites?

  Which algorithm would be best suited to this task? Do I need something more secure like SHA-1 or will the more primal MD5 be adequate (would anyone care enough to try to break the hash)?

When constructing security protocols you'd have to assume that somebody "cares". Otherwise you might as well skip the whole thing. That said: no, SHA-1 or MD-5 will likely not influence the choice much.

That all said and despite all the indicated issues, hashing the password is still somewhat more secure than providing a password with extension directly. But since you would need to have a device & application for this anyway, I'd recommend using a password manager instead (that e.g. applies a password hash or PBKDF over the master password to decrypt the database).


Why don't homophones hide multiple-letter patterns? I am reading about mono-alphabetic ciphers, which are prone to letter frequency analysis. To counter this, we can provide multiple substitutions, known has homophones for a single letter e.g. e could be assigned 17, 74, 35, 21. Each homophone could be assigned in rotation or randomly.

This is where I am confused:

  Even with homophones, each element of plaintext affects only one element of ciphertext, and multiple-letter patterns (e.g. diagram frequencies) still survive in the ciphertext, making cryptanalysis relatively straight forward.

How do multiple-letter patterns survive? For example if for h we have homophones 17, 74, 35, 21 and for t we have 11, 69, 27, 24, th could be 11 17 or 11 74 or 11 35 or 69 21 etc.

For starters, you don't have 4 or 5 codes for every letter. The basic idea is, that each symbol in your alphabet for the ciphertext has the same frequency. Most letters will still have only 1 or 2 symbols, and just the more common ones will have 3 or more.

So the frequencies of single symbols is roughly uniform. Let's take your example of a th, which is the most common bigram in english language (the  frequencies are just examples, other sources might have different ones)

$t$ has frequency $0.0894$
$h$ has a frequency $0.0496$
$th$ has a frequency of $0.0271$

Now let's imagine we have a total of 100 symbols in the ciphertext, where we have 9 symbols for the letter $t$ and 5 for the letter $h$, so that each symbol has roughly the frequency $1/100$.

Now there are $9\cdot5 = 45$ possible combinations for $th$. With 100 symbols in the alphabet, the number of possible bigrams is $10000$ and the frequency should be 0.0001 if it is uniform. We know that $th$ has a frequency of $0.0271$, spreding that uniformly over 45 combinations and we get a frequency of $0.0271 / 45 \approx 0.0006$.

So, even if we have the monogram probabilities almost at $1/100$ for every symbol, then those $45$ bigrams for $th$ have a frequency that is roughly 6-times as high as the average bigram should be. In comparison: The monogram $t$ has just a frequency, which is not even 2.5 times higher than $1/26 \approx 0.0385$.


Is there a way to do anonymous encryption to a recipient? Is there a way to do anonymous encryption to a recipient's Public key, where the only way to open a message would be to decrypt with your own private key + passphrase?

You can write one very easily, but luckily there are libraries for these like Sealed boxes
From the site;

Sealed boxes are designed to anonymously send messages to a recipient given its public key.
Only the recipient can decrypt these messages, using its private key. While the recipient can verify the integrity of the message, it cannot verify the identity of the sender.
A message is encrypted using an ephemeral key pair, whose secret part is destroyed right after the encryption process.
Without knowing the secret key used for a given message, the sender cannot decrypt its own message later. And without additional data, a message cannot be correlated with the identity of its sender.
Note: the emphasis is mine.

The sealed boxes based on Crypto boxes that uses

Key exchange: X25519
Encryption: XSalsa20 stream cipher
Authentication: Poly1305 MAC

Keep in mind that the additional data can be, your IP address, your MAC address, your writing style, etc. This may leak your identity or location. You may need some protections/countermeasures like TOR network against the identification of the sender.


What is the definition of a Linear Cipher Is there a precise definition of what counts as a Linear Cipher? If so, what is it?

A linear cipher is a cipher that all of its inner operations (diffusion and confusion operations) have the mathematical linear property. Linear property in mathematics is defined in such a way: f(a+b) = f(a) + f(b). But what does it mean in origin? It means that if we think a cipher like a magic box, then if we give this magic box the sum of two quantities, then in the output of this magic box we can distinguish these two quantities. But how does it relate to cipher security? This linearity property causes the transformation of any inputs properties to output properties. For example, think about one of these properties can be the odd or even of inputs. Then, if the input data to the cipher are all even, then all of the output data be even, too. As we told, every cipher operates with two operations. Each of these operations is defined with mathematical functions: Substitution function that makes the confusion property and Permutation Function that makes diffusion property. Permutation functions are originally linear or affine functions(affine function: linear function + constant value). The only part of cipher that should be non-linear is confusion parts. For example SBoxes. And choosing a good SBox that has the high nonlinearity property is very important. So if we can change a cipher to a linear or affine form(by some technics of cryptanalysis like Linear cryptanalysis), we can change the cipher to some linear equations and by solving these equations, we can extract the Key.