Who issued the first SSL certificate? When SSL was introduced in ~1996, there was only a few CAs issuing certificates for that specific use and a few sites which actually used SSL.

Which Certification Authority issued the first SSL certificate and whom was it issued to?

Spelunking through https://crt.sh, one finds a CA certificate for RSA Data Security, Inc., from 1994, but the oldest certificate it has issued has a validity period starting only on 1998-02-13.  That doesn't mean that that CA didn't issue certificates before—maybe the records in crt.sh are incomplete.  Indeed, pursuing the PostgresQL interface doesn't reveal any non-CA certificates until 1997, for www2.superb.net, which strongly suggests the records are simply incomplete.

To do further research, with a bit more effort, you might query the EFF's SSL Observatory database.  Netcraft also alleges to have data about historical certificate trends, in exchange for money, but it's not clear that they have the actual certificates or just some summarized properties like what serial number and what type of key.


Diffie Hellman Exchange Confusion I am working on this question and I am wondering I have figured out the secret key, but my problem is I don't know how to use the secret key to decrypt the ciphertext.

Thanks for the help!

Diffie Hellman(DH) is a key exchange method, it is not a encryption/decryption algorithm.
You have to use the secret key generated from DH in a symmetric cipher algorithm which is the algorithm used to create ciphertext from plaintext in the first place.

For example, lets say Alice and Bob make a DH key exchange to generate a secret key $K$, then Alice uses that key to send a message $M$ to Bob by encrypting it using an encrption algorithm such as AES. So Alice creates ciphertext $C =AES_{Enc}(M,K)$ and Alice sends $C$ to Bob. Then Bob takes ciphertext $C$ and decrypts it using the same algorithm and the same secret key that Alice used to get the message: $M =AES_{Dec}(C,K)$.


Elgamal test vectors I know that Elgamal algorithms have fallen out of fashion, and they are not included in any widespread cryptographic standard nowadays. However, they are still present in several popular crypto libraries (bouncy castle, botan, cryptopp, etc). One disturbing thing I found is that such libraries have no or very limited test vectors for Elgamal.

Do test vectors exist at all for Elgamal? What is a good reference? I especially refer to encryption and signing algorithms over $Z_p$.

There seem to be no standardized ElGamal test vectors available in the public domain.  However, there are some ElGamal test vectors generated with libgcrypt 1.5.0 available in this fork of the pycrypto project.


Can a repeated random sequence be considered random? Imagine I have a 1000000 bit sequence that is considered random ( ie the output of a TRNG).

Now imagine I 'double' that sequence : I concatenate the same sequence 2 times :  " my 1000000 bits "concat" my same 1000000 bits "

Can we say that the resulting sequence is random ?? ( note that if someone know the construction structure of the concatenated sequence can know the bit 1000001 and following ones as they are the same ones as the beginning ones...)

