why to use a safe-prime in Diffie-Hellman key exchange? In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime.

so my question is what extra benefit of using such a prime, what's new does it bring to the table.

and does using a regular prime make the problem much easier to solve(make an attack practical).

g^ab mod safe-prime is more secure than g^ab mod prime ?

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime.

We don't have to; there are other options which achieve the same effect.  However, it works.

so my question is what extra benefit of using such a prime, what's new does it bring to the table.

Well, a lot of the security of DH depends on the subgroup structure of $\mathbb{Z}_p^*$, and that depends on the factorization of $p-1$.
For any generator $g$ we use, the order of the subgroup $q$ (the smallest positivie value $q$ such that $g^q = 1 \bmod p$) satisfies $p-1 = h \cdot q$, for some integer $h$.
In addition, we generally prefer working with a prime subgroup, that is, where $q$ is a prime value.  That's because if $q$ is composite, that is, $q = r \cdot s$, then given $g^x \bmod n$, we can recover the value $x \bmod r$ in $O( \sqrt{r} )$ time; if $r$ is not large, this leaks more information that we'd care for.
Thirdly, there is a invalid key share attack possible if you reuse DH public keys (which sometimes we do).  That is, if $h$ has a moderate factor $t$, then by issuing an invalid key share, the attacker can rederive $x \bmod t$ (where $x$ is your private value).  This attack can be detected, but the detection is expensive, and so it is often not done (even when you do reuse key shares).
So, with all that:

and does using a regular prime make the problem much easier to solve(make an attack practical).

What do you mean by a "regular prime"?  Do you mean just picking a random prime $p$ and random generator $g$?  Well, while the order of $g$ is probably large, it is likely to be composite, and will often have moderate factors; these factors (if present) would allow someone listening in to recover some information about your private value (and if you use one that's not full length, it may be enough to recover the entire value).  However, possibly this is not the case; however you're taking a gamble here.
In contrast, if we have a safe prime, well, we're safe.  We generally use a prime that's in the "quadratic residue" subgroup, that is, the one where every member (other than 1) has order $(p-1)/2$, which is prime.  And, if we happen to pick another generator (other than 1 or $p-1$), the only other subgroup is the one of size $p-1$, which means that the attacker can find $x \bmod 2$, but nothing else about $x$.
In addition, the invalid key share attack can only recover $x \bmod 2$ (because $h=2$), and so even if we reuse key shares, that's not a concern.
Now, there are other ways to make sure that we work within a prime-sized subgroup.  On the other hand, safe primes have the property that we can have $g=2$; these other methods generally require larger $g$ values (which makes part of the computation more expensive).


Reversing SHA1 (don't know the correct term) Given sha1(pad(A) || pad(B)), where B is known, can I calculate sha1(pad(A))? pad(A) means its length is exactly 1 block (64 bytes for SHA-1)

If yes, for which other hash functions it will work too?

Would it work vice versa when A is known?

Why do I think it's possible?

If you take a look on SHA-1 source, 16 ints block is expanded to 80 ints and then during 80 rounds one int is added using invertible operations. When you have the block in plaintext, you can calculate the expanded block and revert the hash round by round until you'll get the IV of the block, i.e. the hash of the last block. Do you understand what I mean?

SHA-1's compression function (as well as MD5 and SHA-2) is build from a (custom-made) block cipher in the Davis-meyer construction. (These are the "invertible operations" you describe in the question.)

The basic idea is to use the message block as the key for the cipher to "encrypt" the previous state:

                    message block
                          |
                          ↓
                     .---------.
previous state ----> | Encrypt | ----> new state
                     '---------'

If this would be the only thing to do, then we actually could (knowing a block of the message and the new state) revert the cipher to calculate the previous state, just like you sketched in your question.

A compression function with this property is not what we call a "one-way" compression function, and would not be a good thing to use as a compression function for a hash function. Therefore this is not what is actually done, the Davis-meyer construction has one more step:

                    message block
                          |
                          ↓
                     .---------.
previous state ----> | Encrypt | --⊕---> new state
                 \   '---------'   ↑
                  \                /
                   \--------------/

This XORing of the "ciphertext" with the "plaintext" has the effect that we don't know the ciphertext output of the block cipher, and can't do our backtracing. This is actually enough to make the compression function one-way, if the block cipher is secure (for some formal notations of one-way and secure).

  If yes, for which other hash functions it will work too?

As explained, no hash function with your trackback property can be deemed secure, so we can conclude that no modern hash function should have this property.

  Would it work vice versa when A is known?

If A is known, you also know sha1(pad(A)), e.g. the state after hashing the first block, e.g. the input to the second block.

Looking at the diagram above, we now know both the plain text input as well as the cipher text output of the block cipher. From this deriving the (or any) used key is known as a known-plain text key retrieval attack (or chosen-plaintext, if the attacker can actually influence A and see hash(pad(A)||pad(B))). If the block cipher is any good, it should not feasible to retrieve any useful information about the key pad(B) (other than by trying examples, i.e. brute forcing).


Best approach for storing private key I'm working on a web service application which uses a self signed certificate. I apologize up front if this turns to be a dumb question. When using openssl for generating private key, it reveals (as per my understanding) the encryption algorithm and initial vector. A bit of googling showed it follows PKCS5. These information of algorithm and key was not present in another private key which followed PKCS8.

Does this mean that PKCS8 has better security ? At present which is most popular and secure, while there is a requirement to store private key in filesystem?
Private key is encrypted with a passphrase and I use the hardcoded passphrase in the code to decrypt it. Is this the right way of using it?

PKCS#5 (RFC2898) is a standard for key derivation, not for key storage. Openssl can store an RSA private key either in its own format (default) or in PKCS#8 format. You can convert a key using the openssl pkcs8 command. Securitywise, there is no difference between the two.
You should rather store the password in a configuration file or make the user type it when starting the server software. Otherwise, you would have to recompile and reinstall your whole software, everytime you change the key's password or the key itself. Also, the password can be more easily protected in a single file on the server than in a source code repository.


Which symmetric encryption systems, pseudorandom number generators, and hash functions are best suited for reversible computers? Reversible computing refers to the type of computing where one minimizes the the amount of data to be deleted usually to save energy (Reversible computing could also thwart side-channel attacks). Energy efficient reversible computers do not exist yet in the free market although some have constructed prototypes and they should become the computers of the future.  In reversible computing, the AND and OR gates are forbidden since they delete data (the AND gate has 2 inputs but 1 output so one bit is necessarily deleted).

With purely reversible computing, only the bijective logic gates are allowed for computation since non-bijective gates delete information. For example, the CNOT $(x,y)\mapsto(x,x\oplus y)$, Toffoli $(x,y,z)\mapsto(x,y,(x\wedge y)\oplus z)$, and Fredkin
$(0,y,z)\mapsto(0,y,z),(1,y,z)\mapsto(1,z,y)$ gates are all reversible gates.

While reversible computing theoretically should save energy, it typically takes more steps to compute something reversibly than it does to perform the same computation irreversibly. However, in symmetric cryptography, one could potentially design cryptosystems such as encryption systems, hash functions, (cryptographic and non-cryptographic) pseudorandom number generators which do not contain any such algorithmic overhead (the only irreversibility that is required in a cryptographic hash function is that unless one wants to keep the hash around forever, one must eventually delete the hash).

1) Are there any symmetric cryptosystems which are specifically designed to be used by reversible computers?

2) Are there any symmetric cryptosystems which were not necessarily designed to be used by reversible computers but which just-so-happen to be reversible?

3) Are there any symmetric cryptosystems which are nearly reversible and which can potentially be modified slightly to become reversible?

Here are some characteristics that one would like in reversible cryptosystem.

-The cryptosystem should ideally be computed using solely reversible gates without any garbage bits, ancilla bits, uncomputation, or irreversible gates.

-The inverses of all parts included in the cryptosystem should be computed in exactly the same way as the forward direction (for example, the inverse $\chi$ in Keccak is computed differently than the forward direction; $\chi$ has algebraic degree 2 while the inverse of $\chi$ has algebraic degree 3 (see page 16 of these slides)).

-The cryptosystem must not require any uncomputing. Uncomputing is an overhead that arises in reversible computing even though irreversible computing does not require any uncomputing.

-The cryptosystem should not use any lookup tables.

-The cryptosystem should not use modular multiplication, finite field multiplication, or finite field inversion at all these operations require uncomputing.

We can think of encryption as a deterministic function producing ciphertext $C$ from key $K$, plaintext $P$, and for other than deterministic encryption an extra input $R$ for randomness/Initialization Vector. That function $(K,R,P)\mapsto C$ can't be both secure and reversible. Proof: it would be possible to obtain $(K,R,P)$ from $C$ because of reversibility, and from that extract $P$, which goes straight against the security goal.

The same reasoning shows that a fully reversible TRNG can't be secure, or a fully reversible hash function first-preimage resistant.

However, we can implement all steps reversibly, except discarding some of the final result. In particular, for any size-preserving symmetric cipher, in principle we can reversibly implement $(K,R,P)\mapsto(G,C)$, with garbage $G$ the same width as $K$ (and $C$ the same width as $R$ and $P$ combined), and discard $G$ from the output. For a block cipher, that is $(K,P)\mapsto(G,C)$ (proof and/or straightening welcome; Scott Aaronson, Daniel Grier, Luke Schaeffer's The Classification of Reversible Bit Operations would be a useful reference).

With that conception of reversible cipher allowing to discard garbage the width of the key, I tentatively answer:

Yes, if your AES-128 replacement with easy implementation as Toffoli-like gates qualifies.
Yes. The AES block cipher is a well-studied example, and all its standard modes qualify. For the reversible construction of AES-128, see

Kamalika Datta, Vishal Shrivastav, Indranil Sengupta, Hafizur Rahaman's Reversible Logic Implementation of AES Algorithm, in proceedings of DTIS 2013. My reading is that it reports implementing $(K,P)\mapsto(G,C)$ for AES-128 using less than $2^{17}$ Toffoli gates.
Markus Grassl, Brandon Langenberg, Martin Roetteler, Rainer Steinwandt's Applying Grover’s Algorithm to AES: Quantum Resource Estimates, in proceedings of PQCrypto 2016, seem just over $2^{20}$ Toffoli gates using a different approach.

Rather no. Making things easily reversible when they are not would be a huge design change, likely to compromise security. That applies in particular to Feistel block ciphers using large non-reversible round functions, which I guess are quite hard to re-express as reversible.

I asked how costly DES would be.


Show how an efficient algorithm for computing discrete logarithms with base a can be used to efficiently compute discrete logarithms with base b I have an exercise that says the following:
Let $p$ be an odd prime, and let $a$ and $b$ be generators $\mathbb{Z}_p^*$. Suppose that we have an efficient algorithm $A$ for computing discrete logarithms with base $a$. Show how this algorithm can be used to efficiently compute discrete logarithms with base $b$.
With considering a change of base rule, I have done the following:
B(b,x):
    return A(x) / A(b)

Is this correct and the end of the exercise? I would say that it is, but this is very easy compared to the other exercise I'm currently solving, so I think that I have missed something...

Is this correct and the end of the exercise?

I can't say to what extent your professor wants you to be explicit, but it is essentially correct (and I'd accept it as an answer if I were grading it).  Now, your professor may be expecting you to explain (or give a proof) why this is correct.


