RSA How to find the private key to a given public key when n doesn't consist of two primes? I have the homework to find to the public key (120, 3) the private key. I guess 120 is n and 3 will be e.
So that $\lfloor\sqrt{120}\rfloor=10$ I can't find a matching prime number. So it gets more complicated. I also know $\phi(n)=(p-1)(q-1)$ and $3\cdot d\equiv 1\mod (p-1)(q-1)$
But here I stuck, could somebody help me from this point on?

I also know $\phi(n)=(p-1)(q-1)$

This actually only holds if $n=pq$ and if $p$ and $q$ are both primes.

When $n$ doesn't factor as nicely you'll need the more general definition of $\phi(n)$ which can be computed from the following three axioms (given the prime factorization of $n$):

If $\gcd(n,m)=1$ for any $n,m$ then $\phi(n\cdot m)=\phi(n)\phi(m)$
If $p$ is prime and $k\geq 1$ then $\phi(p^k)=p^{k-1}(p-1)$

So in your case $$\phi(120)=\phi(2^3\cdot 3\cdot 5)=\phi(2^3)\phi(3)\phi(5)=(2^2\cdot1)\cdot2\cdot4=32$$

  does multi-prime RSA make any sense in practical use?

Yes, using more than two primes can make sense if you use the chinese remainder theorem (CRT) which yields a speed-up of $k^2/4$ for $k$ primes compared to using only $k=2$. See fgrieu's excellent answer for a discussion of why one wants that and what one has to look out for when actually deploying multi-prime RSA and the table in DW's answer to the same question for an overview of how many primes to use for each modulus size.


What are the differences between curve NIST P-521 and Edwards E-521 for signature? I implemented and used the P-521 curve for ECDSA. Signatures are 132 bytes long.
It seems that Edwards E-521 is safer but I did not investigated very deeper.

What is its signature length ?

How is it better ?

What is its signature length ?

Depends on what algorithms you use, but with ECDSA the signature length is twice the length of the order of the base point. For P-521 that's 1042 bits, or 132 bytes when using whole bytes for each part. For E-521 it's 1038 bits or 130 bytes.

  How is it better ?

The design criteria for E-521 are stated in A note on high-security general-purpose elliptic curves:

  The curves Curve25519 and Curve1174 have been engineered to facilitate simple, efficient and secure implementation of general-purpose elliptic curve cryptosystems, with impressive results [8]. On these grounds, it makes sense to look for similar curves at higher security levels.


Evaluatung Shadowsocks Crypto strength I recently asked a question on security.stackexchange.com about whether Shadowsocks is MITM-able and the answer was helpful yet I would like to understand symmetric crypto / the crypto used in Shadowsocks to be able to answer the following questions :

How long should key lifetime be assuming a 28 character random password (base64 char set)
What is the maximum shared key size (assuming AES-256-CFB) and what is the relationship between shared key size and the "strength of security".
Shadowsocks supports chacha and salsa ciphers yet they recommend aes-256-cfb as default - why is this when Dan Bernstein's crypto seems to be the direction we are heading.
Does symmetric crypto use session keys derived from the secret keys?
How much data needs to be transferred before an attacker can have enough ciphertext to affect security or is this not a consideration?
How can I learn more about Crypto to answer these questions easier myself?

See  Shadowsocks website

First, the expression "password" usually refers to "bad entropy, relatively easy to brute force". And basically the only way to deal with this is to use a decent key derivation function, which is designed especially for passwords. Examples are script, bcrypt or PBKDF2. The main difference to other key derivation functions is that you can tune up the process to actually take a long time - which is wanted in this case.

So, that leads to the first problem: What kind of key derivation do they have? I couldn't find it on their page. So probably, they don't have any.

Considering their "one time authentication", my guess is that they just offer the option to use MAcs. And they use HMAC-SHA1 for this, which is quite on the lower border of acceptable - for legacy systems but not for current development. SHA-1 should not be used today any more, but in HMAC it is not broken so far. But developing a new system should not actually involve such an outdated hash function.
And then: They use $(IV + KEY)$ as the key for the HMAC, which seems not that great either.

That last part actually leads me to believe they don't have session keys but just use that passwords (called $KEY$, I guess) directly, and maybe for both encryption and integrity check.

And then I stumbled over this discussion, which gave a little inside in their development of security features: github

Oh, and it seemds they are using libsodium as cryptographic library. And that one already gives you pretty much everything you would want: KDFs, key exchanges, state-of-the-art encryption and hashes, previously mentioned scrypt, etc. I don't know how good those implementations are, though.

Interestingly, there you can also find the term "onetime authentication" (link), which doesn't really make that much sense. But there you can find this:

  Finally, Poly1305 is not a replacement for a hash function.

Building an HMAC out of this sounds weird.

Overall, it doesn't look too good, and probably their security is lacking.

Coming back to yout questions:

Passwords should never be used as key directly, which might be what they do. And then it depends if your password actually has full entropy(uniformly chosen of all strings of length 28). In that case it should be fine. If it is words in language, that's entirely personal preferance.
AES 256 has a key size of 256 bit. The question is if they use actually the full size. If they use a password in base 64 encoding as key directly, that would be really, really terrible. Strength of security of AES is: Unbroken, don't worry about it. More of a problem could be their mode of operation, because you would actually want an authenticated one.
Well, using AES as standard is a really good thing. Supporting other ciphers is quite common. However, I doubt your statement, that we're heading into the direction of Bernstein's Chacha or Salsa ciphers. AES is the de-facto standard for state-of-the-art symmetric encryption.
It should, but I have doubts that this is done in Shadowsocks.
This isn't a consideration, because the encryption scheme is almost surely not the weakest part of their system. Security depends only on the weakest link of the system, and it is basically never the encryption scheme. One other possibility is wrong usage of an encryption scheme (e.g. hard coded key), maybe have a look here.
Well, that depends on how much you already know. For starters, Wikipedia has a really good quality for a lot of cryptographic topics. Then there are online courses for cryptography, books like Applied Cryptography by Bruce Schneier, etc. Most importantly, focus on scientific publications and try to spot and avoid amateur publications. Other than that, it mostly depends on the time and effort you are willing to invest.


Here's a guess: when you ask to compute h ** (a * b), it actually computes h ** (a * b mod q), where $q$ is the order of $g$ in $G1$.
If that is the case, well, a random element from $G2$ is not going to be a divisor of $q$ - any element that is the result of a pairing operation will be; however most elements of $G2$ cannot be the result of a pairing operation.
And, if the order of $h$ is not a divisor of $q$, then $h^{a \cdot b} \ne h^{a \cdot b \bmod q}$
The above would give the expected result if you set $h$ to be the result of a pairing operation, possibly with two random $G1$ elements...
(This is labeled a guess because I'm not familiar with the Charm framework, so I'm guessing about its behavior)


Is 3 rounds of Feistel enough for making a PRP? I know that one round of Feistel is not enough for making a PRP (Pseudo Random Permutation). I am also aware that two rounds are not enough. How about three rounds of Feistel?
I did a lot of reading on this topic, but it has not been helpful. For example, here they say that because of the Luby-Rackoff theorem, we have a PRP after three rounds, but here it says that it is not enough.
Which is it?

Wel'll consider a symmetric Feistel cipher with $n$-bit block using ideal independent random functions at each round.

Making it computationally indistinguishable from a random permutation requires some number of rounds depending on the attack model; and on if we are content with asymptotic security for $O(2^{n/2})$ work, or want asymptotic security with more work, or want security for a prescribed small $n$.

Classical results for asymptotic security with $O(2^{n/2})$ work:

under random known plaintext, we need 2 rounds;
under chosen plaintext (that is, assuming an encryption oracle, the criteria for a so-called weak PRP), we need 3 rounds; see the famous work of Michael Luby and Charles Rackoff, How to Construct Pseudo-random Permutations from Pseudo-random Functions (in SIAM Journal on Computing Vol. 17, No. 2, 1988, initially  presented at Crypto 1985);
under chosen plaintext and ciphertext (that is, additionally assuming a decryption oracle, the criteria for a so-called strong PRP), we need 4 rounds; for a proof that 3 rounds are not enough, see this answer.

These classical results are nice, and relatively easy to establish, but not directly applied in common practice. First, $O(2^{n/2})$ suggests that for 128-bit security (the current baseline), we'd need a 256-bit block cipher (which is uncommon: 128-bit is mainstream, 64-bit used to be). Also, ideal independent random functions at each round is assumed, but actual round functions are quite far from that.

Things are more complex (and more rounds are needed) for asymptotic security with more work; see Jacques Patarin's Security of Random Feistel Schemes with 5 or More Rounds in proceedings of Crypto 2004, or his earlier Luby-Rackoff: 7 Rounds are Enough for $2^{n(1−\epsilon)}$ Security, in proceedings of Crypto 2003.

Even more rounds are needed for prescribed small $n$, and to my knowledge we only have heuristics.


