Is the following a PRG? Let $G: \{0, 1\}^n → \{0, 1\}^m$ be a PRG. We construct a function $G': \{0, 1\}^{m + n} → \{0, 1\}^{2m}$ defined as follows
$G'(x || y) = x || (G(y) ⊕ x)$
for all $x ∊ \{0, 1\}^m$ and $y ∊ \{0, 1\}^n$. (The symbol || denotes here the concatenation of binary strings.)
Is $G'$ a PRG?

I believe that it is not, but I could easily be wrong.
I know, given a random string s of length $2m$ (split into equal length strings $s_1$ and $s_2$), that $s_1$ would be equivalent to $x$, and that $s_2 \oplus x$ would be equivalent to $G(y)$. But since $G(y)$ is indistinguishable from $U_m$, I'm having trouble reaching the conclusion of my contradiction.
I'm still relatively new to all of this, so any help would be appreciated.

I believe that it is not, but I could easily be wrong.
... I'm having trouble reaching the conclusion of my contradiction

The problem is you can't show that contradiction, because there isn't any. As a rule of thumb for homework questions: If it becomes clear that you can't prove your initial assumption, consider that your intuition was wrong.
Here are some pointers how you can show that $G'$ is in fact a PRG, in a proof by contradiction:

Let's assume $G'$ is not a PRG, and that means a distinguisher $\mathcal{D}$ exists.
The input for $\mathcal{D}$ is one element either uniform random or of the form $x||(G(y)\oplus x)$, and then it has some non-negligible advantage $\epsilon$.
We want to build a distinguisher for $G$. So as input we get one element, which is either from a uniform random distribution or from the image of $G$.
In general, if $a$ is uniform random, then $a \oplus b$ is also uniform random -  this is true as long as $b$ is independent of $a$. This includes fixed $b$ as well as $b$ drawn independently from any distribution.


Deciphering a key from XOR encrypted cypher using boolean logic Assume there's an unencrypted message A, and an encrypted message B. You know that message B was encrypted using a simple XOR method of A with a private key K, resulting in message B. Thus,

B = A ⊕ K

Can I use Boolean algebra, i.e. truth tables, and sum of products to decode the key?

If $K$ is random and you only know $A$ or $B$ (but not both) then, no, there is no way to infer anything about the key - this is the (in)famous one-time-pad.

If you know $A$ and $B$, then you can recover $K$ very easily. Exclusive-or has those properties:

$\forall n$, $~~~~ n \oplus n = 0$
$\forall n$, $~~~~ n \oplus 0 = n$ (identity element)
$\forall a, b$, $~~~~ a \oplus b = b \oplus a$ (commutativity)
$\forall a, b, c$, $~~~~ a \oplus b \oplus c = (a \oplus b) \oplus c = a \oplus (b \oplus c)$ (associativity)

So we can do the following:

$B = A \oplus K ~~~ \Rightarrow ~~~ A \oplus B = A \oplus (A \oplus K) = (A \oplus A) \oplus K = 0 \oplus K = K$

So $A \oplus B = K$

Viewed differently, the exclusive-or operator is invertible:

$\begin{array}{|c|c|c|}
\hline
\oplus &0 &1 \\ \hline
0 &0 &1 \\
1 &1 &0 \\
\hline
\end{array}$

$\begin{array}{|c|c|c|}
\hline
A &B &\oplus \\ \hline
0 &0 &0 \\
0 &1 &1 \\
1 &0 &1 \\
1 &1 &0 \\
\hline
\end{array}$

And since the truth table is symmetric, the exclusive-or operation just happens to be its own inverse, i.e. $x \oplus^{-1} y = x \oplus y$. So if we take our original equation:

$A \oplus K = B$

We can represent it as follows:

$K \oplus A = B$

And we can then undo (invert) the exclusive-or by A:

$K \oplus A \oplus^{-1} A = B \oplus^{-1} A ~~~ \Rightarrow ~~~ K = B \oplus^{-1} A$

And as we found above, this is identical to:

$K = B \oplus A = A \oplus B$

As found at the beginning.

However, this is assuming A, B and K are all the same length. If K is smaller than A and B, then it means that K will be used multiple times (repeated over the length of the plaintext, presumably). This repetition can be exploited to successfully recover K from only B provided there is enough repetition and there is enough ciphertext to work with - see Vigenere cipher.


How to securely share AES key between two remote devices (client and server) through UDP protocol? I have two separate system (client) and (server). I am having a problem which is to encrypt a message from the client and decrypt at the server. In order to do that, I am required to transmit my key along with the message through UDP packets. However, is there any possible ways to ensure the key is transmitted securely?

You don't transfer the key, not at least un-encrypted.
There are several ways to "establish a shared key" between authenticated systems.
Using key exchange schemes such as Diffie-Hellman, its elliptic-curve versions such as ECDH, X25519/X448, etc, as well as some schemes secure even if you attack it with a quantum computer such as NTRU (formerly NTRUEncrypt), Kyber, Saber.
Notice I said authenticated system. key exchange schemes require the public key of the peer - which is static if you just hard-code it into your application; a better way is to use a digital signature to sign an ephemeral key exchange public key and hard-code the digital signature verification key into the application.
All in all, there is a well-established protocol with existing free and open-source implementations called TLS, which you can use to exchange an initial key, then import that key into your UDP-based protocol.
The QUIC protocol does about just that: it doesn't design new key exchange or authentication handshake protocol, it imports the key from TLS handshake and use it in the en/de-crypting UDP packets.


a possibly stronger type of attack on identity-based encryption What is known about the security of identity-based encryption schemes against attacks that involve seeing multiple ciphertexts and then receiving the private keys corresponding to some of those ciphertexts?

For example, is it known that feasible adversaries will have a negligible (in the security parameter $k$) probability of succeeding in the following, for IND-CCA2 IBE schemes?

Challenger generates $\:\langle$pub,msk$\rangle\:$ and then gives $\:$pub$\:$ to $\mathcal{A}$
$\mathcal{A}$ outputs a list of $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)\hspace{-0.01 in}+\hspace{-0.02 in}1\:$ distinct IDs
Challenger chooses $\:x\in \{0,\hspace{-0.04 in}1\}^k\:$ uniformly
Challenger computes $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)\hspace{-0.01 in}+\hspace{-0.02 in}1\:$ Shamir shares of $x$ so that one needs $\:k\hspace{-0.03 in}+\hspace{-0.04 in}1\:$ of them to recover $x$
Challenger encrypts those shares using $\:$pub$\:$ and the corresponding IDs from the list provided by $\mathcal{A}$
Challenger gives the resulting list of ciphertexts to $\mathcal{A}$
$\mathcal{A}$ outputs a list of $k$ IDs
Challenger uses $\:\langle$pub,msk$\rangle\:$ to extract the private decryption keys for those IDs
Challenger gives the corresponding list of private decryption keys to $\mathcal{A}$
$\mathcal{A}$ outputs $y$
$\mathcal{A}$ succeeds if and only if $y = x$