Synthetic Jitter to Combat Timing Attacks We are working on some tooling. It has a networking kernel.
We would like to think that jitter built into the kernel would help with timing attacks?

Is this true?

Yes, and no.

Adding random jitter makes things harder, but since you cannot force the device to go faster then the minimum number of instructions it would take to perform the computation without interrupts, it would still be possible to perform a timing attack using a large number of traces and statistical tools such as low percentile filters, in a similar way as in this paper by Crosby et al.

In the end, the only reliable way to fight timing attacks is really to have constant time code.
You can read more about constant time crypto on BearSSL's website.

But you can encrypt all the data you're sending over the network, using constant time crypto and that's it.
No need to have the whole network stack constant time, if it's only sending encrypted data!


McEliece information set decoding attack vulnerability Wikipedia states that McEliece is open to "information set decoding attack". What is an "information set decoding attack" and how serious is the vulnerability? (is it just a matter of choosing proper padding/parameters or is the issue deeper)

(motivated by Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable?)

An old thread, but I thought it deserved an answer.

Information-set decoding

In short, the idea behind information-set decoding is to pick a sufficiently large set of error-free coordinates in a sent codeword such that the corresponding columns in the generator matrix form an invertible submatrix. Then, the information sequence can easily be obtained by linear algebra.

A plain information-set decoding algorithm is the simplest form of information-set decoding. It randomly selects an information set and then computes the information by solving linear equations. Consider the following. Let $\mathbf u \in \mathbb F_{2}^{n}$ be an unknown information sequence and

\begin{equation}
\mathbf r = \begin{pmatrix}r_1 & r_2 & \cdots & r_n\end{pmatrix} = \mathbf u \mathbf G + \mathbf e \in \mathbb F_{2}^{n}
\end{equation}
a received codeword encoded by an $[n,k]$ linear code with generator matrix
\begin{equation}
\mathbf G = \begin{pmatrix} \mathbf g_1^T& \mathbf g_2^T& \cdots & \mathbf g_n^T\end{pmatrix}.
\end{equation}

Suppose we pick an information set $\mathcal I \subset {1,2,\ldots,n}$ of size $k$. Recall that $\mathcal I$ is an information set if and only if the vectors $(\mathbf g_i)_{i \in \mathcal I}$ are all linearly independent.
Now, define a masking function $\phi$ such that
$
    \phi(\mathbf G) = (\mathbf g_i^T)_{i \in \mathcal I}
$
and, thus,
\begin{equation}
    \phi(\mathbf r) = (r_i)_{i \in \mathcal I} = (\mathbf u \mathbf G + \mathbf e)_{i \in \mathcal I} =  (\mathbf u \mathbf G)_{i \in \mathcal I} + (\mathbf e)_{i \in \mathcal I}.
\end{equation}
There is non-zero probability that symbols in the information set being perturbed by error, and therefore the procedure usually needs to be iterated with different information sets until it finds one that is entirely error free.
Whenever the selected information set $\mathcal I$ is non-corrupted, i.e., $ (\mathbf e)_{i \in \mathcal I} = \mathbf 0 \iff \mathcal I \cap supp(\mathbf e) = \emptyset$, then the information symbols can be obtained by computing
\begin{equation}
    \phi(\mathbf r)\phi(\mathbf G)^{-1} = \phi(\mathbf u \mathbf G)\phi(\mathbf G)^{-1} = \mathbf u.
\end{equation}
If, on the other hand, the information set contains a non-zero number of errors, then consequently $\phi(\mathbf r)\phi(\mathbf G)^{-1} \neq \mathbf u$, and therefore another different $\mathcal I$ must be chosen, until a solution satisfying the weight constraint is found.

There are several improvements to this technique, involving birthday techniques. One classic and commonly referenced algorithm is Stern's algorithm.

Decoding attack

Message recovery:  Recovery of the message from a ciphertext is best done (if no structure can be exploited) by information-set decoding algorithms, by finding a minimum-weight codeword in the coset $\mathbf r+ \mathcal C$. This can be accomplished by constructing an extended code with the generator matrix
$$
\mathbf G' = \begin{pmatrix}\mathbf G\\ \mathbf r\end{pmatrix}.
$$
Then, an information-set decoding algorithm may be applied to find the minimum-weight codeword $\mathbf{e}$.

Key recovery: The purpose of a key recovery (structural attack) is to recover the private key from the public key. Many codes used in information transmission have a structure which allows for an efficient decoding procedure. In the context of information transmission, it does not pose a problem to have a structured code. In contrast, for code-based cryptography such as McEliece, security of the cryptosystem relies on that the public-key generator matrix is indistinguishable from a random one. Therefore, when structured codes are used, security will degrade because of the inherent structure of the public key.
It is sometimes possible to recover the private key by looking for low-weight codewords in the code generated by the public key. By exploiting the structure of the code, this procedure can sometimes be accelerated.

Information-set decoding is a big hammer

Information-set decoding applies to basically all code-based cryptography. Therefore, it serves as an upper bound on the security and naturally, parameters are designed according to this bound. The linear decoding problem is NP-hard and therefore breaking McEliece remains exponential in the worst case. If or when a new, more efficient information-set decoding algorithm is invented, the old parameters must re-scaled.


Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$.

I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to compute $d$. That's where I get stuck.

Here's my work so far:

First I use the Euclid algorithm to calculate:

40 = 2(17) + 6
17 = 2(6) + 5
6 = 1(5) + 1 = gcd

So I know the GCD is 1. Applying the 'extended' section of the algorithm:

6 = 40-2(17)
5 = 17-2(6)
1 = 6-1(5)
1 = 6-1(17-2(6))
3(6) = 1 (17)
3(40 - 2(17)) - 1(17)
3(40) - 3(17)

I know the answer is $33$, but I have no idea how to get there using the extended Euclidean algorithm. I can't figure out why I'm getting $3(40) - 3(17)$ when I know the answer should contain $33$.

The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards.

Your goal is to find $d$ such that $ed \equiv 1 \pmod{\varphi{(n)}}$.

Recall the EED calculates $x$ and $y$ such that $ax + by = \gcd{(a, b)}$. Now let $a = e$, $b = \varphi{(n)}$, and thus $\gcd{(e, \varphi{(n)})} = 1$ by definition (they need to be coprime for the inverse to exist). Then you have:

$$ex + \varphi{(n)} y = 1$$

Take this modulo $\varphi{(n)}$, and you get:

$$ex \equiv 1 \pmod{\varphi{(n)}}$$

And it's easy to see that in this case, $x = d$. The value of $y$ does not actually matter, since it will get eliminated modulo $\varphi{(n)}$ regardless of its value. The EED will give you that value, but you can safely discard it.

Now, we have $e = 17$ and $\varphi{(n)} = 40$. Write our main equation:

$$17x + 40y = 1$$

We need to solve this for $x$. So apply the ordinary Euclidean algorithm:

$$40 = 2 \times 17 + 6$$

$$17 = 2 \times 6 + 5$$

$$6 = 1 \times 5 + 1$$

Write that last one as:

$$6 - 1 \times 5 = 1$$

Now substitute the second equation into $5$:

$$6 - 1 \times (17 - 2 \times 6) = 1$$

Now substitute the first equation into $6$:

$$(40 - 2 \times 17) - 1 \times (17 - 2 \times (40 - 2 \times 17)) = 1$$

Note this is a linear combination of $17$ and $40$, after simplifying you get:

$$ (-7) \times 17 + 3 \times 40 = 1$$

We conclude $d = -7$, which is in fact $33$ modulo $40$ (since $-7 + 40 = 33$).

As you can see, the basic idea is to use the successive remainders of the GCD calculation to substitute the initial integers back into the final equation (the one which equals $1$) which gives the desired linear combination.

As for your error, it seems you just made a calculation error here:

3(40 - 2(17)) - 1(17)

which incorrectly became:

3(40) - 3(17)

It seems you forgot the factor of 3 for the left 17, the correct result would be:

3(40 - 2(17)) - 1(17) = 3 * 40 - 3 * 2 * 17 - 1 * 17 = 3 * 40 + (-7) * 17

Which is the -7 expected.


How to determine required number of rounds for RC6 cipher given custom W and B parameters? The RC6 symmetric block cipher is parameterized with three parameters :

W : The number of bits in a machine word (8 , 16 , 32 , 64)
B : The number of bytes specifying key length (0 to 255)
R : The number of rounds to execute (1 to 255)

A data block is specified as 'uint_t data [4]' where 'uint_t' can be 8, 16, 32, or 64 bits resulting in a 32, 64, 128, or 256 bit data block size respectively.

These parameters allow the end user to select block size, key size, and to trade off performance for security.

The question I have is : Given parameters W and B, along with a desired security strength (not sure how to specify this exactly, but it depends on R), how does one determine the minimum value of R to ensure this minimum security bound?

ie: I desire to parameterize an instance of RC6 for a 256 bit data block (W = 64) and a 256 bit key (B = 32).  I would like the cipher to have 256 bits of security (that of the key B) which clearly depends on the value of R. Assuming a full 256-bit key is used, what is the minimum number of rounds (R) required to ensure full diffusion and security equivalent to a brute-force search of the 256 key?

I have researched the original RC6 specification, alternative research papers that I could find which discuss various attacks on RC6, etc. but I have not yet seen any summary, equation, or guidelines on how to select values of R for tailored instances of RC6.

It seems to me that without an equation or clear instructions on how to select R, the specification is not 100% complete and layman implementing the cipher for a practical application will be left guessing, which will cause bad things to happen.

Note : I am not an expert cryptographer, but I do know enough not to "roll my own" and follow a standard to-the-letter.  This standard, while awesome, seems to be missing a letter... :)

In the case of AES, they had a lower bound on the highest probability differential (and the analogous linear hull), and they were able to use that information to determine at how many rounds would be required for a differential (and analogous linear) attack of a specific cost.

Ideally, that is how you would proceed.

However, Rijndael (later AES) has some specific properties that enable such a calculation to be made. All of the constituent operations are very cleanly and precisely defined, and they operate on sizes that are small enough to enable such analysis to take place.

With ciphers built from bitwise and arithmetic operations ad-hoc*, especially when those operations function on large words, finding the worst-case differential probability is more challenging, if/when it is possible.

You can find the sort of average worst-case probability (which is not really the worst-case) and make the calculation for rounds using that, but that does not prove that no attack costs less then the desired amount, because there could be some higher probability differentials you don't know about yet.

Still, that is probably the best strategy you have.

Note

You can only perform this type of process for attacks that you know of already. You could prove that no basic differential attack costs less than $\frac{1}{2^n}$, but that does not mean that no attack costs less than $\frac{1}{2^n}$.