Making a cipher non-malleable using a plaintext transform? NOTE: By malleable/non-malleable, I mean the ability/or not to change a byte/block of the ciphertext and have it change only that byte/block of the plaintext.
I understand that we use authentication (via HMAC/UMAC/etc.) to verify integrity. However, where authentication is not possible (perhaps in a case where one has a very limited environment on storage/CPU power), can we transform the plaintext before encryption?
Using several "rounds" of a move-to-front transform that reverses the plaintext after each iteration does exactly that. Once the plaintext is over 1kb (or so), you only need a few rounds. This creates a sort of avalanche effect' so that tampering in any place affects a large amount of the plaintext.
My MTF transform uses an index of possible bytes (0-255). Each "round" consists of an MTF transform, resetting the index, reversal of the plaintext, and another MTF transform.
Running some tests suggests that with two rounds of my MTF for random 256-byte inputs, flipping any bit will, on average, change over 50% of decoded bits. For a 512-byte input, the average is 53%. For a (barely tested) 1024-byte input, the average (and lowest) number of bits changed is over 50% for any flipped bit.
The outliers (minimum number of bits changed) are linear for small enough inputs. For a 512-byte (or less) input, the lowest number of bits changed is always achieved by flipping the first bit (further right) of the first input byte. Additionally flipping any bits at the end of a small input always results in a greater than 50% change, but not at the beginning. These undesirable effects seem to disappear with a 1024-byte input, although testing this takes me too long (about 2 minutes per input!) to make any useful statement.
The main problem with this approach is that it takes too long. I am using a small notebook with Intel Atom CPU Z3735 @ 1.33GHz. One KB takes around 0.034 seconds to encode. To encrypt a KB using ChaCha takes around half this time.
NOTE: The transform function is completely known (per Kerckhoff's principle). It is completely dependent on the plaintext. The function does absolutely nothing except add non-malleability to the plaintext and thus ciphertext. It works before ANY cipher, and not with.
UPDATE: I've updated the transform function, altering the indexes used for the transform rounds, reducing the rounds to 2, and adding a running sum of data input to the process. It is now quicker than ChaCha and achieves non-malleability at 512 bytes of input, without any bias (within limits of my testing). It adds a nonce on encoding that it removes on decoding. The code is here if anyone wants to have a look.
I'm aware I could make the code faster, but I still think there must be some standard approaches to the overall problem. The only modern, similar thing I've found relates to an all-or-nothing transform, which Rivest discusses here. It seems strange that the idea (assuming Rivest is correct about added security) didn't really catch on.
My questions:

Is there any existing approach that does anything similar to this? Basically some sort of modern version of Russian copulation?
Does anyone know a potentially quicker way to transform plaintext (completely independent of the cipher) and make it (potentially) non-malleable?

Is there any existing approach that does anything similar to this? Basically some sort of modern version of Russian copulation?

There is one existing idea which is currently used in some RSA implementations that could be tweaked slightly to fit the requirements of Russian copulation.  I will briefly describe below, and then mention a potential additional benefit of such a 'transform'.
OAEP
Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption.
The algorithm takes the form of a Feistel network which uses a pair of random oracles $G$ and $H$ to process the plaintext prior to asymmetric encryption. When combined with any secure trapdoor one-way permutation $f$, this processing is proved in the random oracle model to result in a combined scheme which is semantically secure under chosen plaintext attack

As using OAEP as an all-or-nothing transform would require processing in blocks (with padding) and potentially some extra tweaking to design it for the purposes of non-malleability.

Finally, it is not necessarily be the case that using such a transform function would only provide the benefit of non-malleability.  As per the Ron Rivest's paper All-or-nothing encryption and the package transform

We present a new mode of encryption for block ciphers, which we call all-or-nothing encryption. This mode has the interesting defining property that one must decrypt the entire ciphertext before one can determine even one message block. This means that brute-force searches against all-or-nothing encryption are slowed down by a factor equal to the number of blocks in the ciphertext. We give a specific way of implementing all-or-nothing encryption using a “package transform≓ as a pre-processing step to an ordinary encryption mode. A package transform followed by ordinary codebook encryption also has the interesting property that it is very efficiently implemented in parallel. All-or-nothing encryption can also provide protection against chosen-plaintext and related-message attacks.

Below I will give an example of how we can use OAEP as inspiration.  It can obviously be improved upon (and I could probably use a variant of ChaCha QR).  My code is here and may well be easier to read than my explanation below.
This CAN be done in a single-pass, and it is significantly quicker than my previous function which looked up/sliced/rearranged arrays, and processed byte-by-byte.
First, I took an unbalanced Feistel cipher and set it up (with 10 double rounds). It is made up of 8 blocks of 32 bits.
The blocks are XORed with fixed circular rotations of other blocks, and shift position after each double round.  In each double round, most blocks are affected in some way by most other blocks.  For example, block0 (in one double-round) is affected by Blocks 1,2,4,5 & 7.  Odd blocks are affected by one less, eg. Block 1 is affected by Blocks 2,3,4 & 5.
After 10 double rounds, this achieves good (over 50%) diffusion in output blocks 0,3,5 & 6.  In the other "bad" blocks it is around 56%.
We will process input data in 128 bit chunks, using the "good" blocks of the Feistel and the "bad" blocks of the Feistel will be the state/capacity which is initialised with random data and saved with the final encoding.  Thus allowing us to decode (backwards), and the initial randomness providing a nonce.
Finally, we add a 128 bit "counter" into the Feistel.  This keeps a XOR of all the data blocks processed (and begins on 0).  This doesn't need to be saved, but does require slightly more computation for decoding as we need to "count" all the blocks before we begin the decoding process.
As we decode in reverse, it is obvious that the last data block affects any of the previous data blocks (due to the saved state).  And as the "count" of previous data blocks affects the last data block, we have all bits affecting all bits.
It would require padding the input, but it's incredibly quick. 1KB is processed in <0.003 seconds on my rubbish machine.  It's actually too quick for my rubbish testing and often registers 0 at lower amounts.
The problem I can see is that it generates differing diffusion levels depending on the size of input.  If the input is 128 bits, the average number of bits changed for any bit flipped is around 75%.  For 1024 it is around 57%.  For 3072 it is around 53%. For 4096 it is still around 52.5%. At 1KB it is around 52%
I have not found a single bit that could be flipped that didn't cause over 50% of bits to change for any input size.


why ransomwares are still problematic? There is some points that I don't understand yet about ransomwares :

the attacker generally put his bitcoin address in the malware, can this address be used to identify and reach him ?
on the assumption that the malware use symmetric encryption, can we use reverse engineering to retrieve the key ?
on the assumption that the malware use asymmetric encryption, can we use the server which deliver the decryption key after payment to reach the attacker ?
as far as I know practically the files themselves aren't encrypted, but another file is created using the secret key then the original file is deleted, so can we use a file recovery program to recover everything ?

Public key cryptography lets the ransomware encrypt files so that only the malware author (who has the private key) can decrypt them or supply the needed per infection key.
Payment in Bitcoins is traceable, since all Bitcoin transactions are public. If the attacker transferred their Bitcoins to an exchange directly and converted them to a conventional currency, law enforcement could demand the records and find their identity. Mixing services allow the attacker to mix their coins together with lots of other legitimate coins, hiding where they end up. Mixing services exist and are only getting better.
The decryption for Bitcoins service can be hosted as a TOR hidden service. The attacker can set up a server that watches the bitcoin blockchain for bitcoin payments and provides one decryption key per payment. There is no link between the attacker and the servers except for the initial setup (which can be done through tor) and hosting fees (which can be paid in bitcoins).

All of these technologies are proven. It's just a matter of setting everything up and infecting victims. Until the general public learns to do better backups ransomware is here to stay.


How to encrypt huge amount of data using AES-CTR As far as I know, AES-CTR depends on nonce. If I will use same key and nonce for encrypting 1 block of data and another - it will be unsecure. So, how can I encrypt a huge block of data (about 1GB) using AES-CTR?

So, how can I encrypt a huge block of data (about 1GB) using AES-CTR?

So CTR-mode works as follows $C=P\oplus E_K(N)$ where $P,C$ are the plain- and ciphertext respectively and $E_K(N)$ is the encryption of $N$ under the key $K$ for every plaintext and ciphertext block.

Now if you were to re-use a $(N,K)$ pair this would indeed break security. This is why normally in CTR-mode to encrypt block $i$ we apply some function $f(N,i)$ to our nonce, for example $f(N,i)=N+i$ or $f(N,i)=N\|i$ ($\|$ denoting concatenation here) so we get different values for each block.

Of course you can't always maintain a global state value $i$ which is why for each new message $N$ or point where you don't to carry around $i$ you either derive a new $N$ from some contextual information (e.g. a packet counter) such that the $f(N,i)$ are unlikely to overlap or you choose a random $N$ and transmit it along.


How to show something is not a one-way function? Lets say that $f:\{0,1\}^* \to \{0,1\}^*$ is a strong one way function.
Let
$h(x)=f(x)||x_n$ where $x_n$ is the $n$th bit of $x$.

I understand that $h$ will not be a strong one-way function. However, I wish to gain an intuitive understanding why that is.

Actually the proof that $h$ is one-way is not that trivial... First, a reminder on definitions. A function $f$ is (strongly) one-way if for all probabilistic polynomial-time adversaries $A$, all polynomials $p$ and all sufficiently large $n$, we have
$$\mathrm{Pr}[A(f(U_n),1^n) \in f^{-1}(U_n)] < \frac{1}{p(n)}$$
(where $U_n$ represents a random variable with uniform distribution over all strings of length $n$). Put in words, we choose uniformly a string $x$ of length $n$, we compute $y = f(x)$ and we run $A$ on input $(y,1^n)$, noting its output $x'$. Then the definition states that the probability that $f(x') = y$ is less than $1/p(n)$. We prove that $h$ is one-way by contradiction. That is, assuming that $h$ is not one-way, we show that $f$ is not one-way, contradicting our hypothesis.

So what does it mean to say that $h$ is not one-way. It is easily seen that "all sufficiently large" is equivalent to "all but a finite number", so we obtain the following. There is a probabilistic polynomial-time algorithm $A_h$ and a polynomial $p_h$ such that for infinitely many $n$ we have
$$\mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \ge \frac{1}{p_h(n)}.$$
We restrict out attention to such $n$. We will show that there is a probabilistic polynomial-time algorithm $A_f$ and a polynomial $p_f$ such that for all such (infinitely many) $n$, we have
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)] \ge \frac{1}{p_f(n)}.$$

$A_f$ works as follows, on input $(f(U_n), 1^n)$ (that is, on input $(y,1^n)$ where $y = f(x)$ for a uniformly chosen $x$ of length $n$).

Run $s \gets A_h(y||0,1^n)$. If $f(s) = y$, output $s$ and halt.
Run $t \gets A_h(y||1,1^n)$. If $f(t) = y$, output $t$ and halt.
Output $0^n$ and halt.

$A_f$ clearly runs in probabilistic polynomial-time, and we analyse its success probability. We observe that if the last bit of $U_n$ is $0$ and the call to $A_h$ in step 1 succeeds, then $A_f$ will succeed. Likewise, if the last bit of $U_n$ is $1$ and the call to $A_h$ in step 2 suceeds, $A_f$ succeeds. Hence (letting $\mathrm{last}(X)$ be the last bit of $X$)
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] $$
and
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1].$$

Now,
$$\begin{align*}
\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)]
  &= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \\
  &= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \\
  &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \\
  &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \\
  &\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \\
  &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \\
  &\ge \frac{1}{p_h(n)}.
\end{align*}$$


Proving equality of two Schnorr Signatures Given two Schnorr Signatures that were made from the same $x$, where each $x$ is private. Is there a way to prove that they came from the same $x$ without revealing $x$?
I heard about Chaum-Pedersen Protocol and how it is supposed to address this, but I am a bit confused how it should work. The book I'm reading has the following notation:
Equality is proven so long as:
$r_1 == g^{s_1}$. $y_1^{c_1}$
and
$r_2 == h^{s_2}$. $y_2^{c_2}$
Where $g$ and $h$ are generators
$s$ is the proof
$y_1$ and $y_2$ are the public keys of the the secret $x_1$ and $x_2$
and $c_1$ and $c_2$ are the challenges
I am seriously confused about what the relation between those numbers are: With the above, you prove that each Schnorr Signature came from a different $x$, but not that they came from the same $x$, right?
Answering some questions that came up:

Are $g$ and $h$ different generators from the same group?

Yes, they are.

Are $c_1$ and $c_2$ hashes?

Yes they are. Made with a random oracle. The term "challenge" might be weak here since they are non-interactive.
I'm just really trying to wrap my head around the possibility of proving equality for Schnorr signatures.

