RSA: Fermat's Little Theorem and the multiplicative inverse relationship between mod n and mod phi(n) I'm learning about the proof of the RSA encryption algorithm, and I'm clearly fudging or missing something, because for me it doesn't add up.

When generating keys for RSA encryption, we make sure that:
$ed \equiv 1\pmod{\varphi(n)}$

But when encrypting or decrypting, we use:
$C \equiv M^e \pmod{n}$

Now I would understand if we had made:
$ed \equiv 1 \pmod{n}$

because now raising $C$ to $d$ will get us $M$ again.

But we use $\varphi(n)$ instead.

I understand that we use $\varphi(n)$ to make $d$ difficult to compute, since to find $\varphi(n)$ you need to know the prime factorisation of $n$.

But how do you link a multiplicative inverse mod $\varphi(n)$ with a multilicative inverse mod $n$?

From reading around it seems that according to Fermat's Little Theorem, a multilicative inverse mod $\varphi(n)$ will hold mod $n$.

If a multiplicative inverse relationship works for $\varphi(n)$ and $n$, why does an attacker not work out the multiplicative inverse of $e \pmod{n}$? Even if the key were originally made mod $\varphi(n)$, surely using an inverse mod $n$ would work just as well?

Clearly I'm missing something - could someone please help enlighten me?

You are misunderstanding Fermat's Little Theorem (or rather, its more general form as Euler's Theorem) which does not state that a multiplicative inverse modulo $\varphi(n)$ is the same modulo $n$. What the theorem says is that if you have an integer $a$ coprime* to $n$, then the following is true:

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

In other words, the order of the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is $\varphi(n)$. In other words, the relationship above induces a cyclic order on the powers of $a$ modulo $n$, meaning if you keep multiplying $a$ with itself you will eventually get $1$ (not necessarily after exactly $\varphi(n)$ exponentiations, but Lagrange's theorem says that if $k$ is the smallest nonzero $k$ such that $a^k \equiv 1 \pmod{n}$ then $k$ must divide $\varphi(n)$. Perhaps more intuitively, it (informally) means that powers of an integer modulo $n$ behave as if they were taken modulo $\varphi(n)$. Note this says nothing about multiplicative inverses being the same.

So what does this mean? It means that when you raise a plaintext $M$ to the power $e$, you get:

$$M^e \equiv C \pmod{n}$$

So how exactly do you decrypt this? One possibility is to take the $e$th root modulo $n$, but this is expensive and problematic. Fortunately, there is another way. Since we know from above that:

$$M^{\varphi(n)} \equiv 1 \pmod{n}$$

It follows that, for any integer $k$:

$$M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

So we just need to find an integer* $d$ such that $ed = k \varphi(n) + 1$, that is, $ed \equiv 1 \pmod{\varphi(n)}$. Then:

$$C^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

And this is why it works. You are choosing $e$ and $d$ multiplicative inverses of one another modulo $\varphi(n)$ precisely so that their product is congruent to $1$ modulo $\varphi(n)$, and Euler's theorem does the rest. If you are observant you will notice the rule $(M^e)^d = M^{ed}$ really is what makes RSA work as a public key scheme by separating $e$ and $d$, and this is exploited in Diffie-Hellman and some other public key schemes as well.

This doesn't however work if you had chosen $ed \equiv 1 \pmod{n}$, because $kn + 1$ doesn't actually mean anything modulo $\varphi(n)$. There is no structure to be exploited here, and you will just get an arbitrary number that won't help you decrypt $C$. In the same way, multiplicative inverses modulo $n$ do not "carry over" modulo $\varphi(n)$. There is a relationship between integers modulo $n$ and integers modulo $\varphi(n)$, but it is not that simple (I just described that relationship above), and you have to work with that relationship to make your algorithm work.

So the answer to your question is really "because this is how arithmetic works out modulo $n$" :)

* in fact RSA "works" even when the plaintext is a multiple of $p$ or $q$, but never mind that now.

* in practice, $\varphi(n)$ is sufficient but not necessary, and we use $\lambda(n) = \mathrm{lcm}(p - 1, q - 1)$ (the Carmichael function) which is basically $\varphi(n)$ with any prime factors shared between $p - 1$ and $q - 1$ left out - this means we still have all the nice properties that we require for RSA, but with the numbers involved as small as possible (but still secure, of course - knowledge of either $\varphi(n)$ or $\lambda(n)$ is polynomial-time reducible to factoring $n$, so knowing one is equivalent to knowing the other).


What is significance of recovering the chaining value of a hash compression function? What is significance of recovering the chaining value of a compression function, when the message and its output are known? in other words, if a compression function $CF$ takes a chaining value $h_{in}$ and a message $m$ as inputs and outputs $h_{out}$.

$h_{out}=CF(h_{in}, m)$

Is it a bad property if given $m$ and $h_{out}$ to recover $h_{in}$?

This should be considered as a weakness of the compression function, which is not a preimage resistant anymore. Sometimes, but not always, this may imply an attack on a hash function or a larger construction using this compression function.

For instance, consider the prefix MAC scheme, which is constructed out of a hash function $H$ as follows:
$$
MAC_K(M) = H(K||M).
$$
The prefix scheme is secure for some hash functions, for example the SHA-3 (Keccak) hash function.

However, if the compression function used by $H$ is not preimage resistant, then an adversary given $MAC_K(M)$ may recover the chaining value
$$
CV=H(K),
$$
and construct a valid MAC for any other $M'$ even though he does not know $K$.


EdDSA Verification vs. Cofactorless Verification In the EdDSA for more curve paper the authors defines:

Keys

  An EdDSA secret key is a $b$-bit string $k$. The hash $H(k) = (h_0, h_1, ... , h_{2b−1})$ determines an integer $s = 2^n+\sum_{c≤i<n} 2^ih_i$ , which in turn determines the multiple $A = sB$. The corresponding EdDSA public key is $A$.

Note that $B$ is defined to be a point of order $l$ where the cardinality of the curve is $\#E(p)=2^cl$

Signature

The signature of a message $M$ under key $k$ is created as:

Define $r = H(h_b, ...., h_{2b-1},M) \in \{0,1,...,2^{2b}-1\}$.
Define $R = rB$.
Define $S = (r + H(\underline{R},\underline{A},M)s) \mod l$