* Technically the operations in Rijndael are built from bitwise and a certain type of arithmetic operations - but all circuits are powered by these, at the circuit level.


Why is the security of block cipher not a function of key and tweak? The proofs and security of block ciphers constructed especially of Luby Rackoff Constructions and Feistel Networks is based on the number of queries and round functions. The security measure is always based on the probability with which the attacker can distinguish the randomness in the cipher text. For example Patarin's proof says the encryption can be distinguished in O($ m^2/2^{(l/2)}$)  where m is number of queries and l is length of input bits.

But in general the bigger the key length it is considered as good against brute force and adding tweaks is considered provides additional randomness. Then why is the  security measure not involving the key length or tweak length ? or is there a security measure that involves key and tweak ?

Generally speaking, in proofs of security for Feistel ciphers with various numbers of randomly selected round functions, the secret 'key' is the set of round functions.  Thus, when Patarin or whoever gives upper bounds on the Adversarial advantage for distinguishing a Feistel cipher with $k$ rounds from a random permutation, the key 'length' (i.e. the size of the key space) is implicit in $k$, the number of rounds.  Keep in mind that many of the bounds (e.g. of Patarin) are information theoretic, so brute force isn't really an option -- that is, even someone with an infinitely powerful computer would not be able to distinguish the Feistel cipher from a random permutation better than the relevant bound.

Tweaks are not commonly included mostly because tweakable block ciphers are a recent innovation.


Elliptic Curve Verifiable Secret Sharing I'm reading this paper, which on page 3(Section IV.C) presents a Jointly Random Verifiable Secret Sharing Scheme for Elliptic curves. The algorithm makes sense to me save for this part:

"Each $P_{i\neq j}$ verifies that his share is consistent with other shares i.e. $a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$"

Just to explain the terms for those that haven't read the whole paper:$E$ is an elliptic curve, the base point is $G \in E(Z_p)$ of order $r$.

Player $P_i$ shares secret $a_0^{(i)}$ via $f_i(x)$, a random polynomial of degree $t$. $P_i$ then sends other players their share, i.e. sends $f_i(j)$ to player $P_j  \hspace{3pt}\forall j \in \{1,\cdots,n\}$. $P_i$ also broadcasts $f_i(j)G \hspace{3pt}\forall j \in \{1,\cdots,n\}$.

So, can someone please explain to me why this equation holds:$$a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$$

The authors do not seem to define $B$ or $b_i$. However, later in the same paper,in a related context,  they define $b_i = \prod\limits_{j \in B, j \neq i}\frac{j}{(j-i)}$. I'm not sure if that definition applies here too.

The values

$b_i = \prod\limits_{j \in B, j \neq i}\frac{j}{(j-i)}$

are the evaluations of the so called Lagrange basis polynomials at point $0$. These terms are often also called Lagrange coefficients and can be computed by any participant and $B$ is the index set of the participants.

The formula

$a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$

is just a Lagrange polynomial interpolation, i.e., a weighted sum of the lagrange coefficients. That's just Shamir's secret sharing in the "exponent" (not literally, because we have an additive group here, but the reconstructed value $a_0^{(i)}=f_i(0)$ is hidden due to the DL assumption).

This means reconstruction of the secret (the share $a_0^{(i)}$ of party $i$) without revealing the secret value itself (since the value $a_0^{(i)}$ is not revealed from $a_0^{(i)}G$ as this would require solving the discrete log problem in the used group and the values $f_i(j)G$ also do not reveal the values $f_i(j)$.

Basically, the verifiable secret sharing is achieved by letting every party $i$ revealing "shares" of their share value $a_0^{(i)}$ (hidden due to the DL assumption). Consequently, the participants can verify whether their shares $a_0^{(i)}$ are consistent without revealing their share values (what verifiable secret sharing is about).

Hope that helps.


Elliptic Curve Factorization: Why are elliptic curves suited for this kind of task? Currently I'm working on a presentation of a paper that talks about the factorization of large numbers. In the paper elliptic curves are presented as a way to factorize large numbers. After hearing a lot about elliptic curves it's the first time that I delve into the details of elliptic curves and I'm a bit bit baffled to say the least.

My question is: why are elliptic curves suited for the factorization of numbers?

In the paper it's stated that for an integer number $n$ there exist various suited elliptic curves that can be used for its factorization, meaning that checking multiple elliptic curves for a number can be parallelized. But still, what is the real reason (from a mathematical point of view) why elliptic curves are used for this kind of task?

It's probably best to understand Lenstra's Elliptic Curve factorization algorithm by way of contrast with its predecessors, the Pollard's p-1 method, the Williams' p+1 method and the Cyclotomic Polynomial method of Bach and Shallit.

These are all Algebraic-group factorisation algorithms which require you to select a stage 1 bound $B_1$ and stage 2 bound $B_2$ where $B_1<B_2$.

The most common way for Pollard's p-1 method to fail is if none of the primes dividing the composite N to be factored have the order of the group of multiplicative elements (i.e p-1) able to be written as a product of prime powers smaller than $B_1$ and at most one prime between $B_1$ and $B_2$. Numbers having this representation are rare and can be loosely termed "smooth".

This is purely a characteristic of the composite to be factored and without knowledge of the factors you don't know whether the p-1 method is doomed to failure.

The Williams' p+1 method uses the multiplicative group of a quadratic extension of N which (if successfully chosen) has order p+1. So it fails if  none of the $p+1$s are smooth .

The Cyclotomic Polynomial method succeeds if let's say $p^2+p+1$ or more complex expressions are smooth but these numbers are getting larger than $p$ and the chance that they are smooth (unless N has a special structure) is rapidly decreasing.

What would be nice would be to have an effectively unlimited number of different groups with different orders that we can try where there's nothing stopping the group orders being smooth and the group operations are reasonably quick. That's what Lenstra's Elliptic Curve method delivers.

The way it works is that you choose a random $\sigma$ which specifies an elliptic curve where the orders of the multiplicative groups is somewhere in the range $p+1 \pm \sqrt p$. The algorithm will succeed if for one of the curves you try, the order is smooth.

In terms a layman might understand, when Pollard's p-1 algorithm was discovered, we could all of a sudden quickly factorize a whole swathe of numbers where p-1 is smooth but we were still stuck on other numbers. When Williams' p+1 algorithm came along then we could now factorize a whole lot more numbers where p+1 is smooth but we were still stuck on lots of numbers. When Bach and Shallit's Cyclotomic Polynomial method came along, a few more numbers were factorizable but it's clear that the effectiveness of each successive algorithm was diminishing. With elliptic curves, each $\sigma$ value is essentially making available a new algorithm as good as p-1 which works if $p+1-a$ is smooth for some $|a| \lt \sqrt p$. Unlike previous algorithms, we don't know what $a$ will be until the factor has been found. Now we no longer have to worry about the prime factors being small but "hard". The difficulty is purely dependent on their size.


What is the best current way to cryptographically secure databases? I'm currently working on a proposal for some secure complete system and one of the things currently lacking is the database security.
However I don't want to roll my own crypto there and thereby need a secure, somewhat reviewed / standard way to cryptographically secure the databases.
I had a look at CryptDB for this but it lacks authentication which I consider needed and I couldn't easily find out what ZeroDB provides except "end-to-end" encryption.

What is the best cryptography based database currently specified / available?

My definition of "best" in this case: Provides authenticity and secrecy (most important), provides integrity over the whole database (no silent dropping of data), leaks as less information to the server as possible, doesn't have to hide access patterns, allows for complex (cryptographically enforced) access rules.

It can be assumed that the clients do use / own public / private key pairs and / or passwords and everyone without valid keys is considered an adversary to the data he doesn't have access to, i.e. attackers may not undetected modify, add or drop data or being able to read the data if they have compromised everything except the client.

The server should hold the only copy of the database and should not have to give it out (due to size) if possible. As for the API, more standard APIs (SQL?) are preferred but custom ones are also acceptable as long as they support the usual queries (like ZeroDB and CryptDB do).

Reading your message, we (in ZeroDB) realize that we need to add some things to our documentation.

  Provides authenticity and secrecy (most important)

That one we do have now

  provides integrity over the whole database (no silent dropping of data)

We pretty much have it at the level ZODB we base on has (ACID-compliant)

  leaks as less information to the server as possible, doesn't have to hide access patterns

We don't leak properties of encrypted data like CryptDB, but we do slowly leak access patterns. Seems suitable for you

  allows for complex (cryptographically enforced) access rules

In the version currently on github, access rules are pretty simple (users own their sub-databases, but there are also "admin" users). We have a version with proxy re-encryption and possibility to grant/revoke access in end-to-end encrypted manner, in a granular way (column and row-based).

  It can be assumed that the clients do use / own public / private key pairs and / or passwords and everyone without valid keys is considered an adversary to the data he doesn't have access to, i.e. attackers may not undetected modify, add or drop data or being able to read the data if they have compromised everything except the client.

In current implementation, clients by default have their private keys derived from passphrases (trivial to add a possibility to use certificates though). Attackers may not modify or add data, though we need to add some extra protection against dropping data (detecting that an attacker removed piece of your data is possible but currently would take a while).

  The server should hold the only copy of the database and should not have to give it out (due to size) if possible.

This is how it works in ZeroDB

  As for the API, more standard APIs (SQL?) are preferred but custom ones are also acceptable as long as they support the usual queries (like ZeroDB and CryptDB do).

Seems like you're quite familiar with our query language :-) In future, we're going to add SQL compatibility since many people ask for that. May I ask: what types of queries do you need?

And yeah.. Merry Christmas :-)


Why did the NSA create SHA? new to cryptography, i'm trying to learn the program veracrypt, and i'm now trying to understand the history of hash functions and how it applies to veracrypt.

so this is what i understand so far, the NSA made SHA2, which is one of the hash functions that veracrypt can use for it's "key derivation function" and the NSA made SHA2 because they wanted an improvement on SHA1, and they made SHA1 because they wanted an improvement on SHA0.

what i don't understand is, why did NSA make SHA0 in the first place? and when did hash functions start being used for password storing and "key derivation functions"?

did hash functions start with the need for network security for verifying package? or did they start with the need of hashing passwords or both or what was the deal?

thanks!

The NSA created SHA (quickly replaced by SHA-1 to fix a security issue that remained unpublished for years) because they/the US government needed a 160-bit hash function, so that it has 80-bit security against collision-resistance, in particular towards use in the DSA signature system of FIPS 140.