You can probably prove the security against your game from the security in the IND-ID-CCA game of Boneh and Franklin (see http://courses.cs.vt.edu/cs6204/Privacy-Security/Papers/Crypto/IBE-Weil-Pairing.pdf). The idea is to create an adversary $\mathcal{B}$ against IND-ID-CCA from your adversary $\mathcal{A}$. Essentially $\mathcal{B}$ will play man-in-the-middle between the IND-ID-CCA challenger and $\mathcal{A}$.

When $\mathcal{B}$ receives the $2k+1$ identities from $\mathcal{A}$, he chooses one of those at random (let's call it $ID_0$) sends two random values $(x_0,x_0')$ together with $ID_0$ to the challenger and receives an encryption $C_0$ of either $x_0$ or $x'_0$. For each of the other identities $ID_i$, $\mathcal{B}$ encrypts values $x_i$ chosen in such a way that $(x_0,\cdots, x_{2k+1})$ are valid shares for the secret sharing, the ciphertexts are denoted by $C_i$. Then $\mathcal{B}$ returns the ciphertexts to $\mathcal{A}$. [Note that if the challenger has chosen $x_0$ your game is perfectly emulated, otherwise, the shares are invalid]

When $\mathcal{A}$ sends the $k$ identities, if $ID_0$ is in the set $\mathcal{B}$ aborts the communication with $\mathcal{A}$ and returns a random guess to the challenger. Otherwise, $\mathcal{B}$ asks the $k$ keys to the challenger and sends those to $\mathcal{A}$. When $\mathcal{A}$ returns $y$, $\mathcal{B}$ proceeds as follow:
If $y$ is consistent with the share $x_0$, then $\mathcal{B}$ guesses that the challenger returned an encryption of $x_0$, otherwise $\mathcal{B}$ guesses at random.

If $\mathcal{A}$ wins your game with probability $\epsilon$, the advantage of $\mathcal{B}$ is approximately $\epsilon/4$.

Additional information:

The advantage is not $\epsilon/2$ as I wrote initially but $\epsilon/4$, this is due to the fact that there are two possible definitions for the advantage of a distinguisher. Some papers use the absolute value of the difference to $1/2$ and some papers use twice that. For technical reasons, twice the difference is preferable and I did not initialy noticed that Boneh-Franklin don't use this version.
How is the advantage computed ? This needs an additional hypothesis which I did not mention. Take your game with a variable number of shares, say $\ell$, keeping $k$ fixed and denote by $\ell_0$ the smallest value for which there exists an adversary with non-negligible advantage. Clearly, if there exists an adversary for $\ell=2k+1$ then $\ell_0\leq 2k+1$. And, of course, $\ell_0>k$ because with $k$ shares you have no information about $x$.

If $\ell_0=2k+1$ use the above reasoning. in this case, $\mathcal{A}$ cannot return $y=x$ with non-negligible probability when one share contains $x'_0$ because you could then transform $\mathcal{A}$ into an adversary against $\ell_0-1$ shares by just adding a random valued share. If $\ell_0<2k+1$, redo the reasoning with the new $\ell_0$. This changes the advantage to $\frac{(\ell_0-k)\epsilon}{2k}$. The only problem is that in the case $\ell_0=k+1$, the reduction is not tight.

Response to Ricky's comment on the tightness of the reduction:

I don't see how you get a degradation exponential in $k$. Here is a more precise analysis of the full game if you don't assume that the probability of success jumps from negligible for non-negligible but do a more precise analysis.

Let $\epsilon_\ell$ be the best possible advantage for an adversary that wins your game with $\ell$ queries. Note that $\epsilon_\ell$ form an increasing sequence.

Moreover, the advantage in your original game is:
$$
\epsilon=\epsilon_{2k+1}=\sum_{i=k+1}^{2k+1}\epsilon_i-\epsilon_{i-1}.
$$
As a consequence, at least one of the differences is bigger than $\epsilon/(k+1)$.

Run $\mathcal{A}$ for an $\ell_0$ such that $\epsilon_{\ell_0}-\epsilon_{\ell_0-1}$ is not too small. The probability that $\mathcal{A}$ wins with $\ell_0$ genuine shares is higher than the probability with a fake share by at least  $\epsilon_{\ell_0}-\epsilon_{\ell_0-1}$, otherwise $\mathcal{A}$ could be used to improve $\epsilon_{\ell_0-1}$.

As a consequence, $\mathcal{B}$ wins with advantage at least $\frac{(\ell_0-k)(\epsilon_{\ell_0}-\epsilon_{\ell_0-1})}{2k}\geq \frac{(\ell_0-k)\epsilon}{2k^2}$.

So the degradation is polynomial in $k$ not exponential.


Extra attributes in a certificate signing request When creating a certificate signing request, there is a part where openssl says "Please enter the following extra attributes to be sent with your certificate request". One of these is a challenge password.

Under what circumstances will this password be needed?

From RFC 2985:

  The challengePassword attribute type specifies a password by which an
  entity may request certificate revocation.  The interpretation of
  challenge passwords is intended to be specified by certificate issuers
  etc; no particular interpretation is required.

This has also come up over at Information Security Stackexchange with the TL;DR being it's the password you set during the certificate request to share a revocation password with the CA, this however is rarely to never used in practice, because CAs nowadays have "normal" log-in mechanisms just like any other website and use them control revocation.


How can there be insecure elliptic curves if the discrete logarithm problem is hard? The discrete logarithm problem is the mathematical trap door function underpinning elliptic curve cryptography. If it's naturally hard to climb back through the trap door, how can there be insecure elliptic curves?

Any answer would be most beneficial for me if it remained light on the math, if that's at all possible.

Discrete Logarithm on elliptic curves is hard in the following sense: on an $n$-bit curve, solving DL has cost $2^{n/2}$. Thus, this is infeasible only as long as $n$ is large enough to make that cost prohibitive. A 256-bit curve is large enough; a 60-bit curve is not.

Also, some curves have a special structure which can be leveraged to compute DL faster. Notably:

If the curve order is not prime or does not have a big prime factor, then DL is easier (the same applies to normal non-curve DL).
Some curves have a low embedding degree, which allows for converting DL on the curve into a comparatively easier DL in the multiplicative subgroup of a finite field extension. This is very heavy in maths. If the curve is somewhat weakened but not too much, then it can still be safe while allowing computation of a pairing, an algebraic operation which is useful for some complicated cryptographic protocols (e.g. identity-based encryption).
Some curves make it easier to implement them securely, e.g. without leaking secret information through side channels.

Generating a new curve entails trying out equation parameters and checking that the resulting curve is not one of the known “bad cases”. In practice, a non-prime order is the most frequent case; for 256-bit curves, you need to try a hundred curves or so before getting one with a prime order. Curves with a low embedding degree are extremely rare, and easy to check for.


Linear-Feedback Shift Register in Mod 3 I have an exercise for a crypto class that I'm working on and trying to understand. In the problem I have a Linear-Feedback shift register working in mod 3 with digits {0, 1, 2}.

The LFSR is using a recurrence relation of degree 2 which looks like this
$Z_{i+2}=C_0Z_i+C_1Z_{i+1}$

I also have part of the keystream $S=...11022...$

I am looking to find $C_0$ & $C_1$ along with
the three keystream numbers that follow and precede $S$

Unfortunately I have no examples to work off so I'm confused on how i'd start even with finding $C_0$ & $C_1$?

Given any LFSR equation $$Z_{i+L}=C_0 Z_i+C_1 Z_{i+1}+\cdots+C_{L-1} Z_{i+L-1},$$ over any field, you can rewrite it as a linear system
$$
\left(
\begin{array}{cccc}
Z_{i} & Z_{i+1} & \cdots & Z_{i+L-1} \\
Z_{i+1} & Z_{i+2} & \cdots & Z_{i+L} \\
 \vdots & & & \vdots \\
Z_{i+L-1} & Z_{i+L} & \cdots & Z_{i+2L-2}\\
\end{array}
\right)
~
\left(\begin{array}{c}
C_0 \\
C_1 \\
\vdots\\
C_{L-1}
\end{array}\right)
=
\left(
\begin{array}{c}
Z_{i+L} \\
Z_{i+L+1}\\
\vdots\\
Z_{i+2L-1}
\end{array}
\right)
$$

and solve it by using linear algebra, since the right hand vector and the matrix entries are obtained from the observed keystream sequence $(Z_t)$. You will need $2L$ keystream symbols to obtain the coefficients uniquely.

In this case there are faster ways of solving such a system, such as the Berlekamp Massey algorithm, which recursively finds the solution with the smallest $L$, given the keystream $Z_t.$ See the answer to the question berlekamp massey to construct minimal lfsr? for more details.


Feldman's VSSS: Showing the Correctness of shares that are Consistent This is something with which I am struggling to get my head around.

In Feldman's VSSS, I am aware that the Dealer broadcasts exponentials $a_{1},...,a_{t-1}$ of the secret $K$ and the coefficients in the secret polynomial of Shamir's SSS. The users can then combine this information with their knowledge of the public key values $x_{i}$ to verify the consistency of their key share.

What if we are in the presence of a fraudulent Dealer who, in addition to altering the key shares in such a way that the secret cannot be recovered, also attempts to alter the secret in such a way that the participants believe that they are in possession of consistent shares following Feldman's scheme?

In this case the shares of the participant will be Consistent but not Correct.

If $y_{i}$, $x_{i}$, $a_{i}$ and $K$ were the values before the change of values by the Dealer and $y'_{i}$, $x'_{i}$, $a'_{i}$ and $K'$ the values following the change. Then what if:

$g^{y_{i}}$ $\equiv$ $g^{K} (g^{a_{1}})^{x_{i}}\dots(g^{a_{t - 1}})^{x_{i}^{t - 1}}$ $mod$ $p$

and  $g^{y'_{i}}$ $\equiv$ $g^{K'} (g^{a'_{1}})^{x'_{i}}\dots(g^{a'_{t - 1}})^{x' \hspace{0.5mm} ^{t - 1}_{i}}$ $mod$ $p$ $\hspace{2mm}$ ?

My question is that in this case, are the participants in the scheme aware that the secret they can collaborate to form is incorrect? If so why?

There is no such thing as an incorrect secret. There is just some secret, that must be uniquely defined by the distribution phase.


Is a private RSA key vulnerable to a chosen plaintext encrypted with that private key? I grasp that having known plaintext encrypted with the public key doesn't provide a means of discovering the private key (that being the whole point...).

But if one were in a situation where they didn't have access to the private key, but did have access to decryption by the private key, would the actual key be vulnerable?

So the attacker generates a plaintext and passes it to the decryption program as though it were a message encrypted with the public key. That plaintext thus gets transformed via the private key (though instead of going from ciphertext to plaintext as usual, it goes from plaintext to ciphertext). Would that plaintext-ciphertext pair reveal information about the private key or is it similar to trying to deduce the private key from a known plaintext and ciphertext pair encrypted using the public key?

On that note, is it possible to deduce the public key from a known plaintext and ciphertext encrypted with it?

With RSA, there is no known way to deduce the private key based on chosen ciphertext; that is, even if the attacker has oracle access to the private operation, the key is still safe.

However, this doesn't mean that it's safe to give an attacker this access; he can't deduce the key, but he can use this access to decrypt anything he wants (and this is the nonobvious part) he doesn't have to reveal what he's decrypting to the RSA implementation.  That is, even if you design the implementation to attempt to not tell him the decryption of a specific message, he can decrypt that message anyways.

The technique he would use is called 'blinding', and here is how it works; assume that the attacker has a ciphertext $C$ that he wants to decrypt; what he does is pick a random number $r$ and compute: $C_{blind} = r^e C$ (where $e$ is the public exponent).  He then presents $C_{blind}$ to the Oracle for decryption.

Now, $C_{blind}$ is effectively independent of $C$; the Oracle cannot deduce any information about $C$ (because for every possible $C$ value, there is a value of $r$ that makes it work).

The Oracle then returns $P_{blind} = C_{blind}^d = r C^d$.  The attacker then computes $P = P_{blind} r^{-1} = C^d$, which is the decryption he is looking for.

As for your second question; whether it is possible to deduce the public key, no, from a single plaintext/ciphertext pair, it isn't possible.

However, from two plaintext/ciphertext pairs, it is (as long as the public exponent $e$ is sufficiently small).  Here is how it works: if we have a plaintext/ciphertext pair $P_1, C_1$, we know that: $$P_1^e - C_1 = k_1N$$ where $e$ is the public exponent, $N$ is the modulus, and $k_1$ is some integer.  If we have a second pair $$P_2^e - C_2 = k_2N$$ we can then compute $$gcd( P_1^e - C_1, P_2^e - C_2) = gcd(k_1N, k_2N) = N gcd(k_1, k_2)$$ $gcd(k_1, k_2)$ is almost certainly a small integer; allowing us to recover $N$.

If we don't know $e$ apriori, we can just search through the various possibilities (we're assuming $e$ is small, hence there aren't that many)


Is there a multiple asymmetric encryption algorithm, which requires all private keys to reveal the secret? I am looking for an asymmetric encryption algorithm, which allows to encrypt a secret with multiple public keys, but to reveal the secret all private keys must be used. You shouldn't be able to tell how many times secret was encrypted from ciphertext length. Ciphertext can be decrypted in reverse sequence as it was encrypted.

RSA would be perfect, but it can only encrypt shorter messages than its key length. And the output is same as key length.

@Erez points to the simple and often good enough solution. In more general terms, you want to split the private key knowledge into several "shares" such that all of them are needed to actually obtain the private key. This calls for a few comments:

To make the splitting/sharing easier, you can do things indirectly: generate a random symmetric key K, encrypt the RSA private key with K, and so the splitting over K. Thus, whatever splitting mechanism you use, you need to do it only on K, which is small enough to make it easy and allow for short "shares"; it is also "structureless" (it is a bunch of uniformly random bits) which may avoid some problems.
The simplest form of splitting of a secret into n shares is a XOR: for a secret K, generate n-1 random values ri of the same size. Share si is then the value ri, except for the last share sn which is equal to the XOR of K and all the ri together. It is easily shown that the XOR of all shares yields K, and without all the shares you have absolutely no information on the secret K.

Shamir's secret sharing, that @Erez points to, is just a generalization of that XOR mechanism, to support for a threshold: making n shares such that any t of them (t is lower than n) allow reconstruction, but t-1 shares yield no information whatsoever. When t = n, Shamir's secret sharing becomes the XOR-based mechanism described above.
A very nice feature of such "private key split" is that it is entirely done on the key holders side. From the point of view of whoever encrypts, this is plain asymmetric encryption (say, RSA).
When you use a private key sharing, there is a potential conceptual problem: though all shares are needed to decrypt the data, the reconstruction must occur "somewhere", and all people who witness the reconstruction learns the complete secret. This gives them the power to decrypt alone other messages encrypted with the same key. Depending on your context, this may or may not be a problem.

Protocols that solve that issue are called "group decryption" or more generally "multi-party computation". Such a protocol would make share holders participate in a common decryption, such that at the end of the protocol all participants learn the decrypted value, but not the shares from other share holders. There are many variants depending on the threshold you want to achieve, the number of communication rounds, the sizes of individual messages, the number of passively or actively cheating share holders you want to tolerate, whether you want traitors to be revealed... This is a complex research area. Start with this question for some pointers.


Multiple attributes under shuffled differential privacy Notation: eps_c (epsilon central), eps_l (epsilon local), n (number of users), d (number of attributes). A single attribute A_i may have |A_i|=r different values for i in [1,d].
Let's suppose each user holds d discrete attributes (e.g., A_1 = Gender with 2 values, A_2 = Age ranges with r_2 values, ..., A_d = Hours online with 24 values).
Some papers like [1], provide amplification for the generalized randomized response model (a.k.a. k-RR) if eps_c <=1. That is, the central privacy must be equal or less to 1 such that eps_l (local) to be amplified.
If we want to collect many attributes (d>1):

Can we set eps_split = eps_c / d <= 1? This would imply a 'total' central privacy greater than 1 depending on the values of eps_split and d.

Or, is it strictly necessary that for a population n, that eps_c = d*eps_split <=1? This would imply that no matter how many attributes you want to collect, the amplification only holds if the central privacy guarantee remains below or equal to 1.

In the same sense, if only (2) holds, if instead of splitting eps_c/d for each attribute, we randomly sample a single attribute per user and spend the whole eps_c on it. Does the amplification use n (the total number of users assuming a totally random sampling technique) or n/d (the number of users answering each attribute)?
[1] Balle, B., Bell, J., Gascón, A. and Nissim, K., 2019, August. The privacy blanket of the shuffle model. In Annual International Cryptology Conference (pp. 638-667). Springer, Cham.
Thank you for your time and help on this subject.

The theorem in the paper you refer to only assumes that $\varepsilon<1$ because it simplifies the analysis & the proof — amplification happens regardless of the value of $\varepsilon$. If you look closer at the proof (page 10), you can find a tighter formula: the result holds for any $\varepsilon$ and $\delta$ such that $\mathbb{P}\left[\frac{N_1}{N_2}\geq e^\varepsilon\right]\le\delta$, where $N_1$ and $N_2$ are independent variables sampled from $\text{Bin}\left(n-1,\frac{\gamma}{k}\right)$.
If, instead of bounding that quantity using Chernoff bound and assumptions on $\varepsilon$, you estimate it numerically, you obtain much smaller values of $\varepsilon$ and $\delta$, which show that amplification happens regardless of the value of $\varepsilon$. In a paper I co-authored, we do exactly that; the problem is different but the math ends up being the same. This is Theorem 3, you can see the comparison between the closed-form formula and the numeric estimation on Figure 2.


Can Elgamal be made additively homomorphic and how could it be used for E-voting? Elgamal is a cryptosystem that is homomorphic over multiplication.

How can I convert it to an additive homomorphic cryptosystem?
How can I use this additive homomorphic Elgamal cryptosystem for E-voting purpose?

Please explain with examples.

Elgamal can be made additive by encrypting $g^m$ instead of $m$ with traditional Elgamal for some generator $g$ (usually the same one used to generate the public key). This variant is sometimes called exponential Elgamal. The difficulty is decryption: running the standard decryption gives you $g^m$ and recovering $m$ requires you to solve the discrete log. As long as $m$ is small, this can be done algorithmically or with a lookup table.

See this answer for how to build a voting scheme from it (or this paper for the full description). Exponential Elgamal is great for things like voting because after you tally up all the votes, you'll still have a number that is reasonably small.

Paillier is additively homomorphic as well, and can support a proper decryption of any sized message. Dispite this, many voting schemes still use exponential Elgamal because it is faster, easier to do distributed key generation, and not patented.


Known Plaintext attack against XTEA? I'm looking for information on known-plaintext attacks against XTEA. I'm most interested in the worst case scenario: if an attacker has all 8 bytes of input and all 8 bytes of output, how much information can they learn about the key (and how easily). Or I guess worse than that is if they have multiple such pairs of blocks produced with the same key.

Additionally, suppose an attacker knows all 8 bytes of plaintext, but only X bytes of ciphertext (including their position in the block). Then what kind of information can they determine about the key? (this has applications when other modes, like CTR, are used and a crib occurs in the first block).

I know no published attack against the XTEA algorithm, much less one working with a few plaintext/ciphertext pairs and a random key.

There are published attacks against reduced variants of XTEA, AFAIK either with much less than half of the 64 rounds, or up to 36 rounds but assuming related or/and weak keys in addition of known plaintext. Often, especially as the number of rounds grows, much more than one plaintext/ciphertext pair is required.

By the metric of how much extra rounds this Feistel cipher has above the threshold where it it gets broken, XTEA seems on the safe side.

The single known practical weakness of the XTEA algorithm is its 64-bit block size, which opens the door to attacks on modes of operation and protocols using XTEA, especially when the amount of data involved reaches a few megabytes gigabytes processed with the same key. We also must fear attacks against implementations of XTEA, in particular by side-channel cryptanalysis.


AES decryption of MixColumn In the encryption of MixColumn you use the constants 01, 02 and 03. I don't understand why the inverse of 01 becomes both 0D and 09. I also don't understand how you get 01, 02 and 03 in the first place which is probably why the decryption doesn't make sense to me. I would appreciate any help with understanding how to calculate these values.

The MixColumns $MC$ and InvMixColumns $IMC$ implement matrix multiplications. These two matrices defined over Galois Field $GF(2^8)$ and they are inverse of each other.

$$MC \times IMC = I_4$$

To find the inverse, one can use the Gaussian Elimination method. But finding the inverse a bit tricky, since you will need the inverse of the pivot elements. The inverse in $GF(2^8)$ can be found by using the Extended Euclidean Algorithm.

In general, instead of calculating the inverse, the invMixColumn matrix copied from FIPS 197 or  AES submission of  Rijndael.


Is there practical Attack on A5/1 Cryptosystem? There are several and several attacks on A5/1 Cryptosystem, but most of them are impractical. In 2008, Elad Barkan , Eli Biham and Nathan Keller release a practical attack on GSM.

Is there any production of the attack? In another words, does exist any physical production that gets ciphertext as input and get Key or Plaintext in output(due to the EBN attack)?
Thanks.

Elad Barkan has(Possibly had) a company called KeySee Software.
In Elads's words: "KeySee supplies software for off-the-air interception of GSM communications, as well as consulting services for computer security and encryption."

Knowing Elad, and the literature, I have every reason to believe they deliver what they promise.

As others mentioned in comments, Rainbow tables are available for download, the computational requirements don't seem all that difficult to do it yourself in 2019. Obviously there is a difference between having the Rainbow tables and a functioning attack.


How to calculate leaked information from a check digit Given a check digit calculated using mod 11, of an encrypted numeric sequence of 8 digits, how much information can be known about the plaintext?

More specifically, a single 3DES encrypted CBC block for which the check digit of the plaintext is known, would reduce by what factor the complexity in discovering the plaintext (and key)?

A second question is whether using the check digit hash as the IV is a good idea?

Example:

Given

encrypted = 0x672985cdd0484611

How much the information

checkdigit= 9

Will help in finding

plaintext = 12345678
key = 0x5e8667a439c68f5145dd2fcbecf02209  # md5(87654321)
iv = 0x45c48cce2e2d7fbd  # md5(9)[:8]

The motivation is to know if the check digit can be stored in plaintext alongside the encrypted data (always one block), and used as seed for the IV.

Assuming the mod 11 check digit is among 0123456789X, disclosing it reduces the number of possible plaintexts among 8-digit numbers by a factor of about 11 (from 100000000 to about 9090909; exactly how much depends very slightly on the value of the check digit), thus reveals about $\log_2(11)$ bits of information about the plaintext, that is just a little less than 3.46 bits.

The consequences vary depending on context. If the goal of an adversary is to rule out that a plaintext is a certain value, there are about 10 chances out of 11 that knowing the check digit allows the adversary to succeed.

In the hypothesis of "a single 3DES encrypted CBC block for which the check digit of the plaintext is known" because it is used to derive an IV using a deterministic method allowing to recover that check digit (as in the example where the IV is the MD5 hash of the check digit, truncated to 8 bytes), the worse problem might not be that the check digit is revealed by the IV. Another serious issue is that the same plaintext is always enciphered to the same ciphertext, which is foremost among what an IV is designed to prevent. If that's tolerable, we could just as well use 3DES in ECB mode on a single block, and live happier with a simpler system using no IV, and leaking less about the plaintext.

Knowing the check digit of the plaintext does not much help recovering the key. In the example, the key can best be found by enumerating the candidate keys (assumed to be the MD5 hash of a small string of decimal digits), and deciphering the ciphertext until the plaintext makes sense. The check digit still helps, in that it reduces the (already remote) odds of guessing the wrong key, by a factor of 11; however another ciphertext helps even more in this regard.


Does the XML Encryption flaw affect SSL/TLS? A "practical attack against XML's cipher block chaining (CBC) mode" has been demonstrated:
XML Encryption Flaw Leaves Web Services Vulnerable.

Does this weakness of CBC-mode which is used here also affect SSL/TLS?

Related: Is the CBC weakness in XML Encryption a new discovery? Are other applications vulnerable?

No; the problem with XML is that it doesn't include a Message Authentication Code (MAC), or anything else to validate the ciphertext; the only validation that XML does is checking if the CBC padding is sane.  The attack uses that as an Oracle to decrypt data; the attacker generates an encrypted region with the last two blocks being carefully chosen; if the last block decrypts to a sane padding, that gives him information on what the last block decrypted to).  SSL/TLS always includes a MAC along with the encrypted data; hence if the attacker generates his own encrypted data, the MAC will fail (because he can't generate that), and so the attacker will get no details on what the decrypted data looked like.

Now, there is one exception to that; when Vaudenay first discovered this attack (Password interception in a SSL/TLS channel), he realized that (because of the order of operations that TLS uses, it decrypts first and then checks the MAC) if the attacker could distinguish between a padding failure and a MAC failure, he could still use this attack.  Now, in this case, actually trying this attack always causes the TLS connection to drop on the first attempt (and hence it's useful only if you can get the system to set up repeated sessions with the same plaintext); nevertheless, nowadays I would hope that all SSL/TLS implementations try to be careful to not leak that to an attacker.


Is there an equivalent to an RSA UFO in lattice-based cryptography? So there's this concept within the realm of RSA cryptography called an RSA UFO. It is an extremely important function in the context of cryptocurrency. When starting up a cryptocurrency the creator(s) need an initial cryptographic setup. Worst case scenario an untrustworthy initiator uses the startup information to wreak havoc on the cryptocurrency. Its better to have a number of people collectively create the startup information, but you still can't trust them. An RSA UFO allows the creation of the initial cryptography in such a way that even the creator doesn't know the initial values; trustless setup of a cryptocurrency.

Lately with all the fuss about quantum-safe cryptography, especially lattice-based cryptography, I was just wondering if a functional equivalent to an RSA UFO exists in the realm of lattice-based cryptography.

According to your link, RSA UFO means:

  Random moduli are also called RSA UFOs (Unkown Factorisation Objects).

If the definition of an RSA UFO is a modulus generated so that no one knows the factorization, this issue does obviously not exist in lattice-based cryptography, since the factorization problem is never used there. More generally, it is much easier to securely and distributively generate the random parameters of various cryptographic constructions in lattice-based cryptography; distributively and securely generating an RSA modulus with unknown factorisation is a notoriously very hard problem, whose solutions are usually quite inefficient (the link you give ends up with a modulus of total size 81kbits, which is quite huge). In contrast, public parameters in lattice-based cryptography will in general just need to be primes and some public random matrix, which is easy to generate securely and efficiently.


Fixed-prefix IV in CBC mode I know the Initialization Vector needs to be unpredictable. Does it apply to the IV as a whole, or to every bit in the IV?

I have multiple devices with poor entropy sharing the same key and I want to ensure the IV is unique. I am using AES-128 CBC.

Can I use some bits of the IV as the ID of the device? For example can I set the first 32 bits of IV to the IP address of the device and the remaining 96 bits to a random value? Is this still considered 'unpredictable'?

It is the IV as a whole that needs to be unpredictable... but knowing some bits would make guessing the IV easier.

The requirement of an unpredictable IV has to do with chosen plaintext attacks. If the attacker can predict the IV, they can choose the first block of plaintext such that they can verify any guesses they have for the content of previous messages. For this to work, they must be able to end up with exactly the right input to the cipher – even a one-bit difference will generate a completely different ciphertext block and not verify the guess. (It would verify a slightly different "guess", which might sometimes be important, so getting very close to predicting could still be a problem.)

By using some bits of the IV on the predictable IP address, you make it that much easier to guess the rest. If the other 96 bits were completely random, the attacker would have a $2^{-96}$ chance of correctly guessing it, which is uselessly small. If it was less random then the attacker could have a chance.

By reducing the random part of the IV you also make IV collisions more likely (between IVs of the same device). The situations where this would be helpful are few. For example if you have a good CSPRNG but equal/close seeds on the different devices. If that was the case you would be better off seeding the CSPRNG with the IP/MAC in addition. Or using deterministic derivation of IVs as CodesInChaos suggested.


How to key an HMAC with keys from separate mutually untrusted parties? The problem is as follows:

There are two parties, both of whom would like to HMAC a message with a key. Although the keys are known to one another, both parties do not trust that the other one created a truly random key.

The HMAC result must not be easily attackable by a third party. So it is necessary the final key has substantial entropy whether or not one party didn't supply any.

In an optimistic world, both parties generate cryptographically secure 256-bit random numbers to key the message with.

In a less optimistic world, one party generates a secure 256-bit random number but the other party gives back 256 bits of data with hardly any entropy at all whether due to laziness or malice.

If both parties are lazy and/or malicious (worst case), then we can accept that failure is impossible to avoid. We assume for the problem that at least one party sees a good key as being in their best interest.

What would be the best way to structure an HMAC call so that I can use two keys such that one key being weak only means the strength is lower-bounded by the good key and not completely sabotaged due to some sort of subtlety?

The ideas I have are

HMAC(message, key1 || key2)
HMAC(HMAC(message, key1), key2)
HMAC(message, HMAC(key1, key2))

However, this is starting to feel like one of those problems where there is some subtle issue that I'm probably unaware of with all these seemingly straightforward choices.

Edit

After some discussion below, I feel I may need to include some more important details.

Party 1 will hand off an allegedly random 256 bit string to Party 2. Party 2 will also generate an allegedly random 256 bit string. Party 2 will be responsible for generating the HMAC but Party 1 will have the opportunity to reject the result. Both parties know each other's secrets and at least one party cares about having a strong secret although it is possible that the other party is malicious or lazy.

I would just concatenate.

Two 256-bit keys lead to a 512-bit key which is short enough for HMAC with common hash functions to use as is. XOR would allow the second party to easily choose a related key (and has worse behavior when neither key is perfectly random). Hashing and double HMAC use more resources without a clear benefit, unless you care about the size of the key, in which case hashing would be the way to go.

If you had longer/more keys, concatenation would become equivalent to hashing, because HMAC internally hashes keys that are longer than block size (512+ bits for all SHA-x).


What is bignum-free RSA? I recently saw a claim that BearSSL has a bignum-free implementation of RSA. What does this mean? I don't see how one could implement RSA without bignum arithmetic.

First things first, I would not have described BearSSL as being "bignum-free". However, it is true that it does not have a generic implementation of big integers; what it contains is a generic implementation (actually several) of big modular integers. And it matters.

About low-level multiplications

Software libraries run on some hardware and cannot use anything else than what the hardware offers. Regarding multiplications, a common CPU will offer a 32-bit multiplication with a 64-bit result. For instance, the x86 line of CPU has an assembly opcode called mul that multiplies two 32-bit unsigned values (one in the eax register, the other in a register passed as parameter) and yields a 64-bit result, split into two 32-bit halves in eax and edx. When writing C code, you usually obtain a result of the same size as the operand, i.e. if you multiply two uint32_t values, you get a uint32_t result; to obtain the full 64-bit result, you need to use some casts into uint64_t. When BearSSL was first released, this 32×32→64 multiplication was the largest that the implementation was using.

Some architectures do not offer a 32×32→64 opcode. In particular, the ARM Cortex M0 and M0+ have an efficient 32×32→32 opcode, but a 32×32→64 multiplication must use a software routine that is considerably slower (we are talking about 1 cycle vs 40 cycles here) and also often non-constant-time. Some other have a 32×32→64 opcode, but it is not constant-time (e.g. ARM Cortex M3). This is why BearSSL also offers implementations that use only 16×16→32 multiplications (these are codenamed "i15" in the BearSSL API).

More recently, I added some code called "i62" which leverages the 64×64→128 opcodes that are available on some big architectures, in particular x86 in 64-bit mode. This requires using some compiler-specific extensions, because (in general) there is no uint128_t type made available (see here for the relevant source code; this is done only for modular exponentiations, as used in RSA).

About generic bignum code

Many cryptographic libraries include a generic "big integer" implementation: this is a set of memory structures and functions that can represent and perform arithmetic operations on integers which are not a priori limited in length. In OpenSSL, this is called BIGNUM (or "BN"). Internally, each such big integer is a structure that references an array that contains the integer contents, split into elementary "limbs" (in the same way that when you write an integer in decimal, you represent it as a sequence of digits); other structure elements contain the actual integer length and relevant memory management information.

Writing a generic big integer library is a natural way of doing things: a good software engineer thinks top-down and writes code bottom-up. Thus, since many asymmetric cryptographic algorithms are expressed over large integers (e.g. RSA, DSA, ECC...), that engineer will start by writing a good, reliable big integer library, then use it to implement the relevant algorithms. As a second phase, for pure performance reasons, some of the most expensive operations in the said algorithms will be reimplemented with dedicated code (that's how OpenSSL now has dedicated assembly code with AVX2 opcodes that handles, specifically, the modular exponentiations in RSA for RSA keys of length exactly 2048 bits). Also, when implementing cryptography in some languages, a big integer library is already there and ready to be used (e.g. Java's java.math.BigInteger).

Now, BearSSL does not follow that road, and there is a reason. BearSSL does not include a generic "big integer" library. It has something which somewhat looks like it, but really implements operations on modular integers, i.e. integers considered modulo a given (odd) integer. The functions are not part of the public API (this is for internal use) but are documented here. Implementation is in the src/int/ directory.

The underlying reason is the quest for constant-time code, so as not to leak information through timing-based side channel attacks, in particular cache attacks. To really defeat such attacks, the implementation must use a memory access pattern that does not depend on secret information. However, a generic big integer implementation cannot be constant-time, because values are allocated in buffers which are dynamically sized, depending on the represented integer; therefore, an attacker who can observe the memory access pattern of some code will be able to notice when an integer value is "short" or "long".

To follow a strict constant-time discipline in BearSSL, a modular integer is handled in an array whose length matches that of the modulus, not that of the value itself, and all array slots are always accessed, even in cases where some contains only zeros. Internally, that concept is described as "announced bit length": a big integer structure, in its header, states a bit length which is that of the modulus, and all operation loops work on that bit length, not on any length inferred from the value (the big integer "structure" is actually a simple array of words, and the "header" is the first word in that array).

It shall be noted that usual cryptographic libraries like OpenSSL have a long history, which began way before cache attacks were invented; moreover, their "big integer" library is often part of the public API, and thus they cannot simply remove it without breaking compatibility with existing applications. BearSSL is relatively recent (I started it in 2015), and thus I could design its structure and API with full knowledge of cache attacks, hence the lack of generic big integer code, and also the fact that the code for modular integers is not part of the public API (so that I may change things later on, if necessary).


One Time Pad Key Distribution For multiple OTP keys, why not do this:

Key = Hash[(EC)DH Shared Secret + Counter]

The counter will increase per message, and the output of the hash will be random for each new unique input into it. What are the problems or weaknesses with this design??

EDIT:
For clarification: both parties will have the shared secret from an ECDH exchange, random numbers from Pythons os.urandom for generating the ECC key

This principle is commonplace, it is a key derivation from a shared secret. The academic thing to do is to use a Key Derivation Function or a MAC where hash of a concatenation is used, perhaps
$$\operatorname{HMAC-Hash}\;[\;\text{Key}=\text{(EC)DH Shared Secret},\,\text{Message}=\text{Counter}\;]$$

We call the output a derived key, and it can be a one-use key.

I would not call it a One Time Pad key, even if it is used only once to mask some payload with XOR, because the usual assumption is that a One Time Pad (key) is truly random, and this is only pseudo-random.


Finding Private key in RSA with public key, cipher text and plain text Is there a known 'non-brute force' method of determining a private key in an RSA system when all other parameters are know?

I found the values of a ciphertext ($C$), its corresponding plaintext ($P$) and the values of the public key ($e$,$N$) are known.

We know that:
$$P = C^d \mod N$$

Here, the value of $P$ is known (the cipher text has been decrypted) and the values of $C$ and $N$. Given these parameters, is it possible to find $d$?

Also, how do I find an integer $k$ such that $(k\cdot N - P) = C^d$ ?

Any suggestions/discussions are welcome.

No, there is no known efficient method to find an RSA private key from public key, ciphertext and plaintext, including when no padding is used and $e=3$. The best known method is factoring the public modulus, which then trivially allows to find a working private key. Factoring is considered brute force, or tantamount to that. The best known factoring method for a public modulus of cryptographic interest in RSA is GNFS.

We can prove the assertion in the first two sentences, modified by adding that the ciphertext was not chosen by an adversary, and that the hypothetical method works including for small public exponents $e$. The idea is that any such method could be turned into a factorization algorithm for any $N$ suitable as RSA key: we chose a small odd $e$, which with fair odds is coprime with $\varphi(N)$; we choose some plaintext, and compute ciphertext by whatever method is normaly used in the RSA variant considered; we can now apply our hypothetical efficient method that finds a private exponent $d$; we compute $f=d\cdot e$, which is such that $f\bmod(p-1)=1$ for any prime $p$ dividing $N$, and that's enough to efficiently factor $N$ (see this answer).


RSA-OAEP Padding scheme Honestly I'm really confused about padding in RSA scheme. I don't study computer science, and I'm a beginner learning cryptography (self-taught). Can anyone  give me suggestions?

Direct use of textbook RSA for encryption is very insecure. For example, a guess of the plaintext can be checked: if what's encrypted is a name on the class roll, enciphering all names on the class roll until getting the ciphertext breaks confidentiality. There are several other attacks.

That motivates RSA-OAEP. It turns textbook RSA, a hash, and a source of random bits, into a demonstrably secure encryption scheme. Encryption of message $M$ first transforms $M$ into padded message $X$ by mixing it with random bits and applying reversible transformations with the hash; then enciphers $X$ into $X^e\bmod N$, that is per textbook RSA encryption. Decryption starts by textbook RSA decryption, yielding $X$; then the padding is undone, yielding $M$ or an error indication.

I essence, the distribution of $X$ is random enough that textbook RSA becomes secure. A proof of that can be made for the strongest definition of security of a cipher, IND-CCA2, and under some hypothesis:

the RSA problem of finding a random $X$ given $X^e\bmod N$ is hard;
the hash is undistinguishable from a public function selected at random;
the source of random bits is indistinguishable from one producing uniformly random and independent bits;
a decryption device given a cryptogram only outputs the correct plaintext or an error indication (it does not leak any other information).

A (highly technical) reference proof is in Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern's RSA-OAEP Is Secure under the RSA Assumption, in Journal of Cryptology, 2004. A more gentle text is David Pointcheval's How to Encrypt Properly with RSA?, originally in Cryptobytes 5n1, 2002.

The practical form of RSA-OAEP is named RSAES-OAEP and defined in PKCS#1 v2.2.


In Diffie-Hellman, can everything be sent in plaintext? I think my limited understanding of DH might be messed up - what's wrong with this scenario?

C wants to connect to S.
C has an ECDSA public key that it trusts belongs to S.

Here's what happens:

C connects to S.
S sends its part of the DH key exchange, signed to prevent tampering*.
C sends over its part of the DH key exchange, in plaintext and without a signature.
C and S now calculate the shared key.
The shared key is used for all further communication.

*Add padding, etc. to prevent forgeries and reuse.

A MitM can't lie to C, because it can't forge the signature, and if it lies to S, it isn't really gaining anything, because if it could effectively pretend to be C without routing everything back through C, it wouldn't have to make a MitM attack in the first place.

TLDR:

Diffie-Hellman key exchange works differently
Yes, DH is vulnerable to MitM.

Long answer:

Diffie-Hellman key exchange isn't about sending the public key with some kind of signature, but about negotiating the key.

Quick DH explaination (note: these values are very insecure):

Alice and Bob publicly agree on two values:

The generator - g. Let's say this is 3.
The prime modulus (obviously a prime number) - p. Let's say this is 17.

Both Alice and Bob think of a secret value, let's call this x

Alice's secret value is 15
Bob's secret value is 13

They calculate yet another values, using this formula: g^x mod p

Alice: 3^15 mod 17 = 6
Bob: 3^13 mod 17 = 12

Alice sends the result to Bob and vice versa
They both calculate the final value like this:

Alice: 12^15 mod 17 = 10
Bob: 6^13 mod 17 = 10

They have negotiated a key and Eve doesn't know what's the value of this key (the negotiation requires a lot of values to be exchanged and therefore simply listening but not participating in the exchange doesn't let you see the established key)

MitM example:

Imagine this "circuit":

Alice -- Eve -- Bob

Eve changed the values when they were exchanging them, decrypts everything that comes from Alice with the key she has exchanged with Alice, and then encrypts it with the key she has exchanged with Bob and vice versa.

Conclusion:

There's a need for some kind of "pre-shared secret" with DH. DH itself is not MitM-proof. For SSL/TLS that is Certificate Authorities. Instant messaging often uses OTR (which involves a question that only the actual other party should be able to answer - pre-shared secret).


What is an "anonymous admissible timestamp"? Can anybody explain the term "anonymous admissible timestamp" to me? Could you show a case where it is useful to apply it?

I came across this term in the comments of a question on the StackExchange Computer Science site.

What he meant is quite unclear. It could be that he's referring to a Timestamping Authority (TA) (See related RFC like 3161). What they do is basically sign a document/hash with the current time and date and sequential transaction id (IIRC).

Ideally, the TA is public and anonymous, allowing anyone to submit any hash and get a signed timestamp for it, the list of signed transaction freely available for anyone to check and verify.

If I refer to the scenario, the bar could issue anonymous 'tickets' containing a unique and untraceable identifier, meaning the bar doesn't keep tabs (pun intended) to whom a given identifier belongs to. In practical terms, they might just have a check to avoid giving multiple tickets to the same person. When the user wants to get his beer, he gets a stamp from the TA by submitting the ticket content (or hash thereof), and forward the stamp to the bartender. Receiving the stamp, the bartender execute a lookup request to match the ticket to all the related transactions and check the date of the two last transactions (validating the stamp signature as well obviously). If they are separated by at least an hour, the stamp is deemed valid.


Is it possible to carry out multiplication of BGW protocol without communication? I read the following famous two papers related to multiparty computation and I have a question like title.

[AL17] Gilad Asharov, and Yehuda Lindell. "A full proof of the BGW
protocol for perfectly secure multiparty computation." Journal of
Cryptology 2017.
[CDI05] Cramer, Ronald, Ivan Damgård, and Yuval
Ishai. "Share conversion, pseudorandom secret-sharing and
applications to secure computation." Theory of Cryptography
Conference 2005.

In [AL17], authors constructed a protocol that privately computes multiplication given access to the randomization functionality and the degree-reduction functionality. While they also proposed a secure degree-reduction protocol (i.e. protocol to privately compute degree-reduction functionality) without communication, the proposed randomization protocol (i.e. protocol to privately compute randomization functionality) needs n^2 communications.

Authors of [CDI05] showed that a proposed protocol (PRZS) can create a pseudorandom zero-sharing with degree 2t (i.e. the randomization protocol) without communication.

Therefore, I’m wondering whether it is possible to carry out multiplication of BGW protocol without communication if the randomization protocol of [AL17] is replaced by PRZS protocol of [CDI05]. (Except for the communication of input sharing stage and output reconstruction stage)
Moreover, given an application consisting of addition and multiplication, is it possible to construct a multiparty computation protocol based on BGW without communication?

No, it is impossible. We do not know of any way to perform this randomization step without interaction; furthermore, it was shown in this paper that multiplication require interactions in secure computation, in a variety of important settings (including all forms of BGW-style secure computation). Share conversions work for some restricted type of functionalities, but do not allow to evaluate generic multiplication gate over $\mathbb{F}_2$ on secret shares without interaction.

Note, however, that we can have multiparty computation with no interaction (except for sending an encryption of the input and sending back an encryption of the output) in the computational setting, using fully homomorphic encryption (which we can build assuming the LWE assumption).


What is “Implicit Authentication”? What is “Implicit Authentication” in the context of authentication methods?

I searched the Web but could not find any article that describes this.
If anyone can describe it, that would be a great help.

I have seen that used in the context of session keys, to describe how a key is tied to an identity without any certificate relative to that key could only be known by another identified party, without assurance that this party ever held that key.

For example, one generates a random symmetric key, encrypts it using (say) RSA and a public key, and sends the cryptogram to the alleged owner of the public key. Because only knowledge of the associated private key allows to recover the symmetric key, that symmetric key can only be known by the one that generated it and by the rightful holder of the asymmetric key, but it is not yet known if this rightful holder actually knows that symmetric key. There is thus implicit authentication of that symmetric key.

That key can later be used to demonstrate integrity and origin of a message from the holder of the asymmetric key to the originator of the cryptogram that established the symmetric key, using a MAC. As a side effect that demonstrates knowledge of the symmetric key by that rightfull holder, boosting its status from implicit to explicit authentication.

That usage occurs, for example, as "implicit key authentication" in the Key Authentication section of the Encyclopedia of Cryptography and Security, first edition. This is not a recommendation for this book, which I'm seldom using.

Update: reading that reference, I have pretty much turned around my definition. An encyclopedia is useful, sometime.


Meet-in-the-middle with checking complexity In regards to meet in the middle type attacks, I have been considering the amount of operations in order to successfully find a key given two sets of plaintext / ciphertext pairs. All of the sources I have checked have stated that the maximum number of trials that are needed is $2^{n+1}$, however this does not seem to take into account the operations needed to validate key guess.

So taking 2DES as an example where one encryption has an effective key size of 56 bits. A meet in the middle attack against 2DES would need $2^{56}$ encryption plus $2^{56}$ decryption operations resulting in $2^{56}$ possible key matches. However each potential key match would then need to be verified on a second (or more) plaintext / ciphertext pair, adding another two operations to verify each match. The result is a maximum of $4 \times 2^{56}$ operations.

Is there a reason the checks are not included in this attack? Or is there a flaw in my thinking here?

Well, one assumption you appear to be making is that, with 2DES, there will be approximately $2^{56}$ possible key matches.  Actually, there are an expected $2^{48}$ possible key matches; here's why:

Let us assume we're running the meet-in-the-middle attack on 2DES, and consider an arbitrary incorrect encryption trial (that is, we try an encryption key that is not the correct one).  If DES acts anything like what we expect, we'll arrive with an effectively random 64 bit value.  We will do a trial decryption if that value appears somewhere in the decrypt list; there are $2^{56}$ values on that list, and so that specific random 64 bit value will appear an expected $2^{-8}$ times; hence for each incorrect encryption key, we will need to perform an expected $2^{-8}$ verification tests.  There are $2^{56}$ (actually, $2^{56}-1$, however that difference is lost in the noise) incorrect keys, and hence we expect to need to perform $2^{56} \times 2^{-8} = 2^{48}$ tests on incorrect keys (plus the one test on the correct key).

This gets into the more fundamental question of "what do we actually mean when we give a complexity estimate?".  Well, it isn't as straight-forward as you might think; if we say that a specific attack uses $2^{100}$ foo operations, we do not mean that it uses precisely $2^{100}$ of those operations (and never requires $2^{100}+1$ of them), or that it doesn't require any bar operations; what we mean is that the time the attack takes is bounded by those $2^{100}$ foo operations; the time taken by any additional foo operations, or any needed bar operations doesn't significantly increase the attack time, where significantly means "doesn't increase the attack time by more than a factor drastically larger than 1".

Remember, the goal of these estimates is not because we're actually interested in running the attacks; instead, what they're there for is to allow us to be confident that the attack takes much longer than any possible adversary has the budget for.  A factor of 2 might sound significant; however we typically can't estimate the adversary's budget that accurately (especially if we're talking about adversaries in the future); what we attempt to do is to design our systems so that an attack is (say) $2^{40}$ times what an adversary might have; compared to $2^{40}$, a single factor 2 is actually not significant.

Stepping back to your example, what this means that if we have an attack which acts in two phases:

Generate a potential set of solutions (taking time $A$)
Validate those potential solutions (taking total time $B$)

then we'll say that attack takes time about $max(A, B)$; that's because the time taken is dominated by whichever takes the longer (and if they're both the same, the fact that the attack actually takes twice as long isn't a significant factor).

In the 2DES attack (which follows this model), $A$ is much larger, and so we basically ignore $B$ (not because we don't think that it's important, but it doesn't slow down the attack to a degree that we care about).


Security properties and Cryptography objectives applied in algorithms We all know there are five properties of Security. They are:

Confidentiality
Availability
Authorization
Integrity and
Provenance

As Security and Cryptography are co-related these properties also applicable to Cryptography as well (are't they?). I can understand how a Cryptographic algorithms (e.g. AES)  maintain these properties. But what I don't understand how does the last property "Provenance" is applicable to AES or DES/TripleDES ?

There also four objectives  of Cryptography. They are quite same as the Security properties except for "non-repudiation". How does AES or DES/TripleDES fulfils this objective?

AES or DES/TripleDES are just primitives. These primitives aide in building the properties of the system you were describing. The 5 properties are that of the system but not a single algorithm. We need a combination of crypto algorithms sometimes to achieve these properties in certain setup.

Few examples,

Confidentiality of data-in-transit in a "communication system" is achieved by SSL protocol using combination of symmetric (AES) and asymmetric (RSA etc.) crypto algorithms.
Integrity of data-at-rest in a "storage system" is achieved by Hash algorithms
Availability of data could be ensured by having good key management systems, to avoid loss/compromise keys which could make data un-available. Ofcourse there are variety of other high available and fault tolerant designs too with crypto primitives.
Authorization & Authentication protocols like Kerberos are built using symmetric algos again. More modern access controls could be built using Attribute based encryption etc.
Provenance in a cloud storage system is through, "Proofs-of-Storage". Provenance in a cloud compute system is through, "Proofs-of-work". Non-Repudiation in communication protocols are built using digital signatures which in turn could use AES/3-DES internally.

These primitives like AES/DES etc. aide in building much complex security systems. The security properties described are that of the systems but not necessarily the primitives.


Why do we need to use supersingular curve on SIDH? if i'm not mistaken, the supersingular curve's endomorphism ring is non-abelian. but why does it matters? or is it not even related to its endomorphism ring?

There's many different answers to this question, depending on what you mean by "why".

You can't replace supersingular with ordinary and still have SIDH. Supersingular isogeny graphs are regular graphs ((ℓ+1)-regular for the graph of isogenies of degree ℓ). Ordinary isogeny graphs are not in general, so SIDH simply would not work with them.
There is an older key-exchange protocol, proposed independently by Couveignes and Rostovtsev-Stolbunov, which uses ordinary graphs (we'll call CRS this protocol). It is similar to SIDH, but not the same. It is vulnerable to a sub-exponential attack by Childs-Jao-Soukharev, so its quantum security is hard to assess, although the system is not considered completely broken. At security levels that could be considered equivalent to SIDH, CRS is much slower (absolutely impractical).
Recently, Castryck, Lange, Martindale, Panny and Renes introduced CSIDH, which is really the CRS system, where you replace the word "ordinary" with "supersingular", and do some optimizations. CSIDH is much faster than CRS, although slower than SIDH. CSIDH is still vulnerable to the Childs-Jao-Soukharev attack, so its parameters scale worse than SIDH.
CSIDH highlights one of the main reasons we use supersingular curves: it is easy to control their group structure, which in turns makes it easy to have rational torsion points, which allows us to apply Vélu's formulas, which are much more efficient than generic isogeny-computation algorithms.
Finally, going back to SIDH, the Childs-Jao-Soukharev attack does not apply to it. Why? Because the endomorphism ring of supersingular curves is larger (and non-commutative). The Childs-Jao-Soukharev attack requires expressing the isogeny computation problem as an (abelian) hidden shift problem. In the SIDH case, there is no known hidden shift structure. The net effect is that SIDH parameters scale better as security grows.


What cryptographic paradigm is appropriate for this use case? This is a very newbie question...

I have to quickly implement a solution for our application that works like this... We have a binary executable that is given a configuration file. I need to encrypt the configuration file such that a non-trusted user can be given the binary and the encrypted config file (and maybe a public key or something) and he should be able to run the binary with the encrypted file. We're not concerned with the user disassembling or reverse-engineering the binary itself for now.

Could you suggest a cryptography paradigm &/or c++ crypto library that will allow me to do the above? I was thinking of encrypting the config files with a public key, the private key of which would be embedded in the executable but I'm not sure if that is a secure way of doing things.

Thanks

At least you understand that by embedding a key in the software that someone will be able to reverse engineer the binary, extract the key, and decrypt the file. Or they will find the decryption code, put a break-point after it, and dump the decrypted memory.

Since that does not concern you at the moment, you have a few options.

Generate a random AES key, encrypt the file with that key, embed that key into the source code, decrypt the file in your code and store the decrypted information in memory.
Generate a single private key and an AES key. Encrypt the AES key with the public key. In your code you can decrypt the AES key with the private key then decrypt the file with the AES key.

Of those two, 1 seems simpler. Of course in either case, you run the risk of a single user finding the decryption key and writing a simple script that will work on all of your customer's machines.

To "fix" that issue, you could generate a new key (be it AES or private+AES) for each binary you ship. There are still ways to develop a script that would read the binary, extract the machine specific key, and do the decrypt. It will be harder though, but doing this also means you need to track more keys.

Since it sounds like you are not worried about sophisticated attacks, only want to raise the bar slightly to prevent casual users from getting your configuration files, I'd go with #1. Just make sure you understand all the risks.


Crypto that takes n days to solve depending on how many bytes are missing? Is there a good candidate for an algorithm that would takes n days to break depending on how many bytes of the key are missing? I'm writing a story where you need to collect pieces (bytes) of a key and depending on how you have you get an head start in brute-forcing the message.

The message is around 200 chars long (so quite small).  Count on computer resources be what would feasible for a non state-actor (bot nets etc), but still pretty resourceful. The key length / piece length does matter much, but should be viable for 6-8 "pieces"

The main problem I see is that time with brute forcing strong encryption is usually measured in years, or even million of years, and I need it more to be around 3 days per "piece"

You can try 20 billion DES keys per second on a single Nvidia Geforce GTX 1080.

Assuming (roughly) that another algorithm (with much higher keylength than 56-bit) is equally as fast, the bitlength you want for the key is:

$$\log_2(\text{NumberOfSeconds})+\log_2(\text{NumberOfGPUs})+34$$

where $2^{34}\approx 16 \text{ billion}\approx 20\text{ billion}$.

If you want some example numbers, let's do the math:
If we want to wait approximately 3 days (that's $24\times 60^2\times 3$ seconds) and can get hands on maybe the equivalent of 5000 such GPUs using a botnet, that yields about $64$ bits which sounds very reasonable.

What you could do with this is to take AES-128 und give 8 bytes using (8?) puzzles and let them brute-force the remaining 8 bytes. Every unknown byte will increase the brute-force workload by 256.

So TL;DR: Brute-force of 8 bytes (give or take a few bits) sounds like what you're aiming for.


How does the Rijndael 192/256 bits block size mix column works? I am quite comfortable about the 128 bits block size mix column operation, the maths behind it and how to implement it.

However, what about the 192 and 256 bits block size? I can't find any paper describing it.

Do you simply do two times the operation? For 192 one full time and one with half the bits being set to 0 as place holders, and two full time for the 256 bits block size?

The original Rijndael submission to the AES competition (which includes details on how to handle block sizes of 192 and 256 bits) can be found here.  The mix column operation itself is described in section 4.2.3, and that section explains it pretty well.

Since I'm not supposed to have link-only answers, I'll try to explain it myself.
The state in Rijndael is represented by a $4 \times n$ matrix of bytes (where $n=4$ for 128 bit blocks, the AES case, and $n=6$ for 192 bit blocks and $n=8$ for 256 bit blocks).  When you perform the Mix Column step, you take each column in the matrix, and multiply it by the fixed polynomial $03x^3 + x^2 + x + 02$   modulo $x^4 + 1$.  This operation is precisely the same as in AES, except that if you have a larger block size, you have more columns; you still apply this multiplication only once for each column in the matrix.


multi key encryption Is there an algorithm which allows  using multiple keys for decryption?
I had this scenario in mind:  think about being a boss of a corperation which has an encrypted data base with loads of secret files.
and you only want to allow employees access to the specific files they need to work with, would it be possible to give them keys to only a specific part of the encrypted data (while as the boss, holding a sort of master key to be able to read all)?

It is possible to encrypt a file to multiple users by using CMS Envelope Data.

Firstly, you generate a content encryption key(CEK) to use in file encryption. Then the content-encryption key is encrypted for each recipient. Then store the encrypted data and the encrypted CEKs in an Enveloped Data format. To decrypt a file each client should first decrypt the CEK then use that CEK to decrypt the content itself.

In your scenario you should encrypt each file for the users that you want them to open, and you should encrypt all files for your master user.


Factoring RSA number knowing some B-smooth numbers Hi I am studying for an exam and having some problems solving one of the questions. It reads as follows: Factor $$N=44370047$$ using Quadratic Sieve by using the information that you get from squaring the following numbers modulo N.

$$33965, 2145407, 19416874, 15213395$$

I know how the algorithm works, i.e   $$19416874^2\mod 44370047 = 9 = 3^2$$

And then calculating $$gcd(19416874-3,44370047)$$

I can do this using the computer easily but I have no idea how to calculate the modulo of numbers of this size by hand. Any help would be greatly appreciated as I am currently banging my head against the wall.

You probably know the algorithms to multiply and divide numbers by hand; that's what you do. Yes, it will be painful. No, there's no other way, but I don't think you will be expected to do it in an exam (confirm that with your instructor, however).


Checksum vs. non-cryptographic hash What are the differences between checksums (e.g. Fletcher, Adler, CRC), non-cryptographic hashes (e.g. xxHash, MurmurHash, CityHash) and cryptographic hashes (e.g. MD5, SHA1, SHA3)?

I am familiar with checksums and how they're used to detect errors in data, and how the design can influence collisions (like [0,0] [0,0,0] would give the same checksum in many simple algorithms, even Fletcher).

I also have a basic understanding of how cryptographic hash functions work. They're more taxing to compute, produce a more randomized output, and generally have a larger output size than a checksum. And somehow they're designed to be secure.

However, non-cryptographic functions are a mystery to me. None are really taken seriously or standardized. We have CRC32 being implemented in hardware, huge competitions for the new SHA3 standard, etc. But non-cryptographic functions appear to be just curiosities made independently. And Google's CityHash is apparently made specifically for strings.

If hash tables are solely the purpose of non-cryptographic hashes (and strings, as CityHash advertises), then are they not appropriate for error-detection in large binary data files that SHA1 and CRC32 are often employed for?

I have noticed striking similarities in the source code of simple algorithms such as DJB2 and Adler32, for example. They all appear to accomplish the same thing.

I've used MD5 in the past to find duplicate files, errors in file downloads, and to identify minor differences in otherwise identical files. MD5 is also supposed to be not that fast, with CRC32 achieving the same thing, although with potentially more collisions (which bothers me a bit).

As for my ideal use case, I would prefer an algorithm like MD5 (or shorter output length) that is as fast as possible (no security considerations required), with as few collisions as possible. It would be used as a fast checksum/file fingerprint. Recently, I have found the 128-bit version of MurmurHash3 (specifically the x86 version for JS implementation) to fit these requirements. But again, MurmurHash is not a checksum--it's for hash tables, so I don't know if this would be a misuse.

Can anyone explain the differences, or refer me to any books/articles on the subject?

Cryptographic functions are designed to survive some adversarial setting; their designs assume that there will be very clever people trying as hard as they can to "fool" them.  Non-cryptographic functions on the other hand are "optimistic"—they're designed to perform well with the sort of data that their designers expect will be given to them.

In fact, non-cryptographic functions are often observed to synergize with data sets that exhibit the expected patterns—for example, note how the functions tested in this Programmer's Stack Exchange answer have lower-than-chance collisions for the consecutive numbers data set.  This behavior is often by design.

  But non-cryptographic appear to be just curiosities made independently. And Google's CityHash is apparently made specifically for strings.  If Hash tables are solely the purpose of non-cryptographic hashes (and strings, as CityHash advertises), then are they not appropriate for error-detection in large binary data files that SHA1 and CRC32 are often employed for?

The answer to this is that there's no general answer other than whatever the designers of the functions set themselves as their goals.  With cryptographic hash functions, the adversarial setting dictates the standard that functions must meet, but once you take that away authors can just do whatever they think is most appropriate.

It's worth noting however than many of the modern non-crypto hash functions are tested using the SMHasher test suite, so lately you tend to see lots of hash functions that score well at it.  Here's a brief description of its tests.


Is there any difference between cryptography and cryptology? Is there a difference between cryptography and cryptology, if any?

An internet search suggests that both terms can be used interchangeably.

Today, indeed the the terms "Cryptography" and "Cryptology" can mostly be used interchangeably.

Historically things have been more interesting though, where Cryptology was the umbrella term for Cryptanalysis and (constructive) Cryptography. For example the Handbook of Applied Cryptography (chapter 1 PDF) has the following definition (page 15) of "Cryptology":

  Cryptology is the study of cryptography (Definition 1.1) and cryptanalysis.

with "Cryptanalysis" being defined as (on page 15)

  Cryptanalysis is the study of mathematical techniques for attempting
  to defeat cryptographic techniques, and, more generally, information
  security services.

and "Cryptography" being defined as (on page 4)

  Cryptography is the study of mathematical techniques related to
  aspects of information security such as confidentiality, data
  integrity, entity authentication, and data origin authentication.


Can someone clarify two things about the HKDF by Krawczyk? I got a question about the HKDF Scheme by Hugo Krawczyk. On the following link you can find a small explanation of the HKDF-Scheme and some short informations. The HKDF specification itself has been published as RFC 5869.

I got two questions about the short informations. It is said that:

  Research results obtained in recent years point out to the advantages of building KDF functions based on HMAC rather than on plain hash functions as traditional schemes do.

What are the advantages? What is exactly meant by that?

  In particular, these results show that an HMAC-based KDF can be founded on weaker assumptions on the underlying hash function
  …
  Based on such results we propose HKDF, a fully-specified HMAC-based KDF, that can serve multiple applications under a wide variety of requirements and under relaxed assumptions on the hash functions.

What assumptions are exactly meant?

It would be very nice if someone can give me some short explanations or some thoughts.

For example, there are no current attacks to HMAC-MD5, although MD5 is broken for several years. Hash functions have very strong requirements (e.g., collision resistance, preimage resistance, etc.), and some hash functions have been shown to fail some of these requirements (e.g., MD5 is not collision resistant). Hash-based KDFs may be affected by the problems of these hash functions, since they directly use their output, normally a concatenation of iterated inputs. On the contrary, HKDF only requires that the compression function behaves like a PRF, which is a much weaker assumption.

See these other questions for more details:

Is HMAC-MD5 considered secure for authenticating encrypted data?

Security of KDF1 and KDF2 (hash based KDF's)


One-Time Pad: True or False Suppose a message $M$ was encrypted with a one-time pad. If we learned the first half of the original text is some substring $s$, would we have a better chance of cracking the rest of the message?

Is this true or false? I know that OTP is unbreakable in theory but with the knowledge of the first portion of the string, would this help us?

In theory no, there will be no better chance.

The key must be at least as long as the original text. The key must have high entropy (simply said, it should be random enough). Then revealing any part of the original text has no effect on the decryption.

In practice, if the process is realized improperly, there can be some issues:

If the key is shorter that the original message.
If the key is not random enough.
If the the OTP generator is not random enough and the attacker knows a lot of other OTPs produced by this generator.


Clarification of Decoding in Ring-LWE In the paper "A Toolkit for Ring-LWE Cryptography", the proposed public key system has (ignoring subtleties of the dual) Alice generate $a$ uniformly and $s,e$ from a discrete Gaussian, then output $(a,as+e)\in R_q\times R_q$. Bob generates $s_b,e_b$ from a discrete Gaussian, has $m\in\{0,1\}^n$, and outputs $(as_b+e_b,s_b(as+e)+m\lfloor q/2\rceil)$. Then Alice calculates:
$$s_b(as+e)+m\lfloor q/2\rceil - s(as_b+e_b)=s_be-se_b+m\lfloor q/2\rceil$$ Then Alice can decode away the $s_be-se_b$, since they are small, and recover $m$.

Since Eve has just as much knowledge of the ring as Alice does, Eve ought to have just as much decoding capability (she could generate the decoding basis, for example). So as far as I can tell, the reason Alice can decode the final message but Eve cannot decode $as+e$ to $as$ is that in the latter case, Eve isn't really decoding over a lattice at all, since $as+e$ is still in the lattice given by the ring (or its dual). But for Alice, she's decoding a vector in $R$ to a point in the lattice given by $qR$. So the Gaussian error is small enough that Alice can decode the final message, but large enough that Eve cannot "decode" $as+e$.

Is this a correct description of what's going on?

Just so we are on the same page, I recall that the LWE problem assumes that for a secret (and usually small) vector s, it is hard to distinguish (A,b = As+e) from a random (A,b), where A is a random matrix of $\mathbb{Z}_q^{m\times n}$ and e is small. (Considerations about the required parameters and the error distribution are irrelevant for our argument, so I skip them for simplicity.)

With hypotheses for the polynomials $s,a_i,e_i$ that are similar to the ones we had for s, A, e, Ring-LWE assumes that it is hard to distinguish $(a_i,b_i = a_i\cdot s+e_i)$, which we call R-LWE samples, from random $(a_i,b_i)$.

Now, there are at least two (closely related) ways to answer your question :

The public key of Alice is $(a, b = a\cdot s+e)$, and Bob sends her an encrypted message
$$(u,v) = (a\cdot s_b + e_b, b \cdot s_b + e_b' + m \lfloor q/2 \rceil).$$ $(a,b)$ is a R-LWE sample for the secret $s$ so it is indistinguishable from random for Eve. Similarly, if Bob sent $m=0$ to Alice, then  $(a,u) = (a, a\cdot s_b + e_b)$ and $(b,v) = (b, b \cdot s_b + e_b')$ are R-LWE samples for the secret $s_b$ so everything looks completely random to Eve and she wouldn't be able to distinguish whether Bob sent $m=0$ or random stuff to Alice.  To send $m\neq 0$, Bob adds $m \lfloor q/2 \rceil$ to $v$ and it will still look random to Eve.
I also like this more "lattice" approach. This is my interpretation and abusive notations ensue, so feel free to disagree:
$$\binom{u}{v} = \binom{a}{b}s_b + \binom{e_b}{e_b'} + \binom{0}{m \lfloor q/2 \rceil}$$
So $(u,v)$ = [point of the lattice generated by $(a,b)$] + [a small error] + [the message]. The error is chosen big enough so that Eve is unable to decode [lattice point] + [error], let alone [lattice point] + [error] + [message].
However, Alice can perform a "dot product" of $(u,v)$ with the secret vector $(-s,1)$, which is small and almost orthogonal to $(a,b)$:
$$\binom{u}{v} \cdot \binom{-s}{1} = e\cdot s_b + (e_b'-s\cdot e_b) + m \lfloor q/2 \rceil$$
At which point Alice can easily remove the remaining errors and recover m.


How decode works in CCA1 scheme based on MP12 construction? In Section 6.3 from MP12 we have that $encode(m) = Sm$, for $S$ any basis of $\Lambda(G^t)$. Then I have:

$S = \begin{pmatrix}
1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\\
2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 0\\
4 & 8 & 16 & 32 & 64 & 128 & 256 & 0 & 0\\
8 & 16 & 32 & 64 & 128 & 256 & 0 & 0 & 0\\
16 & 32 & 64 & 128 & 256 & 0 & 0 & 0 & 0\\
32 & 64 & 128 & 256 & 0 & 0 & 0 & 0 & 0\\
64 & 128 & 256 & 0 & 0 & 0 & 0 & 0 & 0\\
128 & 256 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
256 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}$

I used very simple parameters: $q=512$, $k=9$, $n=1$, $m=18$. I set $H$ and $R$ to the identity matrix.This way I have that $A_u = [A' \mid -A' + G]$.
Therefore, I have that $encode([1, 0, 0, 0, 0, 0, 0, 0, 0]) = [1, 2, 4, 8, 16, 32, 64, 128, 256] = G$. Fixing $s=1$, I computed $2s.A_u + e + encode(m) = [2.A' \mid -2A' +  2.G] + [0 \mid G] + e = [2.A' \mid -2A' + 3.G] + e \pmod{2q}$.

The inversion oracle returns $z=3$ and a big error $e'$ (but such that $e'.[R \mid I]^t = e.[R \mid I]^t \pmod{q}$). The decryption algorithm returns $m=[1, 1, 0, 0, 0, 0, 0, 0]$.

In general I have that $m$ is being added to $2s$, so the decryption algorithm returns the binary decomposition of $DecimalRepresentation(m)+2s$, instead of only $m$.

In Lemma 6.2, we have that $v^t.[R \mid I]^t = 2(sG \pmod{q}) + encode(m) \pmod{2q}$. Therefore I reached this point successfully. Hence I guess my Decode algorithm is wrong. In order to decode, I am multiplying by $Inverse(S)$. Afterwards I divide the obtained vector by $q^{k-1}$.

What am I doing wrong?

After some time I revisited the problem and found out that before decoding it is necessary to reduce modulo the fundamental region to find a coset, then we have that in the example I gave the internal value $2s+m$ is equal to $[1, 1, \dots]$, and after reduction it turns out to be equivalent to $[1, 0, \dots]$, which is $m$, as needed.


How to solve encryption with ASCII output There are lots of text files which have unknown data packets with ASCII output (no available plaintext exists with regard to any ciphertext, I have only encrypted outputs). The input data is known to be ASCII as well.

Looking both in a hex viewer and a text editor, I can see the string well. I tried to draw histogram of all the data one by one.

One text file data does not have uniformly distribution
Histogram of all of the text file has non-uniformly distributed data

I observed the following from the histogram:

There are 0xA and 0xB ASCII chars and all the other data is in the range of 0x20 to 0x7E
There are lots of parenthesis "{]{[_XWZc" letters in the data that I have. This range makes a peak in the histogram

One more interesting thing is, sometimes the last 3-4 letters look like a meaningful plaintext string (for example "John, eat") and may repeat in some other text files at the end of data (the letter cases are also the same).

Question 1: What are some ASCII encryption methods that look like this encryption?

Question 2: Which strategy should I follow to retrieve the plaintext?

This is my first question on Stack Exchange.  Sorry for any mistakes related to the rules or missing parts in the topic.

Helpful links:

http://www.asciitable.com/index/asciifull.gif
https://www.browserling.com/tools/ascii85-encode (I've tried the algorithms on that page)

I don't think it's possible to give any specific and concrete answer without seeing the actual ciphertext (which in turn would make your question borderline off-topic here).  Nonetheless, I'll try to give a general answer below, outlining how you might be able to approach the problem.

Modern secure encryption algorithms all but invariably produce output that looks like uniformly distributed random bytes.  In particular, they do not natively output printable ASCII text.

Thus, if you see ciphertext that looks like readable ASCII, there are basically two possibilities:

after encryption, some binary-to-text encoding has been applied to it, or
it's not actually encrypted with a secure modern cipher.

In the first case, your first task will be identifying the encoding scheme.  The most common one is probably Base64, but plenty of other choices exist too.

Ideally, you'd like to find a specification describing the scheme, or the code that encodes and/or decodes it.  Failing that, the first thing you should check is the set of characters used in the encoded ciphertext.  Often, this alone may be sufficient to identify the encoding scheme.  Note that the beginning and/or the end of the data may sometimes contain extra padding or metadata tags that aren't actually encoded with the same scheme as the encrypted data itself, and which may use different characters.

You should also check how often each character occurs in the encoded ciphertext.  Binary ciphertext (which looks like random bytes) encoded with a base-conversion scheme like Base64 will typically feature all of the actual data-encoding characters with roughly equal¹ frequencies.  Characters that appear with significantly different frequencies may be padding or formatting characters, like = and newlines in Base64 or the length markers at the beginning of each line (usually M, except for the last line) in uuencoding, or they might only occur in metadata.

Alternatively, if some characters appear significantly more often than others, that may be a sign that you're actually dealing with a variable-length encoding like URL-encoding or MIME quoted-printable, or that the unencoded bytes are not uniformly distributed (which may indicate that they're not really encrypted after all).

Note that, if the (supposed) encryption is any good, then you might still be out of luck even if you do manage to decode the ASCII text back into binary.  Modern encryption schemes are generally designed according to Kerckhoff's principle, which says that a cryptosystem should remain secure even if the attacker knows everything but the key.

Even if the encryption scheme used is broken and vulnerable to attacks, with just a bunch of captured messages you're basically restricted to ciphertext-only attacks, which are the weakest kind of attacks possible — and that's assuming that you even know how the encryption scheme works, which may not be the case here.

It's also possible that the data you're trying to analyze is not properly encrypted at all, at least not in the modern sense.  It might be text encrypted with some classical cipher (i.e. something from the era before byte-based computerized ciphers like DES became commonplace) or with some weird custom home-brew encryption scheme that might be more or less (usually less) deserving of the name "encryption".

It's also possible that the data is not really encrypted at all, but merely obfuscated to make it harder to read.  The difference between obfuscation and encryption is basically Kerckhoff's principle, as mentioned above: actual encryption is designed to remain secure even if the attacker knows everything about the system except the key, whereas an obfuscation scheme may not even have a key, and simply relies on the attacker not being smart enough to figure out how it works.

One common place where obfuscation is often found is in computer games, which may "encrypt" (more properly speaking, obfuscate) their data and save files to deter players from modifying them in order to cheat.  Sometimes, such obfuscation schemes may be designed to keep the obfuscated text as printable ASCII, e.g. to reduce the chance of accidental data corruption when editing partially obfuscated files.

Of course, in practice, these categories can blend together: many classical encryption schemes that were considered reasonably secure in their time are nowadays little more than puzzles for amateur cryptographers armed with computers and modern codebreaking techniques, and similarly, many home-brew encryption schemes developed by amateurs with little if any knowledge of modern cryptography also amount to little more than mere obfuscation.  In any case, the techniques to attack all such schemes are similar:

if possible, try to analyze the code that encodes or decodes the data;
failing that, try to obtain and/or generate ciphertexts corresponding to known plaintexts with small differences, and see if the differences between the ciphertexts reveal a pattern;
also, if possible, try to submit slightly modified ciphertexts for decryption and see if there's any pattern in how changes to the ciphertext affect the plaintext;
if none of the above are possible, try to simply guess what the scheme might look like, based on resemblance to other common and/or standard encoding or obfuscation schemes.

You might also find the answers to these related questions useful:

Is it generally possible to employ brute force methods when the encryption scheme is not known? Why or why not?
Possible ways to crack simple hand ciphers

(Yes, the top answers to both are mine, because I was lazy and only looked through my own contributions.  If you can think of other related earlier questions with good answer, feel free to suggest them in the comments.)

Also, here's a practical example of ciphertext-only reverse engineering of (double) binary-to-ASCII encoded data that I posted to SO a while ago.

1) As a rule of thumb, two character counts may be considered "roughly equal" if their difference is no more than a couple of times the square root of their average.  This is because, for a string of independently chosen random characters, the number of times each character occurs in the string approximately follows a Poisson distribution, which has a standard deviation equal to the square root of its mean.


Public-key generation - primes reuse Given the following Trap-door Commitment scheme

Secret key receiver: $x_B \in_u Z_q$
Public key receiver: $y_B = g^{x_B} \mod p$

Here, $p=q*k+1$ for two primes $p,q$ and $k \in Z$. And $g$ is the generator of subgrup $G_q$ of $Z_p^{*}$, of order $q$.

To the sender commit $w \in Z_q$, he selects $r \in_u Z_q$, the commitment is $c=g^wy_B^r \mod p$. To open a commitment, he sends $(w,r)$.

My question is: if I want create milions of theses public-secret keys for milions of different senders, could I reuse $p,q$?

Yes you can reuse $p$ and $q$, i.e. you can have multiple key pairs using the same group, as long as the secrect keys $x_B$'s are chosen independently at random.

Essentially, what you are asking is this, given $y_B=g^{x_B} \in G$ where $G$ is the order-$q$ subgroup of $Z_p^*$ and $x_B \in Z_q$, and additional $y_i =g^{x_i} \in G$ for polynomial many $y_i$'s, is the trapdoor commitment is still secure?

Some more details:

The security of commitment requires two things: hiding and binding.

For the hiding property, note that your commitment scheme is perfectly (information theoretically) hiding, thus a commitment $g^w{y_B}^r$ is uniformly random and the uniformity comes from the fact $r$ is uniformly random. This also means the distribution of $g^w{y_B}^r$ is independent of all $y_i$'s the adversary can get, and those $y_i$'s provide no advantage for the adversary to learn $w$. So the hiding property holds.

For the binding property, you can reduce it to the DL problem such that if an adversary $A$ can break the binding property of your scheme, then we can use it to break the DL problem. Suppose a DL adversary who has $y=g^x \in G$ and needs to find $x$, he can choose random $x_i,x_2,\ldots,x_n \in Z_q$ and compute $y_1=g^{x_1},y_2=g^{x_2},\ldots,y_n=g^{x_n}$ and invoke $A$ with $y$ and the additional $y_i$'s. The adversary $A$ can break the binding property means with a non-negligible probability, $A$ can find two different pairs $(m,r)$ and $(m',r')$ such that $g^my^r=g^{m'}y^{r'}$. If $A$ returns such a pair, it must hold that $m+xr=m'+xr'$, and $B$ can compute $x=\frac{m'-m}{r-r'}$, thus solve the DL problem. Since we assume the DL problem is hard, such $A$ does not exist. Therefore the binding property also holds (as Squeamish Ossifrage also said in the comment).