Output: $(\underline{R},\underline{S})$
(note that underline is a byte encoding of points or integers which doesn't matter for this question)

Verification

Verification of a signature  $(\underline{R},\underline{S})$ of a message $M$ is defined as:

$2^cSB = 2^cR+2^cH(\underline{R},\underline{A},M)A$

Cofactorless Verification

Cofactorless verification of a signature  $(\underline{R},\underline{S})$ of a message $M$ is defined as:
$SB = R+H(\underline{R},\underline{A},M)A$

They comment that:

  Any alleged signature that passes cofactorless verification will also pass verification. The signature of a message will pass cofactorless verification, so it will also pass verification. However, a signer using a secret key outside the above signing procedure can create strings that pass verification without passing cofactorless verification.

I can't really understand the above comment and I have a few questions.

What does it mean "secret key outside the above signing procedure" ? Does it  mean that $s$ is a string without a leading nth-bit set and not multiple of $2^c$ ?
How does the $2^c$ factor affects the verification compared to cofactorless verification?
Can you provide me an example/way of generating a secret key "outside the above signing procedure" that generates a signature that pass verification without passing cofactorless verification ?

1. It means that someone possessing the private key $s$ can create signatures which pass verification but not cofactorless verification with respect to the public key $A$.

3. For example, if $C\in E$ is a point of even order (e.g. $2^c$), and the signer replaces $R:=rB$ in step 2 of the signing procedure by $R:=rB+C$, then
$$
  2^cR+2^cH(\underline R,\underline A,M)A
  \;=\; 2^cSB+2^cC
  \;=\; 2^cSB
$$
but
$$
  R+H(\underline R,\underline A,M)A
  \;=\; SB+C
  \;\neq\; SB
  \text.
$$
The private key is necessary to create such a signature because anyone modifying $R$ (or one of the other parameters) after the signature has been finalized (e.g., someone who does not know the private key) is very likely to be caught by $H(\underline R,\underline A,M)$ contributing to the verification formula. (Note this contradicts Cryptostasis' comment above.)

2. Due to the Pohlig-Hellman algorithm, the security of the whole system is dependent on the large prime-order subgroup $E[\ell]$ of $E$, while small prime factors of the group order do not reasonably contribute to the hardness of computing discrete logarithms.
Group-theoretically, multiplication by $2^c$ realizes a projection to the subgroup of $E$ of size $\ell$, which is a direct factor: From the structure theorem of finite abelian groups,
$$ E\;\cong\;E[\ell]\times G\text, $$
where $G$ is an abelian group of order $2^c$, hence multiplication by $2^c$ maps an element to $E[\ell]\times\{e\}\leq E[\ell]\times G$. (And since $\ell$ is coprime to $2$, multiplication by $2^c$ is an automorphism on $E[\ell]\times\{e\}$.)
Thus multiplication by $2^c$ throws away a little bit of information from the factor group $G$, but that wasn't useful anyway.

In practice, it is not going to matter which variant you use. As explained above, cofactorless verification is a little stricter, hence you might run into interoperability problems with non-conforming signers (but I see no reason why anyone would implement it in a way that makes this happen). On the other hand, verification (with multiplication by $2^c$) will take a few cycles more.


OCB - brute force against unknown IV I read that brute force attacks against a plaintext encrypted in OCB with unknown key and IV has approximately the same complexity as an attack where only the key is unknown.

Why is that?
Is there a description of this attack? If not, could you give me a hint on how this attack might work?

Ok, here is one possible sketch of a brute-force style attack against OCB, which doesn't assume you know the nonce.  It takes 512 trial decryptions for every key tested, so it's a bit more expensive than, say, a brute-force attack on CBC, but only by a constant factor.

Let us assume that:

you have an encrypted message that is $16n+15$ bytes long
that you know the last 15 bytes of the plaintext
and there's another block $P_n$ that you have enough information that you can recognize it if we decrypt it properly.

If we look at the OCB processing of the last 15 bytes, we have:

$C_{last} = P_{last} \oplus Trunc( E(K, \Delta_{last} ))$

where $Trunc$ is a function that chops off the last byte.  So, we know the first 15 bytes of $E(K, \Delta_{last})$, namely $C_{last} \oplus P_{last}$.

To test a value of $K$, we iterate through all 256 possible values of the last byte $B$, and compute

$\Delta_{last} = D(K, (C_{last} \oplus P_{last}) || B)$

From each $\Delta_{last}$ value, we compute the corresponding $\Delta_{n}$ value (which is a $GF(2^{128})$ multiplication, so that's easy), and then compute:

$P_n = \Delta_{n} \oplus D(K, C_n \oplus \Delta_n)$

and check if that is a plausible plaintext value.

Once we have a plausible values for $K$ and $\Delta_i$, we can check the authentication tag to validate the decryption.

Once we have all that, we can also recover the nonce that was used to encrypt the message; this may be useful if related nonces were used to encrypt other messages with the same key.

Now, obviously this attack can be improved if we can get a plaintext message which is $128n+127$ bits long; that is unlikely in practice.


Probability of a prime number of points on an elliptic curve over a prime field Suppose we have some elliptic curve defined over $\mathbb F_p$, with $p$ a large prime. Let $n$ be the number of points on the curve. I am interested in what is currently known about the probability* that $n$ is prime (i.e. some reasonable lower bound on this probability).

$n$ is well-known to be within the "Hasse-Weil interval":
$$t := \left| n - (p + 1) \right| \le 2 \sqrt p$$

By PNT there are something like $\frac {4 \sqrt p} {\log p}$ primes in this interval, but obviously the probability distribution of $t$ in this interval is non-uniform, so this does not directly give us a good bound. Is there perhaps some known constant multiple of this that is a correct bound?

*Note: To clarify the meaning of "probability": Suppose that the curve was chosen at random (uniformly) from all the nonsingular elliptic curves of form $y^2 = x^3 + ax + b$ over $\mathbb F_p$.

It is known, that as in your setting, when $p$ is prime every possible integer in the Hasse-interval $\mathcal{H}_p$ arises as group order of an elliptic curve $E/\mathbb{F}_p$. For arbitrary prime powers $q = p^f$
this is not generally true: there are often not enough supersingular curves to cover the cases $N \equiv 1 \mod p$.

Galbraith and McKee gives a formula for the probability that a randomly
chosen elliptic curve over a finite field has a prime number of points. The conjecture is the following: Let $P_1$ be the probability that a number within $\mathcal{H}_p$ is prime. Let $C_2\approx0.6601$ be the Hardy-Littlewood twin primes constant. Then the probability that an elliptic curve over $\mathbb{F}_p$ has a prime number of points is asymptotic to $c_pP_1$ as $p\to  \infty$, where

$$c_p=\frac{3}{2}C_2\prod_{l\vert p-1,l>2}\Big(1+\frac{1}{(l+1)(l-2)}\Big) .$$

One might say that $P_1\approx\frac{1}{\log p}$, however this estiamte might not be precise in short intervals.

If all numbers of points in $\mathcal{H}_p$ were equally likely, then we would have $c_p = 1$. The expression given for $c_p$ lies between
about $0.44$ and $0.62$, indicating the phenomenon that prime numbers of
points are disfavoured.

Even though prime numbers of points are seem to be disfavoured by nature, you can efficiently generate such curves in poly-time, ie. in $\mathcal{O}(\log^{3} p)$.


What is a Message Transmission Scheme? I've been given as an exercise to show an encryption scheme that is CCA-secure but is not a secure message transmission scheme.

What is a message transmission scheme, and how does it differ from a regular encryption scheme?

An "encryption scheme" defines the encryption/decryption of data.

A "message transmission scheme" is about securing transmission and defines both "privacy" and "authenticity" between a sender and a receiver.

Since you haven't asked about the definition of CCA-secure (encryption) schemes and since you've been given this as an exercise, I won't mention anything about CCA-secure schemes because that would quickly provide an answer which would almost solve your exercise for you (and you wouldn't learn from that). But, when you keep in mind what I wrote above, you should be able to quickly come up with an encryption scheme that is CCA-secure while not being a secure transmission scheme.

Hint:

Your CCA-secure scheme will be missing something a "message transmission scheme" provides… look closely at what I wrote, ask yourself what a "CCA-secure scheme" defines at a minimum, and then start thinking. You should be able to wrap your brain around it easily if you look at what each scheme defines.


fixing WEP by treating all messages as one long stream in the course of introduction to cryptography on coursera
professor suggested treating all messages as a long stream XORing them with the key
this way we will not need to change the key and will not have the IV problem
and the question is
if so how can we generate a key that will encrypt the whole traffic using just XOR

Well, WEP uses RC4 to encrypt, and RC4 can be used to generate a long keystream to encrypt multiple messages.  The key would be negotiated when the connection starts; both sides would hand over the negotiated session key to the RC4 algorithm, and RC4 then generates a long keystream that can be used to encryption.  In fact, when SSL uses RC4, it does exactly this.

However, when it comes to WEP, there is a significant practical problem that doesn't arise with SSL; message reliability.  With SSL, the protocol assumes that the protocol is run over a reliable transport (generally TCP); the transport protocol will ensure that the receiver will get every message the sender sends, and in the correct order (and if it can't ensure that, it raises an error condition that shuts down the connection.

This is important for RC4; it generates a separate part of the keystream for every message.  For, if we encrypt two 100 byte messages, bytes 0 through 99 of the keystream will be used to encrypt message 1, and bytes 100 through 199 of the keystream will be used to encrypt message 2.  When the receiver gets the encrypted message 1, he can use his copy of the RC4 keystream generator to create bytes 0 through 99 of the keystream, and decrypt message 1.

The problem comes in if the receiver never receives message 1, and instead receives message 2.  If he were to ask RC4 for the next 100 bytes of the keystream, he'd get bytes 0 through 99, which won't decrypt message 2 properly at all.

With SSL, this situation never comes up; the underlying TCP protocol will ensure that message 1 will always arrive first (unless there's some man-in-the-middle attacker; yes, he can cause the connection to shut down; there's other protections in place that ensure he can't do anything else).

However, WEP is designed to protect wireless connections; the messages that it protects are datagrams transmitted over the radio.  In practice, it is quite common for messages to not be received correctly (because of interference).  Because of this, WEP cannot assume that all transmitted messages will be received, and so WEP cannot use a long-standing RC4 key.

A cryptographic protocol needs to meet multiple goals; they ought to be secure; however, they also need to work well with the overall system design.  WEP, as designed, does the latter reasonably well; it's just the former they missed a bit.


Why EMI/EMC testing is necessary of Cryptographic Equipment? In the Book, "Endpoint Security" Page 265, It includes Electromagnetic Interference / Electromagnetic Compatibility Testing in Heading Level 1.

Why is it necessary for Cryptographic Equipment to have EMI/EMC
Testing?
What equipment is used to carry out such testing?

It’s my understanding that the information gained from a side channel attack would typically be isolated to the particular cryptographic algorithm’s structure, and physical hardware implementation. Provided the context of the article completing EMI/EMC testing would generally be a requirement of governing bodies like the Federal Communication Commission, which have jurisdiction even if the hardware is not running cryptographic systems.

So in the interest of security and responsibility it would be necessary to complete this testing to ensure that the particular cryptographic software/hardware is resistant to side channel attacks, while simultaneously maintaining compliance with regard to preventing the emission/receiving of harmful EM interference. Personally completing side channel testing adds nothing to security except to gain insight on the capabilities of a potential attacker on a particular system, because even if the system being tested is resistant to side channel attacks the tester will gain zero insight into undocumented modes of operation.


Is this man in middle atack possible in quantum cryptography? Lets consider there is channel between Alice and Bob, sequered with quantum cryptography.
To put it simple, Alice is left, Bob  is right  and the quantum states are 'up'  ~ U and 'down'  ~ D.
Alice and Bob generates pair of bounded particles ,always one u one d but you dont know wtigth one flyes left or right , what fly always in both direction. Also they can capture particles. If captured, a particle is destroyed.

Alice captures the particle what flyes left and sends free what flyes to the right, Bob does the mirrored. If anyone captures the particle, he would know that other particle of the pair is.

Lets consider the MiM attacker Eve, what can do like Alice and Bob do.

Eve captures the next particle send by Alice, let it be U. So she knows, that the particle what Alice captured locally was D. But the particle U is destroyed, Bob will know that way, that there is something wrong with the channel.

Important : Eve then generates own particles, while capturing the left one.
If the captured is D, Eve knows that the pair is U and it might be send further to Bob. In the model that there are only 2 states, the probability of producing the right pair is 50% , therefore Eve in average need to be capable to generate and send particles twice faster that Alice and Bob do, that generally fair possible practicly.

Alice can not distinguish between cases whether a sent particle was captured by Bob or Eve, neither Bob can distinguish,  because the quantum features of particles match.

Later Eve can, as usually in MiM take over a channel and start to send false data to them.

Is there something wrong it this szenario or generaly quantum cryptography is a big talk about nothing?

Is there something wrong it this scenario?

Obviously, yes.  Any such QKD system would require an authenticated channel back from Bob to Alice; that's to make sure that Bob is the one that's actually receiving the quantum signal, and not a man-in-the-middle.

More fundamentally, your system doesn't actually take advantage of any Quantum Effects; by measuring a particle, you can deduce its entire quantum state (or, at least, as much of the state that the protocol cares about); as such, it can be entirely described with classical physics.

There are actually several proposed QC systems; the simplest is probably the original BB84 system.  This system has the photon being in one of four quantum states, and takes advantage of the fact that a measurement will give only 1 bit (and this is the crucial quantum effect); using the authenticated channel, Alice and Bob can coordinate which of Bob's measurements gave answers consistent with what Alice sent; because the attacker cannot measure things without losing information, any attempt by him to measure and retransmit will introduce a measurable error rate.

  [Or] quantum cryptography is a big talk about nothing?

A number of people (including myself) are quite skeptical about quantum cryptography; however that doesn't have with us not thinking it doesn't work.  Instead, we look at the limitations (need for special quantum channel, cost of equipment, low data rate, low range, vulnerability to side channels), and ask "what advantage does it have compared with classical cryptography (either symmetric or asymmetric) to justify dealing with these limitations".


ElGamal with weak public key Assuming this setup: A prime $p$, a generator $\alpha$ in $\mathbb{Z}_p^\ast$. Alice chooses her private exponent $d$ from $[2, p-2]$ and calculates her public key $\beta$ = $\alpha^d$.

Bob then chooses his private key $i$. The resulting masking key $k_M$ used to encrypt the message is then calculated as $k_M = \beta^î$.

I wondered if the following attack is mathematically possible:

If $\beta$ turns out to be $p-1$, there will be only two possible results from the $k_M$ exponentiation being $1$ and $p-1$. This is because the element $p-1$ in a cyclic multiplicative group always has $ord(p-1) = 2$, so only those two elements can be generated by $\beta$. This in turn means that only two masking keys $k_M$ exist. The attacker can then easily try those two keys and will immediately be able to decrypt the message.

Can you confirm whether this attack will work and, if yes, if real-world ElGamal implementations are vulnerable against it?

Can you confirm whether this attack will work

It depends on a situation which is mind boggingly unlikely to happen, but if it is does happen, yes, it will work.

We'll have $\beta = p - 1$ iff $d$ just happens to be the value $(p-1)/2$; this happens with probability $1 / (p-2)$.

For El Gamal to be secure at all, $p$ needs to be large, say, at least 2048 bits.  This means that this has a probability circa $2^{-2048}$ of happening.  We typically don't sit around worrying that we'll be hit by a meteor in the next 10 seconds; that has a much higher probability of happening than us picking the bad $d$.


ECDSA vulnerability related to recovering private key using same r I'm considering this for bitcoin transaction as it uses ECDSA so if the signer generates two signatures suppose s1 and s2.
where:

I get it that any attacker who have s1 and s2 can recover its private key x.
But the question is can the signer use a different private key x1 for instance to generate s2..in such a way even if he uses same k but still its private key will be safe.??(cryptocurrency like bitcoin allows multiple public private key pair of a user)
Am i getting something wrong otherwise this would have been not a well known ECDSA vulnerability in bitcoin.
Please explain the contradiction. Thanks in advance

You are positing that the signer signs two messages $m_1$ and $m_2$ under different private keys $x_1$ and $x_2$, but the same per-signature secret $k$.

\begin{align*}
  s_1 &= (h(m_1) + x_1 r)/k, \\
  s_2 &= (h(m_2) + x_2 r)/k.
\end{align*}

Note that $r = x([k]B)$ where $B$ is the standard base point.  Even if you are given $s_1$, $s_2$, $m_1$, $m_2$, and $r$, this is a system of two equations in three unknowns.  This doesn't even constrain you to a unique solution: for any nonzero value of $x_1$, there is a corresponding value of $(x_2, k)$; likewise $x_2$ and $(x_1, k)$, and $k$ and $(x_1, x_2)$.  Indeed, for, e.g., secp256k1, there are approximately $2^{256}$ possible solutions for $(x_1, x_2, k)$.


Which are the current solutions to the illegal values in the homomorphic secret sharing? There is a usual example about homomorphic secret sharing, focused on e-voting. Supposing we use Shamir's scheme for the Secret Sharing system, a participant generates a polynomial whose a0 is +1 (yes), 0 (abstention), or -1 (no), and then distributes the calculated n points to the tellers. Each teller will calculate the sum of every point, and publish the result. Everyone is able to calculate the resulting polynomial, which is equal to the sum of all the generated polynomials by the voters. The secret revealed then, is the sum of every +1, 0, or -1.
One of the vulnerabilities this system has, is that a malicious player could generate a polynomial with a0 = 7893. If the a0 value is out of the {-1,+1} range, it will corrupt the final outcome. Which are the current solutions to this problem? In other words... How is it possible to ensure that the a0 is between a and b, without revealing its value?

This is a "known vulnerability" of Shamir's secret scheme. While it is known to be information-theoretically secure, here security means privacy.
Shamir's scheme has no authenticity properties --- a single party can change the output by modifying a single share.
There have been recent suggestions to augment the notion of "secret sharing" to impart it with a notion of authenticity as well. This can be viewed similarly to how the primitive of "Encryption" (which only gives privacy) was augmented to "Authenticated Encryption" (which gives both privacy and authenticity).
I've seen this proposed in the RealWorldCrypto 2020 talk Adept Secret Sharing, presented by Phil Rogaway (Mihir Bellare and Wei Dai are listed as co-authors/co-contributors though). It seems that there hasn't been a paper/slides made public as a result of the talk though.
The talk itself is available here.
I don't remember the entirety of the talk, but the conclusion was something along the lines of a generic transformation to get private + authentic secret sharing, but the privacy becomes computational (rather than information theoretic).
This likely does not work for your purposes though --- such a scheme is likely no longer homomorphic (I cannot remember details from the talk currently though). So what do people do in practice? I believe some combination of "standard" Shamir's secret sharing, and a non-interactive zero knowledge (NIZK) proof that $a_0\in (a,b)$.
This is called a "Range proof" (see for example this).


How strong is XOR encryption of 256 bit plain text with 256 bit key? I was wondering if we take just 256 bits of plain text and simply XOR  every bit with a 256 bit key, how strong can it be ?

That construction is called a one-time pad or OTP (not to be confused with a one-time password). OTP's are theoretically perfectly secure as long as the key is not repeated or reused and the key is indistinguishable from random by any adversary. In that case any 256 bit plaintext message is equally likely, so it is impossible to even brute force the key. Because of that, the size of the key and plaintext do not even matter, as long as there are as many bits for the key as there are bits in the plaintext.

Note that an OTP does not provide message integrity nor authenticity, only confidentiality. Of course the exact size of the input is leaked by an OTP too, so that's not kept secure either.

Of course, generally the practical security depends on the system, the quality of the randomness, the actual access to the key etc. etc. etc.


Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key? I have just learned about using PGP/GPG for email encryption and one thing bugs me:

How is it possible that a message encrypted with somebody's public key can be decrypted only with that person's private key?

This concept of asymmetric encryption is not easy for me to understand. Simply said, I would expect that the process to encrypt with the public key should be unique and therefore be able to be reverted with the same key.

What's the key operation that ensures this is not possible?

The basic explanation is that you need both keys to make a complete encryption/decryption cycle.

Basically the encryption works with modulo arithmetic so that

$$c=m^a \mod n$$

and

$$m=c^b \mod n$$

where $a$ and $b$ are the public and private key of the algorithm. $m$ is the plain text message and $c$ s the ciphertext.

The most important thing about the formulas is

$$m=(m^a)^b \mod n = (m^b)^a \mod n$$

For this to work $a$, $b$ and $n$ must follow certain restrictions.

This is the basic idea behind RSA and other asymmetric encyption systems whereas you can make the operations more complex/different but the basic idea that using two different keys to complete the encryption/decryption cycle.


SSL Traffic Inspection Is the firewall decrypted my session? There is an error "Certificate Not Trusted" (Server Certificate changed to Firewall Cyberoam Certificate). Which public Key I got? Is Main server Public Key or Cyberoam Public Key? Is SSL traffic inspection is same for Authenticated Encryption "GCM" ?

Is the firewall decrypted my session?

In order to inspect the encrypted traffic, your firewall has to decrypt it firts, one way, or the other. Since it can't do it any other way, it "impersonates you/your computer" as the client to the server (and creates an encrypted connection to the server) and also "impersonates the server" to your computer as the client (and creates an encrypted connection with you).

  There is an error "Certificate Not Trusted" (Server Certificate changed to Firewall Cyberoam Certificate).

That's because the firewall has to "impersonate" the server to your client and as it can not use the real servers certificate for authentication/en/decryption/data integrity of the traffic between you (as the client) and it (as the server), it has to use its own. The certificate the firewall uses is issued by its own CA that's obviously not set as trusted in your browser.

  Which public Key I got? Is Main server Public Key or Cyberoam Public Key?

The firewalls (Cyberoam).

  Is SSL traffic inspection is same for Authenticated Encryption "GCM" ?

AFAIK, yes.

The only problem I see here is if you don't know your encrypted traffic is being inspected / don't want it inspected. If you do, you should set the firewalls CA as trusted in your browser and that'd be that. Here are the instructions from Cyberoam Knowledge Base

Hope I helped.


implementing GCM with dev/urandom for a nonce I'm currently trying to integrate GCM into my code, and I have just enough knowledge to know I'm probably doing this wrong. I know for GCM and other CTR like ciphers, using the same key with the same nonce multiple times is a terrible, horrible, very bad idea. the question is, using the same key for a decently long period (several hundred or thousand messages), what is the likely hood that a nonce is repeated, if the nonce is randomized each message with /dev/urandom. or should I simply stick to a counter beginning at a random number?

clarification: the keys are unique per session, being derived from diffie hellman group 14. my only concern is the likely hood of generating two matching nonces, given a pool of say 20000 nonces from dev urandom

If you are following NIST recommendations and you use a 96 bit NONCE (12 bytes), then you should be fine using a random NONCE generated by /dev/urandom. It should provide sufficient entropy for your needs.

But you'll be better off using the deterministic construction for the NONCE. It requires the NONCE to be composed of a 32 bit "fixed field" and a 64 bit counter. You can use a sequence number for your fixed field or a randomly generated string as recommended by the standard specification. As such you'll be able to do at most 264 opertions with the same key/NONCE. But then you have a hard limit on the number of operations you can process from the underlying CTR mode of operation to 232 - 2.

Another data point in your decision might be the recommendations in Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS:

  We conclude that an attack on an implementation using random nonces is unlikely, but it cannot be definetly excluded. For safety reasons random nonces should be avoided and a counter should be used.

I have summarized some more considerations on how to use AES-GCM correctly in a blog post.


How is a public key actually used to encrypt something? One thing cryptography articles never seem to explain is how the message actually gets encrypted. You get this long-winded lecture on number theory which ends with, Ta Da! and we have a public and private key. Then, they never explain the process of exactly how some 100,000 byte word document gets encrypted using the public key.

Other times the explanations seem downright misleading. For example, in my book Cryptography (by Meyer and Matyas) it says for RSA the ciphertext is the plain text to the power of key. How do you exponentiate a word document? I don't get it.

Rick Demer already wrote the answer in the very first comment, but without explanation: Hybrid encryption.

But since you asked for a real practical example to encrypt your word document, this is how: Your file is on your disc, and it is 100,000 byte large. You can then do:

First, you start up a random number generator. Preferably you should either have true randomness or at least a cryptographically secure RNG.
Let the RNG generate a random 256 bit number.
Start up your AES 256 engine/program/hardware module, and choose the appropriate mode of operation like CBC. Use the random number as key.
Use AES to encrypt the entire content of the file.
Get your public key or generate private/public key, depending on what you want to do.
Encrypt the random number (used as symmetric key) with your asymmetric encryption scheme. In the case of RSA, do not just use the textbook variant but RSA-OAEP or a similar padding scheme.
Create a new file: Put relevant information in the file header (whatever you want to be accessible without decryption). In the data of the file, write down the encrypted random number (it was encrypted with the public key), and then you just add the entire encrypted file-content (encrypted with AES).
Optional: You can add delimeters inside your file to make it easier to see where the key ends and where the ciphertext starts. If you want you can also note down which algorithms you actually used to encrypt this specific file.

AES can obviously be replaced with any other symmetric cipher, you can also pick a different mode of operation or use a specific asymmetic encryption scheme to encrypt the random key. If you do so, putting it into the file might help if you ever forget which file was encrypted with which algorithm.

Note on using asymmetric encryption directly

It is also possible to use for instance RSA directly on your $100,000$ byte document. If your RSA key is $1240$ bit long, then you can split your document into $800$ blocks with each block having $1000$ bit (or e.g. $650$ blocks of $\approx 1231$ bits, whatever suits you). Then you can apply RSA directly to each block and be done with it. The problem is that this is extremely slow. The ratio of processed bits per second is magnitudes lower for asymmetric encryption than for symmetric encryption. And then you have the problem, that RSA shouldn't be used in the textbook variant and RSA-OAEP increases the length.


MAC security using encryption If a message $M$ contains $n$ message blocks and I XOR the message blocks and encrypt the result using AES, can i use the resulting cipher-text as MAC? is it a good design or bad one?

TL;DR: It is a bad one.

Proof:

Consider a message $m$ such that $m = M_1 || M_2 || \ldots || M_n$ where $||$ is the concatenation and $M_{1..n}$ are of the same size (typically here 128 bits) and let your MAC be
$$
\begin{align}
MAC(M) &= AES( M_1 \oplus M_2 \oplus \ldots \oplus M_n)\\&=
AES(\bigoplus_{i=1}^n M_i)
\end{align}$$.

We have a forgery if we can find $M$ and $M'$ such that $MAC(M) = MAC(M')$.

Consider:
$$M \;= M_1 || M_2 || \ldots || M_n$$
and
$$M' = M'_1 || M'_2 || \ldots || M_n$$
where $M'_1 = M_1 \oplus 1$ and $M'_2 = M_2 \oplus 1$

Thus:
$$
\begin{align}
MAC(M') &= AES( M_1 \oplus 1  \oplus M_2  \oplus 1 \oplus \ldots \oplus M_n)\\
&= AES( M_1 \oplus M_2 \oplus \ldots \oplus M_n)\\
&= MAC(M)
\end{align}$$

With this I created a forgery $M'$ of $M$ which would still have the same MAC. $\square$

Remark:

You don't even need the key used for the AES encryption to create the forgery.


How can I generate large primes for Pedersen commitment? I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and  Information-Theoretic Secure Verifiable Secret Sharing".

To implement the commitment protocol, I need two LARGE primes $q$ and $p$ such that $q \mid (p-1)$. How can one generate such primes?

Note: This is different from generating a safe prime since I'm required to generate a prime with specific characteristics.

You can find two algorithms for generating such $p$ and $q$ in Appendix A.1, FIPS-186-4 (digital signature standard).

edited to add: Essentially, the two algorithms generate a pseudorandom prime number $q$ of the desired size first, then generate a pseudorandom random number $p$ (such that $q|(p-1)$) of the desired size, and test whether $p$ is prime. If so return $(p,q)$ pair, otherwise start over again. The difference between the two algorithms is that the one in A1.1 uses probabilistic primality testing thus returns probable prime numbers and the one in A1.2 returns provable prime numbers. The two algorithms use hash functions as pseudorandom generators so that the seed can be provided for people to verify the numbers are generated pseudorandomly from the seed.


How to calculate end point from private key in elliptic curve cryptography The drawing of lines on the elliptic curve is repeated n times, where n is your private key, resulting in a point Ω. When calculating Ω, is there a short cut function that lets you skip having to actually iterate n times? If not, does not seem that difficult get n by just brute force..

Suppose that I can add two points together. Now, I have a point $G$, and I want to compute 197 times that point $G$. I could do that with 196 additions. But I can also do so much faster:

\begin{eqnarray*}
G + G &=& 2G \\
2G + G &=& 3G \\
3G + 3G &=& 6G \\
6G + 6G &=& 12G \\
12G + 12G &=& 24G \\
24G + 24G &=& 48G \\
48G + G &=& 49G \\
49G + 49G &=& 98G \\
98G + 98G &=& 196G \\
196G + G &=& 197G \\
\end{eqnarray*}
As you see, I computed 197 times the point $G$ in only 10 point additions, which is far cheaper than 196 additions.

This is known as the double-and-add algorithm. The gist is that when you have $nG$ for some integer $n$, then a single addition of $nG$ with itself yields $nG + nG = (2n)G$; and you can also get $(2n+1)G$ with an extra addition with $G$. You can think of the algorithm as maintaining a current point $P = nG$, and step by step altering $n$ so as to reach a given target value; it helps to think of $n$ as an integer in base 2:

Adding $nG$ to itself means multiplying $n$ by $2$, i.e. shifting it one bit to the left, filling the blank with a zero.
Adding $G$ to $(2n)G$ replaces that newly inserted zero with a one.

Thus, the square-and-multiply algorithm simply rebuilds the multiplier bit by bit. This yields a cost of $\log m$ doublings and at most $\log m$ extra additions, to compute $mG$.

There are many possible optimizations (window, NAF, wNAF...) that can be done to save on the extra additions. The baseline cost is that, to multiply by an integer that fits on $k$ bits, you'll need $k-1$ doublings, and some extra additions; the costs of doublings is the dominant one, because the window/NAF optimizations only reduce the number of extra additions.

The same algorithm is known as square-and-multiply in the context of modular exponentiations; it has its own Wikipedia page. This is the same thing, except that point additions become multiplications of integers, and multiplication by an integer becomes exponentiation.


Partial key recovery from linear equations I have searched for my question but I didn't find any relevant answer to my situation. I guess maybe it is too easy but I am a newbie in crypto and I can't figure out the answer.
Here is the exercise:

An attacker mounts a partial key recovery attack on a cipher with a
128-bit key and manages to find a system of $k$ independent linear
equations involving the secret key bits with $k < n$.
For example:
$k_{1} \oplus k_2 \oplus k_{63} = 1$
$k_{1} \oplus k_3 \oplus k_{17} = 1$
$k_{43} \oplus k_{56} \oplus k_{60} = 0$
Does this info
help him to attack the cipher? If yes, what would be the attacker’s
gain over the complexity of an exhaustive search?

I know intuitively that this reduces the complexity because of the common $k_1$ in 2 of the equations and I tried using truth tables for each equation but I can't extract the answer from them. Can anyone explain how is the complexity reduced?

Firstly consider the simple case where we know that there is only a simple x-or relation between two key bits. $k_i \oplus k_j = 1$ and $i \neq j$ and call it $R1$. If we consider the x-or table we will see that only half of the rows for $k_i$ and $k_j$ will satisfies this equation.

\begin{array}{cc|c}
 k_i & k_j & k_i\oplus k_j \\ \hline
 0 & 0 & \color{blue}{0} \\
 0 & 1 & \color{red}{1} \\
 1 & 0 & \color{red}{1} \\
 1 & 1 & \color{blue}{0} \\
\end{array}

An equation with equal to $0$ has the same result, i.e. x-or splits the table into half.

Now, lets look at a key search by brute-force.

   for key in possible_keys
       if ciphertext = Enc(key,m)
            return key

Clearly, this will take $\mathcal{O}(2^n)$-time for n-bit cipher.

Now using the relation update this key search

   for key in possible_keys
       if the key doesn't satisfy R1
           continue
       if ciphertext = Enc(key,m)
            return key

What is the gain here? For half of the keys, the loop will not compute the Enc this means that the keyspace is reduced by one-bit due to the R1.

One might say that we are still looping as the number of all possible keys. The cost of an Enc is not considered in the $\mathcal{O}(2^n)$-time. If you add it then you will see that, you will get an approximately a double speed up. It might possible to design an iterator that only loops valid keys, however, that is a software issue. There is a another approach for this see, below.

A relation having more than two key bits will have the same result. Half of the time we don't need to calculate the Encryption.

If we have more than one relation for the speed up calculation we will use fixing bits by equations. Lets look at your your equations to see this:

  $k_{1} \oplus k_2 \oplus k_{63} = 1$

  $k_{1} \oplus k_3 \oplus k_{17} = 1$

  $k_{43} \oplus k_{56} \oplus k_{60} = 0$

While iterating we if we know $k_1$ and $k_2$ than the value of $k_{63}$ is fixed. Even if one of $k_1$ and $k_2$'s is flipped $k_{63}$ is also flipped. So, you iterate overall, expect the $k_{63}$ since it is fixed. To benefit this you can use a permutation on the keys for better iteration.

Similarly, for your second and third equations. So, you have fixed three keys depending on the relation. This can result in a 3-bit key search advantage. Roughly, we can say, $l$ equations gives $l$-bit advantage.


Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF? Given: F is a pseudorandom function, G is a pseudorandom generator with $l(n) = n+1$. The following schemes should be classified as being insecure, IND-COA secure, IND-CPA secure.

To encrypt $m \in \{0, 1\}^{n+1}$ choose a random $r \leftarrow \{0, 1\}^n$ and output $[r, G(r) \oplus m]$
To encrypt $m \in \{0, 1\}^{n}$ output $m \oplus F_k(0^n)$
To encrypt $m \in \{0, 1\}^{2n}$ choose a random $r \leftarrow \{0, 1\}^n$ and
send $[r, m \oplus (F_k(r) \; | \; F_k(r + 1))]$

My guesses are that:

Insecure, since an attacker A is not only given the ciphertext c, but also the key $r$ with which the message was encrypted. Thus, it can easily decrypt the ciphertext.
I would say that it's not IND-CPA secure, since it's deterministic. But how can I prove/determine whether it's IND-COA secure? I would usually do proof a by contraposition, but I don't know how to start.
I have no idea whether this scheme is IND-COA or IND-CPA secure, since I don't know whether $(F_k(r) \; | \; F_k(r + 1))$ is a pseudorandom function.

Any hints or ideas? I appreciate any help!

This scheme does not have indistinguishable encryptions since the encryption function does not use the key, so an adversary can run the decryption function in the same way as the intended recipient.
This scheme is not CPA-secure because it is deterministic (so it does not even have indistinguishable encryptions for multiple messages). To show that it has indistinguishable encryptions for a single message, we first note that if $f$ is a random function, $f(0^n)$ is uniformly distributed and we get a one-time pad. Now, if a distinguisher $D$ can distinguish $m_0\oplus F_k(0^n)$ from $m_1\oplus F_k(0^n)$, we can distinguish $F_k$ from a random function as follows. A distinguisher $D'$ chooses at random $b\in \{0,1\}$ and runs $D$ on $m_b\oplus O_{D'}(0^n)$. $D'$ outputs $1$ if $D$ answers correctly, and $0$ otherwise. If $O_{D'}$ is a true random function, $D$ answers correctly with probability exactly $1/2$. On the other hand, if $O_{D'}$ is $F_k$ for a uniformly chosen $k$, then by hypothesis $D$ answers correctly with probability non-negligibly higher than $1/2$, which translates to a distinguishing advantage for $D'$.
This scheme is CPA-secure, try to apply the idea of the previous one to transform a distinguisher for the encryption scheme into a distinguisher for $F$.


Understanding Public key and Private key I try to understand the private and the public key concept, and need some validation about my statements:

If I encrypt a message with public key, I can only decrypt with private key.
If I encrypt a message with private key, I can only decrypt with public key.
I can generate public key (derived key) from private key(base key).
I can not generate private key from public key.
Private key name comes how I handle the key: I keep it in secret, so I call it private key.
Public key name comes how handle the key: I publish it, anybody can use it, so this is the public key.
If I publish the base key, I can call it public key
If I keep in secret the derived key, I can call it private key.

If I encrypt a message with public key, I can only decrypt with private key.

True, except that public/private keys must match, and there might be several equivalent private keys (as in many definitions of RSA). We should thus say:

In a secure asymmetric encryption system, a message encrypted with a public key can only be decrypted with a matching private key.

  If I encrypt a message with private key, I can only decrypt with public key.

Encrypt with private key and decrypt with public key is infeasible in many cryptosystems, including those based on the Discrete Logarithm Problem, where public and private keys are fundamentally different. Encrypt with private key is also impossible in many implementations of RSA, and with many asymmetric encryption programs like PGP/GPG.

In an RSA encryption system, it is indeed can be mathematically defined how to to apply the encryption operation with the public exponent $e$ in the public key $(N,e)$ replaced by the private exponent $d$ from the private key. But if this heresy is performed, then anybody can decrypt with the original public key (which is public, see 6), and that goes against the primary goal of encryption. Don't do that.

In cryptosystems that perform signature rather than encryption, it is possible to sign a message with the private key, but that's not encryption. RSA can do both signature and encryption, but usual secure RSA-based signature and encryption cryptosystems have more differences than exchanging the role of public and private key.

  I can generate public key (derived key) from private key (base key).

Not in general. Cryptosystems based on the DLP indeed derive the public key from the private key (and the definition of the group, either public and fixed, or part of the private key). But that applies less to RSA.

In RSA as in the original article, the private key can be considered to be $(N,d)$, where $d$ is chosen essentially at random. It is impossible to find the public key $(N,e)$ from the private key $(N,d)$ alone (for proper choice of $N$): it is also needed the factors of $N$, which are not necessarily part of the private key.
In modern RSA, it is typically first chosen a small public exponent $e$, then drawn secret random prime factors $p,q$, forming $N=p\,q$, with $(N,e)$ the public key. Only then is the private exponent $d$ and the rest of the private key derived from $e,p,q$. So part of the private key is derived from data including a part of the public key.

What always holds it that a public/private key pair is derived from secret base data (output by a Random Number Generator), but the details of that derivation depend on the cryptosystem.

  I can not generate private key from public key.

True. Generating a private key matching a given public key would be a total break of any asymmetric cryptosystem.

  Private key name comes (from) how I handle the key: I keep it in secret, so I call it private key.

True. Notice that secret key is preferably reserved to symmetric cryptography, where the secret key is shared between cooperating parties; and private key is used for asymmetric cryptography, and assumed a secret that is not shared with anyone unless otherwise specified.

  Public key name comes (from) how (I) handle the key: I publish it, anybody can use it, so this is the public key.

True. There typically are additional differences beyond naming. That's the case with DLP, and often in RSA.

  If I publish the base key, I can call it public key.

No. The base key should not be published, if the base key is the private key, or is the secret base data that was used to generate a public/private key pair. Doing so would make the key pair useless, by revealing the private key matching the public key. Private keys must be kept secret, because knowledge of a private key allows to decipher, or forge signature.

  If I keep in secret the derived key, I can call it private key.

Not in general. In particular, not with DLP, where the "derived key" is bound to be the public key.


What will browser show when a user access website and website present certificate of some other domain with same top level domain For example, User tries to access a.example.com and server presents abc.example.com with a.example.com not in SANs list.
Will it be just a warning or an error?

A well designed browser should display a warning page whenever there is a problem with a certificate for the asked paged.

Firefox and Chrome will provide a way to manually bypass the page.


Relation between decisional SIS and leftover hash lemma in lattices The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\in \mathbb{Z}_q^{(n+1)\times m}$ and uniformly random $x \in \{0,1 \}^m$, the term $Ax\in \mathbb{Z}_q^{n+1}$ is close to uniform.

Now, I'm a little confused. I see no difference between this lemma and the hardness of decisional SIS problem. I think the condition on $m$ is also for being able to guarantee the existence of a solution for the corresponding SIS problem (and so having the right version of this problem).

Can someone explain this?

The leftover hash lemma (LHL) says that $(A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)}$ is very close to uniformly random.  In particular, this implies that for uniformly random $(A,u)$, there exists a solution $x \in \{0,1\}^m$ to $Ax=u$ with very high probability.  For if not, a significant fraction of $u$ values would admit no solution, hence the distribution of $Ax$ would not be close to uniform, because it never produces any of those $u$ values.  (In fact, most $u$ will typically have many solutions.)

All the above is unconditional---we're not relying on any assumptions about whether a problem is hard or not, we're just making statements about probability.

The "decisional SIS problem" is not a standard concept, because it's not so meaningful.  If one were to define it, the problem would ask to distinguish between $(A,u=Ax)$ and uniformly random $(A,u)$.  But by the above we know that's just impossible: the two distributions are very close, so they can't be told apart.

The computational SIS problem (in its inhomogeneous version) asks, given uniformly random $(A,u)$, to find some short (e.g., binary) $x$ such that $Ax=u$.  Again, the choice of $m$ is such that solution(s) exist with very high probability; the computational question is whether we can efficiently find a solution.

The SIS problem is believed to be hard, thanks to much supporting evidence (e.g., reductions from worst-case lattice problems). However, we can't rule out the possibility that SIS actually is easy, but we just haven't yet found an efficient algorithm to solve it.  Yet even if SIS were easy, that would not contradict any of the above probability statements; it would just mean that we can efficiently find a solution among the several that are likely to exist.


KDFs for symmetric encryption master key & serial number Let's assume that I generate a high entropy AES master key (through /dev/random for example) and I want to derive it with a fixed-length serial number (12345 for instance).
The derived key is used to encrypt and authenticate files that can be read by a specific device only (with said serial number). Therefore, to create files for that device, only the master key and the serial number would be required.
Which KDFs would you recommend for that scenario?
Thanks!

Any standard key derivation function should do.

There are, in general terms, two kinds of KDFs: those that are meant for deriving keys from (potentially) low-entropy passwords, and are thus designed to be deliberately slow (key stretching), and those that are meant for deriving keys from a high-entropy master key / secret, and so can be made much faster.  Your use case falls into the latter category.

One example of a non-key-stretching KDF you could use is HKDF, a nice and versatile KDF based on a cryptographic hash function (used in the HMAC construction).  HKDF is an "extract and expand" KDF, where the output keys are derived in two steps:

in the extraction phase, the master key and an optional non-secret "salt" are used to derive an intermediate "pseudorandom key" (PRK), whose size is determined by the output length of the hash function used; and
in the expansion phase, the pseudorandom key computed in the extraction phase is combined with an optional "info" string to derive one or more output keys of arbitrary length.

In situations (like yours) where the master key is already a uniformly random bitstring, the HKDF standard allows the extraction phase to be skipped, and the master key to be used directly as the pseudorandom key.  Thus, you could simply skip the HKDF extraction phase, and use the device ID as (one part of) the "info" parameter to HKDF-Expand.

Alternatively, e.g. if you wish to derive multiple keys for each device (say, an encryption key and a message authentication key), you could use the device ID as the non-secret "salt" in the HKDF-Extract stage to obtain a device-specific PRK, and then derive the actual device keys from this PRK using HKDF-Expand.

HKDF requires you to choose an underlying hash function to use.  Basically any secure cryptographic hash would do, but Richie Frame's suggestion to use SHA-512 seems fine to me, and at least ensures that the size of the PRK will not be a security bottleneck.

Finally, let me briefly note that the general extract-and-expand construction use in HKDF could also be instantiated with some pseudorandom function other than HMAC; some possible variants are mentioned in the HKDF paper (Krawczyk, 2010).


Private Key - Memory Lifecycle I often heard about private key storage, but rarely about key life cycle in memory.

For example, when SSL is used from one peer, the private key is used to sign messages or decrypt other peers' messages, so it has to be in memory as long as the http process goes on.

It may raise some security issues that clear private key is in memory for days and days ?
Is that right or I missed something (master key, ...) ?

Short answer, before someone marks this as a duplicate or answers it with an essay or something:

You're exactly right. This was one of the biggest consequences of the infamous Heartbleed exploit in OpenSSL, which exposed the memory of processes using OpenSSL for TLS to anyone with an Internet connection. It's also significant for cold boot attacks, where someone with physical access to a computer shuts it down and boots a live CD or rips out the RAM and reads it before it loses all charge (moments, normally; much longer with enough refrigerant).

There are mitigations, including storing your keys in a hardware security module (HSM), a physical device designed to be difficult to attack. If your protocol uses forward secrecy -- such as TLS with DHE or ECDHE cipher suites -- new encryption keys are generated for each connection and thrown away relatively quickly (if they're properly erased from RAM, and not counting session caching and resumption mechanisms). In that case, your long-term RSA key would only be used for signatures. Exposing it would allow you to be impersonated and facilitate future MITM attacks, but would not allow decryption of past communications.


Public-key based on roots of polynomial In general it's hard to calculate the roots of a given polynomial $P(x)$.
But the other way back calculating the coefficients is much easier (Vieta's formulas).

If this is a one-way function, is it possible to create a public-key cryptosystem
based on these facts? Or does it already exist?

First, note that having a one-way function is far from enough to construct a public-key encryption scheme (a famous result of Impagliazzo and Rudich actually shows that it is impossible to construct public key schemes from one way functions only).

Second, cryptographic constructions which aim at being implemented at some point rely on the hardness of problems over finite sets in general (this is a vague statement, but quite intuitive). Over finite fields, finding roots of a univariate polynomial is easy.

However, a problem related to what you ask about is that of the difficulty of solving systems of equations of multivariate polynomials. This problem is hard (it is even NP-hard) and was used as the underlying cryptographic assumption for the construction of public key cryptosystems and signatures schemes. Unfortunately, no public key cryptosystem built on such assumption has survived cryptanalysis (to my knowledge); every attempt was proven insecure at some point (this is not true, however, for signature schemes).

Hence, even though it might be possible to construct public key cryptosystem based on problems related to finding roots of (multivariate) polynomials, this has proven to be at least a very hard task. See e.g. the Wikipedia article on Multivariate cryptography for more details on the topic.


For security, need a 1-1 crypto-mapping be NP-complete? The book Foundations of Cryptography states:

  It was understood that problems related to breaking a 1-1 cryptographic mapping could not be NP-complete and, more important, that NP-hardness of the breaking task was poor evidence for cryptographic security.

But I thought the whole point of complexity theory was to determine which problems were NP so that we might be able to use the infeasibility of their solutions to produce security?

NP is about worst case hardness. An NP-hard problem can in fact be very easy to solve for the majority of cases. This would obviously be a poor cryptographic system. Further, some NP-hard problems may even be quite easy to approximate. This could also be bad for cryptography.


Difference between using Schnorr Protocol and just compare hash function to prove knowing something? I am studying the Schnorr Protocol, and I just come up a case.
For example, I am a Prover and have a secret $x$. By using the Schnorr Protocol, I create $h=g^x \bmod p$ and save $h$ to a public place.
When a Verifier needs to prove to the Prover,

Prover sends a commitment to verifier $c = g^r \bmod p$ where $r$ is a random value
Verifier sends a challenge to prover $t$ is a random value
prover sends a response to verifier $s = r + t\,x$
verifier accepts iff  $g^s \bmod p= c\,h^t\bmod p$

What is the difference if I store a hashed value for example $h = \operatorname{sha512}(x)$ to a public place, and if prover want to prove he know secret $x$, he just need to send $h'$ to verifier and verifier compare if $h = h'$ stand.
I know that a dishonest prover can send the hash to the verifier directly to fool the verifier. Apart from this, is there any difference? It seems that using a hash can still prove the prover knows secret $x$.

The question does not correctly describe the Schnorr protocol. Here it is (with restriction to a multiplicative subgroup of $\Bbb Z_p^*$, because that's in the question).

It is chosen a large prime $q$ (e.g. $>\approx 2^{512}$) and a larger prime $p$ (e.g. $>\approx 2^{8192}$) with $p=2\,a\,q+1$ for some integer $a\ge1$ (with $p$ not of a special form facilitating SNFS), and an integer $g$ of order $q$, that is with $g^q\bmod p=1$ and $g\bmod p\ne1$ (one such $g$ is $4^a\bmod p$). Parameters $p$, $q$, $g$ are public.

A random secret $x\in[0,q)$ is known to a Prover, who publishes $h=g^x\bmod p$. The above choice of parameters $p$, $q$, $g$ is such that the Discrete Logarithm Problem of finding $x$ given $h$ is believed hard.

The protocol's goal is that a verifier gets rightly convinced that a party knowing $x$ with $h=g^x\bmod p$ participates in the protocol, without revealing $x$ to the prover or to adversaries, including active (in particular, adversaries are able to impersonate the prover w.r.t. the verifier, and vice versa). Towards this:

Prover draws a random value $r\in[0,q)$ and sends commitment $c=g^r\bmod p$
Verifier draws a random value $t\in[0,q)$ and sends that challenge to prover.
Prover computes and sends response $s=r+t\,x\bmod q$
Verifier is content that prover knows $x$ iff $g^s\bmod p=c\,h^t\bmod p$

That equality normally holds because $s=r+t\,x\bmod q$ implies that $\exists k,\ s+k\,q=r+t\,x$ therefore $g^s\equiv g^{r+t\,x-k\,q}\equiv g^r\,g^{t\,x}\,g^{-k\,q}\equiv c\,(g^x)^t\,(g^q)^{-k}\equiv c\,h^t\,1^{-k}\equiv c\,h^t\pmod p$.

It can be shown that breaking this protocol is equivalent to solving the DLP.

  What is the difference if I store a hashed value for example $h=\operatorname{SHA-512}(x)$ to a public place, and if prover wants to prove he knows secret $x$, he just need to send $h'$ to verifier and verifier compare if $h=h'$ stands.

The proposed protocol fails to prove to the verifier that another party knowing $x$ participates in the protocol. Argument: since $h$ is in a public place, an adversary not knowing $x$ can get $h$, send that as $h'$ like the prover knowing $x$ is supposed to do, and thus pass the verifier's test.

If prover and verifier both know $x$, a solution is possible using $\operatorname{SHA-512}$ in a challenge-response protocol: verifier draws and sends random $t$, prover computes and sends $s=\operatorname{SHA-512}(t\mathbin\|x)$, verifier checks $s=\operatorname{SHA-512}(t\mathbin\|x)$.

The advantage of Schnorr's protocol is to achieve the same goal without requiring the verifier to know $x$. In particular, in the MAC-based protocol, the verifier must keep $x$ secret, which is hard even for an honest verifier, and is not necessary with Schnorr's protocol.


SIKE as Diffie-Hellman exchange SIKE involves a Diffie-Hellman like construction using isogenies between elliptic curves. Is it possible to express it as an instance of Diffie-Hellman? I.e. what is the underlying group if so, and further, why wouldn't Shor's algorithm apply and render it vulnerable?

I am one of the inventors of SIKE.

There is no actual Diffie-Hellman group in SIKE. If there were, then SIKE would be vulnerable to Shor's algorithm, as you said, largely defeating the purpose of a post-quantum cryptosystem.

Among other reasons, isogenies typically have a domain different from their codomain, so an isogeny cannot be iterated. You can compose two different isogenies (provided that their respective domains and codomains are compatible), but usually not an isogeny with itself.


Security issues of a MAC-then-Encrypt-then-MAC approach? Encrypt-then-MAC does provide ciphertext integrity, but no plaintext integrity. With MAC-then-Encrypt it’s the other way around: Plaintext integrity but no ciphertext integrity.

What comes to mind is that it could make sense to use both to fix that “partially missing integrity” issue:

$$\tt …\ MAC_2(ENCRYPT(plaintext,MAC_1(plaintext)))$$

Trying to research if this would introduce more problems instead of solving them, I wasn’t able to find any useful papers that provide a security analysis of this approach. Also, I wasn’t able to find any papers discussing related schemes.

Ignoring potential speed impacts and focusing strictly on the security aspects… is there any obvious reason I’m not seeing why such a scheme should not be considered in the first place? Or do related references/papers exist and I was simply too inapt to find them? (If, what should I be looking for?)

EDIT:
As some confusion was expressed in the comment area – please note that the above LaTeX merely represents a readable hint at what I’m talking about. It is not meant to describe a whole formula (which I assumed be clear due to the prepended “$…$” and the fact that there is no $key$ in the above LaTeX either). The reason to prefer posting a hint instead of a complete formula was simple: the complete formula renders/formats much less readable and could have confused some people – which I wanted to prevent. Obviously, “what is less confusing to some, is more confusing to others”. That’s something I honestly hadn’t anticipated…  my bad. Here’s the whole thing:
$$CypherText = IV || Encrypt(PlainText || MAC_1(PlainText, MacKey_1), IV, CipherKey) || \\
MAC_2(IV || Encrypt(PlainText || MAC_1(PlainText, MacKey_1), IV, CipherKey), MacKey_2)$$
Don’t even ask how this would look if I wouldn’t be using a <sub> tag… yet, it may help understand why I opted-in to posting a hint.

Using a MAC on the plaintext may potentially leak information about the plaintext (MAC algorithms do not necessarily ensure confidentiality of the data they are applied to, although some MAC algorithms like HMAC seem pretty safe). If you want to avoid this (theoretical) problem, then you should encrypt the MAC on the plaintext (i.e. MAC-then-encrypt, not MAC-and-encrypt).

As long as you encrypt the inner MAC along with the plaintext, and the key for the inner MAC is unrelated to the key for encryption, then it is "obvious" that this inner MAC does not induce extra trouble; that inner MAC can be viewed as some plaintext redundancy. (In fact, you could replace the inner MAC with a simple hash function.)

Having two MAC algorithms still seems wasteful, in CPU and data size. If the problem you are trying to fix is a wrong decryption key in an encrypt-then-MAC setup, then a more efficient solution is to derive the encryption key and the MAC key from a single master key, using a KDF. If you do that, then, when the MAC matches, you know that you used the right MAC key, and, by property of the KDF, you also know that the encryption key is the right one. It so happens that deriving encryption and MAC key from a single source with a KDF is a very common situation; so the problem of "lack of plaintext integrity" does not happen in practice. This is why the construction with two MAC you are alluding to does not appear to be much studied.


Difficulty of Reversing Elliptic Curve In ECC, it is apparently easy to verify the final point given the starting point and the number of hops. But it is difficult to compute the number of hops given just the starting point and the final point.

Can anyone explain in regular English why this is the case (no intense math, please).

From my understanding, hopping along the curve is analogous to addition, and thus the iterative hopping is analogous to multiplication. I've read that the reason it's faster to compute the final point given the number of hops is that we can use exponentiation by squaring to make logN computations as opposed to N.

My question is this: wouldn't there still be a large number of points to hop in between two squares?

E.g. if the number of hops is 1524, then we would compute 2, 4, 8, 16, ..., 512, 1024 — but then we'd still need to do 500 hops after getting to 1024. Or would we use squaring again to get from 1024 to 1524?

On an elliptic curve as used in crypto, we can add any two points $P$ and $Q$ of the elliptic curve, yielding a new point of the elliptic curve: $X\gets P+Q$. It holds $(P+Q)+R=P+(Q+R)$, making $P+Q+R$ unambiguous.

For any integer $k>0$ and point $P$, that lets us define $k$ times $P$, noted e.g. $k\times P$, as the result obtained by adding $k$ copies of $P$, that is $k\times P\;\underset{\text{def}}=\;\underbrace{P+\ldots+P}_{k\text{ times}}$

We can efficiently compute $k\times P$ per the following (recursive) method:

if $k=1$ then return $P$
otherwise, if $k$ is even, compute $Q=(k/2)\times P$ and return $Q+Q$
otherwise, compute $Q=(k-1)\times P$ and return $Q+P$

This efficient computation method for $k\times P$ takes time proportional to the number of bits in $k$, whereas applying the definition would take time proportional to $k$. The $k$ used in crypto are often about $2^{256}$, which is many times the conjectured number of atoms in the universe, but the computation still takes a fraction of a second with the efficient method.

Now, consider the problem of finding $k>0$ such that $Q=k\times P$, given $P$ and $Q$. A basic method is to start from $P$ and, while $Q$ is not reached, add $P$. The desired $k$ is one more than the number of additions made. Problem is, that takes time proportional to $k$.

We know better methods that take time proportional to $\sqrt k$. The main ones are baby step/giant step¹ and Pollard's rho². But when $k$ is about $2^{256}$, $\sqrt k$ is about $2^{128}$, and we can't even count to that number: collectively, all the computing devices ever made by man did not count to that, much less made that number of elliptic curve operations.

We know³ no better method than those requiring time proportional to $\sqrt k$, and that explains the difficulty of reversing multiplication on an elliptic curve with the parameters used in cryptography.

Extra meat for thought:

¹ Baby step/giant step works as follows:

chose an $l$ large enough that we'll have $k\le l^2$
store the point $Q_0\gets Q$
for $i$ from $1$ to $l-1$

compute and store the point $Q_i\gets Q_{i-1}+P$ (these are the baby steps)

compute the point $R\gets l\times P$
initialize the point $S\gets R$
for $j$ from $1$ to $l$

search $S$ among the $Q_i$ (this can be done without scanning all the $Q_i$, much like we can find a book in a library), and if there's a match

compute and output $k\gets j\,l-i$, done!

update the point $S\gets S+R$ (these are the giant steps)

² Pollard's rho replaces the systematic search of baby step/giant step¹ by a pseudo-random walk, and replaces the impractically large array $Q_i$ by a detection that the walk goes along an already explored path. The point where the paths merge yields the solution.

³ Q: But why can't we find a better method, when we have efficient methods to solve the similar problem of finding $k>0$ such that $v=k\times u$ given ordinary integers $u$ and $v$ ? $k$ is the quotient of $v$ divided by $u$ in Euclidean division, and that's feasible for numbers with million bits.
A: Euclidean division relies on comparing integers and finding the smallest, for a definition of smallest compatible with addition, in the sense that if $a<b$, then $a+b<a+c$. But there can't be any such notion of order on a large but finite set like an elliptic curve as used in crypto, hence Euclidean division won't cut it⁴.

⁴ Q: But that argument does not hold water! We have efficient methods to solve the similar problem of finding $k>0$ such that $v=k\times u$ given $u$ and $v$ when working in some large but finite sets. For example, in arithmetic modulo $p$, there's a systematic method published in 1621 by Bachet, using an extension of the so-called Euclidean algorithm, which uses Euclidean division.
A: This does not cut it either, but for a different reason: in arithmetic modulo $p$ and all cases where similar methods are known, it is relied not only on addition of elements $a$, $b$, $c$ of the set, but also on multiplying them in a way compatible with the premise that $a\,(b+c)=a\,b+a\,c$ . When in elliptic curve arithmetic we can add points, but not meaningfully multiply them together.


Is there a length-preserving encryption scheme? Is there a length-preserving encryption scheme, that preserves the lengths of input sizes such that the length of the input plain text is same as length of the output cipher text ?

As @fgrieu mentioned, what you're after is FPE. The papers he linked deal with FPE on a very small domain, but it looks like you're interested in encrypting longer strings.

For that, you need a wide block cipher. Unlike traditional blockciphers, these typically allow different input lengths, which is a plus. They meet your criterion of not revealing shared prefixes/suffixes. Examples (any of which will be secure): EME, EME2, HCTR, HEH, TET, PEP. Tracking down a good implementation might be problematic; I don't know any off-hand. Some, including EME/EME2, are patented (but can be licenced under "reasonable, non-discriminatory" terms). Depending on the mode, they operate at roughly half the speed of standard encryption algorithms.

In terms of providing confidentiality, a result by Bellare and Rogaway ("Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography") shows that you get it for free as long as you can guarantee that all plantexts are distinct (e.g., they already have distinct sequence numbers encoded into them somehow). The only information these ciphers leak is plaintext length, and whether or not a plaintext is repeated.

You said authenticity was not a concern, but perhaps it's worth noting that you can get this fairly cheaply if the plaintext contains some type of redundancy that you check upon decryption.

Finally, these algorithms are tweakable ciphers, which means the take an additional input, called the tweak. You can use (meta)data from any accompanying headers as the tweak (or just used a fixed string). Again, if the tweak is distinct each time, then you have confidentiality even if a plaintext is repeated. But at that point it might be easier to, e.g., take a 64-bit nonce from the headers and use that as the high-order bits of a counter-mode IV.


Having trouble understanding reduction functions in rainbow tables I'm continuing doing some personal research on rainbow tables, but forsome reason I cannot understand how to choose the correct reduction function. Wikipedia states that

"Only when the attacker has a good idea of what the likely plaintexts will be they can choose a function R that makes sure time and space are only used for likely plaintexts, not the entire space of possible passwords."

In this case, how can a reduction function like taking the last 6 characters of a hash as a reduction function serve in a rainbow table trying to find a password such as Password123? It would be really helpful if someone would explain this for me. Thanks

In this case, how can a reduction function like taking the last 6 characters of a hash as a reduction function serve in a rainbow table trying to find a password such as Password123?

It can't. Assuming the reduction function takes the last six bytes of output it can only be used to generate passwords up to 6 (ASCII) characters long.

To crack any password up to 6 characters long you need to precompute a number of hashes on the order of $256^{6}$. That takes more space/time than is actually needed. If you don't target passwords that use non-ASCII or non-printble ASCII characters then you can reduce $256^6$ to about $95^6$. ($95$ being the number of "printable" characters.)

So then you substitute your reduction function that simply reinterprets binary data, substituting 6 bytes of hash output for a six character long string, with a more complex function. You can convert the bytes of output to a base 95 number, then create an ASCII string where each value 0 through 95 corresponds to one of the printable ASCII characters.

You don't want to use the first reduction function because it creates unlikely passwords. No ASCII string with any character in the range [0, 31] or [127, 255] is likely to be a real world password, so your rainbow table will be inefficient if you use this reduction function.

The base-95 example I gave is one reduction function that improves efficiency because it avoids characters from these two ranges. For six bytes of hash output you could actually generate 7 character long passwords. (Because $\log_{95} (256^6) \approx 7.30$)

More efficient reduction functions could be used but they would need to be more complex. Maybe you want to rule out candidate passwords that have 4 or more of the same letter in a row unless it's in the form "aaaa.....a" or "aaaa...123". Then you have to make assumptions about what is considered a "likely" password in the real world and then you need to find a way to implement it efficiently.

There are tradeoffs to such choices. If you omit a string from the set of possible outputs that a reduction function can produce then your rainbow table can not crack those passwords if they're used in the real world. If the reduction function can't produce a string then the rainbow table can't crack that password.

You can crack a larger set of potential passwords by increasing the amount of bits your reduction function uses. In the naive implementation you can crack passwords up to six characters long if you use six bytes. Or seven characters if you use seven bytes. And so on.

But when you grow that password set you also need to do more precomputation (and us more time and/or memory during querying). In practice you get diminishing returns by using more and more bytes.

If you don't do precomputation work proportional to the entire then your table will only cover a fraction of all possible passwords. If your password set is $X$ elements large and you do $X \over 2$ work then less than half of those candidate passwords will actually be covered by a rainbow table.

A larger candidate password set size means you need to do more hashing, even for rainbow tables. Rainbow tables are not effective for targeting long low-entropy passwords. Instead dictionary based cracking and rule-based-brute-force cracking is used.

Rainbow tables are not the go-to algorithm for password cracking anymore. It is a precomputation-based cracking method. Any precomputation method for sound password hashes using cryptographic hash algorithms can easily be made ineffective by using a unique (per-password) random salt.

Today, people attempt to crack correctly hashed passwords by using brute force methods that run in parallel. GPUs differ from CPU hardware in that they do identical operations in parallel. GPUs have many more (simpler) cores than CPUs have, so the are better at doing certain tasks in parallel.

Rainbow tables aren't so important anymore where proper password hashing (with salts) is used. And they never really worked very well for long passwords.


Verification of HMAC in libsodium libsodium verifies that the HMAC is correct with the following code:

return crypto_verify_32(h, correct) | (-(h == correct)) | sodium_memcmp(correct, h, 32);

where crypto_verify_32 is

for (i = 0; i < n; i++) {
    d |= x[i] ^ y[i];
}
return (1 & ((d - 1) >> 8)) - 1;

and sodium_memcmp is

for (i = 0U; i < len; i++) {
    d |= b1[i] ^ b2[i];
}
return (1 & ((d - 1) >> 8)) - 1;

Why not using a simple memcmp?

memcmp() is not constant-time. The property called "constant-time" does not mean (confusingly) that every runs in a constant amount of time; an algorithm implementation is said to be "constant-time" if it does not leak information about secret data through timing-based side channels.

In the case of memcmp(), the leak is simple: memcmp() looks at bytes in increasing address order, and stops at the first index where bytes differ. Thus, the execution time, and the memory access pattern, if observed by attackers, may reveal how many bytes are identical. If the attacker can repeat the experiment with various purported "HMAC" values, he can use that leak to learn the complete true HMAC value, which can be a very bad thing in some contexts.

For more on the subject, see this page in BearSSL documentation.


How to design a secure challange-response authentication protocol? I am implementing a custom challenge-response protocol to authenticate a client to a server. Mutual authentication is not required, i.e. the server doesn't need to be authenticated to the client.

The protocol works over TCP. Client and server are in a LAN (not over the internet). There is only one server and only one client. The authentication is designed as follows:

$S \rightarrow C : N$

$C \rightarrow S : \{N\}_K$

Where the server $S$ creates a 128-bit random number and sends it as nonce $N$ to the client $C$. The client encrypts the nonce with AES-192 with the pre-shared key $K$ and sends it as response to the server. Then the server decrypts the message and checks the nonce.

Questions:

Is this protocol design secure?
What would be the advantage to use HMAC (or any other MAC) instead of AES encryption?
Did I miss something?

Is this protocol design secure?

See below.

  What would be the advantage to use HMAC (or any other MAC) instead of AES encryption?

HMAC was originally proposed as a construct that turns a Merkle-Damgaard hash function based on compression functions built from block ciphers, into a message authentication code. Although there's no decryption in HMAC, you can actually easily replace your AES decryption-based authentication with comparing HMAC-signed tags.

  Did I miss something?

What you're doing is essentially an authenticated security transport without confidentiality.

What you're missing is that you didn't authenticate the exchange following the initial authentication - this allows for connection hijacking, arbitrary injection of data packets, and more.

Therefore, you should use HMAC+[hash] or CMAC+[block cipher] to authenticate all of your messages exchanged, and also keep a counter as a state to detect duplicate packets and message replay attackes.


Is it generally considered acceptable for app owners to be able to retrieve private keys from users when their apps offer end-to-end encryption? E2EE promises that data sending between two endpoints can be decrypted by only those two endpoints. If an app offers E2EE but still has functions to retrieve private keys from users for any purposes such as for multi-device sync, is that considered acceptable as the app owner can get the private keys from the users and decrypt user messages when they need as the app resides on the user devices has the functions for retrieving user private key which could be invoked for other purposes such as for legal execution ?

If you define E2EE as the promise "that data sending between two endpoints can be decrypted by only those two endpoints", then by definition, if the app owner can decrypt, what you have is not E2EE and you shouldn't advertise it as such.


Pedersen commitments, what happens if I choose $H$ such that $H = a\times G$? For Pedersen commitments of the form $C = x\times G + r\times H$, what is the worst thing I can do if I already know $H$ such that $H = a\times G$ ?

For standard curves, there are specifications for what value of $G$ should be used. Is there any such specification for values of $H$ ? What is the worst an adversary can do when they choose $H = a\times G$ and the rest of the world assumes that no-one knows a relation between $H$ and $G$ ?

If the committer knows $a$, then it is no longer binding.

For any $m$ you commit, the commitment will be $(m+a)G$, so it is easy to find $m'$ and $a'$ such that $m'+a'=m+a$ to open the commitment.

Edit to add:
If the receiver knows $a$, then it is still information theoratically hiding because the sender chooses $r$ which is uniformly random.


Discussion about the importance of communication complexity for MPC? Communication complexity is generally discussed among many papers on secure multi-party computation (MPC).
However, I do not still understand the importance of it.

What communication complexity affects is total computation time in a protocol depending on available bandwidth rate (10Mbps, 1Gbps, etc).

Is the communication complexity really important?
When is it captured as primary result of some paper?

With a specific programming implementation detail, I can understand the total execution time including data transmission during the protocol. But from the communication complexity (even if some paper reduced it significantly compared with prior works), I wonder when and why it makes sense.

What is the advantage of reducing communication cost (in general at the expense of computation time on some nodes) in practice?

It's safe to say that any Cryptographer would want his/her protocol to be implemented and used by the public. Ideas in MPC have been floating around for quite some time now and have been proven to be theoretically sound. The challenge now is to make them efficient enough that it is feasible to use them in practice. In the domain of MPC, sizes of the messages blow up very easily in most protocols as you may have already noticed.

Given that in most situations the network speed is a bottle neck compared to local execution times, it becomes very important to reduce communication complexity if one is serious about implementing the protocol.


Use AES-256 Or AES-CTR-256 For One Block? I am have one block of data to encrypt that is 32-bytes long. Is it better to use the AES-256 primitive for this single block (not a stream) or AES-256-CTR, and also would there be any cons or pros to using one and not the other such as to security or something else I am not thinking about.

This question relates to this question: AES-CTR-256 Sub Keys With Encrypted Sub Key Index

In relation I was wondering if I should just use the AES-256 to encrypt the sub-key with the master key instead of using the nonce and XOR operation, or maybe it would be better to use AES-256-CTR and use a nonce for the master key prefixed to the file.

Like said in the comments, a 256-bit message is two blocks of AES, no matter the keysize.

The main issue with ECB mode (i.e. using AES directly on 128-bit blocks) is that you leak whether two blocks are equal. When encrypting perfectly random data, that means there's a $2^{-128}$ chance the two parts of the key are equal, and the attacker knows that. The probability you see a collision between halves of any two keys becomes significant once you reach about $2^{63}$ keys, but that probably doesn't help the attacker much unless he knows one of the keys already.

In contrast, with CTR mode the chance that you get two equal ciphertext blocks is the same, but that only leaks the fact that the two halves are not equal, which helps the attacker a minuscule amount – and is always leaked by ECB. So CTR is obviously better. (Assuming you can ensure unique nonces.)

However, lets get realistic. In CBC mode, with random and unequal IVs, the attacker could instead learn the XOR of two key blocks with the same probabilities as above. Knowing that helps an attacker about as much as knowing an equality. Yet, we consider CBC a secure enough mode to use.

So I wouldn't really worry about it, but if you can easily use CTR it only costs you the IV storage. Even 128-bit keys would be secure, though.

Note: The above is only the case when you encrypt purely random data. With non-random data ECB is almost always broken. The above also assumes the attacker can't get a chosen plaintext encrypted or anything similar.


I'm curious on methods of encrypting files using C++ I'm making a personal security tool in C++ and was curious how I would go about encrypting files in C++. If anyone has a method that would be great, and more specifically I was interested in 3DES encryption.

3DES is an old and slow cipher.
In 2019, it is probably a bad idea to build new applications based on this algorithm.

Choosing a cipher, is not the only thing that matter in cryptography.
You need a mode of operation like CBC or GCM to specify how to combine encryption function on long messages.
If you don't use AEAD modes, you probably need a MAC construction to protect ciphertexts from malleability.

Choosing all theses things in a secure way is difficult.
That's why, your best option is to use a library that provide a secure API for encryption.
Libsodium is a mature example of such library and the crypto_secretbox_* functions are probably what you need.
They are based on XSalsa20+Poly1305 construction.


How to use CRT to compute 4 square roots while decryption in Rabin Cryptosystem I'm reading Rabin Cryptosystem which requires to compute 4 square roots $r, -r, s,- s$ while decryption of cipher text $c$ such that

$$r = (y_p \times p \times m_q + y_q \times q \times m_p) \mod n $$
$$-r = n - r $$
$$s = (y_p \times p \times m_q - y_q \times q \times m_p) \mod n $$
$$-s = n - s $$

$m_p = c^{\frac{1}{4}(p+1)} \mod p; \, \,m_q = c^{\frac{1}{4}(q+1)} \mod q; \, \, y_p \times p + y_q \times q = 1$

I'm not getting, how we can compute $r, -r, s,- s$ using Chinese Remainder Theorem.

As first step to compute the four square roots of $c \pmod N$ one can compute the two square roots $\mod p$ and the two square roots $\mod q$ and then using the Chinese Reminder Theorem combine them to the four square roots $\mod N$ where $N = p \cdot q$.

Let's start computing the square root of ciphertext $c \mod p$.
Usually $p \equiv q \equiv 3 \pmod 4$.
So $m_p = c^{\frac{1}{4}(p+1)} \pmod p$.

Proof: $m_p^2 = c^{2\cdot\frac{1}{4}(p+1)}= c{\frac{1}{2}(p+1)} = c \cdot c^{\frac{p-1}{2}} = c \left( \frac{c}{p}\right) = c \pmod p$, because $c^{\frac{p-1}{2}} = \left( \frac{c}{p}\right) = 1 \pmod p$, where $\left( \frac{c}{p}\right)$ is the Legendre Symbol of $c \mod p$ and $c$ is a square (so the symbol is equal to 1).

Similarly: $m_q = c^{\frac{1}{4}(q+1)} \pmod q$.

Now you have the two square roots modulo the two primes numbers $(m_p, m_q, -m_p = p-m_p, -m_q=q-m_q)$.

Consider now the system:
$$\left\{ \begin{eqnarray}
m = m_p \pmod p \\
m = m_q \pmod q
\end{eqnarray}
\right. $$
Using the extended Euclide algorithm you know that:
$p\cdot y_p + q\cdot y_q = 1$ because $\gcd(p,q)=1$.
So multiplying by $m$:
$m\cdot p\cdot y_p + m\cdot q\cdot y_q = m$.

look at the equality $\mod p$:
$$m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m \pmod p$$
but you know that $m = m_p \pmod p$ and $m = m_q \pmod q$so:
$$m_q\cdot p\cdot y_p + m_p \cdot q\cdot y_q = m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m\pmod p$$.

Combining the two possibilities for the square root $\mod p$ with the two possbilities $\mod q$ you'll find the four results you listed.


Why does symmetric encryption require padding? Why does symmetric encryption require padding? Is it to avoid the attacker to learn the size of the plaintext?

Symmetric crypto does not always have padding. Stream ciphers often will not require padding. Padding is necessary when using a cipher that requires plaintexts to be a multiple of a particular size. For example, AES in CBC mode requires plaintexts that are a multiple of 128 bits. So if your plaintext is not, you must pad to make it the right size.


ROCA Implementation, Coppersmith Algorithm does not return roots We are currently trying to reproduce the implementation of the ROCA-Paper. Therefore we calculated $M'$ from $M$ and $Order_M'$ from $Order_M$ to reduce the search space, but when we hand these values to the coppersmith algorithm as described in Algorithm 1 of the paper, this algorithm does not find any roots.vIt only finds "potential" roots, which are fractional numbers and result in float numbers between $0$ and $1$.

These Roots have the form:

7903163834028830451137438186485015861/17304344567133368654502628603056098610,
213501605850162343745788742125935233/17304344567133368654502628603056098610, ...

Our Implementation can be found on Github

Does anybody have an idea, why the coppersmith algorithm does not return correct roots?

At the end of the function coppersmith_howgrave_univariate, you have

if gcd(modulus, result) >= modulus ^ beta:

You created $f$ as
$$
f(x) = x + (M'^{-1} \bmod N)(65537^{a'}\bmod M),
$$
so when you put $\mathrm{result} = f(\mathrm{root[0]})$, you do not get $p$ or a multiple of $p$, so the gcd makes no sense (and if ever you get a gcd greater than 1, you may have a factor of $N$).

I suggest that if root[0] is an integer, put it in roots and return that. That's what I did and it works fine.


3DES Feasibility and Security Questions are as following:

Is 3DES still feasible (in terms of security and
performance) to use?
Is 3DES safe to use in ECB mode?
Every time on giving the same input (plain text) to encrypt via 3DES
results same output (cipher text). What would the reason be for
that?  For example: Every time I gave input plain text 'wealth'
the output generated was 'VxDfWEQA'. Or is that even possible?
If one would want to discourage a company to not to use 3DES with
cipher mode ECB and padding PKCS7 what would that reason
would be and why?
If a company/entity still insists to use 3DES. What configuration
would be the most suitable to be set for it e.g. cipher mode and
padding.

Would like to have the answer of third question considering all possible scenario's if applicable e.g. considering all 3 keys for 3DES were same.

Is 3DES still feasible (in terms of security and performance) to use?

3DES is very slow except if you have specialised hardware, so it at most wins in speed on legacy hardware that has dedicated DES circuitry but no AES circuitry. If no specialised hardware is available, AES or most other modern lightweight ciphers will be significantly faster.

3DES also has a very small block size, meaning it can start leaking data after just a few GB of encrypted data, see also Sweet32. Additionally the 112-bit key is considered to be quite short these days even though technically still sufficient, but it could be too short for e.g. reasonable security against multi-target attacks.

  Is 3DES safe to use in ECB mode?

No block cipher is safe to be used in ECB mode, as you will always see which plaintext blocks appear multiple times. Additionally deterministic encryption (such as when ECB is used) cannot achieve security against chosen-plaintext attacks (a rather weak security notion).

  Every time on giving the same input (plain text) to encrypt via 3DES
  results same output (cipher text). What would the reason be for that?
  For example: Every time I gave input plain text 'wealth' the output
  generated was 'VxDfWEQA'. Or is that even possible?

(3)DES is a deterministic function, so if you give it the same input (that is the same message-key pair) twice you will get the same output twice. Randomness usually is only brought into the picture when using the block cipher. Also note that the probability of getting an ASCII-text ciphertext is $(52/256)^8\approx 0.000002898$.

  If one would want to discourage a company to not to use 3DES with
  cipher mode ECB and padding PKCS7 what would that reason would be and
  why?

See (1) and (3).

  If a company/entity still insists to use 3DES. What configuration
  would be the most suitable to be set for it e.g. cipher mode and
  padding.

EAX or CCM mode or if neither are an option CTR mode with a counting (context-dependent) IV and then a secure message authentication code (MAC) applied on the ciphertext (which is what CCM and EAX do). These modes require no padding.