I have been testing some setups like the one exposed with NIST test suite and seem to show the resulting sequence is random ( anyway im no real expert in NIST test suite so maybe I'm missing some crucial point)

Remember, sequences themselves are not random or not; the process for generating the sequence is random or not.  The question is: is your repeated sequence compatible with the hypothesis that its source is random?

Given a uniform random bit generator, the chance that it will generate any one sequence of $n$ consecutive bits is $2^{-n}$.  The chance that, given that the previous $n$ bits were $x$, a random bit generator will proceed to produce $x$ again as its next $n$ bits is also $2^{-n}$.  So in your case with $n = 10^6$ the chance that a random bit generator is $2^{-10^6}$—a crazy small number.  If we observed such a sequence, then, we would reject the hypothesis that the bit generator is random with near certainty.


Finding and matching SHA512 Unsalted Hash We are given a list of possible strings, there are $32^{16}$ ($=2^{80}$) to be exact.

We also have the unsalted SHA512 of the original target string.

How long would it take to go through those strings, generate an unsalted SHA512 hash and then check if that hash matches the target hash?

It's for a research project, we have labs full of computers/processing power, and additionally/potentially hundreds of people willing to run software on their computer for it as well, so possibly some sort of blockchain design?

We really are just looking for input or for someone to validate/invalidate this idea. Thanks for your feedback!

A brute force search is probably impractical with your resources.

It appears that a CPU-based SHA-512 implementation might be able to do 2,000,000 short hashes per second per core (the figures I have are a bit slower - I'm assuming things will get a bit faster)

Given $32^{16}$ target images, that translates to approximately 20,000,000,000 core-years to search through the entire list (or about have that to get a 50% chance of finding it).  If you have 1,000,000 volunteered computers, and each computer has 10 cores, that translates to an expected time of 1000 years to get to a 50% chance of finding it.

A quick look at GPU performance looks a little closer to practical; however you'll still need millions of dedicated GPUs to get the time down to a practical level.

About the only way to do it practically would be to go with FPGAs or (better yet) dedicated ASICs - either approach would appear to be out of scope for what you have.


Intuitive explanation of the $\varepsilon$ parameter in differential privacy I think I have a decent intuitive understanding of what the $\delta$ parameter means in $(\varepsilon,\delta)$-differential privacy: I can explain it to a non-specialist in terms of "what are the chances that something goes horribly wrong".

Even if I understand (and can work with) the formal definition, I'm not sure I could do the same for the $\varepsilon$ parameter. I've recently been asked to design a differentially private mechanism for a simple survey, and I have no idea which $\varepsilon$ to choose in practice nor how to justify this decision.

Ideally, I'd like to successfully explain what a particular choice "means" to somebody who isn't a privacy specialist. Any idea how to do that?

A colleague gave me the following explanation that I think makes a lot of intuitive sense, so I'm reproducing it here. Skip to the last paragraph it you don't care about the proof.
Suppose you're trying to track one individual user, and you're trying to figure out whether they're in the database. You have some prior knowledge about this: $\frac{P(in)}{P(out)}$ is how much more likely you think the user is in the database than isn't.
How does this change once you know the output $O$ of the algorithm? The posterior knowlege can be written as $\frac{P(in|O)}{P(out|O)}$. We can use Bayes' theorem to decompose it:
$$\frac{P(in|O)}{P(out|O)}=\frac{P(in)P(O|in)}{P(out)P(O|out)}=\frac{P(in)}{P(out)}\cdot \frac{P(O|in)}{P(O|out)}$$
If the algorithm is $\varepsilon$-differentially private, then it satisfies $e^{-\varepsilon}\le\frac{P(O|in)}{P(O|out)}\le e^{\varepsilon}$, since there's only one user different between the two scenarios. Using the previous formula, we get:
$$
e^{-\varepsilon} \cdot \frac{P(in)}{P(out)} \le
\frac{P(in|O)}{P(out|O)}
\le e^{\varepsilon} \cdot \frac{P(in)}{P(out)}
$$
This is essentially telling us that $e^\varepsilon$ is how much confidence we can gain about whether one user has been added/removed from the data, by looking at the output. When $\varepsilon=\log(2)$, we can gain a factor of $2$ in the knowledge we have: if we had no information at the beginning (say, $P(in)=P(out)=0.5$), now we might have information like $P(in|O)=2/3$ and $P(out|O)=1/3$, but not a bigger difference.
If you want to dive a bit deeper, I wrote a blog post to elaborate a bit on this reasoning and give a concrete example. I also explain how the formula above can be used to find bounds on the possible values of $P(in|O)$ depending on $P(in)$ and $\varepsilon$:


phi(P*Q) = (P-1) * (Q-1) I was trying to understand RSA when I encountered the Euler Function. I do understand this: $\phi(P)$, where $P$ is a prime is $P-1$.

However it seems that for a number $N$ such at $N=P\cdot Q$ where $P$ and $Q$ are non-equal primes:

\begin{equation}
    \phi(P\cdot Q) = (P-1)\cdot(Q-1)
\end{equation}

I'm having trouble understanding why that is so. Could someone point me toward the proof of the same?

This is actually a special case of a more general property of the Euler totient function: it is a multiplicative function, meaning that, for any two coprime numbers $p$ and $q$, $\phi(pq) = \phi(p)\phi(q)$.

The special case where $p$ and $q$ are (distinct) primes is easy to prove.
By definition, $\phi(n)$ gives the number of positive integers coprime to and smaller than $n$, i.e. the number of integers $k$ satisfying $0 < k < n$ and $\gcd(k,n) = 1$.

Since $p$ and $q$ are the prime factors of $pq$, an integer $k$ is coprime to $pq$ if and only if it isn't a multiple of either $p$ or $q$.  In the range $0 < k < pq$ there are $p-1$ distinct multiples of $q$, and $q-1$ distinct multiples of $p$, and a bit of thought shows that these two sets cannot overlap, as any positive number that was a multiple of both $p$ and $q$ would have to be at least as large as $pq$.

Thus, out of the total $pq-1$ integers $k$ in the range $0 < k < pq$, all but $(p-1) + (q-1)$ are coprime to $pq$, and so $$\begin{aligned}\phi(pq) &= (pq-1) - (p-1) - (q-1) \\ &= pq - p - q + 1 \\ &= (p-1)(q-1).\end{aligned}$$


Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)? Let $n = p*q$, with $p \neq q$ and $x^2=1 \pmod n$, $x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n$ (So x is a non-trivial square root mod n.)

I don't see how $\gcd(x+1,n) \in \{p,q\}$ follows.

I understand that $x^2=(x+1)(x-1)$, so $n=p*q$ is a factor of $(x+1)(x-1)$, but neither of $(x+1)$ nor of $(x-1)$ (as a x is a non-trivial solution). Every proof I've seen so far stops at this point, leaving me confused. In my opinion, it holds that $gcd(x+1,n) \in \{1,p,q\}$ (so the trivial solution 1 is indeed possible). How can we be sure that $x+1$ and n have common factors other than 1?  I'm sure I am missing something very obvious, but I just can't make it out.

If $x^2\equiv1\mod{n}$, it means that $(x+1)(x-1)\equiv0\mod n$. In other words, $(x+1)(x-1)=k\cdot n=k\cdot p\cdot q$ for some $k\in\mathbb{N}$. And there you go: if $x\neq\pm 1\mod n$, neither $x+1$ nor $x-1$ equals $p\cdot q$ and must contain either of the primes in their factorization (plus perhaps some factor of $k$). Hence, $\gcd(x+1,n)\in\{p,q\}$.


How likely is it that AES-256 is crackable within 100 years (2120)? When people ask for a block-cipher with a larger key space than AES-256 replies usually just state that there is no need. I see where that is coming from the future is hard to predict.

The two main problems I can see are Grover's algorithm (see below) and the fact that we can not see all the problems.

I have no idea how powerful quantum computers will be in 2120 so we may consider upper bounds. e.g. At 20ºC, the Landauer limit* is about 2^-80 watt-hours per bit. I do know that some other ciphers (like threefish) have larger key spaces.

The fact that AES may be broken within 100 years (exactly) was apparently addressed by the OneHundredYearCryptography project by XORing it with XSalsa20.

To reiterate I want to know if AES-256 will be safe throughout our life time.

*To the best of my knowledge, experimental quantum computers that operate at the limit are actually much faster than other experimental computers that are also at/near the limit. I don't know if there is a price difference however.

Edit for background: Grover's algorithm is an attack that is analogous to brute force attack. The differences are that its complexity is the square root of the key space (2^(256/2)) rather than the key space itself, and that it can only be run on a quantum computer. I'm confident that no conventional or quantum computer will be able near-brute-force it, but I'm not that sure that a quantum computer won't be able to Grover it. Therefore, the power of quantum computers by 2120 is of more interest than the power of electrical computers at that time.

I want to know if AES-256 will be safe throughout our life time.

No one knows that.  Here is what we do know:

A brute force search (by conventional computers) will be totally impossible.  This can be shown by a power analysis of the minimal amount of power used per step (the minimal amount of power to change a state is $kT$, where $k$ is Boltzman's constant circa $1.38 \cdot 10^{-16} \text{ erg/}^\circ\text{K}$, and $T$ is the temperature in Kelvin.  If we assume a computer that's running at cosmic background radiation temperature ($3.2 ^\circ K$), the minimal energy to step a counter though $2^{256}$ keys would be about $5 \cdot 10^{61}$ ergs; the annual output of the Sun is about $1.21 \cdot 10^{41}$ ergs, so unless you can harness a considerably larger output than our Sun within 100 years, this is impossible
A Grover's search (by a Quantum Computer) will also be impossible.  In theory, Grover's could find a 256 bit key in $O(2^{128})$ steps (which is far more achievable than the $2^{256}$ steps in the previous paragraph), it turns out that, to achieve this "low" amount of computation, Grover's search would require $O(2^{128})$ sequential AES evaluations (where you can't start the next until the previous one has completed).  If we assume that our Quantum Computer can't compute an AES function in less than a femtosecond ($10^{-15}$ seconds [1]), then this would take $10^{16}$ years, rather longer than your 100 year deadline.  To meet your deadline of 100 years, you would need to split up the key space into $2^{94}$ parts, and give each part to one of a total of $2^{94}$ Quantum Computers (each one performing AES operations at this completely unrealistic speed).
Cryptographical advancement (that allows an attacker to recover the plaintext without trying all possible keys); this is an open question.  I personally don't expect a total break; that is, something that, given a reasonable amount of ciphertext (and possibly some known plaintext), will allow them to decrypt; I wouldn't be that shocked if someone in the next hundred years found a theoretical break (e.g. $O(2^{150})$ effort given vast mounds of chosen plaintext).  However, this is what people are worried about (as it is easy to see that the other two break methods are totally infeasible).

[1]: For reference, a femtosecond is approximately the time it takes light to travel 0.3 microns; this implies that our AES evaluation engine must be considerably smaller than your average bacteria...


Secret shared input for garbled circuit? I’m curious about what the secret shared input for a garbled circuit is. Essentially, a garbled circuit is a two party computation framework where each of two players has each input as bit string. In this case where is secret shared input?

If there is a case when secret shared bit string is used as input, I want to know it’s mechanism and it’s reference material. Thanks

Normally the inputs to garbled circuits are known by the party who owns the input and are plaintexts.

There are scenarios in which the functionality (implemented by GC) needs to be evaluated on shared input. For example, if the two parties are not trusted with the plaintext input (may be owned by a third party) and instead only get shares of the input. The garbled circuit then consists of two sub-circuits: (1) the first sub-circuit combines the shares and recovers the secret input, and feeds it (without revealing it) to (2) the sub-circuit that implements the functionality to be evaluated on the secret input. At the end, the output is given to the parties (or if you want, you can append another circuit to split the output into two shares and give one share to each party)


DSA Vulnerability in ECDSA I have implemented a ruby code where i generate private and public keys as below.

However, I read few articles [1] on DSA and why it should not be used. I'm not good at cryptography. But still wanted to know whether my implementation is vulnerable to recover public/private key?

$group = ECDSA::Group::Secp256k1
$private_key = 1 + SecureRandom.random_number($group.order - 1)
$public_key = $group.generator.multiply_by_scalar($private_key)

Your confusion seems to be between DSA, the discrete signature algorithm and the Elliptic Curve variant ECDSA. The answers to the question you point to already seem to make a distinction between the two, which this answer won't re-iterate.

The key size of 256 bits is considered secure for Koblitz curves such as SECP256K1. So if used correctly the shown code is secure when it comes to the algorithms and key sizes used. Using a bad random number generator for ECDSA signatures is known to lead to catastrophic loss of key material.

Notes:

using a single-person implementation of ECC is not recommended: there is a bigger chance of implementation mistakes or side channel attacks (e.g. during the multiplication to calculate the public key or signature generation);
SECP256K1 provides somewhat less than 128 bits of security, which is currently not feasible to crack (although the bit size is slightly at the low side). But EC(DSA) is vulnerable against attacks from future quantum computers (and so is DSA).


Simulator Transcript in ZKP I need a bit of clarification about the definition of transcript of a simulator in Zero-Knowledge Proofs.

Basically, the way I understood it, the simulator is given access to the (potentially malicious) Verifier as a sub-routine, and the goal of the simulator is produce a transcript that's computationally indistinguishable from the transcript produced between the Prover and the (potentially malicious) Verifier.

My question is: Does the transcript of the simulator include the final Accept/Reject output of the verifier or not? In other words, if the verifier accepts in an interaction with the real Prover, should the simulator also be able to produce a transcript, that will be accepted by the verifier, or can the simulator just leave the verifier's output out.

If it leaves the verifier output, then the definition doesn't seem to make sense to me, because I can always generate a random transcript that looks like the interaction between prover and verifier. However, in most lectures, I don't see people requiring the result of verifier in the transcript, which is what's confusing me.

There are two formulations which are equivalent. One formulation is where the simulator outputs the verifiers view and the other where the simulator outputs the verifier's output. In neither case does the verifier's output need to be present. However, since it depends the verifier, and we quantify over all PPT verifiers, the simulation must work also where the verifier outputs accept/reject on top of whatever else it may want to output.

These formulations are equivalent since the distinguisher can just run the verifier on its view to get the output.

Just to complicate things, note that if a definition is used that allows an expected polynomial-time verifier and simulator, then the distinguisher cannot run the verifier on its view unless it too runs in expected polynomial-time (and things are typically not formalized this way). However, this really isn't very important and you should be able to ignore this complication.


Why did they choose $x^4+1$ for the MixColumns step in Rijndael/AES? In The Design of Rijndael page 39, It describe the design criteria for MixColumns step

Dimensions. The transformation is a bricklayer transformation operatingon 4-byte columns.
Linearity. The transformation is preferably linear over GF(2).
LisDiffusion. The transformation has to have relevant diffusion power.
Performance on 8-bit processors. The performance of the transformationon 8-bit processors has to be high.

However, it does not said why choose modulo $x^4+1$ operation in this step. I guess it is becasue it is the simplist polynomial operation otehr than modulo $x^4$, which will cause multiple zeros. I will glad if anyone tell me my guess is wrong.

The idea is that when you're multiplying two four-term (four-byte) polynomials together, you could wind up with a seven-byte polynomial, but you need to reduce it to another four-byte polynomial. They chose $x^4 + 1$ because

$x^i \mod (x^4 + 1) = x^{i \mod 4}$

See this for an example.


Why ECDSA has its form? According to Wikipedia, if Alice wants to sign some message, she computes $s = k^{-1} (z + r d_A)$ then sends $(r, s)$ to Bob.

I don't understand why they use this particular formula $s = k^{-1} (z + r d_A)$ for signing the message ? Why don't they just take $s = r d_A + z$ (i.e. $k = 1$) or $s = d_A + z$ or some other form ?

The main reason is historical (and a bit sad).

ECDSA can be seen as a repurposed authentication mechanism. The private key owner wants to prove knowledge of the private key $x$ that matches a given public key $Q = xG$, but without revealing that private key. Thus, this is organized as a three-step protocol:

The prover makes a commitment on a newly generated random value $k$; the commitment is the point $kG$ (value $r$ is basically the X coordinate of that point).
The verifier issues a challenge (let's call it $e$).
The prover responds to the challenge with a value $s$, which is such that the verifier can check that the prover knew a value derived from $k$ and $x$, but without actually revealing $x$.

This authentication scheme is then turned into a signature scheme by making the signer play the protocol against himself: the challenge is computed deterministically from the commitment, making the physical presence of the verifier unnecessary. The signer can play the protocol by himself, and the transcript of the protocol (the pair $(r,s)$) can be verified non-interactively afterwards.

Now, in the 1980s, there was a nice protocol fitting that mechanism, known as Schnorr signatures. In a Schnorr signature, the challenge $e$ is computed as a hash value over the signed message and the commitment, and the response is computed as $s = k - xe$ (some variants make it $s = k + xe$). However, Schnorr had filed a patent on that algorithm. When the US federal government looked for an algorithm to standardize for all US federal organizations, they wanted to avoid patents as much as possible (otherwise, they would have used RSA, which was also patented). Thus, they looked for a more-or-less Schnorr-like protocol that would be nonetheless different enough so as not to infringe on the patent. They thus lifted the ElGamal signature scheme, which was not patented (at that time! Certicom filed patents afterwards, for ElGamal adapted to elliptic curves). It was ElGamal that introduced the modular inversion of $k$, which is cumbersome to implement. The result of the adaptation of ElGamal into a US standard was called DSA. ECDSA was later defined as DSA applied on elliptic curves.

Thus, you can say that the specific formula of DSA and ECDSA, with the $k^{-1}$, was chosen for patent avoidance reasons, not for any cryptographic advantage. Indeed, that formula sucks: it makes implementation more complicated, it prevents some security proofs, and it makes the signatures somewhat malleable (if $(r,s)$ is a valid ECDSA signature, then $(r,-s)$ is also a valid ECDSA signature on the same message with the same key), a property which has induced some occasional trouble (namely, transaction replay attacks in Bitcoin).


Three-way hash collision According to the birthday paradox we need approximately $O(|T|^{1/2})$ samples from the tag-space to find a collision for a hash function $h:K\times M \to T$. But how many samples are needed to find a three-way collision, i.e. $h(a) = h(b) = h(c)$ for three messages $a,b,c \in M$ hashed with the same key $k\in K$ ?

I thought that it would be $O(|T|^{1/2})$ to find $h(a) = h(b)$ and another $O(|T|^{1/2})$ to find a third, but when thinking about it, that feels wrong. How can I calculate this?

The hand-waving argument goes thus: when you accumulate $n$ hash outputs, you are actually producing $n^3/6$ triplets, each of them having probability $t^{-2}$ to be a three-way collision (where $t = |T|$, i.e. the size of the output space). So you should expect the first three-way collision to appear when $n^3/6 = t^2$, i.e. $n = 6·t^{2/3}$. For a perfect hash function with 128-bit output, this means that you would need about $2^{88}$ hash function invocations.

Now that's just an approximation which does not give the exact result because the triplets are not exactly independent of each other; but it yields the proper order of magnitude.

More importantly, this assumes a perfect hash function. For a concrete hash function, even a "secure" one, you could get multicollisions much faster. As shown by Joux in 2004, an "iterated hash function" (e.g. MD5 or SHA-256) with an internal state of $s$ bits, you only need to produce $k$ "simple" collisions (of indidivual cost $2^{s/2}$) to deduce a $2^k$ multicollision. When $s$ is equal to the output size (that's called a "narrow pipe design", as @Codes says), this is much lower than the cost above; even if MD5 was not broken, it would still allow a four-way collision with cost $2^{65}$, an eight-way collision with cost $2^{66}$, and so on... The usual security property of "resistance to collisions up to $2^{s/2}$" is not incompatible with "beyond $2^{s/2}$ there may be an orgy of easy multicollisions".


What is the difference between CPA and IND-CPA? I am writing a paper and I got comments from the reviewer that I don’t really understand.

Is there any difference between a CPA (Chosen Plaintext Attack) and IND-CPA (Indistinguishability under Chosen Plaintext Attack) when evaluating the security of an encryption scheme?

IND-CPA is equivalent to semantic security under CPA.


Can CBC encryption have separate keys for separate blocks of plain text? Can we have separate key for separate blocks which we get while operating a plain text message  using CBC encryption model? If yes, what are it's advantage? Please enlighten me.

SHORT: The key remains the same. CBC mode is one of the ways which allow block cipher to securely process multi block input.

Block cipher with single key produces same output for same input, as it is relatively common for input to contain duplicate blocks, instead of using block cipher as is, a more complex construct is needed.

The idea of CBC mode is that the ciphertext of the previous block affects encryption of the next block. Specifically, plaintext input is XORed with the previous block cipher text (or with "Initialization Vector" also known as IV) for the first block. This operation is much less time consuming than key change.

So shortly, the benefit of CBC mode is that it allows securely using the block cipher, something that raw block cipher (ECB mode) generally does not allow for multi block messages.

In addition to CBC mode, also numerous other block cipher modes of operation exist. There are circumstances where one of the other block cipher modes of operation is more appropriate than CBC.

The most basic block cipher modes of operation (ECB, CBC, CFB, OFB, CTR) are described e.g. in Wikipedia and NIST Special Publication 800-38A. The Wikipedia article contains great picture, which illustrates the need for modes of operation beyond ECB.


Rational exponents on group generators In elementary concepts, mostly scalar exponents shows up in group operations:

$g^x$

As one may encounter in more advanced papers, there are rational exponents over generators. Simply seems like:

$g^{1/x}$

For example, it can be seen at the fouth definition in the paper: q-weak Diffie Hellman assumption

Q1: How should we interpret rational exponents on generators?
Q2: What is elliptic curve notation of the rational multiplicators? $(1/x)G$ ?
Q3: What is relationship between $g^{x}$ and $g^{1/x}$?

Thank you.

If $$x \times \frac{1}{x} = 1$$

then $$g^{x\frac{1}{x}} = g^1 = g$$

Alternatively, you could denote $\frac{1}{x}$ as $x^{-1}$.

In the context of cryptography, $\frac{1}{x}$ will usually mean the modular multiplicative inverse of $x$, because cryptography usually works with modular arithmetic.

With modular arithmetic, the way to evaluate the division operation is to multiply by the inverse. For example: $$3 \times 7 \equiv 10 \bmod 11\\10 \times 4 \equiv 7 \bmod 11$$

You wouldn't be able to use the traditional division operation to divide $10$ by $3$ to obtain $7$. But you can use multiplication by the inverse of $3$ (which happens to be $4$ here) to obtain the correct result. So we could also denote the above by: $$10 \times 3^{-1} \equiv 7 \bmod 11$$ or equivalently: $$10 \times \frac{1}{3} \equiv 7 \bmod 11$$

So in general, $\frac{y}{x}$ means $y \times x^{-1}$.

  Q2: What is elliptic curve notation of the rational multiplicators? $(1/x)$G ?

What you've written looks plausible, but it wouldn't surprise me if they tended to use $x^{-1}G$ instead.*

Either way you denote it, people will probably understand the intent - especially if you provide helpful definitions for your notation.

* I'm not well-versed in literature on elliptic curves, so I'll leave it to someone else to confirm/deny that.


Safe way to derive IV from the DH shared keys for AES-GCM? I am preparing to use AES-GCM to make a secure communication program.
Here is the procedure

DH key exchange to get shared keys
SHA256(shared keys)
Use AES-GCM to encrypt a message while the key only used once.

However, I was confused about the way to get IV in step3. I know IV/nonuse must be unique. The size of the IV should be 96 bits. I know we can use the timestamp to generate iv. However, I need to generate the IV from the shared key. Is there any method to do it safely?

If there is no regulatory requirement, for AES-128, a good option would be splitting the SHA-256 hash into a key (128-bit), IV (96-bit), and any unused portion. That allows us to make the IV implicit (and secret, which is unnecessary, but does not harm) thus saves even so little bandwidth. For AES-192 or AES-256,  we can do this with SHA-512 instead of using SHA-256.

On a related note, make sure that the same derived key is never used by a given party both to encrypt and decrypt/authenticate because that opens to mirror attacks. If the communication is bidirectional, derivation could use
$$\operatorname{HMAC-SHA-xyz}(\mathsf{key}=\text{DH-shared-secret}, \mathsf{message}=\text{sender-ID})$$
as the origin of the session key and IV used by the sender to prepare its message. HMAC internally hashes the shared secret if it more than a certain size (64 bytes for SHA-256), that's fine.

For even stronger assurance:
$$\begin{align}
\text{Key}&=\operatorname{HMAC-SHA-xyz}(\mathsf{key}=\text{DH-shared-secret}, \mathsf{message}=\text{'K'}\mathbin\|\text{sender-ID})\\
\text{IV}&=\operatorname{HMAC-SHA-xyz}(\mathsf{key}=\text{DH-shared-secret}, \mathsf{message}=\text{'I'}\mathbin\|\text{sender-ID})
\end{align}$$

which gives an argument that the leak of IV (which should be assumed even if the IV is not sent in clear) can't harm the secrecy of Key even if the hash has some level of defect. Also, HMAC has a parameter (now shown) to specify the output size, making the definition cleaner.


How can I prove that ElGamal encryption in $\mathbb{Z}_p^*$ with OAEP padding is ind-CPA secure? How I can prove that ElGamal encryption in $\mathbb{Z}_p^*$ with Optimal Asymmetric Encryption Padding (OAEP) is IND-CPA secure?

This is not a full answer: I only motivate the use of OAEP on top of ElGamal encryption.

ElGamal encryption as stated in modern literature, that is with message in a group where the Decisional Diffie-Hellman problem is hard, is demonstrably CPA-secure. That does not hold for the original scheme in Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, in proceedings of Crypto 1984, even with the obviously necessary and minor correction of excluding $m=0$ from the message space, which we do hereafter.

The original ElGamal encryption scheme uses as public parameters a large prime $p$ and a primitive element $\alpha$ of $\Bbb Z_p^*$ (the multiplicative group modulo $p$). Thus $x\mapsto \alpha^x\bmod p$ is a bijection over $[1,p)$. Insuring that $p-1$ has a large prime factor makes reversing this function (the Discrete Logarithm Problem) hard.

Recipient B chooses a random secret private key $x_B\in[1,p)$, computes and publishes his public key $y_B=\alpha^{x_B}\bmod p$.

Sender A, wanting to encipher a secret message $m\in[1,p)$ to B, picks a random secret $k\in[1,p)$, computes the secret key $K={y_B}^k\bmod p$, computes $c_1=\alpha^k\bmod p$ then $c_2=K\,m\bmod p$, and sends ciphertext $(c_1,c_2)$ to B.

Recipient B receives $(c_1,c_2)$, and deciphers¹ per $m={c_1}^{p-1-x_B}\,c_2\bmod p$. This works because $K={c_1}^{x_B}\bmod p$.

Observe that given $y=\alpha^x\bmod p$ with $y\in[1,p)$, we can determine with certainty if $x$ is odd or even: we compute $y^{(p-1)/2}\bmod p$ and that's $1$ when $x$ is even, $p-1$ when $x$ is odd. Expressed using the Legendre symbol for $y$ modulo $p$, that's $\left(\frac yp\right)=+1$ when $y^{(p-1)/2}\bmod p=1$ (even $x$), or $\left(\frac yp\right)=-1$ when $y^{(p-1)/2}\bmod p=p-1$ (odd $x$). This allows an adversary to win the IND-CPA game with certainty, by:

Choosing two messages $m_0$ and $m_1$ with $\left(\frac{m_0}p\right)=+1$ and $\left(\frac{m_1}p\right)=-1$. The choice of $m_1=1$ and $m_2=\alpha$ will do, or it can be found by trial and error meaningful messages until two have different Legendre symbols.
Submiting $m_0$ and $m_1$ to the challenger, which picks $b\in\{0,1\}$ at random, sets  $m=m_b$, computes and reveals $(c_1,c_2)$ as above.
Finding $b$ per the following table:
$$\begin{array}{ccc|c}
\left(\frac{y_B}p\right)&\left(\frac{c_1}p\right)&\left(\frac{c_2}p\right)&b\\
\hline
-1&-1&-1&0\\
-1&-1&+1&1\\
\text{any}&+1&-1&1\\
\text{any}&+1&+1&0\\
+1&\text{any}&-1&1\\
+1&\text{any}&+1&0\\
\end{array}$$

This works because $\left(\frac{y_B}p\right)=-1\iff x_B\text{ odd}$ and $\left(\frac{c_1}p\right)=-1\iff k\text{ odd}$. Since $K=\alpha^{x_B\,k}$ that allows to determine $\left(\frac Kp\right)$, which is $-1$ if and only if both $\left(\frac{c_1}p\right)=-1$ and $\left(\frac{c_1}p\right)=-1$. And then $\left(\frac{c_2}p\right)=\left(\frac Kp\right)\,\left(\frac{m_b}p\right)$ allows to conclude on $b$.

Further leaks can occur when $(p-1)/2$ has small prime factors. But when choosing $p$ such that $(p-1)/2$ is prime ($p$ a so-called safe prime), the strategy of restricting to $m$ with $\left(\frac mp\right)=+1$ is believed to make ElGamal encryption IND-CPA secure² against classical computers. That can be done without an iterative process to transform a practical message into a suitable $m$, and back on the decryption side: see poncho's nice squaring technique in comment.

The motivation of using OAEP padding in order to prepare the message to form $m$ in ElGamal encryption are²:

it is non-iterative, and faster than even poncho's nice squaring technique;
it should make ElGlamal encryption IND-CPA secure, because the partial information that may leak won't be enough to allow the adversary to undo the padding;
unless I err once more, it should also make ElGlamal encryption IND-CCA1 secure (but not IND-CCA2 secure for the reason pointed there, even if we add range checks on $c_1$ and $c_2$ on decryption).

But I have no proof for the IND-CPA and IND-CCA1 assertions.

¹ The paper computes $K={c_1}^{x_B}\bmod p$, then asks to "divide $c_2$ by $K$ to recover $m$". That requires computation of a modular inverse, perhaps using the extended Euclidean algorithm.

² The complexity is believed super-polynomial in $\log p$, including in a known dip down in security for $p$ of a special form $r^e\pm s$ with $r$ and $s$ small, which enables SNFS.


Can we (with just paper and math) find the prime number "p" of an RSA key? With all our tools in math, isn't it really possible to find the prime number p of an RSA key without brute-forcing it with a computer? I'm not talking about doing it in 2 minutes but doing it in a clever way that is faster than our computers. Some algorithms work really well like MSIEVE and GGNFS, but it takes too much time to proceed. Can't we really find the prime p without the help of an algorithm?

If there was a general strategy to do this with pen and paper, we could do it with a computer just as well. Most pen and paper solutions to any math exercise rely on using lots of “shortcuts” or “tricks” that exploit special situations or specific properties of the numbers in the problem. However, since RSA keys tend to be very big, we'd need an impossible number of special situations to have an approach that works generally.


Why is the payload size is restricted when using RSA Doing some research about cryptography, I've read many times that, when using RSA 1024 and PKCS#1, the size of the payload cannot be bigger than 117 bytes.

This payload cannot be bigger than the modulus size, which is the key size in bits / 8  (1024/8 = 128 - bytesFromPKCS1 = 117).

But why does this limitation exist? Is it in the formula? if so, why?

Thanks for the answer :)

When you're talking about RSA-1024, the "1024" refers to the bit length of n, so n is 128 bytes long. Now let's take a look at RSA decryption process :

In order to recover your plaintext, you will compute
\begin{align*}
c^d \mod n &= m^{e*d}\mod n\\
& = m \mod n
\end{align*}
You can see that if $ m > n$, i.e. if $m$ is more than 128 bytes (in case of RSA 1024), the result will not be $m$, hence the size limitation.


Help with terms: hash function and a pseudorandom function I am a little bit confused about the terms hash function and pseudorandom function. As far as I know, I can use a cryptographic strong hash function as a PRF. The hash function has a IV and is completely public - everybody can look at the construction and at the details. A good hash function maps the input in a pseudorandom way to its output (deterministic).

So a pseudorandom function is quite similar. Here you do not take a fix hash function, rather than you take a function from a set of functions. That model is implied by using a keyed function. So there are often keyed hash functions used for example the HMAC is taken as a PRF.

So in a limited view, is it right to say that a attacker does not know my "internal conditions" of my PRF? (I mean my current Setting: which key i use and which hash function, or if I use HMAC, he does not know my key and my constants and my hash function.)

There's two problems with your question:

The term "hash function" is not as clearly defined as you think.
The most common definition among cryptographers does not imply pseudorandomness.

Generally, you want to be very careful in distinguishing between:

Security definitions, like:

Pseudorandom function
Collision resistant hash function

Cryptographic algorithms, like:

SHA-2
HMAC
AES

Arguments that some given algorithm meets specified security definitions.

"Pseudorandom function" and "collision-resistant hash function" are security definitions:

A pseudorandom function is a keyed function that an adversary who doesn't know the key cannot efficiently distinguish from a randomly selected function over the same domain and range.
A collision-resistant hash function (CRHF) is a function that features:

Compression (turns variable-sized inputs into fixed-size outputs);
Preimage resistance
Second preimage resistance
Collision resistance

Now, you need to understand that the security definition for collision-resistant hash functions does not imply the one for pseudorandom functions:

A pseudorandom function need not compress its input.  Example: AES, or any block cipher (which are designed to be pseudorandom permutations on fixed size blocks).
A function that provides preimage, second preimage and collision resistance may nevertheless be efficiently distinguishable from a random function.

This means that if all that you assume of your hash function is that it meets the CRHF requirements, you cannot conclude that it also provides the PRF requirements.  First because CRHFs may be unkeyed; second because a keyed CRHF may be distinguishable from a random function.

In practice, however, the common hash function algorithms that we use are argued (or just assumed) to meet not just the collision-resistant hash function definition, but also:

To be suitable building blocks for a pseudorandom function, using HMAC or some other construction;
Often they're also treated as random oracles: a public function (no secret key) that produces random outputs.

Some cryptographers get nervous when you assume #2, though, because they'd like to minimize the assumptions that we make about our primitives' security.


Why is CAMELLIA suddenly so widely used? When nowadays I point my browser to https sites, the cipher that is on most occasions used is Camellia. My browsers (Chrome and Firefox) seem to prefer it, even when AES is available.

Is that not kind of dangerous? Camellia did not receive so much scrutiny as did e.g. AES, so we know actually less about its security. Would it not be much better if AES was the default? I know I can change the cipher on Firefox, but it is not obvious how to do the same in Chrome.

The reason why you see that is because Camellia is the highest-preference cipher in NSS (Chrome and Firefox).  Servers that support Camellia and use the client-preferred cipher suite will use Camellia.

NSS's rationale for this ordering is:

  National ciphers such as Camellia are listed before international
  ciphers such as AES and RC4 to allow servers that prefer Camellia
  to be able to negotiate Camellia without having to disable AES
  and RC4, which are needed for interoperability with clients that
  don't yet implement Camellia.

See also: Bug 430875


Impact of super-polynomial extractors on the security of a zero-knowledge proof Interactive zero-knowledge arguments are proven to be secure in three parts:

completeness (the verifier accepts if the prover is honest)
soundness (a dishonest prover cannot convince a verifier)
zero-knowledgeness (the proof does not leak any information to the honest verifier)

Soundness is usually proven using some kind of extractor: by rewinding the protocol, often multiple times over, the verifier can send multiple challenges, and can in the end compute the witness that the prover is holding.
This talk by Benedikt Bünz mentions that there is a problem with the extractor of the original Bootle, J. et al. 2016 protocol (the predecessor to Bulletproofs): the extractor runs in super-polynomial time.
What is the impact of the super-polynomial complexity of an extractor? Is the mere existence of an extractor not enough to show that the prover has to hold a witness?

The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness.
If the extractor runs in super polynomial time, then the prover itself cannot run the extractor. Note that if you took this to an extreme, then in exponential time it is always possible to just find the witness. So, any ZK proof can be said to be a proof of knowledge with an exponential-time extractor. But this is meaningless.
Technically, proofs of security of protocols that would use such a zero-knowledge proof of knowledge would break down.


How are S-box calculated in S-AES? Read the Reference for Simplified AES ( S-AES )

  Q1 Explain how the S- box is constructed  taking example $b_0b_1b_2b_3=1010$

What I did

$\begin{bmatrix}
1 &0  &1  &1 \\
1 &  1&  0&1 \\
 1&  1& 1 & 0\\
0 &1  &  1& 1
\end{bmatrix}
*\begin{bmatrix}
b_0\\
b_1\\
b_2\\
b_3
\end{bmatrix}+\begin{bmatrix}
1\\
0\\
0\\
1
\end{bmatrix}$

$= \begin{bmatrix}
1 &0  &1  &1 \\
1 &  1&  0&1 \\
 1&  1& 1 & 0\\
0 &1  &  1& 1
\end{bmatrix}
*\begin{bmatrix}
1\\
0\\
1\\
0
\end{bmatrix}+\begin{bmatrix}
1\\
0\\
0\\
1
\end{bmatrix}$

$= \begin{bmatrix}
(1011\times1) \bigoplus (1011\times0)\bigoplus (1011\times1)\bigoplus (1011\times0) \\
(1101\times1) \bigoplus (1101\times0)\bigoplus (1101\times1)\bigoplus (1101\times0)\\
(1110\times1) \bigoplus (1110\times0)\bigoplus (1110\times1)\bigoplus (1110\times0)\\
(0111\times1) \bigoplus (0111\times0)\bigoplus (0111\times1)\bigoplus (0111\times0)
\end{bmatrix}+\begin{bmatrix}
1\\
0\\
0\\
1
\end{bmatrix}$

$=\begin{bmatrix}
1011 \bigoplus 0\bigoplus 1011\bigoplus 0 \\
1101 \bigoplus 0\bigoplus 1101\bigoplus 0\\
1110 \bigoplus 0\bigoplus 1110\bigoplus 0\\
0111 \bigoplus 0\bigoplus 0111\bigoplus 0
\end{bmatrix}+\begin{bmatrix}
1\\
0\\
0\\
1
\end{bmatrix}$

$=
\begin{bmatrix}
1011 \bigoplus1011 \\
1101 \bigoplus1101\\
1110 \bigoplus 1110\\
0111\bigoplus 0111
\end{bmatrix}+\begin{bmatrix}
1\\
0\\
0\\
1
\end{bmatrix}$

$=\begin{bmatrix}
0 \\
0\\
0\\
0
\end{bmatrix}\bigoplus\begin{bmatrix}
1\\
0\\
0\\
1
\end{bmatrix}$

Im getting S-box transformation of $1010$ as $1001$ . Where am i doing wrong ?

  Q2 Also Explain the meaning of the statement and its relevance in construction of S-Box
  " The addition and multiplication in the equation above are being done modulo 2 (with XOR), but not in GF(16)

Do the inverse over the field first, then the affine transform on that.

You must first invert $1010 = x^3 + x$ in $\textrm{GF}(16)$, with prime polynomial $x^4 + x + 1$; use the extended Euclidean algorithm for that, and see that $1100 = x^3+x^2$ is the inverse (you can verify this by computing their product and replacing all $x^4$ by $1+x$ an ditto for higher powers $x^5 = x^2+x$, $x^6 = x^3+x^2$ etc.; we are left with $1$, using $x+x=0$ etc.)

You can also make a log table based on the generator $x$:

$$
\begin{matrix}
0 & x^0 & 1 & 0001\\
1 & x^1 & x & 0010\\
2 & x^2  & x^2 & 0100\\
3 & x^3 & x^3 & 1000\\
4 & x^4 & 1+x & 0011\\
5 & x^5 & x^2+x & 0110\\
6 & x^6 & x^3 + x^2 & 1100\\
7 &  x^7 & x^3 + x + 1 & 1011\\
8 & x^8 & x^2 +1 & 0101\\
9 & x^9 & x^3+x & 1010\\
10 & x^{10} & x^2+x+1 & 0111\\
11 & x^{11} & x^3 + x^2 +x & 1110\\
12 & x^{12} & x^3 + x^2 +x + 1 & 1111\\
13 & x^{13} & x^3 + x^2 +1 & 1101\\
14 & x^{14} & x^3 + 1 & 1001\\
15 & x^{15} & 1 & 0001
\end{matrix}
$$
And note that $1010 = x^9$ so its inverse is $x^6 = 1100$ (as $x^{15} = 1$).

We then apply the affine transform over $F_2$ to $1100$, we get for the matrix multiplication as the sum of the first two columns with result $\begin{bmatrix}1\\1\\1\\0 \end{bmatrix}+ \begin{bmatrix}0\\1\\1\\1 \end{bmatrix}= \begin{bmatrix}1\\0\\0\\1 \end{bmatrix}$

and adding the constant vector $\begin{bmatrix}1\\0\\0\\1 \end{bmatrix}$ to that we get $0000$, as required.

As an aside: $0000$ has no inverse, so we use the convention  that its "inverse" is $0000$ and into the affine transform this yields the constant vector $1001$, as the table says. The point of the affine tarnsform is to ensure the $S$-box defined by the (very nonlinear) inverse mapping does not have $0000$ as a fix point. The element $0001$ has $0001$ as its inverse, and then the matrix multiplication gives $1101$ (the last column) and so adding $1001$ gives $0100$ etc.


Are there any applications of Lie algebras or Lie groups in cryptography? I am interested in the applications of algebra in general to cryptography. In particular, I am wondering if there are applications of Lie algebras and Lie groups to cryptography.

Are Lie algebras or groups used in cryptography?
How could Lie algebras or groups be used in a cryptographic algorithm?
Are there any, for example, cryptographic algorithms which use Lie algebras?

My knowledge of Lie algebras and groups is limited, so I hope I get at least some things right.

  Are Lie algebras or groups used in cryptography?

No. Except perhaps by some daredevils, unable to communicate with the rest of us.

  Are there any, for example, cryptographic algorithms which use Lie algebras?

No. Except perhaps some super exotic ones which nobody uses.

Let's focus on the more interesting question.

  How could Lie algebras or groups be used in a cryptographic algorithm?

I'd say the two main use cases of asymmetric crypto are key exchange and signatures. Given any group, we can build both. For key exchange we use Diffie-Hellman, and for signatures we can use for example Schnorr signatures.

A Lie group has a group structure. By the above, we can use them for key exchange and signatures. The answer to the following question is crucial: how hard is the discrete logarithm problem in a Lie group? Once that is answered, the following question is crucial: what is the size of the representation of private and public keys to obtain a 128-bit security level?
Once that is answered, the following question is crucial: are we more attractive than elliptic-curve groups or multiplicative groups of finite fields?

If the answer to the last question is no, then you probably don't want to use Lie groups. My 2-cents: they seem unlikely to be useful. For the discrete logarithm problem to be hard, we'd want our group to have as little extra structure as possible. By the definition of a Lie group, we require a lot of geometric structure which has no use for our protocols. This may make the dlog problem easier, and hence parameters larger.

For Lie algebras there is no direct use-case. When I googled this, I ended up here. So apparently someone has been able to Diffie-Hellman using some Lie algebra structure. Again, ask the questions from above. If you do worse than what's already out there, what is your use-case?

Of course, perhaps there are other ways to build protocols using the Lie algebra/group structure. It could be interesting, but it may be too little too late.


encrypt message with one digest 0-9 instead of 01-26 How much will the security of one-time pad decrease if I use one digit from 0-9 instead of 1-26?

for example plaintext = "blue" and key = "5 9 4 6":

 b  l  u  e  -  plaintext
02 12 21 05  -  plaintext in numeric form
 5  9  4  6  -  key
07 21 25 11  -  ciphertext in numeric form
 g  u  y  k  -  ciphertext

so blue + 5946 = guyk

Is that as secure as if I use numbers from 1-26?

And will blue + 5946 be the unbreakable one time-pad?

Firstly, I presume this is not something you are going to use for protecting data in any kind of real life scenario, but are only asking out of curiosity.

Secondly, just to get the terminology straight and avoid confusion, what gives an OTP cryptographic scheme information theoretic security is that it meets both of the following two criteria:

The key space is exactly as large as the total message space across all messages encrypted. Hence the "One Time" part of the term. The criterion is not that the key is as "long" as each message you encrypt, but both that it is as long as all messages you encrypt combined, and that there are, at each position in your message, at least as many possible key values as there are possible plain text values. Also, when the key is selected, it must be in such way that at each position, no key value at that position is any more or any less probable than any other key value.
When, at each position in your message, you combine a plain text value with a key value to produce a cipher text value, this has to be done using an operation that does not make any cipher text value any more or any less probable, than any other cipher text value. It just happens that a couple of simple operations, such as modular addition or exclusive-or, have this property, provided that the first criterion is already met. Hence, it is not the use of those operations for combining the key with the plain text that makes an OTP into what it is. These operations only happen to be used because they are conveniently simple, provided you already got a key that meets the first criterion.

Consequently, the problem with your proposal is that it doesn't meet the first criterion, that the key space must be as large as the message space. Going with your example, if you are only going to encrypt a four letter string (and only going to do this once), you will get a key space of only  $10^4 = 10000$ keys, but a message space of $26^4 = 456976$ possible plain texts.


How Mutual authentication and Forward secrecy in The X3DH Key Agreement Protocol work? Can someone explain the statement below from section 3.3 in The X3DH Key Agreement Protocol?

  DH1 = DH(IKA, SPKB)

  DH2 = DH(EKA, IKB)

  DH3 = DH(EKA, SPKB)

  DH4 = DH(EKA, OPKB)

  SK = KDF(DH1 || DH2 || DH3 || DH4)

  DH1 and DH2 provide mutual authentication, while DH3 and DH4 provide
  forward secrecy

How do DH1 and DH2 provide mutual authentication, and how do DH3 and DH4 provide forward secrecy?

Are these also providing integrity of keys in X3DH exchange between server and Alice while fetching the prekey bundle ?

Bob uploads his signed prekey along with its signature to the server. This can be used to check the key integrity.

After Alice does this, Bob learns who Alice is because she sends him her public identity key $IK_A$ and they compute a shared secret ($DH_1$). Then Alice tells Bob who she is by generating an ephemeral public key $EK_A$ and they generate another shared secret ($DH_2$) that they can both confirm. Notice that at this point, Bob and Alice have authenticated themselves to each other, but since Alice is using an ephemeral key which will be discarded, they cannot prove themselves to a third party (deniability). This is why they don't just compute $DH(IK_A, IK_B)$.

Right after she calculates the secret key $SK$ Alice deletes her private ephemeral key and the DH outputs, but she sends the public part $EK_A$ as part of the initial message to Bob, who does the exact same calculations. The important part is that $EK_A$ is ephemeral and so will be deleted, providing forward secrecy.

If there's a one-time prekey and you get a $DH_4$, that only gives the $KDF$ more key material to enhance the security of the secret key. But it serves the same purpose of forward security that $DH_3$ does.


Is HMAC-SHA-1 secure? Although SHA-1 theoretically has collisions, HMAC-SHA-1 which is based on SHA-1 is still widely used (in TLS for example) and is considered to be secure. How is that possible?

As shown in the paper Ricky Demer linked in the comments, HMAC can be secure even when the underlying hash function is not collision resistant. Only PRF-ness of the hash function is required, and SHA-1 is not known to lack it. Or a couple of other conditions can suffice even if it isn't a PRF.

Intuitively, it makes sense that HMAC is secure as a MAC even with SHA-1, because a MAC does not allow a collision search. The only way to find the key would be to compromise the preimage resistance of SHA-1. HMAC in turn prevents length extension attacks and the like that would allow a forgery without knowing the key.

As an aside, even HMAC-MD5 hasn't been broken. However, for the same reason as there – attacks only get better – I would recommend not choosing SHA-1 as the HMAC hash for new applications if you can just as easily use SHA-2.


What is an easy method of proving that a cryptographic oracle attack is possible? Lets say an application is using CBC mode without authentication.  The application is generating cipher text.  This cipher text can be manipulated by the attacker and then transmitted back to the application.

Without looking at the code, what is an easy method for the attacker to prove that a Padding Oracle or Decryption Oracle is present?  Is there a method more elegant than brute force manipulation of the cipher text?

We have a Padding Oracle if there is a different response from the server gives us an indication of the correctness of the pad (say if this needs proving). We can establish this by playing a game where we send badly padded cipher-text and random strings to the server, finally submitting some at random and seeing if we can get a non-negligible Advantage is guessing which one we sent.

The problem is that this might be the "brute force" way. It's fairly easy to do if there is obvious data-leakage, but you have to check through a lot of side-channel attacks to rule out data-leakage to an efficient adversary. I sense you want a clever fast way to prove there is no data-leakage, which doesn't sound possible to me.


Is the $\ell$-Diffie Hellman Inversion easy when g is known? From here they define the $\ell$-Diffie Hellman inversion problem as:

  Given $g^{a},g^{a^2}\ldots,g^{a^{\ell}} \in G$, compute $g^{a^{-1}}$

Would this problem become easy if the generator $g$ is also known?

No.

The stated $l$-DHI problem is believed to remain hard when $g$ is known.

Actually, in the quoted page, it is assumed that $g$ is known throughout. This is obvious in particular in the sections on DLP and CDH.


Perfect secrecy with some considerartion According to eavesdropping indistinguishability experiment $PrivK_{A,\Pi}^{eav}$ from page 34 of this book, I define $\varepsilon$-perfect secrecy as this($\varepsilon>0)$: For every adversary $A$ We have: $Pr[PrivK_{A,\Pi}^{eav}=1]≤\frac12+\varepsilon$. I want to prove that $\varepsilon$-perfect secrecy holds, when $|K|<|M|$. Can anybody guide me? ($|K|$ and $|M|$ are the number of keys and messages in our schema respectively).

I want to prove that $\epsilon$-perfect secrecy holds, when $|K|<|M|$.

I think you are misunderstanding something here. For perfect secrecy as defined, $|K| \geq |M|$ does not imply perfect secrecy. It is the other way around: If perfect secrecy is given, this implies $|K| \geq |M|$.

The implication the other way is impossible to show: Consider $E(m,k) = m$, with some keyspace $K$ larger than the message space $M$ (no need to be more specific). In this case we have $|K| \geq |M|$, but obviously it's not perfectly secret.

And the same goes for your idea: You can not show that something has any kind of secrecy definition, when just the size of the messagespace and keyspace fullfill some equation or inequality. The (almost trivial) counterexample $E(m,k) = m$ with matching key- and message spaces works there as well.


How does RSA signature verification work? I understand how the RSA algorithm works for encryption and decryption purposes but I don't get how signing is done.

Here's what I (think) I know and is common practice:

If I have a message that I want to sign, I don't sign the message itself but I create a hash of it and then sign that hash by using my private key.
The signature gets attached to the message and both are transferred to the recipient.
The recipient recalculates the hash of the message and then uses my public key to verify the signature he received.

Here are the questions:

Why is it common practice to create a hash of the message and sign that instead of signing the message directly?
The important part and this is where I really started scratching my head: How can the recipient verify that I own the private key if the public key seems to be enough to recreate the signature?

Why is it common practice to create a hash of the message and sign that instead of signing the message directly?

Well, the RSA operation can't handle messages longer than the modulus size.  That means that if you have a 2048 bit RSA key, you would be unable to directly sign any messages longer than 256 bytes long (and even that would have problems, because of lack of padding).

In contrast, a cryptographical hash can take an arbitrarily long message, and 'compress' it into a short string, in such a way that we cannot find two messages that hash to the same value.  Hence, signing the hash is just as good as signing the original message; without the length restrictions we would have if we didn't use a hash.

  The important part and this is where I really started scratching my head: How can the recipient verify that I own the private key if the public key seems to be enough to recreate the signature?

What made you think that the public key is enough to recreate the signature?  It is sufficient to verify a signature that you're given, but it is not sufficient to generate new ones (or so we hope; if that's not true, the signature scheme is broken).

If you're using RSA, the signature verification process is (effectively) checking whether:

$S^e = \operatorname{Pad}(\operatorname{Hash}(M))\pmod N$

Definitions: $S$ is the signature; $M$ is the message; $e$ and $N$ are the public exponent and modulus from the public key; $\pmod N$ means that equality is checked modulo $N$; $\operatorname{Pad}$ is the padding function; and $\operatorname{Hash}$ is the hashing function. Note I say "effectively" because sometimes the padding method is nondetermanistic; that makes this check slightly different, but not in a way that matters for this discussion.

Now, if we were trying to forge a signature for a message $M'$ (with only the public key), we could certainly compute $P' = \operatorname{Pad}(\operatorname{Hash}(M'))$; however, then we'd need to find a value $S'$ with:

$S'^e = P' \pmod N$

and, if $N$ is an RSA modulus, we don't know how to do that.

The holder of the private key can do this, because he has a value $d$ with the property that:

$(x^e)^d = x \pmod N$

for all $x$.  That means that:

$(P')^d = (S'^e)^d = S' \pmod N$

is the signature.

Now, if we have only the public key, we don't know $d$; getting that value is equivalent to factoring $N$, and we can't do that.  The holder of the private key knows $d$, because he knows the factorization of $N$.


Is it possible to execute elliptic curve encryption on small sensor-tags CC2650? I am working on a project wherein ECC needs to be implemented on small devices, namely, CC2650 sensor-tags for authentication. The ECC implementation should be on Contiki OS. I have read some articles which suggest it is possible to implement ECC on tiny devices. I want to know is it viable practically considering the memory and CPU processing overhead or one should only use Symmetric encryption, AES on these devices? I would also appreciate if someone can give me feedback on the choice of preferrable library among, RELIC, TinyECC, and OpenSSL.

The CC2650 is a Cortex M3 with 128KB flash memory and 20KB SRAM.

This is definitely not enough for RELIC or OpenSSL.

TinyECC fits, but even if this is only for signatures, some symmetric cryptography will be needed in addition to it.

Better options would be Cifra, libhydrogen, tweetNaCl or a minimal BearSSL build. They all fit in about 20 KB flash memory and require little stack to run.


Average case problem and worst case problem in lattice In Regev's lecture there is "In contrast, virtually all other cryptographic constructions are based on some average-case assumptions.
For example, in cryptographic constructions based on factoring, the assumption is that it is hard to factor
numbers chosen from a certain distribution. But how should we choose this distribution? Obviously, we
should not use numbers with small factors (such as even number), but perhaps there are other numbers that
we should avoid? In cryptographic constructions based on worst-case hardness, such questions do not even
arise."

I do not understand the meaning of "In cryptographic constructions based on worst-case hardness, such questions do not even arise." According to my understanding, in cryptographic constructions based on worst-case hardness we based the cryptography scheme on hard subsets in which the problem is hard, so we should also avoid we based the cryptography scheme on subsets in which the problem is easy.

According to my understanding, in cryptographic constructions based on worst-case hardness we based the cryptography scheme on hard subsets in which the problem is hard, so we should also avoid we based the cryptography scheme on subsets in which the problem is easy.

I think the idea of the statement is more along the following line:

"For most cryptographic schemes we have no proof that the distribution we use in practice is actually as hard to solve as the hardest ones we could come up with. With lattices however we have a proof that the sampling strategy we use generates problems that are just as hard to solve as the hardest instances we could come up with."

So the statement is about the average case for lattices being provably as difficult as the worst-case.


Implementing randomness extractors A randomness extractor is a function that takes an input sampled from high entropy distribution and outputs a value that is close to uniform distribution. It is slightly different from a PRG. PRGs take an input sampled from uniform distribution and output a larger length string which is computationally indistinguishable from uniform. Whereas randomness extractors take an input sample from high entropy distribution and output a smaller length string statistically close to uniform distribution.

In my scheme, I use randomness extractors. In the scheme, the extractor takes an element uniformly sampled from a subgroup of $Z_N^*$, where $N$ is a product of 2 large primes. The extractor needs to output a bit string. I want to implement the scheme but couldn't find any implementations of randomness extractors. Are there any randomness extractors in sagemath, or any other library?

Whereas randomness extractors take an input sample from high entropy distribution and output a smaller length string statistically close to uniform distribution.

Not quite.  A randomness extractor is not simply a function $F\colon A \to S$ such that $F(X)$ has small distance from uniform if $X$ has high min-entropy.  Rather, a randomness extractor is a keyed family of functions $F_k\colon A \to S$ such that if $K$ is uniformly distributed and $X$ has high min-entropy, then $F_K(X)$ has small distance from uniform.  In other words, the premise is that you already have a uniform random key.

So, there is essentially no reason to use a randomness extractor in a practical application.  Generally, either:

You have a secret with high enough min-entropy to do cryptography.

Great!  Use HKDF-SHA256 or your favorite KDF to derive keys from it for each cryptosystem you want to use.

You don't have a secret with high enough min-entropy to do cryptography.

No amount of cryptidigitation with randomness extractors will raise its min-entropy.  Just flip the coin a few more times.

Randomness extractors are essentially of theoretical interest only, so it is not surprising if you have trouble finding practical implementations of them labeled as such (although any universal hash serves as a randomness extractor with the leftover hash lemma).  If you actually want to do cryptography, just feed your initial secret with high min-entropy through a hash function like HKDF-SHA256 or SHAKE128.


Difference between the TLS cipher suites? TLS_DHE_DSS_AES256_CBC_MAC / TLS_DHE_RSA_AES256_CBC_MAC

Hi, I have been studying to learn about various cipher suites and their performances. I gathered that DSS is efficient when compared with RSA. Is it correct and please anyone explain me about their performances and differences?

Ok so first thing, RSA is a signature  algorithm where DSS is a signature standard that currently uses the DSA algorithm with fixed parameters. For more details, see this great explanation.

So what we are actually comparing is RSA and DSA. The main difference is, that they rely on completely different hardness assumptions. I will try to explain them in a simplified manner as the underlying  math is very complex, so please forgive me some abstractions.

DSA (as ElGamal) relies on the  assumption that the discrete logarithm is hard in some special  (sub)groups, meaning in those groups dlog is believed to be computationally hard.
In contrast, RSA bases its security on the (assumed) hardness of factoring, meaning given only a large number N that is the product of 2 primes p and q, it is hard to compute p and q from N.

So in the unlikely case that researchers
find an effective factoring algorithm for example, RSA is broken but DSA is still fine. In contrast, if dlog is easy, DSA can not be used anymore and RSA is still secure.

Given that, it seems to be a good idea to have several algorithms which rely on different assumptions just for the case that one is not true.

I hope this gives you a rough idea of the conceptual difference of those two signature algorithms.


If H(m) = 0 for some m, how can a DSA signature be forged? If we know for some message $m$ that $H(m) = 0$, how can we forge a DSA signature with only the public key?

I got that $g^s*r = (g^x)^r$ where $x$ is the private key, but that's one equation with 2 unknowns, and since discrete log is hard, I can't substitute a value for either $s$ or $r$ and find the other and satisfying the condition $0 < s$ and $r < q$ at the same time.

The signature equation is $$r = (g^{H(m) s^{-1}} y^{r s^{-1}} \bmod p) \bmod q,$$ where $g$ is the standard generator of an order-$q$ subgroup of $\mathbb Z/p\mathbb Z$, $y \in \mathbb Z/p\mathbb Z$ is a public key, $m$ is a message, and the signature is $(r, s)$ for scalars $r, s \in \mathbb Z/n\mathbb Z$.

If $H(m) = 0$, this reduces to $r = (y^{r s^{-1}} \bmod p) \bmod q$.  If you pick $r = s = y \bmod q$, then $r s^{-1} \equiv 1 \pmod q$, so $y^{r s^{-1}} \bmod p = y$ and so $(y^{r s^{-1}} \bmod p) \bmod q = y \bmod q = r$ as desired.


SHA-1 collisions with RSA signatures Could you confirm whether my understanding of the SHA-1 collision issue is correct?

If for certificate $A$, the message digest equals to $X$ and a Root CA signs it with its private key everyone can verify its authenticity by decrypting the signature with the public key that is pre-loaded in to the browser in form of a X.509 certificate, correct?

So given the hash value of $X$ over the certificate and while not knowing the private key that signed the hash,  I know that the final result (signature) = $Y$.

I compute another certificate (with the Issuer filed set to the Root CA that signed the real certificate) so that it’s hash value will as well = $X$. So with two different certificates (data input) we were able to get the same hash (collision occurred).

I still don't know the signers (Root CA that signed the original certificate) private key, but I know that the hash value of $X$ signed with his private certificate = $Y$.

I take my fake certificate and try to impersonate the legit  website. I "steal" e.g. copy the signature (bytes) from the original certificate and send them along with the fake cert to the user/browser when the connection is set up.

Now, the browser will run few checks. It will, try to decrypt the signature with the public key that is wrapped in the X.509 certificate that is pre-loaded in to the browser.

Because we assume (we hope) that our hashing algorithm is collision resistant, the public key decrypts the signature and the browser is able to calculate the same hash value, hence proving the authenticity of the certificate and that it was not changed during transit.

Correct. Essentially the issue is that you sign a hash of the document, so any other document with the same hash you have also signed.

However, you should not really mix terminology like "decrypts the signature". Signatures are "verified". Even in the case of RSA where the basic operation is similar to decryption, the verification involves other things like different padding that must be checked.


SHA256_HMAC for deriving session keys using a counter I need to generate some session keys from a master key that was generated from an ECDH key exchange.  The master key is 256 bits and I need 256 bit  sessions keys.

Is it safe to use SHA256_HMAC with a counter as the HMAC input to get the session keys?

skey1 = SHA256_HMAC(master_key, 1);

skey2 = SHA256_HMAC(master_key, 2);

skeyN = SHA256_HMAC(master_key, N);

The counter is meaningful to the application to know which session key to use.  I have also looked at Hashed Key Derivation Functions (HKDF) but it seems like that is more useful when you need a long random output from a given input. My output length is the same as the input length and I need to be able to generate the correct session key based on a counter value (might not be sequential calls). The counter is essentially an id.

Sure, that should be fine. It's probably more secure than KDF1 & 2 that use a normal hash method and a 4 byte counter. HKDF however can certainly be used for this, but it seems you only need to differentiate, rather than extract and expand.


disadvantages of combination stream and block ciphers I've encountered some papers online describing ciphers made through a combination of stream and block ciphers. (See this 2008 paper by Sandy Harris: https://eprint.iacr.org/2008/473.pdf)  In a nutshell, the concept is to use the output of a stream cipher to add whitening and/or update the round keys of a block cipher.  The paper referenced above describes a combination of AES and RC4.  Other examples of this concept I've seen are a cipher called Eris, combining HC128 and Serpent, and a cipher called Enchilada, combining ChaCha and Rijndael. Enchilada was an entry in the Caesar authenticated cipher contest but was withdrawn in the initial rounds.

The security claims for these combination ciphers are impressive.  Standard attacks against the stream cipher portion should be thwarted by the block cipher, and attacks against the block cipher should be complicated by the use of unique round keys for each block of cipher text.  The speed of these combination ciphers can be comparable to (or even better than) the block cipher by itself, because the number of rounds in the underlying ciphers can be reduced.  (For example, Enchilada runs 12 rounds of ChaCha versus the standard 20, and Eris uses 24 round Serpent, versus the standard 32 rounds).

What I have not been able to find is any cryptanalysis or research on these types of combination ciphers.  On the surface, and with my limited knowledge, there appear to be more advantages than disadvantages to this approach.  At the very least, it looks like a promising topic for research.  Yet the fact that there is so little information in the literature suggests these combination ciphers have flaws I am unaware of.  Which brings me to my question:  what are the disadvantages or weaknesses of this combined approach?

The security claims for these combination ciphers are impressive. Standard attacks against the stream cipher portion should be thwarted by the block cipher, and attacks against the block cipher should be complicated by the use of unique round keys for each block of cipher text.

This might or might not be correct. You claim that if I combine two insecure ciphers I should get secure cipher. This will often be incorrect. Worse, flaws in one cipher can weaken security of other one. Or feeding random data instead of secure static data can weaken security, as some research shows, for example here.

  The speed of these combination ciphers can be comparable to (or even better than) the block cipher by itself, because the number of rounds in the underlying ciphers can be reduced. (For example, Enchilada runs 12 rounds of ChaCha versus the standard 20, and Eris uses 24 round Serpent, versus the standard 32 rounds).

So now you combine two ciphers and reduce their strength, and claim that I should get double security. This is obviously wrong. Also, ChaCha12 is valid (and somewhat normal) choice of rounds, not a reduced version. Since they do more than just ChaCha12, they can't be faster than ChaCha12. And security might be improved or worsened.

  what are the disadvantages or weaknesses of this combined approach?

Those ciphers are new and haven't had proper cryptoanalysis
Those ciphers are slower than their single (and unbroken) counterparts
Those ciphers have poor implementation support
Those ciphers seem to mess around with basic ciphers in hope of creating something secure and fast. In turn they seem to rely more on obscurity than security.

So to be honest, there is no reason to use those ciphers when we have many unbroken, fast and verified secure algorithms. Those multiciphers (or extended ciphers, like AES with 2048bit keys) often rely on scare that everything broken, and make unfounded promises that they can make it better. Truth is often opposite, because you can't extend key and improve speed at once, as that decreases confusion (and because of that security).

If you are scared of one of ciphers being broken (for example in next 50 years), use multiple ciphers with multiple keys (at cost of speed). Then you at least have security of last of ciphers. Don't combine their cores in hopes of making something secure, as this can reduce security. Messing with design without understanding why choices were made is easy way to reduce security.


Why not to use curve over field of $p^m$ with $p > 2$ for ECDSA? I'm reading the ECDSA paper and they say you can only use ECDSA with odd-power fields $p$ or with binary fields $2^m$. Why not other power prime fields?

Form a mathematical point of view, one can define ECDSA over arbitrary finite fields.

Form a security point of view, the most important thing is the size of the group order.

Arithmetic is easy in the case
 $GF(p)$.

Arithmetic gets more involved for $GF(p^m), m>1$, because you have to perform polynomial divisions.

Arithmetic in $GF(2^m)$ is easy again, because the polynomial division in $GF(2^m)$ can be done by simple feedback shift registers. This makes it especially well suited for implementation in hardware.


What's the purpose of the smoothing parameter in lattice-based cryptography? I see nearly all the lattice-based crypto papers talk about the smoothing parameter $\eta$. And I believe even some parameters are chosen with respect to that. However, I do not quite understand what's the purpose of it. What's its relation to lattices? Why is it useful and important for cryptography?

As is mentioned in the comments above, there are many uses for the smoothing parameter. Here is one that provides some intuition of why it's useful.

For a basis $B$ of a full-rank $n$ dimensional lattice, let $P(B)$ be a parallelepiped of the lattice $\Lambda = L(B)$. Consider the operation of taking a point $x \in \mathbb{R}^n$ mod $P(B)$, which is to find the unique vector $y \in P(B)$ such that $x - y \in \Lambda$. In other words, $x \equiv y \mod P(B)$.

Now, consider a distribution that samples points in $P(B)$ in the following way. It first samples a point $e \in \mathbb{R}^n$ from the continuous Gaussian distribution with center at 0 and parameter s, then computes $t \equiv e \mod P(B)$. The output of the distribution is $t$. If the Gaussian parameter $s$ is greater than the lattice smoothing parameter $\eta$, then the distribution of $t$ is statistically indistinguishable from the uniform distribution over $P(B)$. Conversely, if $s$ is less than the smoothing parameter, than $t$ is likely to be close to some lattice point.

To provide a more geometric intuition of what's going on here, imagine placing balls around each vertex of the parallelepiped $P(B)$, and consider the region of each of these balls that intersects with $P(B)$. It is a nice exercise to show that these intersections in fact sum to one ball. Now, imagine going in the reverse, direction, taking a ball and dividing it up according to the angles of the vertices in the parallelepiped, then assigning each fragment of the ball to the corresponding vertex. This ball is the continuous Gaussian we started with in the distribution above. The smoothing parameter is the minimum "radius" of the ball such that, when the regions are assigned in this way, the overlapping distributions are indistinguishable from the uniform distribution over $P(B)$.

The smoothing parameter is intimately connected with many other lattice constants, especially parameters like covering radius and successive minima. This is just one of the many interesting properties that it has.


Is every bytestring a valid Ed25519 private key? In other words, is it a bad idea to simply do this?

signingkey = crypto_random_bytes();
verifykey = Ed25519.verifykey_from_signingkey(signingkey);

Are there weak keys that standard libraries protect you from?

There are a few different formats for the standard parts of an Ed25519 private key, which are usually stored as 32-byte or 64-byte strings, so you need to pay attention to the choices made by the system you use it with.  Everyone agrees on how to compute an Ed25519 signature given a secret scalar, which can be a uniform random 256-bit integer, and a PRF secret, which is a uniform random 256-bit string, but the scalar and PRF secret are stored or derived differently in different contexts.

In some exotic protocols where you share a secret scalar between Ed25519 and the X25519 Diffie–Hellman function, the secret scalar may need to be clamped for DH security.  Some libraries do this automatically, particularly those that use a 32-byte pre-master secret; others do not, particularly those that involve hierarchical key derivation.

For example, in libsodium, crypto_sign_keypair generates a 64-byte secret key consisting of the 32-byte pre-master secret seed and the 32-byte public key, with clamping of the scalar.  crypto_sign_keypair_seed derives that same 64-byte secret key from a 32-byte pre-master secret seed.

For the most part, an Ed25519 private key—meaning secret scalar and PRF secret—really is just a uniform random string of either 32 or 64 bytes.  But different libraries may have slightly different rules, so pay attention to the rules of the library.


What is the purpose of the finite state machine in SNOW? I do not know about SNOW 1.0, but SNOW 2.0 and SNOW 3G have a finite state machine that is used in generating the cipher's keystream output. Why use a finite state machine instead of some kind of filter function?

I read a little more into the 3G Finite State Machine (FSM) here.

I think that it is because the output of the FSM is dependent, not only on the state of the Linear Feedback Shift Register (LFSR), but also on the previous state of the FSM.

A filter function, such as the one used in the Mifare CRYPTO1 cipher, has an output which is entirely determined by it's input. This means that for a given output bit, there is a countably finite number of LFSR states which could have caused such an output. This type of attack is sometimes called a guess-and-determine attack. i.e. here on A5/1

The 3G FSM has an output which is dependent, not only on the state of the LFSR, but also on the previous state of the FSM. There are still a countably finite number of LFSR and FSM states which could have caused an output but the number of possibilities is combinatorially greater. The FSM was changed in SNOW 3G to include two inputs from the LFSR, rather than one, specifically to harden the cipher against guess-and-determine type attacks.

Unfortunately, quantifying why this was done, or how much better or worse it is than a filter function, is not something which is dealt with well when considering symmetric primitives.


Is it insecure to generate a key with your own public and private DH keys? Is a secret key generated with its own public and private keys any less secure than a "normal" secret key generated using DH key exchange?

Example:

KeyPair keyPair = kpg.genKeyPair();
publicKey = (DHPublicKey) keyPair.getPublic();
privateKey = (DHPrivateKey) keyPair.getPrivate();

KeyAgreement keyAgreement = KeyAgreement.getInstance("DH");
keyAgreement.init(privateKey);
keyAgreement.doPhase(
    KeyFactory.getInstance("DH")
        .generatePublic(
            new DHPublicKeySpec(publicKey.getY(), P, G)
        ),
    true);

secretKey = keyAgreement.generateSecret();

In traditional DH Key exchange, users A and B derive a common secret $g^{ab}$ from their respective key pairs $(pk_A=g^a, sk_A=a)$ and $(pk_B=g^b, sk_B=b)$. Aside from active attacks, the security of the scheme depends on the Computational Diffie-Hellman (CDH) assumption, since it is difficult to compute $g^{ab}$ from public keys $g^{a}$ and $g^{b}$.

If you perform the key agreement with yourself, you end up obtaining the secret $g^{a^2}$. The question now is if computing $g^{a^2}$ from your public key $g^a$ is difficult. The Square Computational Diffie-Hellman (SCDH) assumption says that, indeed, it is difficult. It can be proved that SCDH and CDH are equivalent for generic groups.


How hard to break a cipher if it has a different key for each word? Recently I watched the movie 'The Prestige' again but this time the cipher diary impressed  me very well. I like to create my own cipher for my diary because I have some time to kill everyday after deactivating facebook.

So If I create my own substitution table like  'Vigenère_cipher', and use a different key for every page or every word (somehow I manage to remember the key and decipher it), Is it still possible to crack this cipher in anyway?

I read about it some articles, Crackers can detect text patterns and it is easy for them to crack if long text is ciphered using the same key, I think using different keys will reduce this kind of pattern analysis. But I am not an expert in this field, so you can tell me about the possibilities of cracking a cipher written in this way.

NOTE: I am not using this kind of thing to cipher any sensitive data, others data, I am just want to know the possibilities of this thing. I maybe in a wrong thought about all these because I'm not a expert in this field.

A Vigenère cypher can be unbreakable if, and only if:

the key is random,
the key is at least as long as the message being encrypted
the key is used only once.

In that case a Vigenère cypher is mathematically equivalent to a One Time Pad, and the same mathematical proof of unbreakability applies.

You proposal is closer to being unbreakable than standard Vigenère, but it is not an OTP either.  Hence your proposal is not unbreakable, but is more difficult to break than a standard Vigenère.


Concrete example of Weil Pairing I am trying to find a concrete example of the Weil Pairing.
What I have done until now is that I took $E=(x-1)(x-2)(x-3)$ over $F_5$.
I took $E[2]=\{\infty,(1,0),(2,0),(3,0)\}$.
I know that there exist a rational function f such that
\begin{equation*}
div(f)=2[T]-2[\infty]
\end{equation*}
How can I find this function f?
How can I find the points of order 4?
How should I continue?

The automatic way to find f is by using the Miller algorithm.

But you can also see this directly here:
Since the line y=0 is not tangent to E , y is a uniformizing function.
You can write  $(x-1) = y^2*((x-2)(x-3))^{-1}$, where $(x-2)*(x-3)$ has neither a zero nor a pole at (1, 0). This says exactely that (1,0) is a double zero of the function x-1. Since it has a double zero it must also have a double pole at $\infty$. This gives you
\begin{equation*}
div((x-1))=2[(1,0)]-2[\infty]
\end{equation*}

In a similar way you can show this for the points (2,0) and (3,0)

Now you have all 2-torsion points, lets find the other points:
x=0 gives $y^2 = -1$, which solves to y=2 and y=3
x=4 gives $y^2 = 1$, which solves to y=1 and y=4
Since the group has 8 elements, at least two of those points must have order 4.
That all 4 points have order 4 can be shown by a direct calculation(2 squarings are sufficient).
One can also see this by a direct argument:
If the group would be cyclic, it would have 4 elements of order 8. This would let no place for an element of order 4. Therefore the group cannot be cyclic and all 4 elements, which are not 2-torsion elements, must have order 4.


Why does UMAC encrypt the output of universal hash function? UMAC uses a key to choose a random hash function from a family of universal hash functions. The value of the hash function is always encrypted using yet another key, and the resulting ciphertext becomes the MAC code.

What would go wrong if I skipped the encryption step?
In case I have to skip the encryption step (but I can choose different universal hash function than UHASH), what properties would be required from the universal hash function to make the scheme secure?

What would go wrong if I skipped the encryption step?

It's be easy for someone getting some message/UHASH pairs get enough information about the key to produce further message/UHASH pairs himself.  If he receives enough pairs (and it wouldn't take that much), he can fully recover the entire key (and then generate a UHASH for any message of his choosing).

To take a simple example, suppose the attacker receives the UHASH for two messages that differ in a single block.  If we call the data from the block that differs from one message $(A, B)$, the UHASH for the first message is $(k_1 - A) \cdot (k_2 - B) + M$ (where $M$ is the contribution from the rest of the message, and $k_1, k_2$ is the UHASH keying data for that block); if the data from the second message is $(C, D)$, then the UHASH for that second message is $(k_1 - C) \cdot (k_2 - D) + M$ (with $M$ being the same, as we assumed that the rest of the message is the same).

If we substract these two, the attacker can recover the value $(k_1 - A) \cdot (k_2 - B) - (k_1 - C) \cdot (k_2 - D) = AB+CD - (B+D)k_1 - (A+C)k_2$

He has a nontrivial probability of being able to recover $k_1, k_2$ just from this; if not, a third message that differs in only this block will make the recovery unique.

This observation is not difficult to extend to sets of messages that differ in multiple blocks.

  In case I have to skip the encryption step, what properties would be required from the universal hash function to make the scheme secure?

I can't add much to what Ricky Demer has already said; if you need a function that can be used as a MAC, it needs to have the security properties of a MAC


Does Kasisky test for Vigenère cyphers assumption always hold? In the notes from which I'm studying I read about Kasisky test:

"Key observation: Two identical segments of $l ≤ L$ plaintext letters,
will be encrypted to the same $l ≤ L$ ciphertext letters."

Where $L$ is the length of the keyword in the sense that

$$k=(k_0, k_1, . . . , k_{L−1}) \ with \ k_j \in (0, . . . , 25)$$

Is the cypher keyword with, obviously, the number $0, ... 25$ representing each one a different letter of the english alphabet ($A=0, B=1,...,Z=25$)

But if I think about an example like this one

$ptx: $ "Our is the fury" $\Rightarrow$ "Ouristhefury"

$key: $ "$BCDEF$"

Which denoting the $ptx$ as

$$ptx = p_0p_1... , p_i,... $$

applies the encryption:

$$c_i  = (p_i + k_{i \pmod L}) \pmod {26} $$

Represented with a table:

$$\begin{array}{|c|c|c|}
\hline
\text{$ptx$} & \text{O} & \text{u} & \text{r} & \text{i} & \text{s} & \text{t} & \text{h} & \text{e} & \text{f} & \text{u} & \text{r} & \text{y}
\\
\hline
\text{$key$} & \text{B} & \text{C} & \text{D} & \text{E} & \text{F} & \text{B} & \text{C} & \text{D} & \text{E} & \text{F} & \text{B} & \text{C}
\\
\hline
\text{$ctx$} & \text{p} & \text{w} & \text{u} & \text{m} & \text{x} & \text{u} & \text{j} & \text{h} & \text{j} & \text{z} & \text{s} & \text{a}
\\ \hline
\end{array}$$

Following the definition above the two segments "ur" should be encrypted to two equal letters in the cypertext, but instead they are encypted respectively to:

"wu", first occurrence
"zs", second occurrence

I think that they're encrypted into the same two letters of the $ctx$ only when the two couples of $ptx$ letters are located in positions where the same shift occurs (same letter of the keyword).

So my question is: is there some imprecision in the statement from my notes or I'm interpreting something wrong?

There is imprecision in what is stated in your notes. The Kasisky test only works if the corresponding letters in the two segments are separated by a distance that is a multiple of the key length (in other words they are encrypted by the same letter in the key). For example (source Wikipedia):

[abcdea]bcdeabcdeabcde[abcdea]bcdeabc
[crypto] is short for [crypto]graphy.

Note that the key here is $5$ letters long and the distance between corresponding letters in the two segments is $20 = (5*4)$ so the corresponding ciphertext segments will also be the same. It is also worth observing that there is no need for $l \le L$ as seen in the above example.


LFSR: finding the period for an irreducible Polynomial From what I understand an LFSR produces a maximal length sequence if its characteristic  polynomial $p(x)$ of degree $n$ is irreducible, i.e. if it cannot be factored and the smallest integer $k$ for which $p(x)$ divides $x^k – 1$ is $2^n – 1.$

I understand $2^n -1$ has to do with the period, but how is it calculated whether the polynomial is irreducible? Thank you.

Actually the property you mention

  $p(x)$ of degree $n$ cannot be factored, and divides $x^k-1$ for the first time when $k=2^n-1$

means the polynomial $p(x)$ of degree $n$ is primitive. If $p(x)$ cannot be factored into a product of polynomials of lower degree then it is irreducible. It is enough to consider irreducible polynomials of lower degree (like prime numbers) as possible factors.

Therefore one could check whether $p(x)$ factors by methods similar to checking whether a number is prime. However, the following helps:

  For $i ≥ 1$ the polynomial $x^{2^i}-x \in \mathbf{F}_2[x]$
  is the product of all monic irreducible polynomials in $\mathbf{F}_2[x]$ whose degree divides $i$.

So, you could compute $x^{2^n}-x$ modulo $p(x)$ by the division algorithm and declare $p(x)$ irreducible if the answer is zero.


Does omitting the first two lines of RC4's pseudo-random generation algorithm weaken the cipher? A particular educational software program published by a U.S. government agency uses a variant of RC4 to obfuscate its data files (see Stack Overflow question). The variant of RC4 in question is identical to standard RC4 except at the beginning of the pseudo-random generation algorithm. The developer omitted the first two lines below (from Wikipedia's description) because he based his code on an erroneous implementation from Planet Source Code from around 2005.

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

Thus, i and j retain their final values from when the key scheduling algorithm ran (i = 256, not 0, and j = (j + S[i] + key[i mod keylength]) mod 256 from when i = 255 during the KSA).

In this case, the encryption provides no actual security because the key is hardcoded into the software, but suppose the developer had used the code to encrypt a secret file on his hard drive. Does this implementation error significantly weaken RC4's strength?

Yes, that omission weakens the cipher: the output  $\mathtt K$ has a short cycle (at most 65280 bytes) for a sizable class of keys (one in 65536). The following details why.

Because earlier code leaves $\mathtt i=256$ and the first execution of i := (i + 1) mod 256 makes that equivalent to $\mathtt i=0$, not initializing $\mathtt i$ makes no difference in subsequent code; and hence has no security implication whatsoever.

But earlier code leaves $\mathtt j$ to a key-dependent value, thus the lack of initialization of $\mathtt j$ has an effect. In particular, if at the end of key scheduling $\mathtt j=1$ and $\mathtt S[1]=1$, then (by induction) during the whole of the stream generation we have $\mathtt j=(\mathtt i+1)\bmod 256$ and $\mathtt S[\mathtt j]=1$; thus the output generated has a short cycle of (at most) $256\cdot 255$ bytes.
This never occurs in real RC4 (as observed in 1994 by Hal Finney, in An RC4 cycle that can't happen, summarized on the RC4 page), but occurs for $2^{-16}$ of the keys in the modified cipher.


What quality would an interactive proof executed many times sequentially have that makes it zero knowledge that one executed in parallel would not? The first protocol can be proved ZK, but the second is not believed to be so? What quality of the parallelization makes it such that an identical protocol executed in parallel, as opposed to sequentially, would remove its ZK properties?

EDIT#1: The source of the IP's was asked for so I shall say, they are from some course notes of a graduate cryptography course at UCLA, from a few years ago, and given to be based off of the book "Foundations of Crypto" by Goldreich.

Hint: look at the security proof of the zero-knowledge property of the first scheme. I recommend writing it fully and formally, if you want the solution to become clear. It relies on a common "rewinding" strategy, and requires in particular to guess in advance the challenge of the verifier, with non-negligible probability. Now, what happens to this strategy when we consider parallel repetitions instead? Can you see where exactly it breaks down? We can give you further hints if you explain exactly what you tried and tell us where you are stuck afterward.


Do I need to know the "mode of operation" to decrypt a message encrypted with a block cipher? If I have received an AES encrypted message, and if I do know the key with which it was encrypted, do I also need to know the mode of operation with which it was encrypted in order to decrypt it? My understanding is that this is indeed the case.

If so, how is the mode of operation transmitted along with the encrypted file?

Yes, of course you need to know the mode of operation in order to decrypt.

On the other hand, the mode of operation isn't usually explicitly transmitted in the ciphertext.  Using the same key with different modes of operation may cause unexpected weaknesses.  For example, consider one message encrypted with CFB mode with IV=2 (which is perfectly secure) and another message encrypted with CTR mode with IV=0 (also secure).  If we give the attacker both ciphertexts, he knows a relationship between the first block of the CFB mode plaintext and the third block of the CTR mode plaintext; this is a leakage that does not happen with either mode individually.

Because of this, we restrict a specific key to one mode; that is, both sides agree that this specific key will be used with that specific mode.  If there are multiple modes possible, the two sides will agree to the mode at that time.

Now, there are some cases where a key is used only once; one such case happens we're using public keys to encrypt the file.  In this case, the encryptor will pick a random AES key, public key encrypt that AES key (using the receiver's public key), and then use the random AES key to encrypt the actual message.  In that case, you can encrypt the mode (and other details, such as whether we're using AES and not 3DES) along with the random key.