I don't think that works with keeping the message private - unless you break the signature scheme by reusing the nonce.
Your variables $c_1$ and $c_2$ are the results of the hash function. And those can not be the same by the definition of $r$ being a nonce. Moreover: the hash function does not retain any algebraic structure. By the definition of hash functions, the resulting hash only shows if two inputs wre the same or not. No partial matching or any type of relation between two inputs.
But they are also the only variables, that depend on the private message $x$. And  from that, I don't see any way to distinguish $c$-values , where $x$ is the same or $x$ is different. Unless you allow $r_1=r_2$, which breaks the security of the signature.
The main misconception with using Chaum-Pedersen: They don't use signature schemes. They use commitments. From the statement, that you want to keep $x$ private, maybe you should use commitments instead of digital signatures. They give the privacy requirement, and you can use Chaum-Pedersen directly.


curious DHE implementation for key exchange I have made some reverse engineering on proprietary software and came up with some DHE algorithm that works like this:

First and foremost, the client and the server shares some public parameters (g, p) where p is a prime number :

# the client generates some random number X
# Then...
A = g^X % p
B = 4^X % p

At this stade, A and B are two numbers computed with some exponentioation modulus p.

The client keeps A for itself and sends B over network to the server.

I can't guess out what's the server doing with B.

What comes up next is that the server sends the client back some buffer which is 20 bytes long. This buffer is xored with the first 20 bytes of the little-endian representation of A. Meaning something like this:

key = buffer ^ A[0...20]

And there you go, key is the shared key between the client and the server.

I am trying to guess out how the server generated that xoring buffer, and what did it compute with 'B'. Any clue?

Edit:

For instance, I have these numbers:

g=4251748925932087506992136911681457196421197968417424634771122535345596546655443876920558972863202693157925206950493858768680434551750613271334944372387511

p=7552255105811443149655814117645061441469802313473420161620729142606560015854445500056007762660457578016660416343667268412286196867181440500178902692672641

X (random number) = 8788592173807205653697600075440308493757969005221433286958441247128089107594429784362875543428031794230308326680487467902465260209524609291268858491985100

How could  the server compute A?

I haven't checked, is $p$ a safe prime and/or is 4 a generator over $p$?

Server has random secret $S$, known $p$ and $g$ a generator.  I'm substituting in $V$ for your $g$, with $g = 4$.

$V = g^S \mod p$

$V$ is a verifier of the server, as in SRP.

$V$ is your $g$, so known by the client.  Anyone knowing $V$ can establish communications with the server.

You calculate for random $X$

$A = V^X \mod p$
$B = g^X \mod p$

So, when you send $B$, server calculates

$A = B^S = g^{XS} = V^X \mod p$

This is one-way authentication, of the server only.  You could do the same thing with the client, and have a mutually authenticated DH key exchange (each client would need a secret as well, and the server would have to know the corresponding verifier).

What's curious is why bother sending back anything, why not just use $A$ directly (or a hash of it, for example)?  If the 20-byte value isn't checked against anything else, it seems sort of useless.  It could be used as a proof, e.g. hash of $A$, but you don't indicate that it's used for anything except to XOR it with $A$.  Since it's being sent in the clear, it doesn't really add anything to the security.


cryptographically good random elliptic curves? After an answer here, about generate elliptic curves, I've start thinking about the algorithm. The mentioned algorithm will produce curves in the Weierstraß Reduced Form (WRF) over finite fields:

  $y^2 = x^3 + ax +b$ with $a,b\in \mathbb{F}_p$

And this WRF is the representation used in the NIST (where $a\equiv-3\pmod p$), Brainpool, and probably some others, that can be used in standards like the extension for OpenPGP or TLS.

But this is only one of many ways to describe elliptic curves. In TLS specification it opens to the possibility to use arbitrary curve definition. Or other alternatives are Montgomery curves like the  curve25519 "recently" proposed for EdDSA.

If I like to generate my curve (ignoring the fact that this would affect the maths in the implementations) are there differences between representations? I mean, would be faster to generate random cryptographically good curves depending on the representation? Will curves with different representation and the same bit length, have the same strength?