In this usage, a hash functions condenses a possibly large piece of information $m$ (e.g. a 10MB file) into a smaller, easier to manipulate piece of information $h=H(m)$ (20 bytes for SHA-1), wich is what really gets signed. The hash must be collision-resistant, so that an adversary can't come with two distinct messages $m$ and $m'$ with $H(m)=H(m')$, which would allow the adversary to obtain a signature for $m$ from a legitimate signer, and pass it as the signature for $m'$.

SHA-1 uses principles similar to the earlier 128-bit MD5, but with a more regular design. Also it is big-endian, likely because that's customary (to the point of being unstated) in NIST crypto standards including DES/FIPS 43.


Why is DES secure against differential cryptanalysis I was wondering, why DES is secure against Differential Attacks. Some of the S-Boxes have a very bad Differential Uniformity, only one has a DU of 4, 3 have a DU of 6 and the others are much worse.

So is it because of the few good S-Boxes or because of DES uses 8 different S-Boxes?

It's mainly due to the use of multiple rounds and the presence of the various permutation and expansion mappings that bring the overall maximal differential probability to a very low level for key recovery.

This then leads to unrealistic requirements for chosen plaintext/ciphertext pairs encrypted under the same key, in ECB mode.

And the presence of different sboxes complicates things a bit further. Under current technology, or even for the last 20 years, a simple brute force key search with a small amount of plaintext ciphertext pairs is much simpler and easier.


Stretching definition of pseudo random number generator I am wondering if someone can say if the following qualifies as a PRNG.  Input a random bit seed of length $n$ into the generator, and over $k$ steps the generator uses $k$ publicly known integers to compute the pseudo random bit sequence, outputting a stream of $kn$ pseudo random bits.

I am wondering if the use of the $k$ (predefined) integers in computation still qualifies as a pseudo random number generator; if the integers need not be private, and need not be determined by the user do they count as part of the seed?

The PRNG definition is quite simple. The following two distributions should be indistinguishable

$D_1() :
   Y \leftarrow \{0,1\}^m$;
   Return $Y;$

$D_2() :
   K\leftarrow \{0,1\}^\kappa$;
   Return $G(K)$;

Here, $G:\{0,1\}^\kappa \rightarrow \{0,1\}^m $is your PRNG function. It is required that the adversary knows everything about G, including the values you refer to. The only thing the adversary does not know is K.

A function is a PRNG if an (polynomial time) adversary who has oracle access to $D_i()$ can not tell if they are interacting with $D_1$ or $D_2$.

So yes, it's OK to have your numbers. They are simply part of the description of the PRNG.


understanding LWE public key algorithm I'm trying to understand this LWE public key system

say I use matrix A = [[44, 73, 20, 54],[92, 19, 78, 22],[31, 34, 94, 29],[82, 32, 70, 68]]

q = 97

bit = 1

and secret key s: [56, 90, 0, 46]

and secret error vector e:[1, 0, -1, 0]

then B = As+e mod q is [73 17 18 27]

Bob's secret is [1, 0, 1, 1]

Bobby computes u = A*x mod q and get [21, 95,57, 26]

and v = Bx + bit(q/2) mod q and get 69

Alice decrypts:

v-s*u = 69 - 58 = 11

11 is quiet far from q/2 = 48

what am i doing wrong?

The message bit should be just that, a single bit, and $v$ should be a single integer modulo $q$. I am not sure how you’re getting $v$ to be a vector. Note that $b^t x$ is an inner product (mod $q$), so it is also a single integer mod $q$.


Is there a problem with constructing a CSPRNG using MD5 or SHA1? Is there any security concerns with building a CSPRNG using a broken hash function like MD5 or SHA1?  The design is such that a CRC-like function is used for mixing entropy and MD5 is used as the output function.  If this is a security concern, what is the technical reason?  What would be a better replacement when efficient is a concern?

Well, it is quite possible to have a CSPRNG that uses MD5, or SHA-1, despite their known flaws.  In fact, see Hash_DRBG with SHA-1 for an example that is officially endorsed by the US Government.  They don't endorse it for MD5; however, they really don't endorse MD5 for any reason (except within the TLS key derivation function).

The problem with MD5 and SHA-1 is that it is possible to create two different images that hash to the same value (with MD5, it turns out that you have quite a bit of flexibility, with SHA-1, it's been estimated to be practical, however I have not heard of anyone actually generating a colliding pair).  However, creating a collision means that the attacker gets to select both pairs; with a CSPRNG, the attacker cannot influence the internal state (he can only observe). This implies that the ability to create a collision has no impact on CSPRNG security; after all, even if the attacker generates a colliding pair, he has no way of making the CSPRNG use one of the preimages he has created.

Also, one warning: just because it is possible to design a CSPRNG based on SHA-1 or MD5 doesn't mean that design that you have in mind is actually secure.

Now, when you talk about efficiency, well, SHA-1 and MD5 aren't great; they're designed to hash things quickly, not generate hashed bytes quickly (oddly enough, those aren't the same thing).  The CTR_DRBG CSPRNG from the same document is somewhat better; however, the output of a good keystream generator (such as ISAAC) is going to be faster still.


Difference between plain AES CTR and "CCM-style" CTR I am trying to adapt the following function from SJCL, which does "AES-CCM" style CTR encryption, to do "pure CTR" encryption. I am playing around with SIV and would rather use this well-reviewed implementation rather than build my own CTR cipher from scratch. However, I'm having trouble understanding exactly what the CCM part does, and how I would go about modifying this routine to "strip out" the CCM functionality (the part that deals with the tag and the L parameter). My question is: what exactly is (are) the difference between the two CTR "styles", and how does that translate in the snippet below? Any help is appreciated.

_ctrMode: function(prf, data, iv, tag, tlen, L) {
  var enc, i, w=sjcl.bitArray, xor = w._xor4, ctr, b, l = data.length, bl=w.bitLength(data);

  // start the ctr
  ctr = w.concat([w.partial(8,L-1)],iv).concat([0,0,0]).slice(0,4);

  // en/decrypt the tag
  tag = w.bitSlice(xor(tag,prf.encrypt(ctr)), 0, tlen);

  // en/decrypt the data
  if (!l) { return {tag:tag, data:[]}; }

  for (i=0; i<l; i+=4) {
    ctr[3]++;
    enc = prf.encrypt(ctr);
    data[i]   ^= enc[0];
    data[i+1] ^= enc[1];
    data[i+2] ^= enc[2];
    data[i+3] ^= enc[3];
  }
  return { tag:tag, data:w.clamp(data,bl) };
}

The CTR part of CCM is basically the last for loop in the _ctrMode function:

  for (i=0; i<l; i+=4) {
    ctr[3]++;
    enc = prf.encrypt(ctr);
    data[i]   ^= enc[0];
    data[i+1] ^= enc[1];
    data[i+2] ^= enc[2];
    data[i+3] ^= enc[3];
  }

i.e. CTR is simply: encrypt a counter block with a block cipher, xor the encrypted block into the data, increment the counter, repeat...

(For those not used to the SJCL APIs, they tend to operate on 32 bit words rather than bytes).

As CodesInChaos mentions, while a CTR mode has been standardised (in NIST SP800-38A), 'CTR' is used as a component of a lot of other modes (e.g. CCM, GCM, SIV, EAX) and they differ substantially in how the initial counter is constructed (although most will follow the same basic approach once that is done).


Zero-knowledge signature verification Can you think of any solution to this problem? suppose we have three parties, A, B and C:

A has some data signed by C, a small part of which (not the signature) it wants to hide from B.
A wants to prove to B that the data (including the hidden part) has been signed by C. (B can't just verify the signature normally since some data is hidden).
B knows most of the data and the signature but not the hidden part. B doesn't want to know the hidden part, for him it's enough to know that the rest of the data is what it expects and that all of it was signed by C.
C won't cooperate for this in any way (other than originally signing the data including the hidden part); A and B are on their own.

Here is one possible way, that assumes:

C doesn't mind modifying how it signs data
C knows up front what part of the data is the hidden part
We don't mind if it isn't precisely zero knowledge, as long as we're at least as strong as the signature algorithm.

Then, here is how it works:

We'll assume ECDSA (or EdDSA); this assumption is mostly so we can reuse the same hard problem in our padding as in the signature, to make sure we're at least as strong as the signature.
We'll assume a hash function $F(m)$ which takes a message $m$, and converts it into an elliptic curve point; this function $F$ has the property that, for any two $m \ne m'$, the discrete log problem $nF(m) = F(m')$ is hard.
We'll assume another hash function $g(m)$ which takes a message $m$, and converts it into an integer between $1$ and $q-1$, where $q$ is the order of the Elliptic Curve.

To sign the message $(x, y)$ (where $x$ is the public part, and $y$ is the secret part, $C$ computes the elliptic curve point $(g(y))F( x )$, converts that into a bit string, and signs that.

For $A$ to prove that it knows $(x, y)$ that $sign( (g(y))F( x ) )$ is a signature to, it publishes:

$sign( (g(y))F( x ) )$
$(g(y))F( x )$
$x$
A zero knowledge proof that $A$ knows a solution to the discrete log problem $zF(x) = (g(y))F( x )$

$B$ then verifies that the signature is a valid signature to $(g(y))F( x )$; he then computes $F(x)$, and verifies that $A$ knows the value $z = g(y)$; he then concludes (because $F$ makes the discrete log problem hard) that $g(y)$ must be the value that $C$ originally used to sign, and hence $A$ must know $y$.


Show number of affected blocks using CFB DES decryption of altered ciphertext I have encrypted a file using -des -cfb and now I want to view how many blocks it contains once I decrypt it.

I have done this on the Linux terminal. I know that 9 blocks will be effected if there is an error in the ciphertext.

I need to show proof that this is true. But I'm unsure how to do this in a Linux terminal.

Block size = 1 byte for CFB thus 9 bytes are affected. Why this is true has been answered before. Even for CFB8 it takes 8 shifts to shift the wrong ciphertext value out of the buffer.

To proof this is true just change a single byte of a binary output file using a hex editor (hexedit) and then decrypt. Count the number of differing number of bytes (diff). If you get 8 bytes then the last byte refused to budge - it may regenerate the same value by chance. Redo from start, multiple times if you want "statistical proof".


Is there a signature scheme which doesn't rely on the difficulty of factoring/dlp which generates short signatures? The Lamport signature scheme, for example, doesn't rely on the difficulty of any problem and it only depends on the existence of one-way functions.
Is there an alternative scheme which also doesn't rely on the difficulty of factoring/discrete logarithm, but provides shorter signatures?

There are actually quite a few of these. Interest has been raised on this topic mainly due to the "post-quantum" security of such schemes. Also, Lamport is only a one-time signature, and we want a full-blown signature schemes.

For just one example see, SPHINCS: https://sphincs.cr.yp.to/sphincs-20150202.pdf.


Anonymity of Paillier cryptosystem in e-voting system I'm not an expert so at the moment I'm trying to figure out (at high level) how such cryptosystem would exploit it's homomorphic properties to guarantee anonymity in a e-voting system.

As far as i have understand given two plain number $x$ and $y$, I can sum those numbers and obtain $z$, with such cryptosystem I can encrypt them before the sum, so the adder has no idea of which numbers are involved :

$E(x) + E(y) = E(z)$

When decrypted $D(E(z)) = z$

Reading wikipedia, I find a statement that is not clear to me :

  Semantic security is not the only consideration. There are situations under which malleability may be desirable. The above homomorphic properties can be utilized by secure electronic voting systems. Consider a simple binary ("for" or "against") vote. Let m voters cast a vote of either 1 (for) or 0 (against). Each voter encrypts their choice before casting their vote. The election official takes the product of the m encrypted votes and then decrypts the result and obtains the value n, which is the sum of all the votes. The election official then knows that n people voted for and m-n people voted against. The role of the random r ensures that two equivalent votes will encrypt to the same value only with negligible likelihood, hence ensuring voter privacy.

So if I understand this is like the previous example, with the difference that all the votes are zeroes (against) or ones (for) and are casted for each option.

Eg :

There are four people ($A,B,C$ and the evil Trudy, when only first three people are valid voters).They can only cast $E(0)$ (against) or $E(1)$ (for) that is encrypted in a probabilistic way using election official's public key so $E_c(0) \neq E_a(0)$ and nobody can understand the vote of someone else simply comparing the encrypted votes.

After the votes are casted the election offical will see a sequence like that :

$E_a(0) , E_b(1) , E_c(1)$

Now if each vote is not signed (or identifiable in some way) how can I exclude that Trudy has not forged a huge amount of fake votes? For that reason I suppose that each vote has to be identifiable when still encrypted.
Now the election official sum all the encrypted votes

$E_a(0) + E_b(1) + E_c(1) = E(2)$

And then decrypt the result $D(E(2)) = 2$ obtaining the election result (2 on 3 valid voter is a win of the 'for' and a lose of 'against').

What I can't understand is what prevent the election official to decrypt that votes one by one and see who vote for what.

You've discovered some of the challenges of secure electronic voting. As you can see, merely having a cipher that allows you to confidentially tally numbers is not sufficient to conduct a secure election.

  Now if each vote is not signed (or identifiable in some way) how can I exclude that Trudy has not forged a huge amount of fake votes? For that reason I suppose that each vote has to be identifiable when still encrypted.

This is the issue of ensuring that each voter only gets one vote.

  What I can't understand is what prevent the election official to decrypt that votes one by one and see who vote for what.

This is an issue of vote privacy, the inability for even the officials who run the election to know who voted for what.

There are lots of different schemes that  use different techniques and make tradeoffs regarding the goals and efficiency.

E-voting is a subject unto itself. This paper provides a gentle introduction.


What are the uses of arbitrary length output hashes (other than OAEP)? Functions such as SHA-3 from the Keccak family allow for a hash of arbitrary length output. These functions are (according to Wikipedia) useful for practical, lightweight applications.

I know that SHAKE-128 and SHAKE-256 can be applied for OAEP.

My question is: Are there currently any other applications found for such functions?

Uses for SHAKE/XOF functions
Community wiki answer, please add and edit:

key derivation of any type

such as turning a 128-256 bit secret key into an ECC or RSA public/private key pair

deterministic secure uniform random number generation starting from a small seed

this might be used in fuzzing tools, simulations, etc. where you want a lot of random data for your experiment but you want it to be repeatable

stream ciphers

absorb the key and IV then output the key stream

authenticated encryption

such as the duplex construction

length-preserving data obfuscation or anonymization

One might hash all customer data from a production environment when being copied into a development environment. An XOF can presereve the data cardinality distribution as well as the data size distribution of the "real" production data for accurate testing and performance comparisons in non-production environments.

digital signatures

digital signatures such as EdDSA employ hash functions whose output must be a specific size, some of them "awkward" (e.g. Ed448 requires a 912-bit hash function). This can be easily accomplished with a XOF. (In fact, Ed448 uses SHAKE256.)


Is it acceptable to use a HMAC-SHA256 hash as a secp256k1 private key? Say I want to generate a deterministic private key related to some data, for instance to a domain name. The easiest way I can think of is:

take a secret material which will work as "generator".
take a domain name and HMAC-SHA256(my secret, domain name).
take resulting hash and use it directly as secp256k1 private key.

Question is if that last step is an OK move or are there issues with directly using hash as private key?

If your secret material (you call this my secret so I'll use that name) is chosen with sufficient min-entropy, then yes this scheme is acceptable. my secret, however, must be in itself sufficiently hard to guess; it becomes effectively a password cracking problem. As such, I would suggest my secret be a randomly generated keyfile, or at least a really secure password.
It's worth noting that if my secret is found, this system completely fails. So guard my secret very well. Be wary of keyloggers, shoulder surfers, malware, people nearby who happen to have a parabolic microphone (I'm not kidding), suspicious power outlets (also not kidding), and any number of other attack vectors.
Also, the benefit of a randomly generated key is, in the event of a compromise, you only need to change the key that gets compromised (or keys if multiple get compromised). In your deterministic case you have a single point of failure for the entire system, which according to Happy Quinn is not good (let's see if you can guess what I'm referencing).


Why do all SSH-RSA Keys begin with "AAAAB3NzaC1yc"? My friend and I have been generating a few SSH2 RSA keys and noticed all the public keys begin with AAAAB3NzaC1yc, with the similarity extending to AAAAB3NzaC1yc2EAAAABIwAAAQEA between two keys generated on the same machine in two successive attempts (googling AAAAB3Nz ends up getting a few hits as well).
Is this normal or are we doing something wrong while generating, such as suffering from insufficient entropy?

The public key blob doesn't consist of just the numbers that make up the public key: it begins with a header that says “this is an SSH public key”. The repeated prefix encodes this header.

RFC 4254 specifies the encoding of public key in SSH key format.

  The "ssh-rsa" key format has the following specific encoding:

 string    "ssh-rsa"
 mpint     e
 mpint     n

  Here the 'e' and 'n' parameters form the signature key blob.

The string is encoded as 32-bit big endian length followed by the literal string:

0,0,0,7,'s','s','h','-','r','s','a'

Encoding this sequence of bytes in Base64 gives:

AAAAB3NzaC1yc2E

The public exponent is also usually the same, so the common prefix is even longer. The bulk of the key is the public modulus, and that is completely different in different keys.


Why is the signature field in X.509 a BIT STRING, despite there being ASN.1 (DER) data inside? As can be seen from the following ASN.1 definition of an X.509 certificate, the Signature field is a BIT STRING.

Certificate ::= SEQUENCE {
    tbsCertificate      TBSCertificate ({ x509_note_tbs_certificate }),
    signatureAlgorithm  AlgorithmIdentifier,
    signature       BIT STRING ({ x509_note_signature })
}

However, at least for the rsaEncryption algorithm, there's ASN.1 DER data inside (representing the signature).

So, why is it a BIT STRING?
Wouldn't something like SEQUENCE or just OCTET STRING work better?

The contents of the signature field is dependent on the signatureAlgorithm being used. So it can hold anything (including DER serialisation) for as long as it's eventually encoded as a BIT STRING.

Therefore the length of the signature can be different. Using BIT STRING allows you to know the exact number of bits being used in the signature. With OCTET STRING you may get some extra bits at either ends of the octet-stream which would probably need some special handling to exclude them from further processing at the receiving end.

The SEQUENCE type is like a record, I am not sure why it could be useful here.


Convergent Encryption: integrity and authenticity I have one question about convergent encryption.

Suppose I use AES-256 in CBC mode. I need a 256 bits key and a 128 bits IV. If I use SHA-256 to hash one file, then I can use directly that hash as the key.

When decryption occurs, is integrity and authenticity given by checking the hash of the decrypted plaintext, OR is there a need to add additionnals integrity and authenticity checks like CBC-MAC ?

If you use the hash as a known key, then you do not need any additional authentication to ensure plaintext integrity. An attacker cannot find another plaintext with that hash value unless the hash is broken.
However, there are two problems with that:

Like MAC-then-encrypt the hash only ensures authenticity of the plaintext, not of the ciphertext. This leaves it possible for an attacker to use chosen ciphertext attacks and CBC implementations may be vulnerable to the padding oracle attack.

Typically in convergent encryption you have a longer term secret key that is used to encrypt many plaintexts, and the hash that is used as key for one plaintext gets encrypted for the long term key.
Unless the hash/key is encrypted with authenticated encryption, a chosen plaintext attack could allow an attacker to halve the hash space to 128 bits, for which collisions could be found. I.e. you probably want to ensure the authenticity of the encrypted hash, if you use this setup.

Thus, I would recommend using authenticated encryption the whole way through. If you are concerned about space usage, you can shave off some by getting rid of the IV. One-time keys can be used with zero IV.


Would it be possible to generate the original data from a SHA-512 checksum? So, I have a file that is XY Exabytes big. I create a SHA-512 hash from it.

Are there any theoretical chances that I can retrieve the original data just from the sha512 hash?

Also, are there any better hashes then sha512?

No, because a  hash behaves (simply put) like a lossy compression function.

Meaning: you can use a hash like a sort of checksum, which enables you to identify and compare data. Using hashes, you can see if data has been modified (which, if re-hashed, would show a different hash as a result), or if two or more data packages are the same (every data package you hash will produce the same hash if the data is the same too).

But: you can not recreate the original data that was hashed. For that, you would need a (loss-less) compression function like you might know it from ZIP files.

So, no, you can not recreate the original data from it's hash. The only thing a hash is good for is to compare it with other hashes to see if the hashed data is identical or not.

To give you a real-world perspective on hashing data and your question about "extracting" the original data from a hash: expecting someone to be able to reproduce the original data from a hash, would be like asking someone to create a nice dinner for all of us while only having a receipt available.

The only option to try to recreate data that results in a predefined hash, would be to "brute-force" it with a trail-and-error approach where you create random data sets, hash those, and hope that they produce the same hash you've got. While such a brute-force method works with small data packages, it won't work for big data-sets as you describe them since it would take too long until you "by chance" happen to produce exactly the same data-set that once existed and which produced the originalhash. Good luck with that... you can safely expect to waste a life-time trying to get that one lucky match that fits a specific, predefined hash.

While I'm at it: it might be interesting for you to know that older and mostly broken hashes (MD2 etc) are known to have certain weaknesses that result in so-called "hash collisions". Such hashes are broken because those hash collisions mean nothing else than  that two different data-sets produce the same hash, which should not happen as a hash is expected to produce a unique values for different data-sets. But that's just additional knowledge as hash collisions merely show the related hash fails it's job; they can not and will not help you recreate the data either. Why? Because a hash is something like an identification tag. It does not hold all the hashed data, and can therefore not reproduce it in any way.


Countering Cryptographic Attacks By reading Camellia Design and Analysis document following is my understanding about few cryptographic attacks from designer point of view.

Differential and Linear Crypt-analysis. Number of Active S-boxes along-with the Differential and Linear probabilities of S-box contributes towards resistance against these attacks which also depends upon the branch number of the P Box. (Diffusion layer).
Truncated Differential. If there does not exist an iterated truncated differential with higher probability than exhaustive keysearch then cipher is safe against this type of attack. (I need to learn more about how to counter this attack)
Impossible Differential. There exist one 5 round impossible differential in feistel cipher with bijective F function. So cipher with more than 10 rounds will have a good security margin against this attack.
Boomrang Attack. This uses two differentials and security against these again depends upon number of active S-boxes along-with the Differential probability of the S-box.
Higher Order Differential. To resist this attack, Degree of the Boolean polynomials of the S-Boxes should be higher.
Equivalent Keys. Use of original key as one round subkey reduces the chance of Equivalent key classes.
Slide Attack. Ciphers with iterated identical round functions are suspect-able to such attack however use of Pre and Post whitening keys provide resistance against this attack.(assuming Pre / Post whitening keys have been generated from a strong keyschedule)

Do i have right understanding countering these attacks?

Differential and Linear Crypt-analysis. Number of Active S-boxes
  along-with the Differential and Linear probabilities of S-box
  contributes towards resistance against these attacks which also
  depends upon the branch number of the P Box. (Diffusion layer)

it is not only the branch number that influences on the number of active s-boxes, the cells permutation has a role, different permutations have different number of active s-box over rounds such as in skinny and midori cases.ref

  Impossible Differential. There exist one 5 round impossible
  differential in feistel cipher with bijective F function. So cipher
  with more than 10 rounds will have a good security margin against this
  attack

in term of SPN ciphers , according to this paper, the existence of impossible differential up to 6 rounds which are strongly related to the linear transformation properties.

  Boomrang Attack. This uses two differentials and security against these again depends upon number of active S-boxes along-with the Differential probability of the S-box.

a new measure analysis called boomerang connectivity table of S-box provides insights on boomerang crypt analysis which provides a fundamental understanding how the S-box  properties counter the boomerang attack. ref

  Higher Order Differential. To resist this attack, Degree of the Boolean polynomials of the S-Boxes should be higher.

using larger S-box with higher algebraic immunity provides a counter to higher order differential.

what about integral crypt analysis (division property of sbox) ?


Definition of $x^u \bmod k$ In RSA, $C=M^e \bmod N$ and $d=e^{-1} \bmod φ(N)$ are used for encryption and signatures.
What is the exact definition of $x^u \bmod k$?
Also, what is the difference between $$x^u = y \bmod k$$ and $$x^u \equiv   y\bmod k$$

What is the exact definition of $x^u\bmod k$?

In RSA and most cryptographic contexts, $x^u\bmod k$ is written with:

$k$ in the set $\Bbb N^*$ of strictly positive integers. $k$ is the modulus (plural moduli)
$u$ in the set $\Bbb Z$ of signed integers. $u$ is the exponent.
$x$ in the set $\Bbb Z$ of signed integers, or in the set $\Bbb Z_k$ of integers modulo $k$. The later is a special case of the former, since we'll assimilate $\Bbb Z_k$ to the non-negative integers less than $k$.

$x^u\bmod k$ can be spoken « $x$ raised to the power $u$ [small pause] modulo $k$ », and becomes « $x$ to the $u$ mod $k$ », or « $x$ to $u$ » under time constraints.
For the full definition, skip to $\eqref{fgr4}$. For a gentle introduction, we'll first study the
definition with exponent $u>0$
When $u>0$, the notation $x^u\bmod k$ just stands for $\left(x^u\right)\bmod k$, where $x^u=z$ and $z\bmod k=y$ have their usual definition:

$x^u$ is $\underbrace{x\cdot x\cdots x\cdot x}_{u\text{ term(s)}}\,$ where $\cdot$ is integer multiplication. More formally
$$x^u\,\underset{\text{def}}=\begin{cases}
x&\text{if}\,u=1\\
x\cdot\left(x^{\left(u-1\right)}\right)&\text{if}\,u>1
\end{cases}\tag1\label{fgr1}$$
Note: the parentheses would usually be omitted¹.
$z\bmod k$ is defined to be $y$ such that $0\le y<k$ and $z-y$ is a multiple of $k$. Equivalently:

$z\bmod k$ is obtained from $z$ by subtracting or adding $k$ as many times as necessary for the result to be in range $[0,k)$. More formally:
$$z\bmod k\,\underset{\text{def}}=\begin{cases}
z&\text{if}\,0\le z<k\\
\left(z-k\right)\bmod k&\text{if}\,z\ge k\\
\left(z+k\right)\bmod k&\text{if}\,z<0
\end{cases}\tag2\label{fgr2}$$
If $z\ge 0$, then $z\bmod k$ is the remainder in the Euclidean division of $z$ by $k$;
otherwise, $z\bmod k$ is $k-1-\left(\left(-z-1\right)\bmod k\right)$.
More formally, noting $\ell$ for the quotient (with $\ell=\left\lfloor z/k\right\rfloor$ per the mathematical definition of that):
$$z\bmod k\,\underset{\text{def}}=y\in\Bbb Z_k\,\text{ such that }\,\exists\ell\in\Bbb Z\,\text{ such that }\,y=z-\ell\cdot k\tag3\label{fgr3}$$

Example: We compute $3^5\bmod35$ directly from this definition. That's $x^u\bmod k$ with $x=3$, $u=5$, $k=35$. We compute $x^u=3^5=3\cdot3\cdot3\cdot3\cdot3=243$. We perform the Euclidean division of $z=243$ by $k=35$, yielding quotient $\ell=6$ and remainder $y=243-6\cdot35=33$. Thus $3^5\bmod35=33$.
In Python, the above is obtained as (3**5)%35 or pow(3,5)%35 or pow(3,5,35). The three forms internally use exponentiation by squaring, but only the later uses modular reduction of intermediary results. Using both techniques is essential for even mildly efficient modular exponentiation in RSA, e.g. encryption per $C=M^e\bmod N$ with common parameters like 2048-bit $N$ and $e=65537$.
Starting with Python 3.8, pow also handles all the following.

Extensions to any integer exponent $u$
The full² definition of $x^u\bmod k$ in cryptography is:
$$\begin{array}{l}
x^u\bmod k\underset{\text{def}}=\\\\
\begin{cases}
y\in\Bbb Z_k,\;\exists\ell\in\Bbb Z,\;y=x^u-\ell\cdot k&\text{if }u>0\\
y\in\Bbb Z_k,\;\exists\ell\in\Bbb Z,\;y\cdot x^{-u}+\ell\cdot k=1&\text{if }u<0,\;k>1\text{ and }\gcd(x,k)=1\\
\text{undefined}&\text{if }u<0,\;k>1\text{ and }\gcd(x,k)\ne1\\
1&\text{if }u=0,\;k>1\\
0&\text{if }k=1\\
\end{cases}\end{array}\tag4\label{fgr4}$$
In this, $\Bbb Z_k$ stands for the non-negative integers less than $k$, or equivalently the integers modulo $k$. “$\text{such that}$” is replaced by “$,\;$” which is common practice (suppressing it is also accepted).
This definition extends $\eqref{fgr3}$ to the multiplicative group of integers modulo $k$, that is the subset $\Bbb Z_k^*$ of $\Bbb Z_k$ that forms a group under multiplication modulo $k$. For negative $u$, the notation $x^{-u}\bmod k$ is now defined as the multiplicative inverse of $x^u$ in $\Bbb Z_k^*$.
Definition $\eqref{fgr4}$ maximizes the domain where it holds the property:
$$\begin{array}{l}
\text{if }\,x^u\bmod k\,\text{ and }\,x^v\bmod k\,\text{ are both defined, then}\\
\quad\bigl(\left(x^u\bmod k\right)\cdot\left(x^v\bmod k\right)\bigr)\bmod k\;=\;x^{u+v}\bmod k
\end{array}\tag5\label{fgr5}$$
When $u<0$ and $k>1$, the equation $y\cdot x^{-u}+\ell\cdot k=1$ follows from extending definition $\eqref{fgr3}$ with $y=x^u\bmod k$ constrained to be an integer, while insuring property $\eqref{fgr5}$. With $x^{-u}$ replaced by $z$, that becomes a Bézout identity $y\cdot z+\ell\cdot k=1$. The requirement $\gcd(x,k)=1$ pops up, as well that $y$ and $\ell$ can³ be computed per the extended Euclidean algorithm (that can yield $y<0$; we need to bring it back to positive by reducing it modulo $k$, or equivalently adding $k$).
Example: We compute $3^{-5}\bmod35$ directly from this definition. That's $x^u\bmod k$ with $x=3$, $u=-5$, $k=35$. We compute $x^{-u}=3^5=3\cdot3\cdot3\cdot3\cdot3=243$. We perform the extended Euclidean algorithm to solve for $y$ (and $\ell$ that we don't need) the Bézout identity $y\cdot 243+\ell\cdot 35=1$. Using the pseudocode of this Try It Online!, the steps are
$$\begin{array}{rrrrrrr|rrr}
r&r'&s&s'&t&t'&q&z\cdot s+k\cdot t&=&r\\
\hline
243&35&1&0&0&1&6&243\cdot1+35\cdot0&=&243\\
35&33&0&1&1&-6&1&243\cdot0+35\cdot1&=&35\\
33&2&1&-1&-6&7&16&243\cdot1+35\cdot(-6)&=&33\\
2&1&-1&17&7&-118&2&243\cdot(-1)+35\cdot7&=&2\\
1&0&17&-35&-118&243&&243\cdot17+35\cdot(-118)&=&1
\end{array}$$
and that yields $y=17$, $\ell=-118$. Thus $3^{-5}\bmod35=17$.
The definition $\eqref{fgr4}$ is such that
$$\begin{array}{l}
\text{if any two among the three $\;x^u\bmod k$, $\;\;x^v\bmod k$, $\;\;x^{u\cdot v}\bmod k$}\\
\text{are defined, then all three quantities are defined, and}\\
\quad\left(x^u\bmod k\right)^v\bmod k\;=\;x^{u\cdot v}\bmod k\;=\;\left(x^v\bmod k\right)^u\bmod k
\end{array}\tag6\label{fgr6}$$
Applied for a negative $w$ with positive $u=-w$ and $v=-1$, $\eqref{fgr6}$ allows computing $x^w\bmod k$ using modular exponentiation with a positive exponent, and (after or before that) a modular inversion, thus avoiding monstrously large input to the extended Euclidean algorithm, and using alternative algorithms.

The meaning of $\bmod$ [reference to Monty-Python intentional]
In some contexts including the definition of RSA, we need to distinguish two kinds of $\bmod$

An operator, yielding e.g. the remainder of Euclidean division when applied to two strictly positive integers. It is to be typeset using \bmod k in $\LaTeX$ / MathJax (see this, or this for more). In this case, that operator's result, when and if defined, is always a non-negative integer less than the modulus. And, depending on context, that operator has

two arguments like in $7\bmod5$, or in $7\bmod5\,=\,2$, or in $2\,=\,7\bmod5$. The first is the integer $2$, the later two are two true statements.
three arguments like in $3^{-1}\bmod5$, or in $3^{-1}\bmod5\,=\,2$, or in $2\,=\,3^{-1}\bmod5$. The first is the integer $2$, the later two are two true statements.

The indication of modular equivalence (class) in what stands on its left. That is best typeset:

As \pmod k in $\LaTeX$ / MathJax, which shows as “$\pmod k$” with an opening parenthesis “$($” immediately before $\bmod$ and a closing parenthesis “$)$” after the modulus.
And⁴ with the sign $\equiv$ rather than $=$ anywhere on its left.
And with only the closing parenthesis on the right of the modulus.

Example of typographically and mathematically correct usages of modular equivalence:

Definition: $r\equiv s\bmod m\;\underset{\text{def}}\iff\;\exists\ell\in\Bbb Z,\,r=s+\ell\cdot m$
In any valid RSA public/private key, $e\cdot d\equiv1\pmod{\lambda(N)}$
It holds $7\equiv2 \pmod 5$ thus $2\equiv7 \pmod 5$
It holds $3^5\equiv243\equiv33 \pmod{35}$ thus $33\equiv3^5 \pmod{35}$
$\lambda(35)=12$ and $-5=7 \pmod{12}$, thus $3^{-5}\equiv3^7\equiv2187\equiv17 \pmod{35}$.
$7\pmod 5$ can be seen as the infinite set $\{\ldots,-8,-3,2,7,12,\ldots\}$.

Sometime a statement is false with the operator from, that would be true as a modular equivalence: $7=7\bmod5$ stands for $7\,=\,(7\bmod5)$ thus is false, when $7\equiv7 \pmod 5$ is true.
The distinction matters in RSA encryption, with ciphertext $C$ specified by $C=M^e\bmod N$ where $M$ represents the message. In this, $\bmod$ is an operator, thus implies $0\le C<N$, which is important. An encryption system only specified to output $C$ such that $C\equiv M^e\pmod N$ could output $C=M^e$ and be totally insecure, or leak some sensitive information by selectively producing $C=(M^e\bmod N)+N$.

What is the difference between $x^u=y\bmod k$ and $x^u\equiv y\bmod k$ ?

The cardinal way to read the correct $x^u=y\bmod k$ is as $x^u=(y\bmod k)$ with $\bmod$ an operator. Unambiguously, that implies $x^u\equiv y\pmod k$, that is $y-x^u$ is a multiple of $k$. Formally, $x^u=(y\bmod k)$ also implies $0\le x^u<k$. But it is not often that $0\le x^u<k$ is meant, thus I try to not use $x^u=y\bmod k$, and would use $x^u=(y\bmod k)$ only if $0\le x^u<k$ was intended.
I'm reading $x^u\equiv y\bmod k$ (using \bmod) as a slight $\TeX$po™ of $x^u \equiv y\mod k$ (using \mod, which adds spacing on the left to indicate that it is not an operator) or $x^u\equiv y\pmod k$ (using \pmod, which adds parentheses to more clearly indicate the same thing). Thus here $\bmod$ stands for modular equivalence. I avoid \mod when \pmod rather than \bmod is meant, because except in contexts like tex-SE or a JOC paper, 90% of the audience will not interpret the slight extra space correctly.

¹ Raising to a power is performed before multiplication (thus before addition), tough after any operation in the exponent. The exponent is on the right, and is typographically distinguishable by being higher and in smaller characters. If that's not feasible, it is often used ** or ^^ (or ^ when confusion with eXlusive-OR operator $\oplus$ is impossible), and parentheses.
² Sometime $x^u\bmod 1$ and/or $x^0\bmod k$ with $\gcd(x,k)\ne1$ are left undefined or unspecified, for simplicity and because they are seldom practically useful.
³ Since we do not need $\ell$, we can simplify the extended Euclidean algorithm by removing the two variables $t$ and $t'$. When performing the algorithm by hand, that has the drawback we can't check intermediary results. But we can still check $y\cdot z\bmod k=1$ in the end.
⁴ Sometime, this $\equiv$ becomes $=$, or the $($ immediately on the left of $\bmod$ vanishes [together owith the matching $)$ after the modulus]. But absent at least one of these indications, the meaning changes: we are back to the $\bmod$ operator.


Is it feasible to use combination of ABE schemes for encrypting the data? I have a peculiar requirement for preserving the shared log files. For example I have 1000 records which belong to different organizations as listed below and all the logs are present in a single CSV file.

1-100 records --> ORG-A;
101-200 records --> ORG-B;
.
.
901-1000 records --> ORG-Z;

In the initial set 1-100 records the data should be decrypted only by ORGANZATION-A users, out of those 100 records, few records are accessible by Administrators and other 90 records are accessible by normal users (basically  users with particular role can access some set of records among those 100 records).

I am trying to solve the above problem using combination of ABE schemes viz., KP-ABE and CP-ABE schemes:

Encryption

Basically I would encrypt each of record fields 1-100 using CP-ABE scheme (ciphertext policy). I choose CP-ABE because it  allows RBAC (role based access control) policies to be embedded into the cipher text.
I would encrypt the records 1-100 again using tags related to organization using KP-ABE scheme. This means that only users of particular organization can decrypt the records.

Decryption

Use private keys associated with KP-ABE scheme first and then CP-ABE scheme to access the data.

I am still learning how to use ABE schemes in real world. I will be happy if someone can validate my thoughts in solving the problem related shared-logs along with RBAC policies.

Layering your encryption mechanisms like that would not display collusion-resistance between the two schemes. For example, someone with an Org-A key could decrypt the outer encryption over a record designated for Org-A administrators and then pass the inner ciphertext to someone with an Administrator key. Of course, you could use a different key for each Org's administrators, but that's just business logic, not a cryptographic guarantee.

I think you're thinking ABE too narrowly. It sounds like you're trying to force ABE to operate like IBE, which is totally possible, but not the best use of its capabilities. With CP-ABE, you can specify multiple attributes per key and multiple policies per ciphertext, and relate those ciphertext policies using a custom-built predicate expression.

With this in mind, it seems to me that the simplest option for your log-file problem is to encrypt each record using CP-ABE under a predicate that matches exactly the circumstances decryption is supposed to occur under. Each key can contain both the attributes for organization membership and the attributes for role within the organization. For example, records 1-90 might be encrypted to "Org-A" by itself, and records 11-100 to "Org-A AND Org-A-Admin" instead.


Do I need to worry about the IV if I use a 32 byte random salt with SCrypt and AES-GCM? I am encrypting a DEK (data encryption key) with a KEK (key encryption key). The KEK is generated from a password using scrypt with default parameters and a 32 byte randomly generated salt. The encryption algorithm is AES-GCM.

What are the implications for the IV in this case? Let's assume that the IV is initialized to 0 (96 bits of 0s). If I re-use an IV with a key then this is bad news. Since the key is generated from the password it will always be the same. But I do generate a random 32 byte salt each time I re-encrypt the file which should provide a different key each time. I would assume that a 32 byte salt would change the KEK significantly so that the zero initialized IV would not pose an issue for GCM. Is this a valid assumption?

If you use the key only once, then there is no danger of reusing a nonce with the same key because you're not even reusing the key!

A collision in the salt and password would lead to the same key, but though the probability of such a collision may be nonzero, it is nevertheless negligible for a 32-byte salt—unless, of course, you roll back your VM state and get the same initial RNG state, or equivalent.

Do make sure to use AES-256, by the way, and not AES-128, if you want a 128-bit security level.


Hill Cipher Plaintext Attack: Dealing with Non-uniqueness of Matrix Inverses? I'm following along with my book. Here is an example of a plaintext attack from it:

It is known that:
plaintext = 'friday'
ciphertext= 'pqcfku'
$m$ = 2

We will use this to form the following matrix equation:

$$ C = PK $$
$$\pmatrix{5 & 16 \\ 2 & 5} = \pmatrix{5 & 17 \\ 8 & 3} K $$

Where $K$ is the key matrix. Note that $K = P^{-1} C$. To find that product, we must first find $P^{-1}$.
Now this is where I don't understand the book. The book says:

$$P^{-1} = \pmatrix{9 & 1 \\ 2 & 15}$$
First I tried verifying this in Mathematica. The command Inverse[{{15, 17}, {8, 3}}, Modulus -> 26] yields an error saying there is no such inverse... bizarre. I then found this online calculator to do it, and it returns the result:
$$P^{-1} = \pmatrix{13 & 5 \\ 10 & 23}$$

A quick check tells us that BOTH these matrices are correct inverses mod 26. But, only the inverse provided by the book works in correctly computing the key, and thereby being able to break the cipher.

So... how can I conduct a plaintext attack in this manner? There appear to be multiple inverses. How do I know which one is "right"? And if I must brute force, how can I find ALL possible inverses?

More standard is that we multiply a column with a plain text vector to get the cipher text vector so the known plain text equation (the first two pairs) yield

$$KP=C = K\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix} = \begin{bmatrix}15 & 2\\16 & 5\end{bmatrix}$$ so I get $P=\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix}$ which is invertible as $\det(P) = 15 - 8 \cdot 17 = 9$ and $9$ is invertible modulo $26$, with inverse $3$ as $3 \times 9 \equiv 1 \pmod{26}$.

The inverse is easily computed (as for all $2\times 2$ matrices) via

$$P^{-1} = 3 \cdot \begin{bmatrix}3 & -8\\-17 & 5\end{bmatrix} = \begin{bmatrix}9 & 2\\1 & 15\end{bmatrix}$$

which is easily checked to be the inverse. Note that the matrix in your text uses the transpose (as it left multiplies by $1 \times 2$ matrices instead, so all equations transpose) and the one from the online calculator is not an inverse at all (which becomes obvious if we do the full matrix multiplication; only the first row looks OK). So that online calculation is wrong, and Mathematica is confused (and you made a typo: 15 should be 5 I think).

Anyway, knowing $P^{-1}$, $$K = CP^{-1} = \begin{bmatrix}7 & 8\\19 & 3\end{bmatrix}$$ (your text probably gives its transpose) and this indeed checks out as $$\begin{bmatrix}7 & 8\\19 & 3\end{bmatrix} \begin{bmatrix}0 \\ 24\end{bmatrix}=\begin{bmatrix} 10 \\ 20\end{bmatrix}$$

so it maps the plain ay to ciphertext KU. The decryption matrix is
then $$K^{-1}=\begin{bmatrix}23 & 8\\19 & 19\end{bmatrix}$$ if you want to decrypt the rest (or its transpose if working by rows from the left, as before).


Understanding the linear cipher decryption process Being new to Cryptography, I'm having a hard time understanding the basic concepts.

I understand all parts except why 4 power -1 has become to 7.

Can anyone explain why this is?

First note the $\pmod{27}$ at the end, which tells us that all these equations are to be taken modulo $27$.

Also note that $4^{-1}$ literally means "the number $x$ such that $x\cdot4=1\pmod{27}$" (much like with the real numbers where $4^{-1}=\frac14$ with $4^{-1}\cdot 4=\frac14\cdot 4=1$).

Finally observe that $7\cdot 4=28\bmod 27=1$ and it follows that $7=4^{-1}\pmod{27}$.


Computational indistinguishability: are function parameters known? I would like to clarify something about the definition of computational indistinguishability and pseudorandom number generators. Suppose we wanted to show that linear congruential generators of the form $x_t = ax_{t-1} + b \pmod m$ are not pesudorandom number generators. Then we wish to show that given a sequence of numbers $x_0, x_1, \ldots$, we can distinguish whether these numbers came from the lcg process above, or are coming from a uniform distribution (in polynomial time, with high probability, etc...).

In doing so, do we assume that we are given the parameters $a,b$ and $m$? On the one hand, if we are given these parameters, then isn't this trivial? Just check if the given sequence satisfies the given lcg... On the other hand, even if we don't know $a,b,m$, there still clearly does exist a polynomial time algorithm that happens to have $a,b,m$ hard-coded into it that could be used to distinguish these sequences from truly random ones.

What is the correct interpretation here? Does it even make sense to ask whether LCGs are pseudorandom generators in the sense of computational indistinguishability?

You're right: If you know the setup, calculating the next output from any given $x$ is fully deterministic and you know everything already.

Even if you don't know $a$ and $b$, those are easy to calculate from three consecutive $x_i$. If $n$ is not known, its calculation is still pretty easy, given a few consecutive $x_i$.

Anyway, LCGs are very unsuitable for cryptographic tasks. That's why in pretty much every standard library you find a warning not to use the standard Random class for cryptographic protocols (at least for Java and Python I know those warnings are there).

Usually not the entire output is used, but only a part of it, because otherwise two consecutive numbers can't be equal (and ever change again afterwards). Such an RNG is good enough for almost all non-security-related context, where randomness is needed (it is good enough for a little randomness. But e.g. in simulations, where a lot of random numbers are needed, you want "better" randomness, e.g. from the Mersenne Twister). Anyway, predictable PRNGs (without the CS) based on any such construction is not suited for cryptography. For CSPRNGs, you can find a couple of designs on wikipedia.


How do we know one-way functions can be iterated? Suppose we have some one-way function $h$. Without further specification of $h$, how can we be sure that we can define another function $g(n) = h(h(n))$?

That is, how do we know the range of $h$ is a subset of the domain of $h$?

Relevance to Cryptography: One-way functions are minimal assumptions for the constructing pseudorandom generators. Thus, one-way functions are fundamental to theoretical cryptography (perhaps not for applied cryptography)....but cryptography all the same.

We cannot - we might need another function to adjust the value to be acceptable. Assuming however that $h$ is a hash - this is the crypto site - then it should accept any size of input in bits; up to a seriously high limit anyway.


Block cipher fixed points (plaintext equal to ciphertext) A block cipher is a bijective map from the set of possible plaintexts to the set of ciphertexts, which are the same size and might as well be considered the same thing: $\theta: S\to S$. In this there must exist a fixed point m $\in S$ such that $\theta(m) = m$ (alternatively you could consider encryption to be a binary operator acting on the set $S$ then you could write encryption under key $k$ as $m \odot k = m$, with $m,k \in S$. Unfortunately this cannot form a group since there is no unit $e$ that makes $e \odot k = e$ for all $k \in S$).

It is clear that when the block size is equal to the key size a single fixed point will exist when you hold the plaintext message constant and permute the key. The key allows you to select one of all the possible possible unique mappings, of which one must surely be a fixed point (am I right about my use of the word unique here?).

What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, or equivalently many different keys that will decrypt a ciphertext.

Note: I would also be interested to see articles that apply algebra to the study of block ciphers. Specifically constructing groups to aid analysis that also consider the fact that a block cipher is a composition of several round functions.

The question makes a number of statements that are incorrect.  It is not correct that a fixed point is guaranteed to exist.  It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist.  Moreover, the existence of fixed points has only an extremely tenuous connection to security.

Assume $E$ is a secure block cipher.  A reminder of standard notation: $E_k(x)$ denotes the encryption of plaintext $x$ under key $k$ using this block cipher.

Here are some results on the number of fixed points, for different mappings derived from the block cipher $E$:

If we fix a key $k$ and look at the mapping $x \mapsto E_k(x)$, then we expect this to look like a random permutation.  The expected number of fixed points in a random permutation is 1, but this number varies from permutation to permutation.  The probability that a random permutation has no fixed points is $1/e \approx 0.37$.  For more facts on fixed points of a random permutation, see Random permutation statistics.
If we fix a plaintext $x$ and look at the mapping $k \mapsto E_k(x)$, then for most modern block ciphers we'd expect this to look like a random function.  If the key has the same size as the ciphertext, then the expected number of fixed points (treating it as a random function) is again 1.  The probability that a random function has no fixed points is again $1/e \approx 0.37$.

See also Does AES have any fixed-points?, and also The Ideal Cipher Model (wonky) on Matt Green's excellent blog.

The reason a longer key provides extra security has nothing to do with fixed points.  It has to do with the fact that a longer key provides better resistance against certain other attacks (e.g., brute-force keysearch).

In short: I think you are laboring under some misconceptions about the existence of fixed points in block ciphers, and their relevance to security.


Why are huge prime numbers important in cryptography? I read an article the other day about the search for prime numbers.  According to the article and several online sources the biggest prime number is over 17 million digits!  This made me wonder why anyone would want a prime number that big.  The article went on to say that there is a $250k reward for who ever find the first billion+ digit prime.  The article said that primes are used in cryptography and explained briefly why.  But my question is why is there such a demand for these "super primes" which seem extremely bulky and unnecessarily big(a text file holding a billion digits would be over 1gb of data).

EDIT: I know that similar questions have been asked about primes place in cryptology but I'm wondering specifically about these massive primes that people are paying big bucks for.

Preposterously large primes are not useful for cryptography in and of themselves, but the tools and techniques developed to find them (such as massively parallel distributed computing, algorithms that can efficiently confirm primality, etc) are important for cryptography.  The prizes are meant to spur innovation in those areas.  See e.g. https://www.eff.org/awards/coop


Is it possible to use an algorithm to generate an OTP? I am a software developer, not a cryptologist.

I like the idea of perfect secrecy and would like to use a one-time pad (OTP) to encrypt/decrypt files up to, say, 50Mb.  Is there a way that I can use random number generators and seeds to do this, rather than creating the (very large) pad in advance?

For example, if I used a CSPRNG to create two numbers, then used the first number to seed a (predictable) PRNG, and the second number to determine which number in the sequence to use as the first in the pad, would this still give me perfect secrecy?

This is a standard concept in cryptography, and it is called a stream cipher.

It doesn't give ‘perfect’ secrecy, which is a red herring, but it is the modern standard for how to do cryptography—for example, your web browser is almost certainly using exactly this principle right now to talk to the crypto.stackexchange.com web server, using either AES-GCM or ChaCha/Poly1305, which are authenticated ciphers built out of stream ciphers.

Much more important: Use an authenticated cipher so that a forger can't modify your messages in transit, which can sometimes—like in OpenPGP's EFAIL—have the consequence of losing confidentiality too.


What does the "Type 1 query" model on Miles, Sahai, and Zhandry's paper? On the paper Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13, authors present, in section 2, an abstract model to analyze security of $i\mathcal{O}$ and current multilinear maps candidates.

In this model, there are two queries that an attacker may do, but I'm now interested on the first one: the Type 1 query, which works as follows:

The attacker has a polynomial $p_k = p_k^{(0)}(\{X_j\}, \{Z_i\}) + gp_k^{(1)}(\{X_j\}, \{Z_i\}) + g^2p_k^{(2)}(\{X_j\}, \{Z_i\}) + ...$ on variables $X_j$, $Z_i$, and $g$, and it may submit this polynomial to the challenger. Then, the challenger answers in the following way:

  If $p_k$ is identically 0, then the adversary receives $\perp$ in return. If $p_k^{(0)}$ is not identically 0, then the adversary receive  $\perp$ in return. If $p_k$ is not 0 but $p_k^{(0)}$ is identically 0, then the adversary receives a handle to a new variable $W_k$, which is set to be $p_k / g = p_k^{(1)}(\{X_j\}, \{Z_i\}) + gp_k^{(2)}(\{X_j\}, \{Z_i\}) + ...$.

So, this is my doubt... At first glance, it seemed to me that this query was trying to model the fact that the attacker can multiply the zero-testing parameter $p_{zt} := [hz^kg^{-1}]_q$ by the high-level encoding $u$ it has (as if he/she would test $u$ encodes a zero) but without ending the test to get a bit (encodes or not a zero), taking, instead, another ring element.

In this case, the polynomial $p_k$ would model a level-$k$ encoding. Thus, the two cases where the symbol $\perp$ is returned make sense, but the third case is weird, because I don't see how the returned expression $p_k / g$ may be obtained from $p_{zt}$. It seems that the value $hz^k$ is missing, I mean, I was expecting that

$$p_k \cdot p_{zt} = hz^k p_k / g = hz^k p_k^{(1)}(\{X_j\}, \{Z_i\}) + hz^kgp_k^{(2)}(\{X_j\}, \{Z_i\}) + ...$$

would be returned instead.

Then, am I right about supposing that this query really models the ability of performing a product by the public parameter $p_{zt}$?

If so, how could the value $ p_k / g $ be returned?

Based on the author's presentation at CRYPTO 2016 (available on youtube), we see that the Type 1 query is really modeling the attacker's ability of multiplying the zero-testing parameter by the values it has.

The point is that this abstract query is conservative in the sense that it gives to the attacker more power than it would have (a priori) in practical in multilinear maps setting. Also, this query is modeled like that because it is likely that if an attacker can get the expressions I described as the expected ones, than she/he can also get the ones returned by the queries (for instance, by recovering $g$ and dividing the value $ p_k $ she/he has to get $ p_k / g $).


Proof for composed signatures Assumes that we have 3 signature algorithms, $S^A$ with key pair $(sk^A,pk^A)$, $S^B$ with key pair $(sk^B,pk^B)$,$S^C$ with key pair $(sk^C,pk^C)$. We denote by $\epsilon$, $\epsilon'$ and $\epsilon''$ the advantages for breaking $S^A$, $S^B$ and $S^C$ respectively, in the sense of weak unforgeability.

I have a composed signature algorithm which works as follows : First we sign a message with $S^A$, then the result is signed with $S^B$, and finally the result of $S^B$ is signed with $S^C$. An adversary can plays to the game in which he can make queries to a composed signing oracle for the signature of messages of his choices.
At the end, the adversay has to find a composed signature for a message which was never queried at the oracle.

Is the adversary advantage bounded by $\epsilon+\epsilon'+\epsilon''+\epsilon \epsilon'+\epsilon \epsilon''+\epsilon' \epsilon''+\epsilon \epsilon'\epsilon''$ ?

I try to construct the proof.. This could be a nice example for me to understand well provable security.

Thank you.

Sketch.

Suppose you have an adversary against the composed scheme with advantage $\epsilon_3$. Observe that whenever you have a signature for the composed system, you have a signature for each of the three component signature schemes.

It should then follow that a forger for the composed signature scheme can be turned into a forger for each of the three signature schemes, and it will have advantage $\epsilon_3$. (This involves a few easy technicalities.)

With that proved, it follows that we can bound the adversary's advantage $\epsilon_3$ by the advantages $\epsilon$, $\epsilon'$ and $\epsilon''$.