GCM cipher M0 tables : semantic questions on how to implement GCM I`m reading the PDF "The Galois/Counter Mode of Operation (GCM)". In section 4.1 on the optimization of multiplications with tab, in algorithm 3 I have the following questions:

A vector called M with 128 bits is created, then the value of H is copied into that vector, now M [128] is the same as H, is not it? Or is it after those 128 bits? In programming would be that way.

If I believe that the 128-bit vector is created, and these remain null. because if not the while cycle does not make sense. in this the value of i is multiplied by 2 this results in 128, and the principle of H would be multiplied with the plain text?

P in the plain text, but no matter how long this is, only the first 128 bits of the plain text will be multiplied with H?

Later, it is stored in the vector, but it is being overwritten by what I see in the division of i / 2?

$M$ is a table with 256 elements, where each element has 16 bytes (128 bits), such that $M[x]$ is equal to $x \cdot H$

In the first step, the 128-th element is set to $H$, i.e. $M[128] = H$. The reason for that is the confusing bit order convention of GCM (see What does GHASH really do?). GCM works with binary polynomials, and the polynomial $1$ is represented, as a byte, as the integer value $128$ (e.g. $1000000$ in binary) instead of of $1$ (e.g. $00000001$ in binary). Therefore, what the first step is doing is setting $M[1] = H$, if GCM were defined with a more conventional bit order.

The rest of your confusion probably arises from the same issue. So anywhere you see $M[i]$ in the algorithm, pretend it's $M[rev(i)]$ where $rev$ reverses the bits of the input, and things may start to make more sense.

Also, $P$ is not the plaintext, it's the polynomial $\alpha$ (i.e. $010000...0$)


Can I select a large random prime using this procedure? Say I want a random 1024-bit prime $p$.  The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests.

But suppose instead that I do this:

select random odd 1024-bit number $n$
if $n$ is prime, return $n$
$n \leftarrow n+2$
goto 2

(This approach allows faster selection of primes via sieving.)

Since primes are not uniformly distributed on the number line, it would seem that this algorithm prefers primes that lie after long runs of composites.  Take a piece of the number line around $2^{1024}$ with x denoting a prime:

  ---x-x----------------------------x------------------------x---x

Clearly our algorithm above is much more likely to find the 3rd prime above than to find the 2nd one.

Question: Is this a problem?

This procedure is known as incremental search and his described in the Handbook of Applied Cryptography (note 4.51, page 148). Although some primes are being selected with higher probability than others, this allows no known attacks on RSA; roughly speaking, incremental search selects primes which could have been selected anyway and there are still gazillions of them. OpenSSL uses this prime generation technique.


Why use a 1-2 Oblivious Transfer instead of a 1 out of n Oblivious Transfer? When initiating an oblivious transfer, why would someone use a 1-2 oblivious transfer rather than going for an 1 out of n oblivious transfer? Perhaps a slight time overhead for the extra message encrypts, but with everything as fast as it is these days is that a concern?

Oblivious transfer is mostly studied as a theoretic construction, as it is an important component in achieving interesting protocols (like secure two-party computation and secure function evaluation).

The interest in 1-2 OT is that it is a minimal definition theoretically, and most results that limit themselves to 1-2 are designed to improve some basic properties (number of rounds) or advanced security properties (full simulatability, plain model, UC-secure, etc), as opposed to being designed for real-life implementations. Although some proposals claim to be "efficient", that typically means they are efficient for the level of security they realize, and this level is usually much higher than something you would need for implementation.

A second reason for the interest in 1-2 OT is that OT is often used to securely evaluate boolean circuits. In this particular application, the circuit in constructed from binary gates have only two outputs: so 1-2 OT suffices. However if gates were replaced with more complicated truth tables or if transfers were batched together, 1-N OT might be of interest.

OT is a primitive that rarely finds its way into an implemented/deployed tool. The only application I know of is two-party computation tools based on Yao's garbled circuits, for which some implementations exist. One example is FairPlay and it its original paper, there is some interesting discussion on the overall efficiency of switching between different types of OT. It does however leave implementing 1-N OT for future work.

A MPC tool was also used to run a Danish beets auction however it did not employ OT. Many two-party or multi-party computations try to avoid using the general construction based on OT since it is very inefficient, the OTs themselves are usually the most expensive part, and typically the jump from two-party to multi-party computation means using a different blueprint based on secret sharing instead of OT.


KeeLoq showing that decryption is indeed the inverse of encryption? In some text I am reading, there is an exercise asking to show that KeeLoq decryption function is the inverse of the encryption function. Details about KeeLoq are given in the Wikipedia article.

As I am no hardware guy, I have no clue how to approach this problem. Does someone happen to see, how to show the requested property?

It is difficult to find a complete specification, so I'm going by the Wikipedia article you linked.

These images (public domain, from Wikipedia) describe one round of the encryption/decryption algorithm, with 528 rounds in total. At the start, the plaintext is put into the 32-bit shift register, and at the end the ciphertext is taken out of it (for decryption, the other way around).

In each round, actually only one bit of data is actually changed (the new bit with number 31 for encryption, 0 for decryption), the other bits are only shifted around.

If we number all the bits in the "data queue" over time by $L_0 \dots L_{559}$, with
bit $j$ before round $i$ being $L_{i+j}$, $L_{i+32}$ is the new bit 31 after round $i$, and we can describe the encryption algorithm as follows (from the text to Figure 1 (page 9) in Periodic ciphers with small blocks and cryptanalysis of KeeLoq, which features a similar image):

  Initialize with the plaintext: $L_{31}, \dots, L_0 := P_{31}, \ldots, P_0$.
  For $i = 0, \ldots, 528 − 1$ do
  $$L_{i+32} := k_{i\ \bmod\ 64} ⊕ L_i ⊕ L_{i+16} ⊕ NLF(L_{i+31}, L_{i+26}, L_{i+20}, L_{i+9} , L_{i+1})$$
  The ciphertext is $C_{31}, \ldots, C_0 := L_{528+31}, \ldots, L_{528} $

The decryption is similar, but here we number the rounds from 528 to 1, and the bits over time as bit $j$ before round $i$ is $L_{i+j}$. $L_{i-1}$ is the output of round $i$.

  Initialize with the ciphertext: $L_{528+31}, \dots, L_{528} := P_{31}, \ldots, P_0$.
  For $i = 528, \ldots, 1$ do
  $$L_{i-1} := k_{i-1\ \bmod\ 64} ⊕ L_{i+31} ⊕ L_{i+15} ⊕ NLF(L_{i+30}, L_{i+25}, L_{i+19}, L_{i+8} , L_{i+0})$$
  The plaintext is $P_{31}, \ldots, P_0 := L_{31}, \ldots, L_{0} $

Now all that stays to show is that both equations
$$L_{i-1} = k_{i-1\ \bmod\ 64} ⊕ L_{i+31} ⊕ L_{i+15} ⊕ NLF(L_{i+30}, L_{i+25}, L_{i+19}, L_{i+8} , L_{i+0})$$
and
 $$L_{i+32} = k_{i\ \bmod\ 64} ⊕ L_i ⊕ L_{i+16} ⊕ NLF(L_{i+31}, L_{i+26}, L_{i+20}, L_{i+9} , L_{i+1})$$
are indeed equivalent. (This is a simple index-shift, and reordering some terms.)


Creating a private cryptocurrency without trusted setup I am interested in creating a cryptocurrency which keeps the sender, the receiver and the amount private and does not require a trusted setup.

I have already read the Zerocash protocol but It uses zk-SNARKs which require trusted setup.
I have also read the Bulletproofs protocol which creates short proofs and without a trusted setup so it would be great to use it.

The problem is that Zerocash creates commitments and calculates the address public key using hash function. I would like not to have to prove that a hash function was computed correctly because the proof would be long ans slow.
The second problem is that in Zerocash the sender proves that he owns that address private key and some random numbers such that they combined create a commitment that exists in the Merkle-tree of previous created coin commitments. I cannot find any protocol for proving set membership of a commitment C ϵ S that I know it’s opening; I can only find the opposite (i.e. to prove that one item x ϵ S is the opening of a commitment C).

Is it possible to prove that I know an opening x of a commitment C ϵ S without revealing neither the x nor the C and without a trusted setup?
Is it possible to create/link the address public and the address private without a hash function such that the sender can create that commitment with the address public and the receiver can prove the above with the address private key? What type of commitment would be possible?
How Is possible to fit the coin’s value and the nullifiers to all this? Does a cryptocurrency like that exist?

Thanks.
P.S.
Links to technical papers are welcome.
If this questing best fits in bitcoin.stackexchange.com please let me know.

The cryptocurrency you're describing does currently exist and implements, among other features, using unique Spend/View Keys in Monero (XMR). It capitalizes on a number of clever cryptographic techniques to implement a hardened total anonymization of source/destination (Ring Signatures/Stealth Addresses) and quantity (Ring Confidential Transactions/Bulletproofs).
It has also focused on maintaining a robust decentralized network via the (previously CryptoNote, GPU-optimized) RandomX PoW algorithm (CPU-optimized) that is highly ASIC-resistant, maintaining an optimal network dissemination by preventing any mining dominance by any centralized entity.
The original PoW and subsequent whitepapers can all be found at the webpage for the Monero Research Lab: https://web.getmonero.org/resources/research-lab/


Is there any existing cipher capable of scaling from a 1 bit key up to a one-time-pad? We have ciphers that handle small amounts of entropy, such as a 256 bit key for AES; and we have one time pads for enciphering 1:1 entropy, such as a 1GB key for a 1GB file if you could ever harvest enough decent random noise.

Now in theory you would imagine that there is a universal class or model of cipher that can scale smoothly from a single bit of entropy all the way upto a 1:1 one time pad.

If such an algorithm or cipher already exists - what is it called?

a one time pad ia very different from other fixed key ciphers.
A one time pad is just a xor(or modular addition) It does not miz anything or extend key and even a tiny bit of key reuse is very problematic.
We have stream ciphers which take a key and produce an infinite stream of pseudo random bits.
Perhaps what you are asking for is for a cipher with arbitrary key size with guranteed perfect security for total message length less than key size and reasonable security for reasonable key sizes.
I can suggest the following construct. take the key and duplicate it by concatenation to produce naive infinite key.
Use Each key block to encrypt a counter like in CTR mode.
This by itself doesn't give perfect secrecy. You could then xor each block with the following key block. That would give  perfect secrecy when message is at least one block less than key. It might be possible to do better. But this construct will give at least the security AES CTR.


How much computing resource is required to brute-force RSA? It's been over 30 years since Rivest, Shamir and Adleman first publicly described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for around 40 years—possibly longer.

It's fair to assume that, during those 40 years, certain three-letter organisations have employed their vast resources toward "breaking" RSA.  One brute-force approach may have been to enumerate every possible key-pair such that, upon encountering a message known to be  encrypted with a particular public-key, they need merely lookup the associated private-key in order to decrypt that message.  Signatures could be forged similarly.

How reasonable is this hypothesis?  How much computing resource would have been required over those 40 years to enumerate every possible {1024,2048,4096}-bit key-pair?  I think it best to avoid discussion and leave the question of whether the spooks could have harnessed such resource as an exercise to the reader.

It's not possible.

The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of $512$ bit primes (approximately the length you need for $1024$ bit modulus) is approximately:

$$\frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151}$$

The number of RSA moduli (i.e. pair of two distinct primes) is therefore:

$$\frac{(2.76×10^{151})^2}{2}-2.76×10^{151}=1.88×10^{302}$$

Now consider that the observable universe contains about $10^{80}$ atoms. Assume that you could use each of those atoms as a CPU, and each of those CPUs could enumerate one modulus per millisecond. To enumerate all $1024$ bit RSA moduli you would need:

\begin{eqnarray*}
1.88×10^{302}ms / 10^{80}&=&1.88×10^{222}ms\\
&=&1.88×10^{219}s\\
&=&5.22×10^{215}h\\
&=&5.95×10^{211} \text{years}
\end{eqnarray*}

Just as a comparison: the universe is about $13.75×10^9$ years old.

It's not a question of resources, it's simply not possible.

Also, it would not make any sense to do that. There are much faster ways to find out a secret key. In fact there are algorithms with sub-exponential running time for factoring integers.


What kind of symmetric-key algorithm to use with Diffie-Hellman? Let's assume we use DH with a cyclic group modulo p. As I know safe length of p must be at least 1024 bits. That means that generated key could be very big. But what do next? What kind of symmetric-key algorithm to use? DES requires key length to be exactly 56 bits. AES - 128/192/256 bits. We have no guarantee that key generated by DH will be n bits. It could be longer or even shorter. Do we have to reduce or extend key to fit it in AES or (3)DES? Or is there an algorithm that works with any key length?

What you are looking for is a key-derivation function.

As you have correctly observed one can make mistakes when using a shared secret and the KDF does exactly what you want.

A typical implementation would be a hash.

Note that short keys are not really an issue here. They should only occur with appropriately small probability and when padded with zeros would be acceptable keys.


Why does dragonfly key exchange need hunting and pecking? The dragonfly key exchange scheme (as used by WPA3) received criticism because the way it chooses a generator of the elliptic curve group ('hunting and pecking') is a non-constant time algorithm making it vulnerable to side-channel attacks.
My question is: Why is hunting and pecking used at all?
Assume there is a known generator $G$ for a group of prime size, then $G^P$ would also be a generator of the same group (if $P$ is not a multiple of the group size). With $P$ being a password-derived number (as with the dragonfly scheme as is), this way one would obtain a generator just as random and unpredictable as with hunting and pecking, no?
Where is the mistake in that reasoning?

Where is the mistake in that reasoning?

The problem is that would allow an attacker to test multiple passwords with the same exchange, hence losing the PAKE properties that we were trying to achieve.
With dragonfly, the honest side selects a secret values $p, m$, and outputs the values $s = p+m$ and $P = -m \cdot SKE$, where $SKE$ is the 'secret key element', that is, the one that you suggest to be derived $SKE = [password]G$ (I'm writing it in additive notation because hunt-and-peck comes into play in Dragonfly only if you're using elliptic curves).
Then, the honest party receives values $s'$ and $P'$ from the other side (the adversary), and then computes the secret key:
$$H( p( P' + s' \cdot SKE ))$$
and then sends an encrypted message based on that key (that is, if the adversary somehow obtains a guess to the same key, he can decrypt the message, and thus validate the key).
With your proposal, the attacker will know the discrete log of any SKE, that is, the value $x$ s.t. $xG = SKE$.  So, what the attacker can do (after receiving the honest peers's $s, P$ values) is select arbitrary $s', P'$ values (for which he knows the discrete log of $P' = p'G$) and send those, and then receive the encrypted password based on the value the honest party computed.
Then, for every password in his dictionary, computes the corresponding $SKE$ and $xG = SKE$ and then computes:
$$H( (p'+s'x)(sG + x^{-1}P))$$
If the guess for SKE was correct, this is the same secret key that the honest party computed, and that can be validated.
This can be seen to be the same because, if the SKE is the value the honest party used, then $pG = sG + x^{-1}P$ and $p' + s'x$ is the discrete log of $P' + s' \cdot SKE$
The attacker can perform all this computation for every password in his dictionary, hence he can test every password as the result of a single exchange.
Now, DragonFly doesn't have to use hunt-and-peck; there are other known hash-to-curve transforms that convert a password to an EC point in a way that you can't compute the discrete log.  However, DragonFly needs to use some such method...


Is Quadratic Arithmetic Program NP-complete? I'm reading this paper: Quadratic Span Programs and Succinct NIZKs without PCP
Is QAP NP-complete? as same as QSP?

QAP, like QSP, are a characterization of NP. They naturally capture arithmetic programs. Their advantage over QSP is that they lead to more efficient SNARGs for statements whose verification procedure is compactly represented by an arithmetic circuit. They have at least the same power, and you can represent the verification algorithm of arbitrary NP languages (hence also NP-complete languages) using them. Note that they are a computation model, not a language, so it does not mean anything to say that QAPs (or QSPs) are NP-complete - but they do capture all of NP.


Can a cryptosystem be unconditional secure if the same key $k \in \mathcal K$ is used for more than one encryption? Can a cryptosystem be unconditional secure if the same key $k \in \mathcal K$ is used for more than one encryption ?

I know that the one-time-pad doesn't have perfect secrecy and doesn't provide unconditional security provided the same key is used for more than one encryption.

Is this general for all encryption schemes, that unconditional security is unachieveable given that a key is used repeatedly ?

It is easy to construct an unconditionally secure encryption scheme where the key is reused to encrypt multiple messages. Simply take any unconditionally secure encryption scheme that can be reused $1$ time and then to generate keys sample $m$ keys of this original scheme (e.g., $m$ OTP keys). Now you can use these $m$ keys to encrypt $m$ messages and obviously the security is still that of the original scheme.

Of course, you may argue that this is 'cheating', because now we have an encryption scheme with keys of size $n\times m$, where $n$ is the size of a message. However, this cannot be helped. For the scheme to be unconditionally secure the key must be at least as long as the total amount of bits we can communicate using it. To see why this is the case consider that to have perfect secrecy given a series of ciphertexts any series of messages must be equally likely. This means that for each series of message bits (combining all the messages sent) we need one distinct key, i.e., the key must be at least the size of the total amount of bits encrypted.


Permutations coming from RSA The RSA algorithm can be used to generate a permutation.

Given two prime numbers $p$ and $q$, the key length is $n=pq$.

If $a$ is the private key, then $b$ is the public key, where $ab \equiv 1 \pmod {\phi(n)}$.

We define a permutation $\pi : \mathbb Z/n\mathbb Z \to \mathbb Z/n\mathbb Z$,
given by $\pi(k) = k^b \pmod n$.

Is anything known about these permutations from a group-theoretic point of view?

If you write $\mathbb Z/n\mathbb Z$ first as $\mathbb Z/p\mathbb Z\times \mathbb Z/q\mathbb Z = \mathbb F_p\times\mathbb F_q$, and then $\mathbb F_p$ as $\mathbb F_p^\times\cup\{0\}$ (and the same for $\mathbb F_q$), then you see (using the discrete logarithm) that taking the $b$-th power in $\mathbb F_p^\times$ corresponds to multiplying by $b$ in the cyclic group $\mathbb Z/(p-1)\mathbb Z$, where $b$ is coprime to $p-1$ by assumption.

If $p-1 = \prod_i p_i^{e_i}$ is the prime power factorization of $p-1$, then you get $\mathbb Z/(p-1)\mathbb Z = \prod_i \mathbb Z/p_i^{e_i}\mathbb Z$ and you have to investigate what multiplication by $b$ (coprime to $p_i$) does to $\mathbb Z/p_i^{e_i}\mathbb Z$.

Writing $\mathbb Z/p_i^{e_i}\mathbb Z = \cup_{j=0}^{e_i} p^{e_i-j}(\mathbb Z/p_i^j\mathbb Z)^\times$ you'll see that you have to determine only the order $o$ of (multiplying by) $b$ in $(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ (as it gives the order of $b$ in $(\mathbb Z/p_i^j\mathbb Z)^\times$ for all $j\le e_i$ --- slight caution is necessary for $p_i=2$ as only for odd $p_i$ one has $(\mathbb Z/p_i^j\mathbb Z)^\times = (\mathbb Z/p_i\mathbb Z)^\times\times \mathbb Z/p_i^{j-1} \mathbb Z$, whereas $(\mathbb Z/2^j\mathbb Z)^\times = (\mathbb Z/2\mathbb Z)\times \mathbb Z/2^{j-2} \mathbb Z$ for $j>1$). Multiplying with an element of order $o$ in a group of order $g$ gives $\frac{g}{o}$ cycles of length $o$.

Now you have to assemble everything again using either the product structures or disjoint unions.

If you were just interested in the order of the permutation, take just the least common multiple of all group orders at the level of $(\mathbb Z/p_i\mathbb Z)^\times$ and $\mathbb Z/p_i^{e_i-1} \mathbb Z$ (don't forget to do the same for $q$ and beware of $p_i=2$).


A Modernized Enigma? I've seen answers here and elsewhere discussing how well the WWII Enigma could hold up to modern cryptanalysis, however, those answers always seem to assume the WWII conditions where the Germans had a limited number of rotor constructions, repeated patterns of plain text, and the Allies had access to a lot of the info about the rotors, their wirings and the limited combinations in use.

What if a software based enigma were executed with the following conditions:

38 characters (versus 26)
ten rotors
the rotor settings, stecker settings, and rotor permutations themselves change with each message, all pre-planned using a cryptographically secure PRNG (i.e., the operator no longer chooses and transmits settings in a preamble)
assume (for sake of argument) no cribs and physical security - i.e., the attacker might have access to the encryptor, but not to any keys

How well would this hold up to modern cryptanalysis using super computers or networks? How long might it take to brute force it?

I've seen answers here and elsewhere discussing how well the WWII Enigma could hold up to modern cryptanalysis, ...

Ehm, quote? I would say, the general opinion about the Enigma is actually the very opposite. The Enigma is the prime example why such a drastic change in the cryptographic mindset was necessary, where it is not enough if you can't break your own cryptosystem yourself.

Cryptanalysis has gone a long way since then, and today it is not enough to be resistant to ciphertext-only attacks. Back then, the attacks on the Enigma were made much easier by having some partial known plaintexts.
Today we even assume the attacker to have a lot of plaintext/ciphertext pairs. And known-plaintext attacks are the very least what we consider secure today.

So building a new scheme from an old-and-broken design is quite a bad idea. In today's binary world (in computers) using any other alphabet does't make sense.

And then there is one more thing: You suggest having an RNG responsible for the choice of the rotors. They are what provides confusion and diffusion in the Enigma... but randomly chosen functions are really bad at that. There is a reason, why those steps are never chosen randomly in block ciphers.

So to answer your questions: Probably you can break it with a known plaintext attack within seconds on a normal computer. Brute force or ciphertext-only attacks don't matter at all (unless brute-force is the best known stragety). So even if the brute-force attack cannot be done within reasonable time, it doesn't matter.


Has the Linear Congruent Generator ever been used in any of the early crypto algorithms? The Linear Congruent random number generator is the simplest kind of pseudo random number generator. I know that its now long broken. But I am curious -- has it ever been used in any of the early crypto algorithms, say 70 years ago? Or has it been used for basic statistical simulations from day one. I read somewhere that it was used in the old IBM-360 computers. I am curious what it was used for.

It is indeed the case that the linear congruential generator was used—or at the very least suggested—for cryptographic purposes early on. Below are three examples, but it is likely that there are many more.

In 1982 Vahle and Tolendino broke an encryption scheme based on a linear congruential generator. However, no details about where this encryption was being used were given.

In 1965, Maclaren and Marsaglia proposed a generator that combined two congruential generators, which in their specific instantiation were
$$
\begin{align}
x_{i+1} &= (2^{17} + 3)x_i \bmod 2^{35}, \text{and}\\
y_{i+1} &= (2^7 + 1)y_i + 1 \bmod 2^{35},
\end{align}
$$
after which the output $z_i$ is computed as $y_{x_{i \bmod 128}}$. This was, however, not meant as a cryptosystem by its authors. Nevertheless, in 1984 Retter did find this system used to encrypt real-world data at Data General, and furthermore broke it by reducing its strength to just one of the generators. He also found that another system, the CSI-10 cryptographic unit, using the same kind of encryption scheme.

Perhaps more famously, in 1980 Knuth devised a method to break truncated linear congruential generators. The paper starts by saying

  Therefore, it has been suggested that the leading bits of such a
  sequence might be useful for enciphering data.

There is no associated citation, but it is not unreasonable to deduce that this was a popular idea during this time period. Other contemporary attacks on LCGs include Reeds and Plumstead.

Another class of random number generators very popular during this period were ones based on LFSRs, which are more hardware friendly. Many LFSR-based schemes appeared in the 60s and 70s, the vast majority of which ended up broken. Ritter's survey, starting with the Twigg generator, is a good place to start.


Are low security curves for ECDSA not supported? I am working in a very bandwidth restricted environment, and we are looking to implement ECDSA digital signatures. Although they are no longer recommended, we might be looking to use curves that are not listed as supported by most libs, including OpenSSL: https://en.wikipedia.org/wiki/Comparison_of_TLS_implementations#Supported_elliptic_curves

We are looking at curves such as secp112r2, secp128r1, sect131r1 and so on. This is not to discuss security of these, but their support.

In Cygwin, a huge load of curves is available, including the mentioned low-secutity curves. But in the URL these curves are not listed. Our team has observed that in some other OpenSSL sources (that are not through Cygwin), these curves are not supported. Are they no longer supported by OpenSSL, and if so - why are they available to me through Cygwin?

And by the way - I assume curve support is rather complicated, so that it is not possible to "import" a curve that is not supported in a given library.

I'm not sure, but I guess that two different openssl version or just builds could be done with or without support of Elliptic Curves with unsecure security levels.

Furthermore your curves have very low security level, and you shouldn't use them if security is a concern (and if it's not, you probably don't need ECDSA at all).

However, your assumption that "curve support is rather complicated" is wrong.

With libcrypto, the OpenSSL library, not the command line tool, you can use EC_GROUP_get_curve_GF to create your own elliptic curve. If you put in the parameters of those curves, you will be able to use them, with the library, even if the parameters are not encoded in OpenSSL.


Recovering the random number r For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ which is the private key.

So the public key is $(g,b,p)$ where $b=g^x$ $mod$ $p$.

To encrypt, we compute: $y_1 = g^r$ mod $p$ and $y_2 = M*b^r$ mod $p$. Then the encrypted version of $M$ is the pair $(y_1,y_2).$

I also know $s=(M-a^y)(r^{-1})$ mod $p-1$. Now we know the El Gamal signature on $M$ which is $(y,s)$.

So in conclusion, I know $(g,b,p,x,y,s)$ where $y$ is the message. I want to know how to determine $r$ from all this information. How can I do that?

At first glance

$r = s^{-1} (M - a^y) \bmod p-1$

would appear to be what you're looking for.

If $s$ isn't invertable modulo $p-1$, then you can work around this by working with the factors of $p-1$; in this case, $p-1 = uv$ where $s$ is a multiple of $u$ and $s$ is relatively prime to $v$.

So, we can solve:

$r_v = s^{-1} (M - a^y) \bmod v$

and so we have:

$r = r_v + kv$

for some integer $k$; if you know $y_1 = g^r \bmod p$, then you can recover the correct $k$ in $O( \sqrt{u})$ time.


How can hashes be unique if they are limited in number? I'm curious, how can for example SHA-256 be unique if there are only a limited number of them?!

For clarification:
how many MD5 hashes are there?
$16^{32}$ MD5 hashes can be produced.
$16^{64}$ SHA-256 hashes can be produced.
while there are $16^{128}$ just SHA-512 hashes, let alone long texts.

For more clarification:
assume we want MD5 of all the SHA-256 hashes.
we can have $16^{32}$ number of MD5 hashes, while there are $16^{64}$ SHA-256 hashes.
we will have 3.4*$10^{38}$ duplicate MD5 hashes!

And so is for SHA-256 hash, if we calculate SHA-256 of all the SHA-512 hashes, we will have 1.15*$10^{77}$ duplicate SHA-256 hashes!

Edit: This is not limited to a particular hash like SHA-256.

how can for example SHA-256 be unique if there is only a limited number of them?!

Where your issue occurs is that they're not unique.  It's just very improbable that they'll reoccur.      Unique in this context is not a mathematical definition, it's a humanist one.

In terms of human numbers, $ 2^{256} $ = 115792089237316195423570985008687907853269984665640564039457584007913129639936 which is 0.1% of the number of atoms in the visible universe. So that's a lot of them.

There's a better  answer @ Why haven't any SHA-256 collisions been found yet?, but you should get the gist from the lengthy 116 quattuorvigintillion number.


Just how surjective is a cryptographic hash like SHA-1? From “Are common cryptographic hashes bijective when hashing a single block of the same size as the output” and “How is injective, inverse, surjective & oneway related to cryptography”, it is suggested that cryptographic hashes are surjective. For avoidance of doubt, surjective means this:

whereby all the hash inputs (X) correspond to a reduced set of outputs (Y). This forms holes in the continuity of the output range, and we call them collisions.

Consider any hash function like SHA-1. The size of the possible input domain is $2^{160}$ if we stick to the block size. My linked answers suggest that the output co-domain is less than  $2^{160}$.

How much less exactly?

Are there any proofs or estimates to put a scale on this?  I wonder if the avalanche effect has any bearing on this?  This is probably extremely naive, but does anyone have anything better?

In this regard SHA-1 despite it's weaknesses can be viewed as a pseudo random function.
This means we are are throwing $n$ balls into $n$ bins.
An output bin remains empty if all the balls miss it.
Which happens with probability $(1-1/n)^n$ which is $1/e$ and that is the portion of output bins which are empty.
We also can estimate that the most populated bin has approximately $log(n)$ balls.


Avoid Logjam TLS Attack? As the Logjam attack allows a Man-in-the-Middle attacker to downgrade vulnerable TLS connections to 512-bit export-grade cryptography by modifying the ClientHello and ServerHello, can the Logjam attack be avoided by verifying the integrity of the ServerHello?

Downgrade attacks can be detected when the FINISHED messages are exchanged and verified. Of course, the goal of an attacker is to downgrade the security of the handshake, being able to compute the master key. If the attacker computes this key before both clients proceed to verify the FINISHED message, then he's able to spoof it and trick Alice and Bob.

Pointing to your question, that includes the ServerHello message, as the server would check if the messages received by the client match the messages sent by the server. In the case of a downgrade, the server detects that something different has been sent to the client, as there is a missmatch in the verification of the FINISHED message.


Is Bitmessage a Mix network? I've read the Bitmessage whitepaper and I found it rather lacking on the details, but it promises anonymous routing. Can it be considered a variation on mix-networks, where each peer acts as a mix-node?

YES. What mix-networks provide is anonymous routing. Using a chain of proxies, incoming messages are shuffled and then they are sent in random order. So, the sender remains anonymous. Similarly the Bitmessage protocol mixes all encrypted messages of a given user with all other encrypted messages of the network. As a result, the sender remains invisible. Here, each peer acts as a mix-node.


Proving that RSA encryption function with non-square free modulus is not a permutation Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already a related topic on this (Why does RSA need p and q to be prime numbers?). While most of the answers boil down to efficency and security considerations, there is a single answer which states that RSA encryption function with modulus consisting of prime powers loses it's bijection properties, i.e, it is not a permutation any more. However this behaviour is shown only on example with no proof.
Given that, I've started to search a proof of RSA permutation property, and I found such a proof here. But again, it states that the proof works only if $p \ne q$, while it is not actually clear why it is not for $p = q$.
Then I have started to digging it up by myself. Actually, it seems pretty clear for $p = q$ case if $p$ is prime. Then for $N = p^2$, we got a set of plaintexts $\{m_i\}$ such that $0 \leq m_i < N$ and $m_i \equiv 0\pmod{p}$, and having the exponent $e > 2$ we also got $m_i^e \equiv 0\pmod{p^2}$.
But I'm not sure how to generalize cases for $N = p^s, s > 2$; $N=p^sq, s > 1$; $N=p^sq^r, s > 2, r > 2$. Let's take a second case for example. Let $N=5^23= 75$, then $\phi(N) = (5^2 - 5)(3 - 1) = 40$, and $e=3$ is acceptable exponent. Next if I compute all $c_i=m_i^3\pmod{75}$ for all $0 < m_i < 75$, I see that there are 3 sets of discinct $m_i$ values that give the same $c_i$ after encryption:

$c_i = 0, m_i=\{0, 15, 30, 45, 60\}$
$c_i = 50, m_i=\{5, 20, 35, 50, 65\}$
$c_i = 25, m_i=\{10, 25, 40, 55, 70\}$

Thinking of this $c_i$ values I found the following pattern $5^3 \equiv 50\pmod{75}$, $5^32\equiv 25\pmod{75}$, $5^33 \equiv 0\pmod{75}$, $5^34 \equiv 50\pmod{75}$ and so on. Given that it's clear that:

for $m_i = 5(3k_j + 0)\pmod{75}, k_j \geq 0$ we got $c_i = 0$
for $m_i = 5(3k_j + 1)\pmod{75}, k_j \geq 0$ we got $c_i = 50$
for $m_i = 5(3k_j + 2)\pmod{75}, k_j \geq 0$ we got $c_i = 25$

And that's where I stuck. I have tried to explore the examples for $N = p^s$ and $N=p^sq^r$ and have found similar patterns like shown above. But I still need some clues in order to generalize this behaviour and prove that RSA encryption with non-square free modulus is not a permutation. I believe that there should be some simple concept I missing, but since I'm not much into Number Theory, I need community help.
Just for clarification. I'm completely OK with efficency and security considerations of $p$ and $q$ being two discinct prime. The only thing I'm worrying about is RSA encryption function bijection property (or it's absense, which is the case).
Thanks in advance.
UPD
@poncho gave a clear explanation on existence of multiple preimages for $c = 0$. But it also be great to generalize existence of other ciphertexts that can have multiple preimages.

While most of the answers boil down to efficency and security considerations, there is a single answer which states that RSA encryption function with modulus consisting of prime powers loses it's bijection properties, i.e, it is not a permutation any more. However this behaviour is shown only on example with no proof.

It's rather straightforward to demonstrate (assuming $e>1$; with $e=1$, it is a permutation, but not a very interesting one).
A value $N$ is nonsquarefree if there is a value $p>1, q$ such that $N = p^2q$ (note that $q$ may have $p$ as a factor).  If so, then consider the encryption of the two values $0$ and $pq$.  In the two cases, we have:
$$0^e \equiv 0 \pmod N$$
$$(pq)^e \equiv p^eq^e \equiv p^{2+x}q^{1+y} \pmod N$$
for $x = e-2$ and $y = e-1$.  Now, both $x, y \ge 0$, and so $p^{2+x}q^{1+y}$ is a multiple of $p^2q$, and so this latter is equivalent to $0 \bmod N$
Since these two distinct plaintexts map to the same ciphertext 0, the mapping cannot be bijective.


Difference between decryption and deciphering? Is there a technical difference between decryption and deciphering?

There's no actual technical difference, but it's sometimes used in different contexts.

Decryption: Used when talking about reversing an encryption of any type and when you know for sure that a message has been encrypted.

Deciphering: Used when (mostly) turning a ciphertext back to the plaintext, i.e. when a sentence has been encrypted with some sort of cipher like for example Caesar or Vigenère. It's also appropriate to use this term if people assume that a message has been encrypted or obfuscated.


Dividing a point by a specific number in elliptic curve There is an elliptic curve with parameters:

a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635
b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320

Also the prime number is:

q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297

How can I solve the equation 65537 * P = H and obtain the value of P?

P and H are points and H equals to (72782057986002698850567456295979356220866771008308693184283729159903205979695, 7766776325114464021923523189912759786515131109431296018171065280757067869793).

Note that in the equation we have https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

Find an integer $k$ such that $65537k \equiv 1 \pmod q$; such a $k$ exists because $q$ is prime.

If $65537\cdot P = H$, then clearly $P = k\cdot H$ (keeping in mind that $q\cdot P = \mathcal{O}$ for all points $P$), and conversely $(k\cdot H)\cdot 65537 = H$.


Is there any simple interactive zero-knowledge proof? What is the simplest known scheme that allows one to, given an input x : {0,1}* for which F(x) == y where F : {0,1}* -> {0,1}*, elaborate a proof p : {0,1}* such that V(p, y, F) iff F(x) == y?

What is the simplest known scheme that allows one to, given an input x : {0,1}* for which F(x) == y where F : {0,1}* -> {0,1}, elaborate a proof p : {0,1} such that V(p, y, F) iff F(x) == y?

First, in your definition the verifier needs to know $F,y$ and $p$, as he uses those in the verification process.

As @RickyDemer pointed out, if $F$ is some invertible function, the zero knowledge property trivially holds - but that might not be what you wanted:

If $F$ is invertible, the verifier can calculate $F^{-1}(y) = x$
Knowing $x$ and the distribution of the random coins used in the proof, the verifier can just act like the prover.

However, this is probably not what you had in mind with zero knowledge in the title. It does not mean, the verifier can't learn $x$. In order to achieve that, we need that $F$ is some kind of a one-way function. If we model the prover as computationally unbound, we could also assume that the evaluation of $F$ is super-polynomial, and in that case the polynomially bound verifier could not act like the unbounded prover - but then any  verification would most likely also be super-polynomial.

If we require $F$ to be a one-way function of some kind, a proof of knowing a preimage can take different forms, depending on the function $F$. The most common and simple ones utilize algebraic structures and known hard problems like the discrete logarithm. More generally, for any NP-complete problem you can create a zero knowledge proof (assuming one-way functions exist), and graph coloring is a classic example. For non-algebraic statements, there is also some research, but it's much more complicated. Here are two related questions, which have some relevant references:

Proving knowledge of a preimage of a hash without disclosing it?
How we can create a protocol using Schnorr as identification scheme and a hash function as a puzzle?


Salsa20 Implementation: Sum of 2 Words with Carries Suppressed I'm working on the 2nd part of the Salsa20 spec, and I want to implement a closure for the exclusive-or of two words(u32). The author defines the operation as the sum of two words with carries suppressed, but what does "carries suppressed" mean? Then I come across some summation notation:
$u=\sum_i2^iu_i$
What does the variable "i" mean in this context exactly? I understand summation notation and the index variable, but the context of the spec doesn't elaborate enough for me to know what "i" indexes.
I realize this all may be very rudimentary, but I am a programmer first.

The sum of two words with carries suppressed is just a convoluted way of saying XOR. You don't need to implement any kind of complicated summation operation. Just perform a bitwise-exclusive OR. I have no idea why Bernstein is being so abstruse. No cryptographer who would possibly be reading his paper would need a refresher on something as ubiquitous in that field as a disjunction.

If you're performing modular addition, just like with paper-and-pen arithmetic, you need to use carries. When adding binary you're doing the same but each digit is taken modulo 2 instead of modulo 10.
  1 1   ⟵ carries
0 0 0 1
0 0 1 1 +
⸻⸻
0 1 0 0

We see that  decimal 1 (binary 0001) added to decimal 3 (binary 0011) equals decimal 4 (binary 0100). That is, 1 + 3 = 4. So, what happens if we drop the carries, i.e. perform carryless addition in binary?
0 0 0 1
0 0 1 1 ⊕
⸻⸻
0 0 1 0

This is the same as decimal 1 XORed with decimal 3, and the result is decimal 2 (0010)! So 1 ⊕ 3 = 2. Salsa20 does the same thing, but with 32-bit words instead of 4-bit words. Because the addition is modulo 232, the leftmost carry, if there is one, is always suppressed (there isn't space for a 33rd bit).


Are the GPS coordinates a good source of entropy? Are the GPS coordinates (latitude and longitude) a good source of entropy? If yes, why? If no, why?
The question would investigate on the fact if the GPS location data can be used as source of entropy in the cryptography field, in general. The question could be trivial or not, it depends by several factors (e.g. the scenario, the entity speed and so on).
But what do you think about it?

Probiably not.  If a hacker where to locate the device physicaly then the search space would be greatly decreased.  Even knowing the city (ip can give you that) might be enough.
Other similar sources with a higher entropy could be changes in lat and long, but those are most likely small.
You would most likely get better entropy using the accelerometer/gyrometer/magnomiter instead (if avaliable, I am assuming this is for a phone).
If you wanted lots of entropy, you could ask the user to give their phone a nice toss while poling gyro and acceleration.


Getting the encryption method and key from the encrypted data and the raw data I have some pairs of plaintext and ciphertext data, from which I need to be able to decrypt the other passwords stored in the database.

The password field typically contains something like

ENC:LCznyFywN+3J+AD330rqHg==
ENC:D3H2ODVCAzkzQzRr8ZbJdw==

The raw data for the first is 1234, and the second 62369. ENC: denotes that it is an encrypted field, and the == at the end is always the same (no matter what the password).

If this can be done, then any prods in the right direction would be greatly received.

There is no general method for that. Cryptography is about making it impossible in practice.

In the particular examples, it looks like "encrypted data" is encoded in Base64, as 22 characters, representing 128 arbitrary bits. From that it can't be deduced much about the scheme used.


What is wrong with my Elgamal signature example? I want to construct an Elgamal signature scheme with the group $\mathbb{Z}_{23}^{\star}$ and then to compute the signature for the message $m$ with $h(m)=4$, where $h$ is the hash function that we are using. I want to describe also the verification of the signature.

The algorithm to sign a message $m$ is the following:

Choose a $k \in_{R} \mathbb{Z}_q^{\ast}$ ($1 \leq k \leq q-1 $).
Compute $r=g^k $.
Compute $ s=k^{-1} (h(m)+f(r)x) \pmod{q} $.

$f: G \to \mathbb{Z}_q $

Signature for $m$: $(r,s)$.

The verification is $r^s=g^{h(m)}\cdot y^{f(r)}$.

I have done the following:

A generator of $\mathbb{Z}_{23}^{\star}$ is $5$, $\mathbb{Z}_{23}^{\star}=\langle 5\rangle$.

To construct an Elgamal signature scheme we have to determine the private key $x$ and the function $f(r)$.

Let $x=5\in \mathbb{Z}_{23}$ and $f(r)=r$.

The public key is therefore $y=g^x=5^5\equiv 20\pmod {23}$.

We apply the algorithm for the signature and we get the following:

Let $k=18\in \mathbb{Z}_{23}^{\star}$.
We have that $r=g^k=5^{18}\equiv 6\pmod {23} $.
We have that \begin{align*} s&= k^{-1} (h(m)+rx) \pmod{23} \\ & =18^{-1}\cdot (4+6\cdot 5)\pmod {23} \\ & =9\cdot 34\pmod {23} \\ & = 9\cdot 11\pmod {23} \\ & = 7\pmod {23}\end{align*}

The signature for the message $m$ with $h(m)=4$ is $(r,s)=(6,7)$.

For the verification we have to check if it holds that $r^s=g^{h(m)}\cdot y^r$.

We have that $r^s=6^7\equiv 3\pmod {23}$ and $g^{h(m)}\cdot y^r=5^4\cdot 20^6\equiv 4\cdot 16\pmod {23}\equiv 18\pmod {23}$.

The verification is therefore not satisfied. What have I done wrong?

Example: We consider the group $\mathbb{F}_{47}^{\times}$.

The order of the group is $47-1=2\cdot 23$.

We find that the element $g=2$ has order $q=23$.

Suppose that  the private key is $a=14$, so we compute the public key $y=2^{14}\pmod {47}=28$.

We want to sign the message $m=32$. We choose $k=8$ and we compute $r=2^8\pmod {47}=21$.

We suppose that $h(m)=h(32)=20$.

We compute $s=k^{-1}(h(m)+ar)\pmod q=3\cdot (20+14\cdot 21)\pmod {23}=22$.

So, the signature for the message $m=32$ is $(s,r)=(22,21)$.

To verify the signature we compute $r^s=21^{22}\pmod {47}=9$, $g^{h(m)}=2^{20}\pmod {47}=6$ and $y^r=28^{21}\pmod {47}=25$ and check that $9\equiv 6\cdot 25\pmod {47}$.

So in order to use the function $f(r)$ we have to compute the signature modulo $p$ where $q-1=2p$, and $q$ is the order of the group we are considering, right?

Main problem is: in the question, a generator $g$ of order $q$ is used in the computation of [2.]. Thus if that computation and verification is in $\mathbb Z_{23}^*$ as in the attempted computations, then the modulus to use in [3.] is not $q=23$, but $q=22$ (if we use $g=5$), or rather $q=11$ (if we use another $g$ of prime order, which seems to be the intent: in [1.] it is considered that $\mathbb Z_q^*$ is the set of $k$ with $1\le k\le q-1$, which implies that $q$ is prime, as in the example).
Alternatively, we could use $q=23$ and $p=47$ as in the example (thus using modulo $47$ in the computation of step [2.] and signature verification); but then $g=5$ is unsuitable.

Further, the question misuse notations:

equivalence modulo, where $r\equiv a\pmod n$ means that $n$ divides $a-r$.
the operator $\bmod$, uniquely defining $r\,=\,a\bmod n$ such that $0\le r<n$ and $n$ divides $a-r$.
residue class modulo, where $R=a\pmod n$ means that $R$ is the set of all $r$ such that $n$ divides $a-r$ (this notation is less common, and should not be used without a notice and a good reason; its use in [3.] is accidental and unwelcome).

Note: the question does not follow the standard definition of ElGamal signature, which would use $s\gets k^{-1}\,(h(m)-r\,x)\bmod q$ and verify that $g^{h(m)}\equiv r^s\,y^r\pmod p$.


Understanding modulus math for RSA I probably have this doubt due to poor understanding of modular arithmetic, so an explanation would be greatly appreciated.

In any standard explanation of RSA, the following is present:

c = m^e mod n (where, c is the cipher text, m is the message, e the public key exponent, and n is the modulus)

And for decryption:

m = c^d mod n

To prove this, I've seen that the next step normally shown is :

m^(e.d) = m mod n

My question is, when c is raised to the private key exponent, why is the exponent not distributed over both m and mod n? I.E why is it not m^(e.d) mod n^(e.d)

You have to understand how the modulus operation works. When we say $a=b\mod c$, what we mean is that $a-b$ is a multiple of $c$. Now, since for any positive integer $n$, $a^n-b^n$ is a multiple of $a-b$, we can usually raise both sides to the same power in a modular equation, keeping $c$ intact. However, if $a-b$ is a multiple of $c$, there is no guarantee that $a^n-b^n$ is a multiple of $c^n$. Hence, raising $c$ to the same power makes no sense. I hope this answers your question. For a better understanding of elementary number theory, you can go through the initial chapters of a high-school text (like Burton's).


Why is ECB+CTR not a thing? AES-CTR is nice for its parallelizability and simplicity but if you duplicate an IV you reveal plaintext.

Chaining modes like CFB and CBC don't have that problem per se but they are not parallelizable. (CBC-type modes have padding issues too but that's a separate problem.)

Naive ECB mode is not secure because it reveals structure in the plaintext as shown clearly here.

However if you added a counter to ECB mode and XORed each block of plaintext with the counter, you could avoid that problem.

The advantage over CTR as I see it is that duplicating a nonce/IV (or having no nonce/IV) would not allow actual plaintext recovery. It may reveal duplication, but that's it. In the no-IV case duplicate messages would have duplicate ciphertext, but that again only reveals message duplication but does not compromise secrecy.

Obviously you'd need some kind of padding but again that's a separate issue.

Why is this kind of mode not a thing? Would a mode like that have some problem I don't see or is it simply deemed unnecessary?

However if you added a counter to ECB mode and XORed each block of plaintext with the counter, you could avoid that problem.

This is trivially insecure. Counter-Example: Consider the nonce $0^n$ and the plaintext $0^{2n-1}\|1$. This mode will encrypt the first block to be $E(0^n)$ and the second block to be $E((0^{n-1}\|1)\oplus(0^{n-1}\|1))=E(0^n)$ and so the two blocks will match revealing that they were all zero and all-zero appended with 1. This easily breaks IND$-CPA and RoR-CPA security (the latter being equivalent to more standard CPA security).

  Why is this kind of mode not a thing?

This sort of mode is a thing actually. Just not in the naive formulation as described in the question. Namely if you have a almost-XOR-universal hash function $H_K$ keyed with some key $K$ and a block cipher $E$, then $H_K(T)\oplus E(M\oplus H_K(T))$ is a secure tweakable block cipher1. Now you can put a counter in the tweak $T$ and change it for each block so swap attacks no longer work as do the pattern attacks you know from ECB. In fact tweakable block cipher (modes) are so useful, they see widespread use as XTS (which is based upon LRW which is the above construction and used by essentially all disk encryption software in a variant of this mode) and are the basis for the famously fast OCB modes.

1: Technically this constructs a strong tweakable pseudo-random permutation. For a non-strong TPRP it actually suffices to compute $E(M\oplus H_K(T))$ and the simplest $H_K(T)$ is actually $K\cdot T$ over $F_{2^{128}}$ which when used with a counting $T$ is very close to the question's construction it's just the additional secret value that makes the difference.


Message-Recovery variant of Ed25519 signature? What would be a Message-Recovery variant of the Ed25519 signature scheme?

Ed25519-MR should be simple to use, fast, with a strong security argument, and striving to stay out of the patent minefield, as the original does.

[Ed25519] is a signature scheme with appendix: it adds a signature of 512 bits to the message that it signs, for 128-bit conjectured security. A Message-Recovery variant would embed some of the signed message into the signature, with that so-called recoverable part of the message a byproduct of successful verification, that needs not be explicitly transmitted. We wish to minimize the overall signed message size.

Signatures schemes with message recovery of the Elliptic Curve Discrete Logarithm family have been proposed, patented and standardized (see bibliography), including ECNR (Nyberg-Rueppel), ECMR (Miyaji), ECAO (Abe-Okamoto), ECPV (Pintsov-Vanstone, aka ECPVS, PVSSR, ECSSR-PV), ECKNR (KCDSA/Nyberg-Rueppel) per their name in [ISO 9796-3].

Addition: I'm puzzled at the achievable gain over a signature scheme with appendix. My reading of [PV1999] and [AO1999] is that for $b$-bit security and arbitrary message, ECPV and ECAO embed $b$ bits into a $4b$-bit signature; when my limited understanding of other schemes is that some aim at embedding $2b$ bits.

Bibliography on (possibly Elliptic Curve) Discrete Logarithm Signatures with Message Recovery.

[NR1993]: Kaisa Nyberg and Rainer A. Rueppel, A new signature scheme based on the DSA giving message recovery, in proceedings of CCS 1993;
[NR1994]: id., Message recovery for signature schemes based on the Discrete Logarithm problem, in proceedings of EuroCrypt 1994;
[US'725]: Rainer A. Rueppel and Kaisa Nyberg, Digital signature method and key agreement method, US 5,600,725.

[M1995a] and [M1995b]: Atsuko Miyaji, Weakness in message recovery signature schemes based on discrete logarithm problems (continued), in IEICE TF;
[Mi1996a]: id., Signature equation suitable for message recovery schemes in IEICE TF;
[Mi1996b]: id., A message recovery signature scheme equivalent to DSA over elliptic curves, in proceedings of AsiaCrypt 1996;
[Mi1997]: id., Another countermeasure to forgeries over message recovery signature in IEICE TF;
[JP'357]: Miyaji Mitsuko, Message decoding type signature system, JP Pub.# H09-034357 ;
[JP'492]: id., Signature system, JP Pub.# H09-160492 .

[AO1999]: Masayuki Abe and Tatsuaki Okamoto, A Signature Scheme with Message Recovery as Secure as Discrete Logarithm in proceedings of AsiaCrypt 1999;
[AO2001] id., id., in IEICE TF;
[JP'178]: id., Message recovery type signature system and program storage medium therefor, JP Pub.# 2001-134178 .

[PV1999]: Leon A. Pintsov and Scott A. Vanstone, Postal Revenue Collection in the Digital Age, in proceedings of FC 2000;
[PV2000]: id., submissions to IEEE P1363a, including [PVSSR-D2] and [PVSSR-D3].

[BJ2001]: Daniel R. L. Brown, Don B. Johnson, Formal Security Proofs for a Signature Scheme with Partial Message Recovery, in proceedings of CT-RSA 2001; drafts: [BJ2000-02], [BJ2000-06].

[P1363a]: IEEE Standard 1363a-2004 - Specifications for Public-Key Cryptography - Amendment 1: Additional Techniques.

[ISO ISO9796-3]: ISO/IEC 9796-3:2006, Information technology — Security techniques — Digital signature schemes giving message recovery — Part 3: Discrete logarithm based mechanisms. Free previews in HTML and PDF.

[X9.92-1]: ANS X9.92-1-2009 (reaffirmed 2017, reportedly without change). Public Key Cryptography for the Financial Services Industry - Digital Signature Algorithms Giving Partial Message Recovery - Part 1: Elliptic Curve Pintsov-Vanstone Signatures (ECPVS).

[Ed25519]: Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang, High-speed high-security signatures, in proceedings of CHES 2011.

Fix finite fields $k$ and $k'$, say $k = \mathbb F_p$ and $k' = \mathbb F_{p^2}$ represented by $\mathbb F_p[i]/(i^2 + 1)$ where $$p = 36 u^4 + 36 u^3 + 24 u^2 + 6 u + 1$$ for $u = -2^{62} - 2^{55} - 1$.  Fix a group $G$ written multiplicatively, say $(\mathbb F_{p^{12}})^\times$.  Fix elliptic curves $E/k$ and $E'/k'$, say $E/k : y^2 = x^3 + 2$ and $E'/k' : y^2 = x^3 + 2/(1 + i)$, with a bilinear map $e\colon E(k) \times E'(k') \to G$, say the Tate pairing.  Fix a random function $H\colon \{0,1\}^* \to E(k)$, say $m \mapsto {+}x^{-1}(\operatorname{SHA256}(m))$, where ${+}x^{-1}(x_0)$ is the point on $E(k)$ with $x$ coordinate $x_0$ and the lexicographically smallest $y$ coordinate.  Fix a point $G \in E'(k')$ of large prime order.  (This choice of curve $E/k$ and its twist $E'(k')$ is more popularly known as BN(2, 254).)

A public key is the byte encoding $\underline A$ of a point $A$ on $E'(k')$.  A signature of a message $m$ under $\underline A$ is the byte encoding $\underline\sigma$ of an element $\sigma \in E(k)$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A).$$

A private key is the byte encoding $\underline a$ of a secret scalar $a$; the corresponding public key is $\underline A = \underline{[a]G}$.  To sign a message $m$ with private key $\underline a$, the signer computes $\sigma = [a]H(A \mathbin\Vert m)$.  This yields a signature because
\begin{align*}
  e(\sigma, G)
    &= e([a]H(\underline A \mathbin\Vert m), G) \\
    &= e(H(\underline A \mathbin\Vert m), G)^a \\
    &= e(H(\underline A \mathbin\Vert m), [a]G) \\
    &= e(H(\underline A \mathbin\Vert m), A)
\end{align*}
by the bilinearity of $e$.

Note that in the choice of parameters above, a signature can be encoded in 32 bytes, or even a mere 255 bits, by combining a 254-bit encoding of an $x$ coordinate with a single bit to discriminate between the two possible $y$ coordinates.  (Further compression of the curve points may be possible with techniques like Decaf, left as an exercise for the reader.)

Thus, you have 32 bytes and 1 bit left in your budget for a 64-byte Ed25519 signature to encode a part of the message, thereby enabling message recovery of 32 bytes (plus 1 bit) in 64-byte signatures!

Let us then define a Mr. Signature as a 64-byte string $\underline \sigma \mathbin\Vert m$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A),$$ which admits message recovery by $\underline \sigma \mathbin\Vert m \mapsto m$.

(Am I joking?  Maybe!)


Is it a requirement to understand mathematics when implementing (or breaking) cryptography? Related: What is the lowest level of mathematics required in order to understand how encryption algorithms work? and Recommended skills for a job in cryptology

In the context of putting crypto into applications, in a secure manner, could it be argued to achieve this (securely implementing a crypto system) you would require a thorough and rigorous understanding of the mathematics behind the crypto system?

Or, could it be said that this is more a matter of understanding how to code securely, as the cryptographic primitives themselves can already be securely implemented via libraries such as NaCl?

Edit: I realized the obvious, and in fact necessary, extension to this question. Reversing the goal, what level of mathematics would be required to break a crypto-system? On the one hand, heartbleed seemed to be a break in a crytpo-system but was in fact entirely based in (poor) code. On the other, the BREACH and CRIME compression side-channel attacks were very much discovered in the literature first. Am i answering my own question there?

I would say there are three general areas of necessary expertise for most crypto-related jobs:

Knowledge of primitives and their use cases.
Knowledge of protocols and understanding how to reason about their security.
Deep and abiding understanding of how incredibly stupid people are, including oneself.

The most that knowing the math is going to do for you practically, unless you are in academia/the NSA designing algorithms, is tell you "time to stop using RSA" on the day that you hear that there is a polynomial time factoring algorithm.


Hamiltonian Path Zero Knowledge Proof using Commitments to a Series of Edges Commonly, Zero Knowledge Proofs based on the Hamiltonian Path or Cycle problems are given as follows:

The Prover has a graph $G$, for which he knows a Hamiltonian Path (or Cycle). $G$ is also known to the Verifier and constitutes the public key.
The Prover generates $G'$ which is isomorphic to $G$ via a permutation $\pi$.
The adjacency matrix of $G'$ is individually committed, i.e. a cryptographic commitment for every possible edge is created which holds $1$ if the edge is in $G'$ and $0$ otherwise.
The Prover also sends a commitment to $\pi$ (it could be argued that this step is obsolete due to a recent improvement in graph isomorphy solving)
After receiving all commitments, the Verifier makes a binary choice
When choosing 0: The prover opens all the commitments for all edges that are part of the Hamiltonian path in $G'$ so that the Verifier sees a Hamiltonian path (or cycle) exists
When choosing 1: The prover opens all commitments so that the Verifier can see that the commitments indeed refer to $G'$ and that $G'$ is isomorph to $G$

The biggest problem with this Zero Knowledge Proof is that $O(n^2)$ individual commitments are required. We have recently been wondering if this could not be worked around by committing to a series of edges (in the spirit of adjacency lists) instead would not be more efficient with the same security guarantees.

This would create $|E|$ commitments of 2-tuples of two points each instead of $n^2$ commitments of single bits. (Plus one for $\pi$ in either case.)

For Example: "(commit(1,2), commit(1,3), commit(2,3)" is a valid set of commitments for the 3-Clique

It should be noted that the commitments must not only be for some random permutation $G'$ of the original Graph $G$, but also in random order, or one could potentially derive knowledge about the degree of nodes from the position of the opened commitment (and therefore identify individual nodes when only opening those corresponding to the Hamiltonian path/cycle).

We believe that this should still constitute a Zero Knowledge Proof, as a trivial simulator can be given:

When Prover will choose 0: Create a "Hamiltonian Path" commitment tuple "commit(1,2), commit(2,3), ..." and enough bogus commitments to have $|E|$ commitments in total. Randomly permutate everything. Reveal the "Hamiltonian Path" when Prover asks for it.

When Prover will choose 1: Just follow the protocol, as no knowledge of a Hamiltonian Path is required.

Are there any reasons (beyond tradition) why the literature would always use a version with adjacency matrices?

This does seem to be zero knowledge; as you say, you don't actually commit to the adjacency list. Rather, you commit to a series of edges, in random order.

Regarding the question: First, your assumption is that $n^2$ commitments, each to a single bit, is more expensive than $|E|$ commitments, each to $2\log n$ bits (to encode two numbers for the edge). This is a reasonable assumption for many commitment schemes but not necessarily for all. (Of course, it is very reasonable for sparse graphs.)

However, the main thing here is that the proof of Hamiltonicity is a theoretical proof of feasibility. Improving the concrete cost in this way is not of great interest. In any case, the protocol is unlikely to be used (applying a Karp reduction and then using Hamiltonicity will kill you in almost all cases).


Is an IV useless for encrypting database IDs? In my scenario I need to build a pseudo-anonimization service: a machine that given a plainID return a chiperID and vice-versa. chiperID are created when an unknown plainID is provided. So I have an identities table that grows keeping track of this mapping by storing the couple [plainID-chiperID]. To keep it safe against direct accesses to the db I need to encrypt one of them so I actually store [encryptedPlainID-chiperID]

My app is the only one that needs to encrypt and decrypt IDs so I am going to use a symmetric encryption algorithm like AES-256-* where the key is kept by the application.

Hence:

to obtain the plainID by providing the chiperID the application
needs to query the identities table directly by chiperID and then
decrypt the encryptedPlainID.
Vice-versa, to obtain the chiperID by providing the plainID the
application firstly needs to encrypt the plainID and then query
the identities table by the encryptedPlainID

I know that not using an IV make the algorithm insecure but I have some doubt that storing the IV for later decryption along with the encrypted ID make the whole system secure. To be clear I wonder if I need to store in the identities table the triple [encryptedPlainID-IV-chiperID]

But with this schema I cannot do the point 2 because I don't know a priori the IV used to encrypt the plainID

What can I do? Does the block cipher mode of operation matter?

The mode of operation does not just matter; it defines the properties of the IV! The mode of operation is the part that specifies the size of the IV, the contents of the IV as well as the impact of abusing the IV. AES is a block cipher; by itself it only allows the key and a single message block as input; AES itself doesn't specify or know about any IV.

For instance, CBC mode requires an unpredictable (read: randomized) IV of the same size as the block size for common cryptographic purposes. If you fail to provide it then an adversary can detect identical ciphertext blocks and retrieve information on the plaintext blocks at the same location - very likely including IDs.

GCM mode on the other hand defaults to a 12 byte IV (although other sizes are possible). The IV is actually just a (binary) nonce: a number used once; you would be fine as long as it never repeats for the same key. However, if it fails then you can XOR ciphertext together to retrieve the XOR of two different plaintexts - which would quickly lead to a complete break of confidentiality for most types of plaintext.

Quite often IV's are simply prepended to the ciphertext. Most modes of operation have a statically sized IV (and if they haven't you can standardize the IV size for your specific protocol). Using a cryptographically secure, random IV is a well-established practice which you could use for your specific problem, as long as your DB is able to store the expanded ciphertext.

If you also want the IDs to be integrity protected you might also need storage space for an authentication tag. A mode such as GCM is often used for this; authentication tags are generally 8 to 16 bytes (with 16 bytes giving most protection of course). HMAC could also be used for integrity protection, in which case the IV should be included in the calculation.

Which brings us to the static IV (SIV) mode of operation. With SIV the IV doubles as an authentication tag. For SIV mode the uniqueness of the plaintext assures the uniqueness of the IV. It has storage advantages over IV + authentication tag, and it doesn't require any separate random input or state machine (for a nonce / counter). Although it does expand the ciphertext size it seems otherwise perfect for encrypting ID values - as long as they don't repeat for multiple users.

There is also AES-GCM-SIV which brings the efficiency of AES-GCM to SIV mode. The original SIV uses AES-CMAC as an authentication mechanism.

If IDs are unique and fit inside a single block then you could simply use a single block encrypt to store ID's. Beware that this is brittle; if somebody decides to expand the ID size then the scheme may well break. You can use ECB mode for this if the block cipher is not directly available. CBC mode with a zero IV would perform the same operation for the first block. Using ECB or CBC makes the scheme even more brittle of course; using two blocks or more could introduce vulnerabilities.

And finally, if you need to store the IDs within the same amount of data then you may have a look at Format-Preserving Encryption (FPE). This is a less efficient mode with a higher learning curve and limited support. Like SIV mode it depends on the uniqueness of the input to achieve confidentiality. Its main advantage is that it doesn't expand the ciphertext over the plaintext size, regardless of how much data is occupied by the plaintext. It isn't limited by the block size, in other words.

Notes:

It is also fine to store the random IV's somewhere else in the DB, e.g. in a separate row.
Adding an authentication tag only provides limited protection against active attacks, for instance an attacker swapping encrypted ID's of different users. Generally DB is about securing data at rest, providing confidentiality of the ID's in case the DB gets stolen for instance. It's up to you to decide if the additional space required for the authentication tag is worth the cost.
Beware that messages / IDs may also be repeated in time. Relying on the uniqueness of the ID may e.g. still allow an adversary to track the ID for a specific user. If this is an attack vector or not depends on the specific use case.


Messages exchanged between Bob Alice are encrypted safe? Can you help me understand the following reasoning?

If Alice sends Bob a message and that message is encrypted with two keys simultaneously: a symmetric key (Ks) and Bob's public key. The symmetric key (Ks) is also sent to Bob, encrypted with the private key of Alice. The conclusion reached from this exchange of messages is that Bob can not be sure that the message was written by Alice but Alice can be sure that only Bob can read.

But how can we reach this conclusion: Bob does not know if it was Alice who wrote if he had to get the public's Alice for the symmetric key (Ks)?

Technically, the message is signed by Alice using her private key and encrypted using Bob's public key. So only Bob may decrypt it using his private key and he can check the authority using Alice's public key.

Both should check each other key validity using an external procedure before using such encryption/signing, e.g. meet face to face in a bar and verify keys fingerprints.


Silent Oblivious Transfer Question Recently, Boyle et. al. proposed silent OT extension. In the paper, silent OT, it seems that a GGM based PPRF used as building blocks. However, after reading the paper, I have two questions that are not clear:

For $t$-points PPRF, the authors proposed to have $t$ independent single point PPRFs to be constructed such that those single point PPRFs can be added together to form one multiple point PPRF. Compared to Correlated OT(IKNP-style), which asks the receiver to input the choice bit vector (a.k.a. the points in PPRF), does it mean if I want $t$ 1's in COT choice bit vector, I need to set $t$ corresponding points in multiple point PPRF?

Even compared this multiple point PPRF to Random OT, which still asks the receiver to input the choice bit vector, is there anyway to convert this random choice bit to chosen choice bit with little or no extra communication costs?

Thanks for any suggestions and helps.

No, because this is just an intermediate step. Roughly, if you want to get $n$ standard (correlated or not) OTs where the receiver chooses what he gets, our construction has four main steps:

a) Build a correlated OT where the choice vector is a random $t$-sparse vector (a very large vector, but with only $t$ random 1's). This is what is done using a sum of $t$ PPRFs.
b) Transform the "correlated OT with sparse choice vector" into a "correlated OT with pseudorandom choice vector". This is done using the dual LPN assumption. The idea here is simple: after doing (a), the sender has $\Delta, \vec q_0$, and the receiver has $\vec b, \vec q_1$, where $\vec q_0 + \vec q_1 = \Delta\cdot \vec b$, where the vectors are of length $n$ and $\vec b$ is $t$-sparse (this is exactly $n$ correlated OT with a $t$-sparse vector of choice bits). Now, all parties multiply their vectors using a public random compressing matrix $H$: the sender has $(\Delta, H\cdot \vec q_0)$ and the receiver has $(H\cdot \vec b, H\cdot \vec q_1)$. Observe that
$H\cdot \vec q_0 + H\cdot \vec q_1 = H\cdot (\vec q_0+\vec q_1) = H\cdot (\Delta\cdot \vec b) = \Delta\cdot (H\cdot \vec b)$,
so this is still $n$ correlated OT, but now the vector of choice bits is $H\cdot \vec b$. By the dual-LPN assumption, if $\vec b$ is a random $t$-sparse vector, then this $H\cdot \vec b$ is indistinguishable from a truly random vector.
c) If you want non-correlated OTs in the end, transform the $n$ correlated OTs with pseudorandom choice bits above into $n$ standard OTs with random choice bits; this uses IKNP-style decorrelation, i.e., just hash everything with a correlation-robust hash function to "break" the correlation. If you are fine with correlated OTs, skip this step.
d) It only remains to convert your $n$ OTs with pseudorandom choice bits into OTs with chosen choice bits. This is actually your question 2:

There is standard method to convert an OT with random choice bit (and random inputs as well) into a standard OT witch chosen inputs and choice bits. This involves three bits of communication per OT, which is optimal (you cannot hope to transmit one bit out of two chosen bits, using a chosen 'choice bit', using less than three bits of communication). Note that silent OT has communication sublinear in the total number of OTs generated, but only because the inputs and choice bits are pseudorandom - converted into standard OTs, they give OT with quasi-optimal communication, $3+o(1)$ bits per OT (amortized over $n$ instances).

The standard method is relatively simple. The sender has random inputs $(r_0,r_1)$ and true inputs $(s_0,s_1)$. The receiver has random choice bit $b$, knows $r_b$ (because of the random OT), and has true choice bit $\sigma$. Then, the receiver does the following ($\oplus$ denotes XOR):

If $b = \sigma$, ask the receiver to send $(u_0, u_1) = (r_0 \oplus s_0, r_1 \oplus s_1)$, and recover $s_\sigma = s_b = u_b \oplus r_b$.
If $b \neq \sigma$, ask the receiver to send $(u_0, u_1) = (r_0 \oplus s_1, r_1 \oplus s_0)$, and recover $s_\sigma = s_b = u_{1-b} \oplus r_b$.

Note that the message from the receiver to the sender involves communicating only $b \oplus \sigma$, i.e., telling the sender if $b = \sigma$ or not. Since $b$ is random, this reveals nothing about $\sigma$. Sender security is easy to see as well and is left as exercise for the reader :) In total, the above has two rounds and involves three bits of communication for each chosen OT.


Requirements for attacker-controlled ECDSA identity point signature Wikipedia's description of the ECDSA verification algorithm suggests verifiers should confirm that step 6 doesn't produce the identity point:

  Calculate the curve point  ${(x_{1},y_{1})=u_{1}G + u_{2}Q_{A}}$
  If $(x_{1},y_{1})=O$ then the signature is invalid.

Can a forged signature force this condition? If so, does the entity producing this signature need to know the private scalar for $Q_{A}$? What about forcing this condition for a given message?

The reason for that check is not one of security, but of definition. The verification algorithm entails computing the point $u_1 G + u_2 Q_A$, and use its $x$ coordinate to compare it with the value $r$ (modulo $q$). The "point-at-infinity" (the neutral element on the curve) does not have any coordinate $x$ or $y$, since that point is not part of the plane. Thus, what should happen when a point-at-infinity is obtained is unclear; the rule you cite solves the issue by mandating a signature rejection.

If you remove that rule, then what happens depends a lot on the implementation: rule or not rule, the point-at-infinity still has no coordinates $x$ and $y$. A correct implementation should still refuse to output any value in such a case, and report an error. An incorrect implementation may do... about anything. Including accepting the signature as "valid".

In practice, signature verification is done as:

$w = s^{-1} \mod q$
$u_1 = h(m) w \mod q$
$u_2 = rw \mod q$
compute the point $u_1 G + u_2 Q_A$

The values $u_1$ and $u_2$ can be recomputed by anybody. Thus, in order to produce a signature $(r,s)$ such that the point-at-infinity is obtained, one of the two following must hold:

$u_1 = u_2 = 0$
$u_2 \neq 0$ and $u_1 = -x_A u_2$ (with $x_A$ being the private key)

The second case thus requires knowledge of the private key $x_A$, which is, by definition, unknown to the attacker. And, for the first case, it requires $h(m) = 0 \bmod q$, and simply finding a message $m$ that fits that property is a preimage attack on the hash function, with average cost $O(q)$, thus nominally unfeasible with existing technology.

What might happen with a real-world careless implementation is the following:

The computations on curve points are done with projective coordinates. Each point $(x,y)$ is represented by a triplet $(X:Y:Z)$ such that $x = X/Z$ and $y= Y/Z$. This is a classic representation that allows the use of efficient formulas. The point-at-infinity is then represented by $Z = 0$.
The inversion of $s$ during verification ($w = s^{-1}$) is done with modular exponentiation ($w = s^{q-2} \bmod q$). This is not the fastest possible inversion algorithm, but it is easier to implement than an extended GCD.
The implementer, having obtained the point in projective coordinates $(X:Y:Z)$, instead of computing $x = X/Z$ and then comparing it with $r$, finds it smart to check that $X = Zr$, which avoids an inversion.

Under these three conditions, the "signature" $(r,s) = (0,0)$ will be accepted as valid, systematically, for all public keys and all messages! Note that this entails an implementation that gets it wrong twice:

the implementation gleefully computes $1/s$ for $s = 0$ (and obtains $0$);
the verification on the final $x$ is done without checking that the point is not, indeed, the point-at-infinity.

It is an unfortunate fact that such implementations have existed (I won't give names).


Proof of security for RSA signatures I am new to here, I was having some problems with a problem I am working on:

  "For each of the following variants of the definition of security for signatures, state whether textbook RSA is secure and prove your answer:

  (a) In this first variant, the experiment is as follows: the adversary is given the public key $pk=(N,e)$ and a random message $m$. The adversary is then allowed to query the signing oracle once on a single message that does not equal $m$. Following this, the adversary outputs a signature $\sigma$ and succeeds if $\operatorname{Vrfy}_{pk}(m,\sigma)=1$. As usual, security is said to hold if the adversary can succeed in this experiment with at most negligible probability.

  (b) The second variant is as above, except that the adversary is not allowed to query the signing oracle at all."

The construction for $\sigma$ is:

$$\sigma=m^d \mod N,$$ where $(N, d)$ is the secret key.

And the $\operatorname{Vrfy}$ function is as follows: $$\operatorname{Vrfy}_{(N,e)}(m,\sigma)= \begin{cases}1 & \text{if }m=\sigma^e \mod N \\ 0 & \text{otherwise}.\end{cases}$$

Since the known attacks on textbook-RSA signature forgery arise from two things:

A no-message attack: if the adversary has access to a signing oracle and a public key, he can sign an arbitrary message.
If the adversary has two signatures on two different messages, he can get a third message that is the product of those two messages and sign it with the product of the two signatures and it would be valid.

Would this be a good proof to show how a.) is secure:

The adversary uses the signing oracle to get a signature on $m_1$, so he gets $\sigma=m_1^d \mod N$, where $d$ is the secret key. Now he should be able to take the discrete logarithm of $\sigma$ to find $d$, but that is a hard problem, so the algorithm to forge this signature by finding the secret key is at least as hard as the DL problem, so the probability is negligible.

And my intuition is that b) is also secure, but I don't yet know how to go on about proving it formally.

For (a), what if you query the signing oracle on $m' \equiv -m \mod N$?  Can you see how to compute $m^d$ given $(-m)^d$?  (Hint: $d$ is odd.)

For (b), try showing that doing this is equivalent to solving the RSA problem.


Would RSA-encrypting a private key for itself constitute a vulnerability? I'm planning to encrypt some individual files for storage, using the GnuPG implementation of RSA. If I happened to encrypt the private key corresponding to the public key used for encrypting -- either as an internal GnuPG file or an ASCII-armored exported key -- would this constitute a vulnerability?

The key in question is password-protected, but I'd be interested in both situations.

If there is a vulnerability in encrypting a RSA private key with the corresponding public key, when the private key is password-protected, then it mechanically implies a vulnerability in the password-based protection scheme: if an attacker gets a copy of the password-encrypted key (without the password), he can encrypt it with the public key himself; so an attack on the result (RSA encryption of the password-protected private key, leading to a private key compromise) is readily turned into an attack on the password-based encryption.

Without password encryption, things are a bit less clear. Consider the following hypothetical RSA-like cryptosystem:

$n = pq$ is the public modulus, with public exponent $e$;
private key is $p$ (knowing $p$, $n$ and $e$ is sufficient to recompute the private exponent $d$);
encryption uses no padding (message $m$ is encrypted by computing $m^e \mod n$ directly).

Then the encryption of the private key yields $p^e \mod n$, an integer which is a multiple of $p$ (it is equal to $p^e-kpq$ for some integer $k$) but not of $q$. Therefore, a simple GCD between that value and $n$ reveals $p$.

Now, the real RSA has padding, and, more importantly (here), when used in GnuPG, is an hybrid encryption scheme: what RSA actually processes is a random value, from which is derived a symmetric encryption key, which is then used to encrypt the actual data. For RSA-encryption of the (unprotected) private key to be a vulnerability, it would require the symmetric encryption to somehow transport unscathed algebraic properties from the private key structure to the modular exponentiation. This is highly improbable and my gut feeling is that there is no problem here. But still, no formal proof.

Why would you want to do that, anyway ? To do anything with an encrypted message, you have to know the decryption key -- and if you already know the decryption key, why would you care about obtaining it again from the decryption ?


Encryption, Decryption using OpenSSL How to use OpenSSL in windows for encryption and decryption ?

First, download OpenSSL for Windows from a reputable source. Here is a good place to start: https://wiki.openssl.org/index.php/Binaries

After installing OpenSSL, open a command prompt. You can chose among the many algorithms, but if you dont know what you want, going with AES-256 in CBC mode is a good start.

C:\Users\admin>openssl aes-256-cbc -a -salt -in file.txt -out encrypted-file.txt.enc
enter aes-256-cbc encryption password:
Verifying - enter aes-256-cbc encryption password:

C:\Users\admin>type encrypted-file.txt.enc
U2FsdGVkX19v2JTUzRF/BRwy7egsmi+4A1KXyJfQmBF70cg0Go+EvroxvXd8ugiI

C:\Users\admin>openssl aes-256-cbc -d -a -in encrypted-file.txt.enc -out decrypted-file.txt
enter aes-256-cbc decryption password:

Here is a screenshot of what it looks like on Windows 10. Note, you can't see the password being typed, but you will have to type a password to encrypt the file, and the same to decrypt it.

I hope this helps you get started.


How to sign different messages using deterministic ECDSA? The elliptic JavaScript library implements a .sign function which seems to give the same result when signing the same message. That means the k param is constant. Doesn't that mean signing different messages exposes the private key? If that is the case, how can I correctly sign several messages with the same private key?

Elliptic says:

  ECDSA is using deterministic k value generation as per RFC6979.

This means that every time you sign the same message you'll get the same random value used. That explains why you see the same $k$ param both times.

However, the $k$ value generation process takes the message (or the message hash) as an input. More specifically, $k$ is generated by hashing the message (hash) along with the private key. So every different message will produce a different $k$ value (apart from the negligible probability of hash collisions), and the same message will produce the same $k$ value every time it's signed.

Using the same random value with the same message is not a security risk (obviously, you just get the same signature). If you use the same random value with different messages you immediately reveal the private key, so as you note this should not be done. However, the RFC 6979 approach "ensures"  that with extremely high probability different messages will use different ks.


SHA3-255, one bit less I need a SHA3-255 or 511. What if I simply truncate a standard SHA3-256 or 512? Apart from the doubled probability of hash collision, are there any other things I should be aware of? I could also truncate one byte instead of one bit, if useful.

What I need is being able to store something different than the hash, in the same 32 bytes, or 64 bytes, so I need to sacrifice one bit to mark when the bytes represent a hash or something else.

Alternatively I could say that if the first byte, not bit, is 0xff, then the remaining ones represent something else. This should reduce the probability of hash collision, but what I would have a probability of 1/256 that a hash starts with 0xff, generating ambiguity in my encoding. I could say that if the for 4 bytes are 0xffffffff, then I would end up with probability of generating an ambiguous encoding of 1/2^32, but I would prefer having a well-defined encoding under any circumstances.

Any well known approach I'm not aware of?

With all well-regarded hash functions, the bits of the hash all have equal worth: as far as anyone knows (unless they aren't telling), the bits are not correlated. If you take $k$ bits of an $n$-bit hash, you get a $k$-bit hash function. Truncating SHA-256 to 255 bits gives you a hash that's almost as good as SHA-256: it has $2^{255}$ strength against preimage attacks and $2^{127.5}$ strength against collision attacks.

There are precedents for taking certain bits of a hash. SHA-224 and SHA-384 are obtained with calculations that are essentially the same as SHA-256 and SHA-512 respectively, just with different initial values (which shouldn't matter to the strength of the algorithm) and with the output truncated to the smaller size. Another precedent is that UUID can be constructed from 122 bits of MD5 or SHA-1 hashes (out of 128 or 160 respectively).

For SHA3, there's a cleaner construction. Instead of taking SHA3-256 and cutting off one bit, take the SHAKE256 255-bit or 248-bit output. SHAKE256 is exactly the same as SHA3-256 except for two bits near the beginning of the calculation, so it has the same security properties, but it's explicitly designed to have variable-length output. You can even use SHAKE128 instead of SHAKE256, which is slightly cheaper to compute with no meaningful security loss.

It's unlikely that there's an actual security problem with truncating a hash, but using SHAKE gives you greater confidence that nothing will go wrong. Even better, to avoid domain collisions (where two parts of the system calculate the hash of the same string for different reasons), calculate the cSHAKE output with a unique string as the customization string.


Cryptographically secure PRBGs and the previous-bit test I am reading Junod's paper about the Blum-Blum-Shub PRBG (BBS) and I am having trouble following his reasoning at on page 15, where he argues that the next-bit test can also be peformed for the previous bit in the bit sequence $b_0b_1 \ldots b_k$ , i.e. an attacker can also try to predict $b_{-1}$. If I understand him correctly he deems this obvious as the next-bit test is equivalent to the polynomial-time statistical tests, the latter one being obviously indifferent to a reversal of the given bit sequence.
But I do not understand how this should be applicable, since (in my eyes) random number generators can in any case only build sequences that "extend in one direction infinitely" as they have to have some kind of starting point and the previous bit test can not be applied at the starting bit $b_0$, since there is no previous bit. So wgat is $b_{-1}$ supposed to mean?
Can you explain this to me?

If you only have a subsequence of the output that does not include the first bit, then the bits of your subsequence can be labeled $b_0$, $b_1$, $\dots$. The bits of the overall sequence from which they are taken would then be labeled $\dots$, $b_{-1}$, $b_0$, $b_1$, $\dots$.
In other words, you're not necessarily starting the labeling of the bits at the beginning of the generator output, but rather at some later point. In that case there is a previous bit, and the previous-bit test applies.


Is SHA256 resistant to second preimage attack? I am looking into building a merkle tree algorithm and I need to know if SHA256 is resistant to second preimage attack.

SHA-256 has no known collision attack and has no known second pre-image attack and has no known pre-image attack.

There was a claim Has SHA256 been broken by Treadwell Stanton DuPont? but is has already debunked.

Currently, we have generic attacks: $2^{256}$ pre-image resistance, $2^{256}$ secondary pre-image resistance and $2^{128}$ collision resistance. Collision resistance is lower due to the birthday attack. The academical attacks are on reduced rounds, therefore not practical, yet.

Note per comment:  It is not SHA-256 or any other Cryptographic hash's weakness. It is a problem with hash trees that enables to find secondary pre-images and it can be mitigated with domain separation as mentioned in rfc6992. You can also see this problem in this post;

What is the reason to separate domains in the internal hash algorithm of a merkle tree hash?


Equivalents to a physical hat+shaking? I would like a multiparty protocol, secure in the honest-but-curious model at least, but hopefully other situations as well, that can do the following: every party among $\{P_1, P_2, \ldots P_n\}$ puts in a value $v_i$, and the set of $v_i$'s is computed, in such a way that no one knows which party contributed which $v_i$. In the real world this can be done by putting folded slips of paper into a hat, but I cannot come up with a good search term. References are most appreciated.

You can solve this using mixnets.

Sample protocol:

The parties jointly choose a public/private keypair, such that the random key is shared among all $n$ parties.  (This is threshold crypto, and there are standard protocols for this.)
Each party $P_i$ encrypts his/her value $v_i$ under the public key chosen in step 1.  He/she broadcasts this ciphertext $E(v_i)$.  Now everyone knows $E(v_1),\dots,E(v_n)$.
Party $P_1$ uses a re-encryption mixnet to shuffle and re-randomize the $n$ ciphertexts.  Party $P_1$ uses a zero-knowledge proof to prove that he/she did this step honestly (i.e., the shuffled ciphertexts decrypt to the same set of values as the original ciphertexts did).  He/she broadcasts the results and the zero-knowledge proof.  (There are standard protocols for this.)
Party $P_2$ does the same thing: he/she uses a re-encryption mixnet to shuffle and re-randomize the $n$ ciphertexts that resulted from step 3.
And so on.  Each party in turn performs their own re-encryption mix on the results from the previous party.  At the end of this, party $P_n$ has broadcast a set of ciphertexts $C_1,\dots,C_n$ that are a shuffled and re-randomized version of $E(v_1),\dots,E(v_n)$.
Now all the $n$ parties use the threshold decryption protocol to jointly decrypt the ciphertexts $C_1,\dots,C_n$ and broadcast the result.  As a result, everyone learns the values $v_1,\dots,v_n$, but in a shuffled/permuted order that cannot be linked to the originator of each value.

This should satisfy your goals.  I think it provides about as much security as one could hope for: if a party is honest, she can verify the integrity of the result of the protocol; and if $k$ parties are honest and $n-k$ parties are dishonest, then the dishonest parties learn the set of $k$ values that were contributed by the $k$ honest parties, but cannot associate which of those $k$ values came from which honest party.


Reversing a known encryption algorithm (4-byte repeating key XOR) I've been practicing for an upcoming CTF competition, and I've finally reached the cryptography stage. I'm a complete newbie in this field (my knowledge is essentially that bcrypt is awesome and md5 sucks haha).

This is the challenge:

This is my cipher algorithm:

mysecretvalue = ???;
mysecretmessage = ???;
for (i=0;i<strlen(mysecretmessage);i++)
{
    mysecretmessage[i] ^= ((mysecretvalue>>(8*(i%4)))&255);
}
echo strhex(mysecretmessage);

and my output:
e971de14d87fc406c67fc41ac570c3528a4ec216da7fc2168a78df018a70d50bde3ed31bcb72dc16c479d500863ee71ad07fc2178b3ee012d96dc71cd87a9007c53ec41bcf3ec31ade7b901ad93edd0ad97bd301cf6ac612c66bd553c3709017cf7dd91ecb729e53ed71df178a49df01c13f

Decode it! ;)

I'm more interested in a general method of solving such challenges, however if you want to solve this one as an example it will be appreciated as well!

P.S This is all the info the challenge provides. I couldn't find a function named strhex so I assume it's pseudo-code albeit it does look pretty similar to Javascript.

The actual "encryption" is done on this line:

mysecretmessage[i] ^= ((mysecretvalue>>(8*(i%4)))&255);

Clearly, this line XORs every byte (or at least, every element; but it makes sense to assume that this is indeed a byte array) of mysecretmessage with some value derived from mysecretvalue and the byte counter i.

So what does the expression ((mysecretvalue>>(8*(i%4)))&255) actually return?

The counter i only appears in the subexpression i%4, which divides it by 4 and returns the remainder.  So from this we can already tell that, whatever else the expression might be doing, its value will repeat every 4 bytes.  So we're looking for a repeating 4-byte key that, when XORed with the byte sequence given in hex below, will yield a meaningful (and thus presumably the original) message.

(In fact, all that the rest of the expression ((mysecretvalue>>(8*(i%4)))&255) is doing is taking a 32-bit integer mysecretvalue and extracting the i%4-th 8-bit byte from it.  It does this by shifting the bits of mysecretvalue right by 8*(i%4) bits, and then taking the bitwise AND of the result with 255 = 28−1 = 111111112 in binary to extract the lowest 8 bits of it.)

So this is basically XOR encryption with a 4-byte repeating key.  If your message was exactly 4 bytes long, and the key was randomly chosen, then this would be an unbreakable one-time pad.  Since the message is longer than the key, however, it becomes a "many-time pad", which is easy to break.

There are many standard techniques and even automated tools to break this type of repeated-key encryption.  A simple approach is to split the message into 4-byte segments, take the first byte of each segment, and search for a byte that, when XORed with each of these bytes, yields mostly printable ASCII characters, with frequencies approximating those of English text.  Then repeat for the second byte of each segment, and so on.

Another method is "crib dragging".  Basically, you guess an $n$-byte sequence (the "crib") which is likely to occur in the plaintext message, and try to XOR it with each consecutive $n$-byte substring of the ciphertext.  Likely cribs for English text include the most common English words surrounded by spaces, like "the" (5 bytes), "and" (5 bytes), "that" (6 bytes) and so on.

Each crib in each position will yield a candidate key (or a partial key) which you can then use to try to decrypt the message and see if the result makes sense.  (If the crib is longer than the expected key length, you can immediately rule out most positions by checking whether the candidate key repeats as expected.)  This process can also be fully or partially automated using statistical analysis tools.

Once you have the message and the repeating 4-byte key, simply writing out the key bytes in hex, from right to left (since the encryption code starts with the lowest byte), will then give you the mysecretvalue in hex if you want it.


For Diffie-Hellman, why is a g value of p−1 not a suitable choice? I am currently learning about the Diffie-Hellman key exchange. I understand that for a $g$ of $1$, the resulting key would always end up as $1$ which would obviously not be secure.

I read that the $p\! -\! 1$ value for $g$ is not secure either, but there is no explanation as to why - which is my question. I guess it has to do with $g$ being a divisor of $p\! -\! 1$ but I am not sure.

If $g=p-1$ then $g\equiv -1\pmod p$ that is $g$ is effectively the same as $-1$ which has the obvious drawback that $g^x$ can only ever be $+1$ or $p-1$ which is easily brute-forcable.

Here's a short proof sketch of the above exponentiation statement:

\begin{align}
 (p-1)^2\bmod p  &= (p^2-2p+1)\bmod p \\
  &=(p^2\bmod p)-(2p\bmod p)+(1\bmod p)\\
  &= 0-0+1\\
\end{align}

So when you have $(p-1)^x\bmod p$ this is the same as $(p-1)^{2y}\cdot(p-1)^{z}\bmod p$ for $x=2y+z$ and $z\in \{0,1\}$ which is $((p-1)^2)^y\cdot (p-1)^{z}\bmod p=1^y\cdot (p-1)^{z}$ which is either $p-1$ or $1$.