No, not all curves are created equal. For one thing, the number of points on an elliptic curve defined over $\mathbf{F}_p$ varies in the interval $[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ (Hasse's Inequality). There are also weak instances which must be avoided, the most catastrophic being when the number of points on the curve is exactly equal to $p$ (anomalous curves) or to $p+1$ (supersingular curves).


Merkle Tree space complexity When searching by using the Merkle tree, the time complexity is $\mathcal O(\log n)$ but I don't understand how space complexity is $\mathcal O(n)$. In my opinion, it should be also $\mathcal O(\log n)$. Can somebody explain it to me?

For simplicity assume that the Merkle tree is a perfect binary tree. Let the number of data blocks is $n$ which are linked to the leaf nodes. Therefore the total number of tree nodes are $|nodes| = n + n/2+ \cdots +1$. If we assume that $n =2^k$ for simplicity than $$|nodes| = 1 + 2 + 2^2 + \cdots + 2^k = \frac{2^k-1}{2-1} = 2^k-1 = n-1.$$ In total, we have $n+ n -1 $ nodes, that is together with the data blocks. As a result the number of nodes are $\mathcal{O}(n)$.

In another approach, you can consider the height of the tree as the search complexity, $h = c \log n$ then the maximum number of a binary tree with $h$ is $2^h-1 = 2^{c \log n}-1 = n 2^c-1 \in \mathcal{O}(n)$. Adding the data block will not change the complexity.

Note: In a complete binary tree, if we say that the root is level 1 then the $i$-th level contains $2^{i-1}$ nodes. Each level will contain a double of the previous level.


Does data authenticity always, implicitly, provide data integrity? Does a scheme which provides data authenticity (e.g. HMAC or RSA signature) always implicitly provide integrity? It seems, to me at least, that it must by necessity. However, I have seen cryptographers reference MAC, MIC, and MAIC as separate terms. In my experience, that usually means that there's a subtle difference that's important to pay attention to. However, if MAC and MAIC are identical, what's the reason for the distinction?

There are varying definitions of authenticity and integrity, but generally speaking, no.

In a cryptographic sense, authenticity indicates that a message was endorsed by a particular principal. This principal may endorse multiple messages, and the same authentication tag can validate distinct messages. For example, having a (secure) MAC guarantees the authenticity of the message, but does not guarantee its integrity (see Why have hashes when you have MACs?). HMAC guarantees authenticity and integrity, but other MACs typically only guarantee authenticity: the authenticating party can forge other messages with the same MAC value.

In a data flow sense, authenticity guarantees the provenance of a message, but it does not distinguish between different messages from the same principal. A mere authenticity check does not protect against replay attacks: a message that was authentic in a previous run of the protocol is still authentic now, but integrity demands that the message that is received is the message that was sent as part of the same run. There are situations where integrity is harder to achieve than authenticity. For example, suppose I back up a file to a remote storage service. When I download the file, I can check that I am getting back a properly signed file, and if I include the file's name, I know that I am truly getting back a version of the file that I uploaded: the file is authentic. If I upload multiple versions of the file under the same name, integrity would guarantee that I download back the latest version; with a mere guarantee of authenticity, all I know is that I downloaded some version of that file.


Counting the $\operatorname{XOR}$ of an Element over the Finite Field $\operatorname{GF}(2^q)$ Definition: The $\operatorname{XOR}$ count of an element $\alpha$ in the finite field $\operatorname{GF}(2^q)$ is the number of  $\operatorname{XOR}s$ required to implement the multiplication of $\alpha$ with an arbitrary $\beta$ over $\operatorname{GF}(2^q)$.

Example: Consider we want to compute the $\operatorname{XOR}$ count of $\alpha=x +1$ over $\operatorname{GF}(2^4)$ with the irreducible polynomial ${\bf f}=x^4+x+1$. We denote the element $\alpha$ with $(0,0,1,1)$.
 Let $(b_3, b_2, b_1, b_0)$ be the binary representation of an arbitrary element $\beta$ in the field $\operatorname{GF}(2^4)$, then we obtain

$$
\begin{array}{rcl}
(0, 0, 1, 1) · (b_3, b_2, b_1, b_0)
&=& (b_2, b_1, b_0 ⊕ b_3, b_3) ⊕ (b_3, b_2, b_1, b_0)\\ \\
&=& (b_2 ⊕ b_3, b_1 ⊕ b_2, b_0 ⊕ b_1 ⊕ b_3, b_0 ⊕ b_3),
\end{array}
$$
which corresponds to $5$ $\operatorname{XOR}$s.

Note: The $\operatorname{XOR}$ counting problem is depending on the irreducible polynomial of the field.

For instance, consider $\operatorname{GF}(2^4)$ with the irreducible polynomial ${\bf f}=x^4+x^3+1$, then we get

$$
\begin{array}{rcl}
(0, 0, 1, 1) · (b_3, b_2, b_1, b_0)
&=& (b_2 ⊕ b_3, b_1, b_0, b_3) ⊕ (b_3, b_2, b_1, b_0)\\ \\
&=& (b_2, b_1 ⊕ b_2, b_0 ⊕ b_1, b_0 ⊕ b_3),
\end{array}
$$
which corresponds to  $3$ $\operatorname{XOR}$s.

My question: Is there an algorithm or a software such that its input be  a finite field $\operatorname{GF}(2^q)$ and an element $\alpha$ of $\operatorname{GF}(2^q)$ and its output be the $\operatorname{XOR}$ of $\alpha$ over $\operatorname{GF}(2^q)$.

Thanks for any suggestions.

Let $f=x^q+t$ be an irreducible polynomial, then

  $$\alpha\cdot \beta= (\alpha_{q-1},\dots,\alpha_0)\cdot(\beta_{q-1},\dots,\beta_0):
\bigoplus_{i=0,\alpha_i\neq0}^{q-1}\big( \alpha_i\cdot(\beta<<i) \oplus (\bigoplus_{j=1}^{i} \beta_{q-j}\cdot x^{j-1}\cdot t)\big).$$

With this formula, you can easily calculate XOR count of $\alpha$. Although there may be a simpler solution to answer your question.
Note that in this formula, several $\beta_ k$ may be xor with each other, which should not be taken into account in the XOR count calculation. For this, a $q\times q$ matrix can be used for implementation.

Edit: As an example, let $f=x^8+x^4+x^3+x+1=x^8+t$. Then
$$(x+1)\cdot \beta=\alpha_0\cdot (\beta_7,\dots,\beta_0)\oplus \alpha_1\cdot (\beta_6,\dots,\beta_0,0)\oplus \beta_7 \cdot t=(\beta_7,\dots,\beta_0)\oplus (\beta_6,\dots,\beta_0,0)\oplus (0,0,0,\beta_7,\beta_7,0,\beta_7,\beta_7)=(\beta_7\oplus \beta_6,\beta_6\oplus \beta_5,\beta_5\oplus \beta_4,\beta_4\oplus \beta_3\oplus \beta_7,\beta_3\oplus \beta_2\oplus \beta_7,\beta_2\oplus \beta_1,\beta_1\oplus \beta_0\oplus \beta_7,\beta_0\oplus \beta_7).$$
So, the XOR count of $x+1$ is $11$.


Can we possible to solve the LPN problem using Arora-Ge algorithm? I recently studied how to solve the LWE (learning with errors) using algebraic relations proposed by Arora and Ge (paper : New Algorithms for Learning in Presence of Errors).
As I understood, for LWE instances of the form $\vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~q$ for some integer $q$, adversaries generate algebraic polynomials which has a root $e_i = b_i - <\vec{a}_i,\vec{s}>~mod~q$. If adversaries obtain sufficiently many polynomials, then they can recover the secret vector $\vec{s}$ using linearization technique.
Thus, I think that the Arora-Ge algorithm is also possible to solve LPN (learning parity with noise) problem since the instances are of the form $\vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~2$.
However, I cannot find any references about the result, so I guess that I have some mistakes.
Why can't I use Arora-Ge algorithm to solve the LPN?

It is natural to wonder if Arora-Ge can break LPN, but as you suspect, it does not work. The essential problem is that, because the modulus is $q=2$, the method does not find the unique solution $s$, nor does it even narrow down the set of possible solutions.
The reason is that the first step of the algorithm converts each LPN sample into a quadratic (in $s$) equation that encodes the condition $\langle a_i, s \rangle = b_i \text{ or } b_i +1 \pmod{2}$. It then linearizes these equations and solves for $s$. However, observe that any $s’$ is a solution to these equations, because the right-hand side is always “0 or 1.” So, the system set up by the algorithm does not carry any information about $s$, from the very start.
Arora-Ge works for LWE because/when the modulus $q$ is larger than the number of possible error values. Then, the condition “$\langle a_i, s \rangle = b_i \text{ or } b_i+1 \text{ or } b_i-1 \ldots$” captures a nontrivial constraint on the secret $s$, and enough such equations can uniquely specify it.


What is perfect secrecy? I read some similar questions like Simply put, what does “perfect secrecy” mean?
 (This one defines perfect secrecy as ciphertext conveys no information about the content of the plaintext.

Now, problem 2.3 on this assignment asks:

  show that perfect secrecy of $(GEN, ENC, DEC)$ implies $$\Pr [ENC_k(m) = c] = \Pr [ENC_k(m') = c]$$

Isn't the above equation saying that ciphertext $c$ gives no information whether it's $m$ or $m'$?

What is the exact definition of perfect secrecy then?

P.S. the assignment link above contains the solution. In the solution, I don't understand where the definition of perfect secrecy is used, nor what it is.

The Lindell and Katz, in their book, give the definition as follows;

  An encryption scheme $(Gen,Enc,Dec)$ over a message space
  $\mathcal{M}$ is perfectly secret if for every probability
  distribution of over $\mathcal{M}$, every every message
  $m\in\mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which
  $Pr[C=c]>0$;

  $$Pr[M=m|C=c] = Pr[M=m]$$

We can view this definition as the distribution over messages and ciphertext are independent.

The proof used this definition and the equivalent definition of perfect secrecy

$Pr[C=c|M=m] = Pr[C=c]$

and, this can be said, the ciphertext reveals no information about the plaintext other than the size.

On your proof;

On the third P, on the numerator and denominator;

$Pr[Enc_k(m_1)=c] = Pr[Enc_k(M) =c | M=m_1]$


What is it meant by a "hybrid argument"? Can anyone explain (or point to a reference for) what a hybrid argument is in a security proof, and when it's convenient or preferable to use it?

Among some of the places where I've seen it mentioned, there is the paper Boneh, Sahai, Waters - Functional Encryption: Definitions and Challenges. The term standard hybrid argument is mentioned in the proof sketch of Theorem 1 within section 4.1.

Quoting from "On beating the hybrid argument" (by Bill Fefferman, Ronen Shaltiel, Christopher Umans and Emanuele Viola; 2012):

  The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor $k$ equal to the bit-length of the distributions: $\epsilon$-distinguishability implies $\epsilon/k$-predictability.

As you're looking for a more in-deep and more practical explanation of "hybrid argument", I would like to recommend diving into the PDF "The hybrid argument", which includes a whole bunch of examples to walk through so you can wrap your head around it completely.


Group signatures, security and ECDSA I am reading up on group signatures. With RSA a public key can have more than one private key. For a public exponent $e$, private exponent $d$ and modulus $n$,  there is more than one solution for the equation

$$d \cdot e \equiv 1 \pmod{\lambda(n)}$$

This is possible because of the modulus operation. So, if I want to create a group of keys, I can do so as long as I keep $p$ and $q$ (which are used to compute $n = pq$) secret.

How do I guarantee that two systems/users have not picked the same private key? Would it matter if they did?

Are group signatures possible with DSA or ECDSA? From the key generation steps I see on the wiki it does not look like it's possible. Am I right? I ask this because the parameters ($p$, $q$, $g$) are already public, and the only thing secret is the private key $x$, which was generated first and based on the public key that was generated. So, can I conclude that it is impossible to generate multiple private keys for a given public key?

You seem to be confused a bit. You're talking about three or four distinct things here. At one side, you have RSA. On the other side, there's DSA and ECDSA, which are more or less based on the same cryptographical ideas. Then you talk about group signatures.

Your first question is about RSA

  How do I guarantee that two systems/users have not picked the same private key? Would it matter if they did?

Two different users generate two different keys, by picking random primes $p$ and $q$, both having a bit length around $\log(n)/2$, such that the product of them ($n=pq$) will have length $\log(pq)=\log(p)+\log(q)=\log(n)$. Let's see how many primes there are for an RSA system of 4096 bits. According to Wikipedia, the prime counting function $\pi(x)$, which computes the amount of primes smaller than $x$ can be approximated by $$\pi(x)\approx\frac{x}{\ln{x}}$$. We need primes of length 2048, so we need to substract around $\pi(2^{2047})$

\begin{align}
\pi(2^{2048})-\pi(2^{2047})&\approx\frac{2^{2048}}{\ln{2^{2048}}}-\frac{2^{2047}}{\ln{2^{2047}}}\\
&=\frac{2^{2048}}{2048\ln{2}}-\frac{2^{2047}}{2047\ln{2}}\\
&=2^{2037.5}-2^{2036.5}=2^{2036.5}
\end{align}

That's a lot of primes to choose from. This basically guarantees that no two RSA secret keys will ever be the same.

  Are group signatures possible with DSA or ECDSA?

Let's recall what a group signature is, on an abstract level:
There's a group manager $\mathcal{Z}$, who chooses the group members (setup). The group members can sign a message, and a verifier only learns that the signature was created by someone in the group, without being able to pinpoint who it was. $\mathcal{Z}$ can optionally choose to reveal the original signer.

Now, DSA and ECDSA are two specific instances of a regular digital signature. These obviously aren't group signatures schemes, but regular digital signatures.

What you probably are asking about is whether it is possible to use the mathematical constructs behind DSA and ECDSA to create a group signature scheme, just like Chaum et al. constructed their scheme on RSA. (EC)DSA are based on the (elliptic curve) discrete logarithm problem(s). Indeed, there are a lot of proposed group signature schemes based on elliptic curve, as there are based on regular DH groups.

Also worth noting are ring signature schemes (RST, for example), which provide a similar but spontaneous construction, without a group manager (and thus without possible revealing of the original signer).


Can the AES encryption and decryption algorithms be described as a polynomial for a specific key? AES is a block cipher that consists of non-linear and linear parts to provide the Shannon requirements of confusion  and diffusion respectively. The linear parts can for sure be described as a polynomial and more specifically the SiftRows,MixColumnds,AddRoundKey parts but what about the non-linear one?

Yes, they can be described as a multivariate polynomial over $GF(2)$ (or over $GF(2^8)$).  See algebraic cryptanalysis.  This expression does not seem to help cryptanalyze AES, so far as we know, but it can be done.

For an example of how to write AES in this way, see the following paper:

A simple algebraic representation of Rijndael.  Niels Ferguson, Richard Schroeppel, Doug Whiting.  SAC 2001.

You can also read about the XSL attack, a controversial attack that was claimed by some researchers to work against the AES and which is based upon a representation of AES as multivariate polynomials.


Cryptographically secure product keys I am looking for a scheme to generate and validate cryptographically secure product keys. My requirements are:

Unforgeable. It must be impossible (or at least very hard) for users to forge a product key.
Short. Users may enter product keys by typing so they must be convenient to enter. 128 bits can be encoded using 26 base-32 characters, which is probably close to the maximum that users will type comfortably.
Payload. The keys must be able to carry a limited amount of arbitrary information. For example, this might be flags about enabled product features. 32-bits of payload should be sufficient.
Numerous. There must be a large number of valid (but difficult to guess) product keys for the same payload.
Unique. The product key generation process must generate distinct product keys for the same payload, when invoked multiple times.

In the following I consider only symmetric key schemes. A public key scheme is not necessary in my case because key generation and validation is done on the server, thus there is no need for public/private keys.

I have considered a number of different schemes, but I have found all of them wanting. The main issue is the shortness of the product key.

The obvious first choice is to create product keys of the form

nonce || timestamp || payload || HMAC(K, nonce || timestamp || payload)

The nonce || timestamp ensures that there are numerous unique product keys. HMAC is a secure MAC thus guaranteeing unforgeability. A payload is included. The only issue here is the length of the product key.

Recall that all this needs to fit in 128 bits. Even if we truncate the HMAC to 80 bits (the recommended minimum), this leaves only 48 bits for the nonce || timestamp || payload component, which is clearly not enough (the payload alone requires 32 bits).

Another choice is to create product keys of the form

AES-ECB(K, nonce || timestamp || magic || payload)

Here we use magic to enforce unforgeability. Clearly this is suboptimal, unless we make magic very long. If magic is short it is quite easy for an attacker to keep guessing product keys and feeding them to the validation server to see which ones pass (let's assume for now that the validation server has no countermeasures such as throttling).

The problem is that the nonce || timestamp part also needs to be very long to avoid problems with the use of ECB mode. Ideally it should be at least 80 bits, but perhaps we could get away with 64 bits. This would leave only 32 bits for magic, which I suspect would make this scheme weak.

I have also considered other alternatives, but I have not arrived at a satisfactory solution. I would love to hear any feedback you may have.

Your second solution seems to be quite close to optimal. You perhaps do not need both nonce and timestamp unless timestamp is part of the payload. Anyway, the structure
$$
N||P,
$$
where $N$ is 48-bit nonce and $P$ is a 32-bit payload seems sufficient for your needs, as you are unlikely to generate more than $2^{48}$ product keys. To ensure authentication (unforgeability) you merely add a 48-bit zero string (analogue of your 'magic') and encrypt it with AES:
$$
KEY = AES_K(N||P||0^{48}).
$$
Forgery is unlikely in this scheme unless an attacker makes more than $2^{47}$ attempts (which I also suppose is a fair assumption).

In this scheme you can vary all these parameters if you have a larger payload but expect fewer keys or forgery attempts.


Protocol to identify zone of potential agreement without revealing reservation prices and having to trust third parties? A wants to buy a company from B. Before A and B enter negotiations, they want to make sure that there actually is a zone of potential agreement. Obviously, they don't want to communicate their reservation prices to the other party (A only buys for less than 100m, B only sells for at least 90m). So they both communicate their reservation price to a trusted mediator who then tells them whether or not negotiations makes sense.

Is there a protocol that A and B can use to find out the same thing without having to trust the other and any third parties?

Is there a protocol that A and B can use to find out the same thing
  without having to trust the other and any third parties?

There is. Even more than one.
Your problem actually is equivalent to Yao's Millionaire's Problem.
You have two numbers which two parties want to keep secret and you want both parties to find out whether the one is larger than the other, i.e. compare $a\geq b$ with $a$ being the maximal price willing to be paid by A and $b$ being the least price for which B would sell.

The secure multiparty protocols (credit goes to Ricky for pointing that out) to solve this are various. Because they aren't easy and it's better if you get them from source I'll quickly name three (better protocol suggestions are welcomed):

"Protocols for secure computation" by Yao
"Some Efficient Solutions to Yao’s Millionaire Problem" by Kumar and Gupta
"An Efficient Protocol for Yao's Millionaire's Problem by Ioannidis and Grama


mDP kay agreement protocol where z's are found on the step where the common key is generated? Whilst I was studying the mDP protocol I came across into the following step:

  Group Key agreement:
  Each $U_i$ checks whether $z_1 \bigoplus ... \bigoplus z_n = 0$ and whether all signatures $\sigma_i$ are valid and aborts if any of these checks fails. Otherwise, $U_i$ proceeds as follows:
  iteratively for each $j=i,...i+n-1: z'_{j,j+1}:=z'_{j-1,j} \bigoplus z_j $
  ...

But I cannot understand on the notation what does it mean by $z'_{j-1,j}$ where does it find it is the $z_i$ received from the other participants?

The paper is in springler and is titled as;

"Flexible Group Key Exchange with On-Demand Computation of Subgroup Keys (Full Version)" authored by: Abdalla Michel, Chevalier Celine,Manulis Mark,Pointcheval David

an alternative from Pointcheval's web site.

As said in page 6, Each $U_i$ proceeds as follows;

compute $\text{sid}_i:= U_1|y_1,\ldots,U_n|y_n)$,
$z'_{i-1,i} := H(k'_{i-1,i}, \text{sid}_i)$,
$z'_{i+1,i} := H(k'_{i+1,i}, \text{sid}_i)$,
$z_i := z'_{i-1,i} \oplus z'_{i+1,i}$,
$\sigma_i := \text{Sign}(sk_i, (U_i,z_i,\text{sid}_i ))$,
$\text{broadcast} (U_i,z_i,\sigma_i)$.

since in the beginning, the $(U_i,y_i)$ is broadcasted the above calculation is fine.

When a user $U_j$ gets all $(U_i,z_i,\sigma_i) , 1 \leq i \leq n$, he is ready to verify. Actually, they agree on a key with their neighbors by Diffie-Hellman Key Exchange protocol.


In layman's terms, how does Shor's algorithm work? I've just been reading up on Shor's algorithm, and I find it both fascinating and baffling. I don't understand much about it, other than that it can factor semiprimes in polynomial time.
Could someone explain how it works in layman's terms and why it is reliant on quantum computing?
Keep in mind that while I understand quantum computing basics (i.e., it uses photons instead of electrons, and bits are replaced with qubits that can be 0, 1, or a superposition of both), I don't know anything in-depth about it. I know it's supposedly super-fast compared to classical computing mechanisms.

The question to answer is "Is N the product of P*Q?" I believe that the easiest way to understand Shor is to imagine two sine waves, one length P and one length Q. Assuming that P and Q are co-prime, then the question above can also be answered "At what point does the harmony of P overlapped with Q repeat itself?" And the answer can be determined quickly, based upon the simple observation that we can figure out the phase of each wave at any given point on the number line. (The phase, remember, is "how far along the pattern is this point?" and is often measured in degrees; 90 degrees = 1/4 rotation)

If we look at the point N then the phase of P and Q must be 0 if they are factors of N (or else there would be a remainder of the division N/Q or N/P). Shor just tests whether the phase of P == the phase of Q == 0 at point N. It turns out that phase estimation is pretty easy for quantum computers, so it's a good tool to build into a factoring machine. See http://www.wikipedia.org/wiki/Quantum_phase_estimation_algorithm for more information.


Encrypt text message with Wireguard public key With its public and private key(s), Wireguard looks a bit like PGP. But it is used for encryption of network packets and not normal text messages. I'm on a system with Wireguard already installed and don't want to install more programs than necessary.

How, can I use a public Wireguard key to encrypt a text message which I then can decrypt with a private key?

Wireguard is not PGP. In particular, Wireguard doesn't do several things that PGP does, because doing those things is very difficult to do securely. One of those things is encrypting anything with a public key: Wireguard only does elliptic-curve Diffie-Hellman key agreement.

In general, you should never encrypt a message with asymmetric cryptography (public/private keys) directly. You should either use a Key Encapsulation Mode (KEM), or a Diffie-Hellman style key agreement exchange (probably elliptic-curve based). You then use the resulting shared secret key to encrypt messages using an Authenticated Encryption with Associated Data (AEAD) symmetric cipher, like AES-GCM or ChaCha20-Poly1305 (Wireguard does this).

Asymmetric cryptography is good for key exchange, either with a KEM or a DH agreement. It's also good for signing and verification of messages. It's not good for encryption.


Advantages of a TLS handshake over pre-shared public keys Lets assume the following setup:

A vendor manufactures IoT devices where each is able to generate an individual private/public key-pair. Only the public key is exposed, the private key is assumed to be secured inside the device.
A database of those public keys is provided by the vendor and is transfered to each client out-of-band.

For each connection to a device the client:

gets the ID of the target device
looks up the public key
encryptes a new symmetric key (e.g. AES) with the public key
transfers it, the AES-encrypted data and an AES-encrypted MAC
(further bidirectional data transfers)

Only the selected device can decrypt the symmetric key and thus the rest of the data. Data integrity is verifyed by the MAC.

An attack can happen anytime after the devices were deployed in the field, but please focus on the protocol. Physical side channal attacks or other modifications of the devices themselves should not be considered. The vendor is trusted. Client authentication is not needed.

Question

What are the advantages of a TLS handshake compared to pre-shared public keys?
The simple public key database would be replaced with certificates signed by the vendor to authenticate the devices.

Perfect forward secrecy would be an advantage, other extra features of TLS (like cipher suite selection or session resumption) are not needed.

What are the advantages of a TLS handshake compared to pre-shared
  public keys?

Actually TLS supports raw public keys, so you could actually do what you just described with TLS. Now what it would gain you, for starters, is the fact that you get a protocol which has seen a lot of analysis, which has security reductions, which has some very good implementations and for which  you can somewhat easily / more cheaply buy good security review / consultation on the concrete implementation.

  transfers it, the AES-encrypted data and an AES-encrypted MAC

For example, TLS doesn't do this (in the handshake), because this is known as MAC-then-Encrypt, which is highly discouraged and has lead to attacks on sloppy implementations in the past. Also TLS has eg measures to prevent replay attacks, ie an attacker just sending your device the same handshake and the same record data again as in a previous session.

Beyond that you don't have to use the full flexibility of TLS. You can just turn off and strip away the code for anything but TLS 1.2 and eg ECDHE with RSA and GCM. This will also have the benefit that you can just use a known-good library and don't have to roll your own protocol and thus save dev-time, nerves and benefit from standardization.


Functions that are only second-preimage resistant? Are there functions that satisfy the second-preimage resistance property without satisfying the others (preimage and collision resistance) ?

I'm looking about such functions that compress data (exit the identity function).

Take a function $H:\mathbb S\to\{0,1\}^k$ where $\mathbb S$ is a large finite subset of $\{0,1\}^*$, such that $H$ "compress data" [however this is defined], and $H$ is [conjectured] collision-resistant [thus second-preimage-resistant] and first-preimage-resistant; e.g., SHA-512, for $k=512$. Let $«0»$ and $«1»$ be two public distinct elements of $\mathbb S$. Define $H':\mathbb S\to\{0,1\}^k$ by
$$H'(M)= \begin{cases}H(«1»)&\text{if }M\text{ is }«0»\\H(M)&\text{otherwise}\end{cases}$$

This $H'$ is compressing, and not collision-resistant [argument: $H'(«0»)=H'(«1»)$]. However $H'$ remains preimage-resistant, both first and second [argument: preimage resistance is defined for random message, thus the minor change we made to $H$ in order to build $H'$ does not matter, for odds that a random choice of message hits $«0»$ or $«1»$ are negligible].

Hence $H'$ is second-preimage resistant, but not collision resistant. Which answers the question by the affirmative [I'm reading "without satisfying the others" as "not (satisfying the others)"].

Note: I conjecture without proof that the answer is negative when reading "without satisfying any of the others".

Informal definitions: a function $F$ is

collision-resistant when a [computationally bounded] adversary can't exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$.

Note: these definitions are a compromise between simplicity and precision, but lacking about what random $a$, sizable odds and computationally bounded means. However they can be made formal by making $F$ a parameterized function family; and adding some appropriate parameterized upper bound for the size of that random $a$ when the input domain $\mathbb S$ is unbounded.


How to use salt if I am sending hashed password? If have application that is sending username and hashed password to server for authentication, how would I use salt for this scenario ?

Ask the server for the salt for a specific username.
Compute the expensive salted hash on the client, send to server
Server performs a cheap unsalted hash(or HMAC) on the hash received from the client and compares with the stored value

Note that sending a hashed password doesn't mean you can use an insecure transport. You still need proper transport security, such as SSL/TLS/HTTPS or a specialized password verification protocol such as SRP.


XChacha20poly1305 vulnerability to known plaintext attacks During a security audit, the guy said our cryptosystem is vulnerable to known-plaintext attacks. He said that's because «the implementation uses a crypto_stream_xor() approach» (from libsodium). That's way above my skill, and I did not find anything relevant so far so I'm trying to understand if that's really a problem.

Here is what we do: we derive a key using a global (password, salt) pair. This key −always the same− is used in order to cipher all the documents using xchacha20poly1305. We initialize the stream using xchacha20poly1305::Stream::init_push: it provides us with a header (the nonce ?) that we store with the file for decryption later on. We use rust's implementation of libsodium, sodiumoxide.

Is its assessment correct? (= is xchacha20poly1305 or our usage vulnerable to KPA, and is it due to the fact it uses a xor ?) Didn't the guy mistakingly mixed things with the fact that we reuse password?
How bad is it? Does it mean that someone who can cipher a known document in our system can decipher anything else it puts its hands on?

Edit:
As requested, here is what we do, with more details, using pseudo rust code. I edited out all the irrelevant details but hopefully left enough relevant information and comments.

password, salt, chunk_size are stored in environment variables and never change.

function encrypt(file, password, salt, chunk_size) {
    // first, we derive a key
    sodiumoxide::crypto::pwhash::derive_key(
        &mut key,
        &password,
        &salt,
        pwhash::OPSLIMIT_INTERACTIVE,
        pwhash::MEMLIMIT_INTERACTIVE,
    )

    // Then we initialize the encryption stream
    let (stream, encryption_header) =
        xchacha20poly1305::Stream::init_push(&key);

    // we store the IV
    let encryption_header_bytes = Bytes::from(encryption_header.as_ref());
    store encryption_header_bytes in the output file

    // then we encrypt the file
    buffer = read file content
    while (there are data in the file) {
        // cipher the buffer using xchacha20poly1305's stream
        let encoded = stream.push(&buffer[0..chunk_size], None, Tag::Message).unwrap();
        buffer.advance(chunk_size);
        store `encoded` in the output file
    }
}

function decrypt(encrypted_file, password, salt, chunk_size) {
    // first, we derive a key
    sodiumoxide::crypto::pwhash::derive_key(
        &mut key,
        &password,
        &salt,
        pwhash::OPSLIMIT_INTERACTIVE,
        pwhash::MEMLIMIT_INTERACTIVE,
    )
    // then we read the file in a buffer
    buffer = read encrypted_file content

    // then we read the header, and create a stream out of the header and the key
    let header = Header::from_slice(&buffer[0..xchacha20poly1305::HEADERBYTES])
                        .unwrap();
    stream_decoder = Some(xchacha20poly1305::Stream::init_pull(&header, &key).unwrap());
    buffer.advance(xchacha20poly1305::HEADERBYTES);

    // then we decrypt the rest of the file using said stream
    while(there are data to decrypt in the buffer) {
        let (decrypted, _) = stream
                        .pull(
                            &buffer[0..(xchacha20poly1305::ABYTES + chunk_size)],
                            None,
                        )
                        .unwrap();
        buffer
            .advance(xchacha20poly1305::ABYTES + chunk_size);

        store `decrypted` in the output file
    }
}
```

Using crypto_secretstream that should be fine. It generates a random nonce for each message. Reusing a key in that context is fine.

Original answer, before edit follows:

Yes, that's bad. You have to use a unique IV/nonce for each document.

A stream cipher, such as ChaCha, which is combined with the plaintext using XOR reveals the keystream to anyone who knows the plaintext. That allows them to decrypt other documents. And even if they do not know the plaintext, there can be attacks.

Every document has to have some unique identifier that you can use as a nonce. It does not have to be secret or unpredictable.


Knowing that $G(s)$ is a PRG, is the following construction $G'(s) = G(s||0)$ a PRG? I know there already is a very similar question. However, I can't understand why $G'(s)$ is not a PRG. If $G(s)$ is a PRG, then why $G(s||0)$ can't also be a PRG? How can the distribution over $G(s||0)$ be distinguished from a truly uniform distribution of the same output range?

Knowing that $G(s)$ is a PRG, is the following construction $G'(s) = G(s||0)$ a PRG?

Maybe.

  If $G(s)$ is a PRG, then why $G(s||0)$ can't also be a PRG?

$G'$ can "also be a PRG". (It's just not necessarily also a PRG.)

  How can the distribution over $G(s||0)$ be distinguished from a truly uniform distribution of the same output range?"

$G$ can be such that the last bit of its output is always equal to the last bit of its input.


How do I create a short signature? (e.g. less than 100 bytes) I want to put information into a QR code and have it signed so that the authenticity of the information can be verified. But QR codes have limited storage capacity and when I used e.g. gpg I get signatures typically about 500 bytes long.

For this application it is acceptable to trade some security for both space and convenience.

It would be preferable if there is a way of doing this that can be done with standard or easily obtainable tools such as gpg, openssl or similar.

The usual recommendation is ECDSA, or if you need a really short signature, BLS.  See “Security.SE: What asymetric scheme provides the shortest signature, while being secure?”, “Security.SE: How to encrypt a short string to a short ciphertext using an asymmetric encryption?”, and “Crypto.SE: Short length asymmetric encryption?” for details.

ECDSA should give you a 320-bit signature with approximately 80-bit security.  BLS can get this down to about 160 bits for the signature.  In other words, with ECDSA, you're down to about 40 bytes for the signature; BLS gets you down to 20 bytes.

If even that is not short enough, there are other schemes in the research literature that purport to offer even shorter signatures (e.g., SFLASH, Quartz), though I've heard some cryptographers express doubts about their security, so using them would be really pushing it, bleeding-edge stuff that might get broken.


Fully Homomorphic Encryption over the Integers with Shorter Public Keys I want to implement Homomorphic scheme from the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys.

I successfully implemented key generation by taking $\lambda = 2, \beta = 4, \eta = 4$.

But I am not getting the correct bit after decryption. I think there is problem in encrypting the bit and I am not able to understand how this $2$-dimensional array of $x$ produces $\beta^2$ integers in the encryption function:

$$c = m + 2r + 2 \cdot \sum_{1 \le i, j \le \beta} b_{i,j}\cdot x_{i,0}\cdot x_{j,1} \mod x_0$$

This is code for encryption in which I take an array of 2 rows and $\beta$ columns. Here r is a BigInteger representing a random noise with $4\lambda = 8$ bits, m1 is message, x0 and x[][] are public keys. The random vector b1 is $1$.

Here is the code ---

import java.math.BigInteger;
import java.security.SecureRandom;
public class Encrypt{
    public BigInteger encrypt(BigInteger x0,BigInteger[][] x,int m)
    {
        SecureRandom rnd=new SecureRandom();
        BigInteger r=new BigInteger(8,rnd);//noise 4*λ
        BigInteger two=new BigInteger("2");//constant biginteger of value 2
        BigInteger c=new BigInteger("0");//ciphertext biginteger
        BigInteger summation=new BigInteger("0");//summing x[][] values
        BigInteger b=null,m1=null;//b is random vector and m is message
        int beta=4;//it is  β=√τ
        BigInteger sign = BigInteger.valueOf(new SecureRandom().nextInt(2) * 2 - 1);//used to generate random noise between (-2^ρ1,2^ρ1).
        r=r.multiply(sign).multiply(two);

        for(int i=0;i<beta;i++)  //2 d array with 2 row and beta columns
        {
            for(int j=0;j<beta;j++)
            {
                b=new BigInteger(2,rnd);
                BigInteger b1=BigInteger.ONE;
                b1=b1.multiply(x[0][i]).multiply(x[1][j]);//x[0][0]*x[1][0]+x[0]  [0]*x[1][1]+x[0][0]*x[2][0]+ and so on

                summation= summation.add(b1);

            }
        }
        summation=summation.multiply(two);
        m1=m1.valueOf(m);
        c=c.add(m1).add(r).add(summation);//c=m+2r+2∑x

        //System.out.println("c value "+c);
        c=c.mod(x0);//c=c mod x0
        return c;

    }
}

Any Help Thanks.

If I understood well, you have two issues:

About the $2\beta$ values of $x$ "generating" $\beta^2$ values
About your the bugs in your code.

So, answering (1):   Notice that in the summation (and in your first for loop) for each $x_{i,0}$ you have $\beta$ different values of $x_{1,j}$, which means $\beta^2$ combinations of those $2\beta$ values. You are using the $2\beta$ values you have to perform $\beta^2$ products. Nothing special here.

The point (2) is harder because there are a lot of possible causes to the malfunction of your program. My first guess would be that you are not multiplying $r$ by $2$ in the line

c=c.add(m1).add(r).add(summation);//c=m+2r+2∑x

but it may also be some problem with the intervals each parameter has to belong (are you sure you are respecting them?) or some other restriction imposed on the values. For instance, $x_0$ must be a product of a prime number $p$ with a random odd square free number $q_0$ that does not contain prime factors smaller than $2^\lambda$...

All those restrictions are there to guarantee security or correctness.


Known risks for publishing ECDSA public keys and signatures For an implementation of ECDSA, I'm considering the risks of publishing public keys together with multiple signatures.

From what Google tells me, a common pitfall is the use of the same random value K for multiple signatures.

My question is; are there any other known risks, or common mistakes, regarding the publishing of multiple signatures from one keypair?

ECDSA is advertised to prevent existential forgery even in the face of an adaptive chosen-message attack.  That is: even if the adversary can control the messages you sign, not just see a few signatures, they still can't find a single message/signature pair for a message they didn't ask you to sign.

As part of your obligations of the ECDSA security contract, of course, you must choose the per-signature secret $k$ independently and uniformly at random; if you fail to do this—if you repeat the per-signature secret, or if your choice of it is even substantially biased—then you might leak the private key.  RFC 6979 defines a way to derive the per-signature secret by a pseudorandom function of the message under the secret key, which obviates the need for an entropy source at signing time—or at least mitigates a broken one.

But you could also just use Ed25519, which has this design built-in so you never need to worry about an entropy source at signing time, and has a clearer security story, and is an all-around better design.


What math should I learn to get in depth with Elliptic Curve Cryptography research? My background is computer scientist. I have done applied cryptography research for a while. Currently, I'm working on Elliptic curve cryptography.

To understand the idea and how to use Elliptic curve cryptography (ECC) is not that complicated. I understand basic algebra, EC point addition, finite field, Discrete Logarithm problem, etc.

However, When it comes to improving ECC research, it requires a lot of mathematical knowledge. For instance, if I want to introduce a new curve (like when Bernstein, Birkner, Joye, Lange, and Peters introduced Twisted Edwards curve in 2008) and evaluate its security, or trying to solve Elliptic Curve Discrete Log Problem (ECDLP), what math field(s) should I study?

An Introduction to the Theory of Elliptic Curves (Brown University)

Elliptic Curve Cryptography (Wikipedia)

Performance analysis of identity management in the Session Initiation Protocol (SIP) (IEEE)

Overview of Elliptic Curve Cryptosystems. (RSA.com)

Lecture by Dan Boneh (Youtube)


In bilinear pairings, is it possible to let someone be only able to decrypt ciphertexts in $G_1$ but not able to decrypt the ciphertexts in $G$? For example, in Don Boneh et al.'s paper "Evaluating 2-DNF Formulas on Ciphertexts", they gave an encryption system that the cihpertext can be in either $G$ (when only additional homomorphic operations are evaluated on the ciphertext) or $G_1$ (when one multiplication applies). In such a setting, is it possible to let someone be only able to decrypt ciphertexts in $G_1$ (the target group in bilinear map) but not able to decrypt the ciphertexts in $G$?

No, because the guy who can only decrypt in the target group $G_1$ can take any ciphertext in $G$, use the pairing to map it to $G_1$ and then decrypt in $G_1$ (here I assume the full scheme where the message is a number and not a group element).

You could do it the other way round, i.e., let the guy only decrypt in $G$ and not in $G_1$, by giving him not the full private key $q_1$ but only $g^{q_1}$. Then you force him to decrypt by using a pairing and thus force the ciphertext to be in $G$.


The modes of encryption that preserve the format Can anyone give me some documentation on the various format preserving encryption modes?

I'm aware of only one official specification: NIST SP 800-38G, and recommend to ignore it. Rather, consider NIST SP 800-38Gr1-draft, still unofficial, if something next to a rubber stamp is badly needed.
That draft changes both modes in the official specification, FF1 and FF3, fixing security issues:

The minimal size of the input/output space is increased from a hundred to a million elements (e.g. from two to six decimal digits).
FF3 is changed to FF3-1 with reduced tweak space, following F. Betül Durak and Serge Vaudenay's Breaking the FF3 Format-Preserving Encryption Standard over Small Domains, in proceedings of Crypto 2017.

Note: the NSA reported that FF2 aka VAES3 of NIST SP 800-38G-draft has less than 128-bit security, NIST confirmed that and withdrew it.


What would be the most effective way to brute force a 16 char AES key? I have a file that is encrypted in AES using a 16 char string. The string is (a-zA-Z0-9) and .,?!. Also, it only contains words from a dictionary (but they can be lower/upper case). What would be the most effective way to brute force this?

(No, I'm not trying to brute force passwords. Who would store passwords in AES…)

Based on the comments, it sounds like you know all the requirements/restrictions on the key. One thing that is not clear is if you have a good way of determining if a trial decryption resulted in the proper plaintext. This is usually not a difficult requirement as most data has some structure you could look for. Another important piece of information you are missing (at least as the question is posed) is what mode was used for encryption.

Once you have a plan for both of the items listed above, a dictionary attack is the best you can hope to do as brute forcing the entire keyspace is infeasible. The process is going to be long, but is fairly straight forward. Pick a few words that are less than 17 characters long together. Pad with punctuation to make it 16 characters. Decrypt. Test to see if decryption resulted in the correct plaintext. If not, repeat. You'll want a methodical way to pick words so you don't repeat, but that isn't hard.


ElGamal recovering messages If you use the same ephemeral key in Elgamal, someone can read the future messages. I have two ciphertexts $y_1=62$ and $y_2=4$. The difference between two plaintexts is $x_1-x_2=138$

how do I get $x_1$ and $x_2$? Modulo is $157$

Because the current answers may be a bit cryptic, I'll make a quick write-up of the solution of this one, as the asker has already figured out the solution and the way himself.

First thing to notice: $y_1=x_1\cdot h$ and $y_2=x_2\cdot h$, where $h$ is $g^{ak}$ where $a$ is the recipient's private key and $k$ is the ephemeral key of the message, it's assumed static for this. Let $p$ be the known modulus.

First note that $y_1-y_2=x_1\cdot h-x_2\cdot h=(x_1-x_2)\cdot h\pmod p$ and thus $(y_1-y_2)\cdot(x_1-x_2)^{-1}=h\pmod p$, where $x_1-x_2$ is known. Using this one can recover $x_1=y_1\cdot h^{-1}\pmod p$ and $x_2=y_2\cdot h^{-1}\pmod p$ using the extended euclidean algorithm.


What is degree of randomness in individual bits of MD5 hash? I am researching on Hashing Algorithms and would like to know if we take individual bits of MD5, say we take first 8 bits or any random 8 bits of MD5 then what is the randomness probability of having same 8-bits (at exactly the same position) in any two different MD5 hashes ?

I´ve read somewhere that MD5 being good PRF has uniform randomness in each individual bit. Is this statement true? Also, is there any reference for this?

MD5 was designed with the goal that any change in the input uniformly affects all the bits of the output. It's not perfect, but it's pretty good. If you're choosing the input "randomly enough" (e.g., by appending random bits before hashing) then your question approaches this one:

  Given two randomly generated 8-bit strings, what is the probability
  that they match?

This is $\frac{1}{2^{8}}$.

References:

RFC 1321, Rivest's original description of the MD5 algorithm
How to Break MD5 and Other Hash Functions, by Wang and Yu
The same question
Again
Slightly differently
Yet again
And again


How does partial key escrow work? It is being speculated that one of the ways that NSA leaker Edward Snowden may have created his "insurance policy" – distributing sensitive documents to various individuals with instructions to disseminate them should anything happen to him--is through the use of a partial key escrow.

The concept is described vaguely in the article:

  Modern crypto has lots of ways to accomplish this, including partial key escrow, in which a bunch of encryption keys are distributed to various parties; the individual keys aren't sufficient to decrypt the file, but a quorum of them are. For example, you can release a key to ten people and configure it so that any three can, in combination, unlock the file.

From a technical standpoint, how does partial key escrow work, and how is it most often implemented in practice?

The two most popular ways I am aware of are Shamir secret sharing and additive secret sharing. I'll explain both.

Additive Secret Sharing
I'll start with additive as it is conceptually simpler (but also more limited). I'll also use bitwise addition modulo 2 as the addition operation (i.e., XOR), but know that that isn't the only option. You could use real, no-kidding addition in a finite field (say $\mathbb{Z}_p$ for a prime $p$).

Say I have a key $k$ and a plaintext $p$. I encrypt to get $c=E(p,k)$. Now I distribute $c$ to $n$ friends. I also generate random bitstrings of the same length as $k$, $s_1,\dots,s_{n-1}$. I also set $s_n=k\oplus s_1\oplus\dots\oplus s_{n-1}$. I send $s_i$ to friend $i$. Note that $k=s_1\oplus\dots\oplus s_{n}$. Thus, if all $n$ friends get together, they can reconstruct $k$ and decrypt $c$. If any group of up to $n-1$ of my friends get together they can not reconstruct $k$ and they learn no additional information about $k$ that they didn't already have.

Shamir Secret Sharing
Shamir secret sharing is more complicated, but more powerful. In SSS, I can generate the shares such that any $t+1$ out of $n$ of my friends can get together to reconstruct $k$. Any group of at most size $t$ learns nothing about $k$. It is based on the idea of polynomial interpolation. For example, in school we learned that it takes 2 points to uniquely identify a line. If you only have one point, there are infinitely many lines that could touch that point. If you have 2 points, there is only 1 line. So, what if we encoded the secret $k$ into the line (for example, the y intercept). Then I can distribute different points on that line (excluding the y intercept) to all my friends. Any 1 of them by themselves, cannot figure out the y intercept. But, 2 of them together can reconstruct the line and figure out the y intercept and recover $k$.

SSS uses this idea. Fix a field, say $\mathbb{Z}_p$. Construct the following polynomial:
$f(x)=k+r_1x+r_2x^2+\dots+r_tx^t$ where $r_1,\dots,r_t$ are random field elements. Notice that $f(0)=k$. Send $f(1)$ to one friend, $f(2)$ to another, and so on.

It turns out that any $t+1$ of your friends can then come together and, using lagrangian interpolation, compute $f(0)=k$ to recover the secret $k$. Any group of size at most $t$, however, learns nothing about $k$.


Symmetric : Generate new key from old ones Symmetric keys should be refreshed regularly.

Is is terribly wrong to first agree on $N$ independent keys and then generate the key $k_j$ with $j>N$ by computing some form of hash on the keys $k_{j-100},k_{j-99},...,k_{j-2},k_{j-1}$? The idea being that an attacker would need to know the previous 100 keys to also be able to generate keys.

If it is not wrong, it is at least a little bit useful?

Yes, this idea is good, even though it's usually considered with only one key from which you derive all your following keys.

The "some sort of hash" you describe here, actually is commonly referred to by the name of "key-based key derivation function" (KBKDF) with the most famous instantiation being HKDF, which will also replace the TLS specific counter-part in TLS 1.3.

As for why one doesn't actually use the "cycling idea" your propose here, this has two reasons: a) You have to keep a lot of secret keys secret if you want to have a large $N$ and have $N$ independent keys and b) this solution is worse than simply hashing all $N$ keys in one go (combined with some identifier to ensure uniqueness) and use the derived value, because if only a portion of the keys (i.e. one) is leaked, the corresponding follow-up key is in danger whereas with a full hash nothing bad happens because there's still enough entropy left.

As for why this sort of key-derivation is useful:

Backward secrecy. If your current encryption keys get leaked, an attacker can only predict the ones you'll use in the future but can't recover the old ones.
Key rotation. Rotating the keys limits the number of plaintext-ciphertext pairs an attacker can obtain under the same key which is crucial for most cryptanaltic attacks on block ciphers.


Why are different private and public key generated in online brainwallets? Why is that different wallet generating sites give different public and private keys when you enter the same passphrase even though they both use the same Algorithm (Sha 256)?
Thank you
P.S.
Ok...one site is bitaddress.org and the other site is walletgenerator.net. i tried getting a brainwallet and used the exact passphrase but got different keys. The passphrase was: robertarmenkery.
Obliged

They are the same, bitaddress.org uses an option that you missed; compressed and uncompressed addresses. Turn the compressed address on, then you will get the same values.
They both use base58 while displaying the content when converted to hex
uncompressed
pub  00515da4ade2ea43379043341d158ba1637e695c7b9d942422
priv 8012e29482949d92ef7c159f27065ef7bda744cc0dde8551cc324b312ce6736e24 7af43428

and compressed
pub  00b3f704fd7f30d5868f0e070b7adf75703313775717588aa4
priv 8012e29482949d92ef7c159f27065ef7bda744cc0dde8551cc324b312ce6736e24 01 3445217c

0x08 is always prepended, 0x01 is the indicator for the compression, and the last 4 bytes are trimmed double SHA256 checksum.

Note that generating your private key online is really really a bad idea.


ElGamal scheme attack when one message is known and ciphertexts are intercepted Let $G$ be a finite cyclic group of order $p$ and let $pk = (g, h=g^a)$ and $sk=(g,a)$ be Bob's ElGamal public/secret key pair in $G$. To encrypt a message $m$, a random number $r$ is selected and a ciphertext is set to: $Enc(m):=(g^r,mh^r)$.

ALice uses an PRNG which generates outputs: $r_i$ and encrypts messages $m_1,...,m_k$ obtaining ciphertexts $c_i=(g^{r_i},m_ih^{r_i})$ which are sent to Bob. Every message is intercepted to Eve. Some time later, Eve finds out that $r_{2i}=2r_i$. Moreover she convinces Bob to reveal message $m_j$ ($1\leq j\leq k$). Can she learn a content of any other message? How she can do that? If Eve is able to pick $j$, how many messages she can read? Which one?

Could you help me?

Let's assume that Eve picked $j=J$. She knows about:

$g$, $h$ (parts of public key)
$(g^{r_1},m_1h^{r_1}), \cdots, (g^{r_k},m_kh^{r_k})$ (intercepted ciphertexts)
$m_J$
$r_{2i}=2r_i$

She knows $m_J$ ---> how can she retrieves $r_J$?

I guess that she needs to pick $j=1$. Then she can decrypt $m_1, m_2, m_4, m_8, \cdots, m^{\log{k}}$  ($O(\lg{k})$ messages)

EDIT:
I have some idea without calculating $r_J$. Let

$(c_J,c'_J)=(g^{r_J},m_Jh^{r_J})$

then

$(c_{2J},c'_{2J})=(g^{r_{2J}},m_{2J}h^{r_{2J}})=(g^{r_{2J}},m_{2J}h^{2r_{J}})=(g^{r_{2J}},m_{2J}(h^{r_{J}})^2)$

Let's compute $m_J^{-1} \mod k$. Then:

$h^{r_J} = c'_J m_J^{-1}$

and:

$m_{2J} = c'_{2J} (h^{r_J})^{-2}$

and go on, and go on... am I right?

Knowing the message $m_j$ should not help you to get $r_j$. In-fact, ElGamal is assumed to be CPA secure (assuming that DDH is hard). Meaning that even if we choose two different plaintexts and give them to alice and she is encrypting only one of them, we won't be able to know which one she encrypted.

You can easily show that if you could retrieve $r_j$ ElGamal won't be CPA secure, as your can try both messages and try to retrieve $r_j$, you will only succeed when you try the right message.

Moreover, you are right about the messages Eve learns and how she does that.


RSA: Letting $p$ and $q$ have different bit-size I am aware that there are concerns if $p$ and $q$ are close i.e. $\Delta=|p-q|$ can't be too small. But I would like to know if there are any known attacks for cases where $p$ and $q$ take on different bit-sizes. (Don't mention extreme cases where the bit-size is close to the modulus.)

Are there vulnerabilities? Can we select $k\pm i$ bits for $p$ and $q$ respectively (where $k$ is the bit size of the modulus and $i$ a small integer)?

No, there is no specific vulnerability associated to choosing $p$ and $q$ with size differing by $i$ bits (or $2\cdot i$ bits as in the statement) for small $i$. However, if $i$ gets too big:

That improves the odds that ECM will manage to factor $n$ for some fixed size of $n$, and at some point ECM will become the best algorithm; this is the case if $i$ is about one fourth of the modulus size, perhaps lower.
That reduces the speed benefit one can gain from CRT for the private key operation.

Also: unless $i$ is a multiple of $32$ or $64$, that implies one at least of $p$ or $q$ does not have a bit size exactly multiple of $32$ or $64$; in turn, that implies an implementation using the CRT can't assume that $p$ and $q$ have a bit size exactly multiple of $32$ or $64$, which is customary and slightly simplifies implementation.

And more generally, $i\ne0$:

Is not standards-conforming: in the venerable ANSI X9.31:1997, and its current successor FIPS 186-4, $p$ and $q$ of an RSA modulus must both have exactly half the bit size of the modulus (among other requirements).
Reduces the odds that a key generated on some device can be successfully used as a private key on a different device (it has no impact on usability as a public key, as long as the modulus size remains standard). Addition: an hypothetical CRT implementation of the private exponent exponentiation modulo $n$ that fails to handle one of the exponentiation modulo $p$ or $q$ because of its unusual size, and does not check its final result using the public key, much likely leaks information leading to factorization of the modulus; thus the issue is not only an interoperability issue, it could be a security issue too.

Most importantly, precautions aimed at insuring that $\Delta=|p-q|$ is big enough are technically pointless: the justification given to such precautions is protection against Fermat factoring, which in its most basic form enumerates integers $b$ from $0$ onwards, stopping when $n+b^2$ is a square $a^2$, revealing $q$ as either $(a+b)/2$ or $(a-b)/2$. However, all known improvements of Fermat factoring have fully negligible odds to succeed in factoring $n=p\cdot q$ with $p$ and $q$ of equal size at least $256$ bits, but otherwise mostly random (for the number of $b$ to enumerate by the basic Fermat factoring method is $|p-q|/2$, which is higher than $2^{212}$ with odds better than $1-2^{-40}$, and none of the known improvements lowers that $2^{212}$ steps to something workable). If $p$ and $q$ are known to have the same size and the same leading $50$ bits, GNFS is still a much better choice than Fermat factoring .

As an additional argument, if the adversary had a Fermat factoring variant with sizable odds to factor $n$ knowing that $p$ and $q$ are of equal size, then that method likely can be adapted to $q$ known to be $i$ bits bigger than $p$, much like the basic Fermat factoring can be adapted to the situation $q\approx2^i\cdot p$: enumerate odd $b$ stopping when $2^{i+2}\cdot n+b^2$ is a square $a^2$, revealing $q$ as whichever of $(a+b)/2$ or $(a-b)/2$ is odd.

According to my memories of Robert Silverman's account: the requirement in ANSI X9.31 (kept in FIPS 186-4) that $|p-q|$ must be more than $100$ bits less than half the modulus bit size (for $1024$-bit modulus and higher) was introduced to please the bankers chairing at the standard's committee, who wanted that there is a simple rebuttal to a court argument on the tune of: " I claim that my client did not produce that signature! One simple explanation is that the modulus has been factored. An expert has testified that Fermat factoring, known since the 17th century, potentially could do that, and allow such forged signature. No precaution against it was taken! Whoever carelessly specified that signature system must bear the consequences! "


Algorithm for proving Carmichael numbers I have an application for determining if a number is a prime or not, currently I'm getting a random number, then doing the Fermat primality testing to find out if the number is probably prime (so this can still be a Carmichael number), I then test with a Miller-Rabin algorithm to determine if the number is probably prime (with probability of 2^-81 that this can still be a composite).

My questions are:

Is there an algorithm to find out if a number is a Carmichael number (deterministic or not)
Does proving Fermat primality test and the number is not a Carmichael one is enough to prove that the number is a real prime

Well, yes, there is a probabilistic polynomial time algorithm the determines whether a number is a Carmichael number of not (probabilistic in the sense that it  always returns the correct value, it terminates quickly with high probability).  However, it isn't as helpful as you are thinking for your application.

The algorithm is based on two observations:

Carmichael numbers are easy to factor
Given the complete factorization, it is easy to verify whether a number is a Carmichael number or not (Korselt's criterion, as Thomas mentioned).

Here's the details on the first observation: if we have a composite number $N$, and an even value $e$ for which $x^e \equiv 1 \bmod N$ for a nontrivial fraction of the values $x$, then we can factor $N$.  We do this by computing $\lambda$ a power of 2 such that $e/\lambda$ is odd, and for random values of $x$, compute $x^{e/\lambda}, x^{2e/\lambda}, x^{4e/\lambda}, ..., x^e$.  If the series ends in 1 (which it will with good probability; that's the condition we placed on $e$), we look at the value immediately previous to the first 1; if that value $x^{ke/\lambda}$ is not -1, then we have the nontrivial factors $gcd(N, x^{ke/\lambda}-1)$ and $gcd(N, x^{ke/\lambda}+1)$ (because $x^{ke/\lambda}$ is a nontrivial square root of 1).  In addition, if $N$ has more than 2 factors, this yields a random factorization of $N$.

Now, if $N$ is a Carmichael number, then $e = N-1$ is such a value; in fact, for any $x$, we have either $gcd(x,N)>1$ (and hence we have a factorization of $N$), or $x^{e} \equiv 1$ (and hence we have a factorization with good probability).  In addition, if we pick a value $x$ and we find that $gcd(x,N)=1$ and $x^{e} \neq 1$, then we've just shown that $N$ is not a Carmichael number.

Hence, the probabilistic algorithm would look like:

Check if $N$ is prime; if it is, then return FALSE.
While we have don't have a complete factorization of $N$

Select a random $x$
If $gcd(x, N)=1$ and $x^{N-1} \ne 1 \bmod N$, then return FALSE.
Otherwise examine $gcd(x, N)$, $x^{(N-1)/\lambda}$ for a nontrivial factorization of $N$
If we have found a nontrivial factor, use that nontrivial factor to attempt to find more prime factors of $N$

Once we have a complete factorization of $N$, apply Korselt's criteria to determine whether $N$ is a Carmichael number.

This answers your question, however it's not very useful for determining whether a number is prime.

On the other hand, if you need an algorithm that produces large prime numbers, and you aren't happy with probabilistic methods, have you considered the Shawe-Taylor algorithm appendix A.1.2.1?  The numbers this algorithm generates are guaranteed prime, and my experience is that it is about as fast as searching for primes using a Miller-Rabin test.


RSA with small exponents? Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse of $d \bmod \varphi(n)$).  Given a plaintext message $m$, we obtain the ciphertext $c = m^e \bmod n$; we subsequently decrypt the ciphertext by calculating $c^d \bmod n$.

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long.  I decide to make my implementation run faster by choosing small values for $e$ and $d$ (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?

First I must state that a secure RSA encryption must use an appropriate padding, which includes some randomness. See PKCS#1 for details.

That being said, $d$ is the "private exponent" and knowledge of $d$ and $n$ is sufficient to decrypt messages. $n$ is public (by construction) so $d$ must be kept private at all costs. If it is very small then an attacker can simply try values for $d$ exhaustively.
On a more general basis, if the size of $d$ is lower than 0.29 times the size of $n$ (in bits) then there exists an efficient key recovery attack. The accepted wisdom is that trying to get a $d$ much smaller than $n$ is a bad idea for security.

On the other hand, there is no problem in having a small $e$, down to $e = 3$. Actually, with RSA as you describe, there is a problem with a very small $e$: if you use $e = 3$ and encrypt the very same message $m$ with three distinct public keys, then an attacker can recover $m$. But that's not really due to using a small $e$; rather, it is due to not applying a proper padding.


A file chunk in a group/field I am reading a paper by Shacham and Waters on Compact Proofs of Retrievability. In this paper on page number 3 under section 1.1 in the very first line the author states that an encoded file is broken into n number of blocks $m_1,m_2...m_n \in Z_p$ for some large prime p.

I am not able to understand that in terms of programmimg what does it exactly mean to have a chunk of file data in a group/field. On the same page they mention an equation:

  $σ_i = f_k(i) + αm_i \in Z_p$

What is the value of this $m_i$ in this equation. Is it the number of bytes/bits in each block? What value of $m_i$ would I take if I have to calculate this $σ_i$ in the equation ? The calculated value of sigma lies in the group of prime order $Z_p$.

I am not sure if I have posted the question in the right forum but I could not get any comments in stack overflow hence I have posted it to a forum I find closely related to. Any help will be valuable.

Thanks and Regards

You have to split your file in such way that each block will be smaller then prime $p$ you're using. After that you have $n$ such blocks.

You calculate $\sigma_i$ for every block so $i \in \{1,2,...,n\}$ and $m_i$ means block number $i$

Example:

  Assume you're working in field $Z_p$ with $p=2^{255}-19$ (used in Curve25519 for example) and your file is 254 bytes or $254 \times 8$ bits long. In practice you can split it to blocks of (at most) 254 bits as $2^{254} \ll 2^{255}-19$. You can split your file to 8 parts, each 254bits long. So you have $n$=8, and each $m_1,m2,m3,m4,m5,m6,m7,m8$ are respective blocks from file.

Example2:

  Assume you're working in field $Z_p$ with $p=2^8+1$ and your file is 5 bytes long. You can split it to blocks of 8 bits as $2^8 \lt 2^8+1$. So you have 5 such parts and $n=5$ and $m1,m2,m3,m4,m5$ are respective bytes from file.

Please note that second example is in no way secure as target field is way too small.