AES Decryption followed by Encryption, will it produce the original text? If a plain text is first decrypted (with the AES decryption algorithm) using Key K1 and then encrypted using same K1, would the final result still be the original plain text?

If you are talking about the AES block cipher acting on a one block message, then yes, with K being the actual 128/192/256 bit-key.  For a given key, the encryption E(message, key) and decryption D(ciphertext, key) functions are perfect inverses of each other.  You will always have both E(D(m,K),K) = m and D(E(m,K),K) = m by construction for any block cipher encryption/decryption functions operating on a one-block message m (for AES one block = 128-bits = 16 bytes).

That said in practice, if you use some well-written tool in a secure mode (like openssl aes-[128|192|256]-cbc) that internally uses AES as the block cipher for encryption/decryption this probably will NOT work, if you simply feed your tool a plain text message and ask it to decrypt said message with your key.

This is because your tool that uses AES as your block cipher will make various assumptions for you and does more than just apply AES to each block.  Specifically:

The tool will likely add proper padding to your message before encrypting it and will fail to decrypt if you are attempting to decrypt something that wasn't properly padded.  (Without proper padding their are attacks against multi-block AES encrypted messages).
On encryption, the tool may prepend the ciphertext with a block of a random initialization vector (IV); on decryption doesn't attempt to decrypt the zero-th block assumed to be an IV.   (Without an initialization vector, an eavesdropper can detect when similar starting messages are being sent and potentially tamper with them).
The tool also may include some sort of MAC to verify the data wasn't tampered with that will fail if you attempt to decrypt a plaintext message (as the plaintext message would not have a valid MAC that allows decryption to proceed).


BigInteger in Java and Randomness I'm looking for some PRNGs and – as I have been using Java for a long period of time – I thought that the BitInteger class, together with the Random class, could both generate some large pseudo random numbers.

Are the algorithms behind those generations cryptographically secure, or is it just some sort of a + (b - c) mod d or similar operation?

Presuming this documentation is correct, the answer is no, these numbers are not cryptographically secure. The Random class uses a linear congruential formula with a 48 bit seed. For most purposes it is not enough even if you only require 48 bit security. Given a fairly low number of outputs from a LCG, it is possible to derive the seed, even if only a few bits of each seed iteration are used. That question has been answered here.


Can AES in CBC mode be parallelized? Is there any way to parallelize AES running in CBC mode? (The plan is to parallelize it using OpenMP)

Normal CBC mode cannot be parallelized during encryption; that's because CBC mode encryption is defined as:

$$C_i = E_k(C_{i-1} + P_i)$$

That is, what you encrypt during the processing of block $i$ depends on ciphertext of block $i-1$; hence you can't start the next block until you've completed processing of the previous block.  You can't do any parallelization, except for that parallelization that's inherent within AES.

On the other hand, CBC mode in decryption can be parallelized, and it's fairly straightforward.

In addition, there is a variant of CBC mode where you don't xor in the immediately previous ciphertext block, you xor in one $n$ blocks ago, as in:

$$C_i = E_k( C_{i-n} + P_i )$$

This is effectively running $n$ different CBC mode encryptions in parallel; this can be paralleized $n$ ways.


Combining Hellman Pohlig with Sieve Suppose integer $m$ has $\phi(m)=2pq^5r^2$ where $p,q,r$ are primes.

Hellman-Pohlig says that finding discrete log $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ suffices to find $z\bmod\phi(m)$ in $g^z=h\bmod m$.

It could be that $p,q^5,r^2$ are still very large and there is a Big-step-small-step which is still exponential.

Can we apply sieve techniques to each of $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ cases separately?

I'm not sure if I understand the question correctly, but let's try anyway.

By assumption we have some integer $m$ such that $\varphi(m)=2pq^5r^2$ for primes $p,q,r$. The goal is to solve a discrete logarithm problem in $\mathbb{Z}_m^*$, say we have $g,h\in\mathbb{Z}_m^*$ such that $h=g^\ell$ for some integer $\ell$.

We note that $\mathbb{Z}_m^*$ is a finite abelian group of order $\varphi(m)$, so by the fundamental theorem of finite abelian groups we have that $\mathbb{Z}_m^*\cong\mathbb{Z}_2\times\mathbb{Z}_p\times G(q^5)\times G(r^2)$, where $G(q^5)$ and $G(r^2)$ are groups of order $q^5$ and $r^2$ respectively (they are Sylow subgroups). Pohlig-Hellman implicitly makes use of this fact. That is, instead of finding $\ell\pmod{\varphi(m)}$ directly, we map $g$ and $h$ to elements of $\mathbb{Z}_2$, $\mathbb{Z}_p$, $G(q^5)$ and $G(r^2)$ respectively. We then solve the DL's in those groups, finding $\ell\pmod{2}$, $\ell\pmod{p}$, $\ell\pmod{q^5}$ and $\ell\pmod{r^2}$. Finally we recombine them using the Chinese Remainder Theorem.

For example, since $g$ and $h$ have order dividing $\varphi(m)$, we have $g^{2pq^5r^2}\equiv h^{2pq^5r^2}\equiv 1\pmod{m}$. That means that $(g^{pq^5r^2})^2\equiv (h^{pq^5r^2})^2\equiv 1\pmod{m}$, i.e. they are both elements of order 2. In other words, we can think of them as lying in $\mathbb{Z}_2$. Thus, we have that $h^{pq^5r^2}=(g^{pq^5r^2})^{\ell\pmod{2}}$. This is an easy DL and we solve it to find $\ell\pmod{2}$.

So we have reduced to solving DL's in $\mathbb{Z}_2$, $\mathbb{Z}_p$, $G(q^5)$ and $G(r^2)$. Carefully looking at the Pohlig-Hellman shows that we can actually reduce the DL in $G(q^5)$ to 5 DL's in $\mathbb{Z}_q$. Similarly we reduce the DL in $G(r^2)$ to 2 DL's in $\mathbb{Z}_r$. Hence the remaining problem is solving some DL's in the group $\mathbb{Z}_s$, for $s\in\left\{2,p,q,r\right\}$. That is, a prime order cyclic group.

You may start wondering why I'm going through all of this. The point is that the usefulness of Pohlig-Hellman is precisely this reduction step. Assuming that $p,q,r$ are all small, we can easily solve all DL's in our groups $\mathbb{Z}_s$. However, what if $p,q,r$ are not small? Then we have to solve the DL's in $\mathbb{Z}_s$ some different way, but Pohlig-Hellman does not come with any restrictions. The most straightforward way would perhaps be Baby-Step Giant-Step, but we are free to choose any other method.

Therefore in relation to your actual question, any sieving technique that applies to solving a DL in a prime order group, will also apply here. Although I guess it is most commonly known for factoring, there are definitely applications of the NFS to these groups, see e.g. https://cr.yp.to/bib/2003/joux.pdf.


In ECDSA, why are u and v dividing by s? The verification algorithm for ECDSA is:

$P=e\times G$,
$(r,y)=k\times G$, and
$s=(z+re)\times k^{-1} \bmod n$,

where $P$ is the public curve point, $G$ is the generator point, $e$ is the private key, $n$ is the order of $G$, $z$ is the message hash and $k\in [1,n-1]$.

$u = z\times s^{-1}$ and
$v = r\times s^{-1} \bmod n$.

If $u\times G+v\times P=(r,y)$, then signature is valid.

The math works for this, but why isn't something much easier done?

$P=e\times G$, $(r,y)=k\times G$ and $s=(k-rz)\times e^{-1}$

$rz\times G+s\times P=rz\times G+((k-rz)\times e^{-1})\times P=rz\times G+((k-rz)\times e^{-1})\times e\times G)=rz\times G+(k-rz)\times G=rz\times G+k\times G-rz\times G=k\times G=(r,y)$

So $r,s$ can be used almost directly in the $u\times G+v\times P$ equation and the same condition be used to check that the signature is valid. In addition, the formulation does not use as much division, which is computationally the most expensive part.

I'm sure there's some vulnerability with this more naive signature scheme. What is that vulnerability?

In the actual ECDSA, $(r,s)$ is called the signature of the message $m$ whose hash is $z$ i.e. $z=H(m)$.
By removing $z$ from the equation, you have completely eliminated any correlation of this "new incorrect signature" (which isn't even a signature) with the message, which is completely against the notion of a digital signature being a representative of the message which has been signed. If digital signatures did not depend on the messages, then anyone could just strip off a signature by someone, say $A$, from one message and use this signature to sign any document of their choice without $A$ even knowing.
In ECDSA, it is the $s$ value which is coupled with the message hash $z$, so if the $s$ value is completely independent of $z$ (and therefore $m$), then (r,s) is not at all a signature. It is then just a random linear equation between 2 points on an elliptic curve.


Is lattice-based cryptography practical? How viable is lattice-based cryptography in a "practical" setting?

It has been said that lattice-based cryptography would be a "post-quantum" cryptography scheme, but is it feasibly implementable?

Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different types of algorithms, lattice-based algorithms dominate the submissions. These include NTRU and its variants, R-LWE, and FALCON (designed in part by one of our regulars!). Lattice-based cryptography itself is fairly well understood, exploiting lattice problems as a hardness assumption.

Lattice-based cryptography is one of only a few popular designs for post-quantum cryptography. There are others, such as code-based cryptography, multivariate polynomial cryptography, and hash-based signatures. Of those, code-based algorithms are the only class that could realistically compete with lattice-based algorithms, since it is used by the McEliece cryptosystem which itself has been around for quite a while and is well-studied. Multivariate polynomial cryptography is not as popular, and many of the proposed algorithms using it have been broken. Lastly, hash-based cryptography, while quite secure, is only useful for digital signatures, not key exchange. It additionally requires very large signatures. This explains why so many proposed algorithms are lattice-based.

Lattice-based cryptography is also very fast. For example, NTRU performs private key operations even faster than RSA, since the time increases with the cube of the key size for RSA, but quadratically for NTRU. The viability of lattice-based cryptography is undisputed. All we need to do now is iron out the kinks and standardize a particular implementation.


Given enough RSA ciphertext, is it possible to determine which key was used? Given enough RSA ciphertext, is it possible to determine which public key was used to generate the ciphertext?

Presume an unknown public key that was used to generate RSA ciphertext, and we have quite a lot of ciphertext. Would it be possible to determine which key was used to generate the ciphertext?

It seems to me that any ciphertext would be in the range $[0, N)$ where N is the modulus. So if you have enough ciphertext you should be able to estimate a value for N. Now I don't think that this would be enough to establish N even when given enough ciphertext. But I wonder if you could find out which key was used from a set of public keys with some certainty.

Could there be enough information to establish which key is used? Is there a formula that would allow me to calculate the certainty for each key out of a set? Would that formula only consider basic probability over the range or is there anything in the RSA scheme to be more precise?

Only padded RSA with PKCS#1 v1.5 padding or OAEP padding may be considered, not raw/textbook RSA.

Yes, it is possible to determine with some certainty which public key in some known set was used to produce RSA ciphertexts made with the same key in this set, given enough ciphertexts, and if neither the public moduli nor the random padding are made with intend to hide which public key was used.

Assume that the set of $k$ public keys have public moduli $N_i$, ordered in increasing order, and we initially have no clue about which might be the one used. If we chose random padding as in any of the two PKCS#1 encryption paddings (randomly and independently of the RSA key), any of $r$ ciphertexts is essentially uniform on the interval $[0,N_j-1]$ where $N_j$ is the public modulus actually used to produce the ciphertexts. The obvious strategy to guess the public key used is to determine the largest of the ciphertexts $C$; the most likely public key in the set is the one with the $N_i$ immediately superior to $C$, and $i\le j$ holds.

Odds that our guess $N_i$ of the public modulus is right are $1/\sum_{j\ge i}(N_i/N_j)^r$, which depends only on where $C$ falls in-between the public moduli, and the values of these (justification: only $j\ge i$ can hold; for any of these $j$, the odds to get a $C$ not higher than what we actually got were $p(C,N_j)=(C/N_j)^r$ before we knew $C$; all these $j$ were then assumed equally likely; therefore the odd of $i=j$ are the ratio of $p(C,N_i)$ over the sum of the $p(C,N_j)$ for $j\ge i$, which simplifies to the expression given).

Note: it is easy to defeat this guessing; for example, when using 2048-bit $N$, encrypt a given plaintext until the result is 2047-bit or less, before sending it.


In which cases should the IV be kept secret? When must an IV be kept secret?

There is an ambiguity in the way that the lack of need for secrecy of the IV is described in multiple places.  Does this ambiguity suggest that there are, in fact, situations in which the IV must be kept secret?  Or is it a quirk of language that has persisted across several popular sources?

The (ISC)2 Guide to the CISSP states (emphasis mine):

  There is no need for the IV to be secret, in most cases, but it is
  important that it is never reused with the same key.

Crypto.StackExchange:

  IV usually does not need to be secret, However, in most cases, it is important that an initialization vector is never reused under the same key.

Wikipedia:

  An initialization vector has different security requirements than a key, so the IV usually does not need to be secret.

I understand the role the IV plays and the reasons that is is generally considered to be non-secret information.  I am curious if there are situations in which it must be treated as secret information, or if this is merely a linguistic no-op that has gotten repeated.

Normally, in a properly designed cryptographic system, everything that must remain secret is either actual data (and the system exactly aims at preserving that confidentiality) or a key. Everything else ought to be public or at least publishable with no ill effect, as per Kerckhoffs' principle.

Now it so happens that a number of cryptographic systems are expressed as iterative processes, starting with an "initial value" (or "initialization vector"), i.e. an "IV". It is conceivable that in such a system, the IV is a key. A contrived example would be a hand-made stream cipher with a hash function:

A state s is initialised to some value.
The stream cipher produced pseudo-random bytes by repeatedly hashing s: the first bytes of output are H(s), then H(H(s)), and so on.

Such a stream cipher is then an iterative process that repeatedly produces the next value of the "running state" by hashing that state. The starting value for the state is thus an initial value in the strict sense of the term, and is also the key for the stream cipher, hence the need for secrecy.

This is, however, a quite contrived example. This stream cipher is atrociously weak in several ways (don't use it!). In a properly designed cryptographic system, we really prefer it when keys are reusable: keys that can be used only once tend to imply issues (it was one of the problems with RC4). Instead, we prefer keys that can be used several times (e.g. to encrypt several messages), possibly along with other values that need not be secret, but must be changed each time. This is what normally happens with encryption system: a secret key, that can be reused for several messages, and a per-message "nonce" that must be generated anew for each message, but needs not be secret; hence, the nonce can be transmitted along with the message. The "IV" in most encryption systems fulfils this "nonce" role.

In a more conceptual point of view, the notion of "IV" is not precisely defined. Thus, expressing an absolute such as "IV never need to be secret" is bound to anger somebody, somewhere, would used an IV in a slightly exotic way and found a situation where something can be called an "IV" and still requires secrecy. Using a phraseology like "usually" or "in most cases" is a simple way to avoid triggering an acrimonious debate.


Is it possible to decrypt double-key crypted file knowing public key and a having one or more original files? I have some encrypted files with double-key. I know public key and don't know private key. Can I obtain the private key (and decrypt all files) using two version of one file - crypted and decrypted? And if yes, how?
Thanks a lot.

Short answer: No.

Public Key Encryption Basics

In public key encryption, public key is used to encrypt and private key is used to decrypt. It is not possible to decrypt using public key. It is also not possible to use public key to find private key.
The opposite is commonly true: if you have private key, you likely can easily derive matching public key.

Using two versions of one file, crypted and decrypted, it may be possible to derive the public key. However, again, it will not be possible to use that for deriving the private key.

Implementation issues

The security properties you asked about are generally provided by public key cryptography. However, given the fact that it is not known what program was used and what key length + what padding, so the answer is based on assumption of ideally implemented public key cryptography.

In theory the files will be safe (i.e. undecryptable) from parties without access to the private key. In practice, theory is not neccessarily accurate.


Elliptic ElGamal Public Key Cryptosystem doubt I need an example of Elliptic ElGamal Public Key Cryptosystem. I have been trying with some values but I don't get the right solution.

I have $p=13$, the elliptic curve $E:y^2=x^3+11x+7$ and a point $P=(6,\sqrt{3}) \in E(\mathbb{F}_{13})$.

The message is $M=(0.5,12.625)\in E(\mathbb{F}_{13})$.

Alice, chooses the value $nA=5$, calculates Q$_A=n_A \cdot P=(2.5,11.125)$ and sends $Q_A$.

Bob chooses the integer $k=2$ randomly and calculates $C_1$ and $C_2$:
$$C_1=k⋅P=(12,\sqrt{23})$$
$$C_2=M+k⋅Q_A=(5.5,8.875)$$

Bob sends $(C_1,C_2)$ to Alice.

Alice calculates M: $$M=C_2−n_A⋅C_1=(−2.5,−8.4455)$$ and the solution should be $ M=(0.5,12.625)$ ... Does someone know what is wrong? I think that my problem is calculating in $\mathbb{F}_{13}$, but I'm not sure.

Thank you :)

In points of elliptic curve instead of $\frac {a}{b} $ you should use $a\cdot b^{-1} \pmod p$. Also: $$\sqrt3=\{i \in [0,12]|i^2=3 \pmod {13}\}=\{4,9\}$$  So $P=(6,4)$ or $P=(6,9)$ which $2\cdot P$ are $(10,8)$ and $(10,5)$ respectively. But your computation show that $2\cdot P=(12,\sqrt {23})$.

Also with $x=12$ we have't a solution for $y$ in your elliptic curve.


SHA-256 Round Equivalence I have calculated the average number of operations in 1 round of SHA-256 as follows:

Additions: 9.25
Bitwise Rotations: 9
Bitwise Shifts: 1.5
Bitwise AND: 5
Bitwise XOR: 10

I have certain proposals that save the following number of operations in one SHA256 evaluation (i.e. 64 rounds) for Bitcoin mining:

Additions: 24
Bitwise Rotations: 12
Bitwise Shifts: 6
Bitwise AND: 0
Bitwise XOR: 12

My question is, how can I represent the above savings in terms of SHA256 rounds?

Do I just consider the additions? So that the saved operations above are equivalent to 24/9.25 = 2.5946 SHA-256 rounds per evaluation?

Ideally, you'd implement both versions of the SHA-256 algorithm on some common platform, benchmark them and compare their performance.  This would give you a measure of their actual real-world performance, or at least something close to it.

If that's not practical, the next option would be to map each operation to some nominal number of CPU cycles typically required to execute it on your target platform (or possibly to nominal gate equivalents, if you're considering hardware implementations instead).  Of course, even this measure will still be somewhat platform-dependent.  Also, for modern superscalar CPUs, "typical" per-instruction cycle counts may not be all that useful as a performance metric, since actual performance will depend highly on the amount of instruction-level parallelism present in the code.

Finally, for a quick back-of-the envelope estimate, you could simply assume that all the basic arithmetic operations you listed (additions, rotations, shifts, bitwise ops) take the same time to execute, and simply add the operation counts together.  Indeed, for many CPUs, this may be reasonably close to the truth: even if the actual execution times differ, they probably won't differ by more than a factor of 2 or 3 at most.

In particular, it's generally pretty safe to assume that addition and bitwise ops are among the fastest instructions on any CPU, and that they'll each take the same number of cycles to execute.  Shifts may or may not be slower, depending on the CPU and the type of the shift: one-bit shifts are nearly always fast (and a one-bit left shift can be emulated by addition anyway), but there are some CPUs that have slow multi-bit shifts, and shifts by a non-constant amount may be even slower.  Rotations are even more of a mixed bag, but you can generally assume that they're no faster than an equivalent shift and no slower than two shifts (because you can always emulate a rotation using two shifts plus an addition / OR / XOR, and the latter can often be amortized away).

For some example timings, see e.g. this report by Torbjörn Granlund, titled "Instruction latencies and throughput for
AMD and Intel x86 processors".  Looking at the first two tables, it seems that all the operations you listed do indeed have pretty much identical latencies and throughputs on AMD processors, whereas on Intel processors the throughput varies somewhat (but still by no more than a factor of 3).  Of course, all those timings are somewhat artificial, and performance of actual code with mixed and partially interdependent operations may vary noticeably from the "nominal" values.


BouncyCastle Elliptic Curve implementation I'm implementing ECDH key exchange in C# using the BouncyCastle library and I'm having a hard time understanding the elliptic curve side (FpCurve).

FpCurve curve = new FpCurve(
    new BigInteger("883423532389192164791648750360308885314476597252960362792450860609699839"), // q
    new BigInteger("7fffffffffffffffffffffff7fffffffffff8000000000007ffffffffffc", 16), // a
    new BigInteger("6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a", 16)); // b

ECDomainParameters ecSpec = new ECDomainParameters(
    curve,
    curve.DecodePoint(Hex.Decode("020ffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf")), // G
    new BigInteger("883423532389192164791648750360308884807550341691627752275345424702807307"), // n
    BigInteger.One); // h

I'm wondering if this is correct, what it means and why would this be static? What are these BigInteger values?

I am assuming you are throughly familiar with traditional Diffie-Hellman. If not, read up on it first.

For our purposes here, an elliptic curve is a curve whose points satisfy the equation $y^2=x^3+ax+b$. That right there tells you what $a$ and $b$ are, they are coefficients of the curve.

In elliptic curve cryptography, we need an algebraic group for a number of algorithms (such as Diffie-Hellman). For elliptic curves, we can get this by taking the curve equation above modulo a prime number (in this case the $q$ value in your code), i.e. $x$ and $y$ are elements of $\mathbb Z_q$, and the $+$ and $·$ operations are done in this field.

For diffie-hellman we need a point on the curve that can generate a very large subgroup (for more info see this question). That point is the $G$ in your code. $n$ is the order of the subgroup generated by $G$ and $h$ is the cofactor (basically it tells us how much smaller is the subgroup when compared to the original group, don't worry too much about this one).

The reason they are static is that they are public parameters. Think of regular diffie-hellman. There are typically numbers $p$ and $g$ which need to be known to both parties. $p$ describes the group we are working in $\mathbb{Z}_p^*$ (just like $q,a,b$ describe the elliptic curve group) and $g$ is the generator (as is $G$ for elliptic curves). In regular diffie-hellman $p$ and $g$ can be static in your code (otherwise the 2 parties have to agree upon the values some how).

You now know what the values are and why they can be static. So, are the values you've chosen correct? Well, where did they come from? There are a number of standard curves (for example FIPS 186-3). If I were you, I'd stick to recommended/standard curves.


Why does Smart's attack only work on anomalous curves? Nigel Smart's attack solves the discrete logarithm problem in linear time. It requires the curve, however, to be anomalous, i.e. to have a trace of Frobenius equal to one or, equivalently, to be of the same order as the underlying field, $\#E=p$.

Smart's paper is here: http://www.hpl.hp.com/techreports/97/HPL-97-128.html

I'm trying to understand why it doesn't work for other curves? I'm guessing that it has something to do with the properties of the p-adic logarithm but I can't quite put my finger on it.

Any hint or explanation will be appreciated.

You can find an answer at section 5.4 of Washington's Elliptic Curves: Number Theory and Cryptography.

Following their notation (and skipping the technical details about reduction $\mod p$ and $E_r$ subgroups), let $N=\#E$ and assume $p\nmid N$. Let $\ell_1=\lambda_1(N\tilde P)$, $\ell_2=\lambda_1(N\tilde Q)$, so that $k\equiv \ell_2/\ell_1 \mod p$ (we want to prove this). Set also $\tilde K = k\tilde P-\tilde Q$. We have

$$k\ell_1 - \ell_2=\lambda_1(kN\tilde P-N\tilde Q)=\lambda_1(N\tilde K)\equiv N\lambda_1(\tilde K) \mod p.$$

In the last step you cannot continue, because the initial assumption makes $N$ invertible $\mod p$ and you can't say that this equals $0$, failing to prove that $k\equiv \ell_2/\ell_1 \mod p$. You can see that this proof does work if $p$ divides $N$.

To my understanding, this would mean that if $p$ divides the number of points, then you may also perform the attack, but I haven't read enough on it to confirm this.


More efficient and just as secure to sign message hash using Ed25519? According to the Ed25519 paper, the (potentially long) input message is hashed twice (see Section 4 page 12 steps 1 and 3).  This webpage has a nice diagram toward the bottom that illustrates this, and I confirmed it in the reference code on Supercop (see supercop-20141124/crypto_sign/ed25519/ref/sign.c, function calls  crypto_hash_sha512(nonce, sm+32, mlen+32) and crypto_hash_sha512(hram,sm,mlen + 64)).

My question is, for long messages, wouldn't it be more efficient and just as secure to hash the entire message just once, and then use the 64 byte hash as the input to the signing algorithm?  In other words, the code would look like:

crypto_hash_sha512(mhash, m, mlen);
crypto_sign(output, mhash, 64, key);

The would seem to me to be faster for mlen > approx 128 bytes without any loss of security.

I'm I missing something here?  Is there a potential loss of security to using mhash as the signing input instead of the original message m?

Peter Schwabe, one of the authors of Ed25519, directed me to a recent paper titled "EdDSA for more curves".  The section "Security notes on prehashing", page 5, says that the Ed25519 algorithm without prehashing the message is resistant to collisions in the hash function, while using the algorithm with prehashing is not.  Of course the hash function is not supposed to have collisions, but if it does, not prehashing gives added protection.


Is it proven that breaking RSA is equivalent to factoring as of 2021? I can't find any publication that proves this.

There is no proof that the integer factorization is computationally difficult and similarly, there is no proof that the RSA problem is similarly difficult.
The RSA problem
RSA problem is finding the $P$ given the public key $(n,e)$ and a ciphertext $C$ computed with $C  \equiv P^e \pmod n$.
Factoring $\implies $ the RSA problem
This is the easiest part. If we can solve the factoring problem then we can solve the RSA problem by factoring the modulus $n$. This implies that the RSA problem is at least as easy as factoring. This doesn't eliminate the case that it might well be easier.
The RSA problem  $\stackrel{?}{\implies} $ Factoring
The most well-known work on the reverse of the problem goes back to 1998

D. Boneh and R. Venkatesan Breaking RSA may not be equivalent to factoring

We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. Thus, in effect an oracle for breaking RSA does not help in factoring integers. Our result suggests an explanation for the lack of progress in proving that breaking RSA is equivalent to factoring. We emphasize that our results do not expose any weakness in the RSA system.

Here, we should note that the RSA problem is the decryption of a specific ciphertext, whereas the factoring reveals the private key $d$ thus all ciphertext under encrypted the same public key.
If we consider the problem of finding the private exponent $d$ then it is proven by Miller to be computationally equivalent to factoring $n$;

1976 Riemann's Hypothesis and Tests for Primality

The below work went on the generic ring model ( in short: a ring has no special property than being a ring) and show the equivalence;

2009 - Divesh Aggarwal and Ueli Maurer - Breaking RSA Generically is Equivalent to Factoring

We show that a generic ring algorithm for breaking RSA in $\mathbb Z_N$ can be converted into an algorithm for factoring the corresponding RSA-modulus $N$. Our results imply that any attempt at breaking RSA without factoring $N$ will be non-generic and hence will have to manipulate the particular bit-representation of the input in $\mathbb Z_N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

This work creates a strong belief in the reverse problem; factoring is equivalent to the RSA problem, however, no proof yet!
Also a notable work on comparing $e$-th root algorithm with the factoring algorithms to see the trend;

2007: Antoine Joux and David Naccache and Emmanuel Thomé When $e$-th Roots Become Easier Than Factoring

We show that computing $e$-th roots modulo n is easier than factoring n with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i+c$.

As a result, we still have;
$$\text{the RSA problem} \stackrel{?}{\implies} \text{Factoring }$$

If factoring can be solved in polynomial time ( a common belief noted by Meir Moar) then by using the reduction from Hamiltonian Path to Factoring as Haldeman did in their DNA factoring then with the Karp's 21 reductions we can solve the $NP$-complete problems in polynomial time with factoring.

Dan Boneh's article with 977 citations is a good starting point to see the RSA's 20 years;

1999: Dan Boneh - Twenty Years of Attacks on the RSA Cryptosystem


Multiple-prime RSA; how many primes can I use, for a 2048-bit modulus? In standard RSA, the modulus $n=p_1 p_2$ is a product of two primes $p_1,p_2$ of the same size.  Suppose we construct the modulus as a product of multiple primes $p_1,\dots,p_k$, i.e., $n=p_1 p_2 \cdots p_k$, where all the primes are of about the same size.  I'm wondering how much this reduces the security of RSA, for typical modulus sizes.

Let me be more concrete.  I want security comparable to that obtained with standard RSA with a 2048-bit modulus.  Can I use $k=3$ (three primes) without significant loss of security?  $k=4$?  What's the largest number of primes $k$ that I can use, without significant loss of security?  Assume that each prime is $2048/k$ bits long, so all the prime factors are of equal length.

Related: see also Who first published the interest of more than two prime factors in RSA?, which asks about the inventor of this technique.  I'm asking something slightly different; in this question, I'm not asking about its inventor; I'm asking about concrete security levels.

If we consider an RSA modulus $N$ of $n$ bits ($n=2048$ in the question) product of $k$ primes of about $n/k$ bits, how high can be $k$ without loosing security? That's a problem studied even before Multiprime-RSA was named, with no definitive answer other than: we can't err on the unsafe side with $k=2$.

Why would we want $k>2$?

For classical multiplication algorithms implemented in software or hardware with fixed word size (which covers all hardware and many software implementations I know), using the standard method described here, there's a potential effort saving of the RSA private-key function by a factor up to about $k^2/4$ compared to $k=2$, and a lot of that speedup is achieved in practice; plus it allows simple and efficient parallelization on $k$ cores.
When there is hardware to perform modular multiplication that enforces a maximum modulus width, increasing $k$ is the only way to increase $n$ (thus security against factoring) while making any use of this hardware resource.
The algorithms [GNFS and previously (MP)QS] that hold factoring records for $k=2$ have run time dependent of $n$ with no influence of $k$; thus the security against factorization attacks using these algorithms remains unchanged when $k$ grows with constant $n$.
Given a public-key and its certificate, and (side-channel-free) access to a black box implementing the RSA private-key function $x\mapsto x^d\bmod N$, the best known way to tell if $k=2$ involves factoring $N$; thus we can increase $k$ without fear of interoperability with devices concerned only with the public-key.

Why would we want to summarily stick to $k=2$?

That's mandated by US standard FIPS 186-4 ever since it includes RSA, and by reference for compliance to some or all of FIPS 140; by French official RGS recommendations; and by pretty much every security authority making recommendations on key size as listed by this reference website, last time I checked; and then some.
In countless cases $k=2$ is the only thing compatible with what's around. One example out of many, in the field of Smart Cards: the Java Card 3 Classic API.
While PKCS#1 standardizes Multi-Prime RSA and even a private-key exchange format for that, there are devices, including some claiming PKCS#11 compatibility, that do not support it. If you want to move the private-key to a different device, or even make a backup of a key generated on-board in a future-proof format, beware!
Some modular exponentiation hardware or software wants prime factors $p$ which exact bit size is multiple of something (usually a power of two, e.g. 64); that's another interoperability hurdle (and in the context of $n=2048$, $k=3$, being a multiple of 64 would force one prime to be 640-bit, rather than 683-bit). Note: it can be worked around by reducing modulo an appropriate multiple of the prime during modular exponentiation, then doing a final reduction.
There has been patents (now expired) delivered at least in USA and Europe (US 5,848,159, US 7,231,040, EP0950302) that created fear, uncertainty and doubt as to whether using Multiprime-RSA cames with a legal risk.

What other things are to be considered when pondering $k>2?$

Main one, by far: the effort (by any measure) of factorization attacks using ECM increases (faster than polynomially) with $n/k$, thus tremendously decreases with $k$ for constant $n$. And the adversary (which, we must assume, knows $k$) has the choice of the factorization method, and will choose ECM if advantageous. All the literature I know (listed below) on deciding $k$ thus aims at choosing it as high as possible so that the expected effort (or runtime, cost..) of ECM is no lower than that of GNFS, sometime with a projection of these expected efforts in the future; the $k$ of the crossover is of course rounded down.
ECM is easy to distribute on many commodity computers that need almost no communication with each others, when as far as we know the matrix step in GNFS requires a heavily connected supercomputer with enormous amounts of memory (or perhaps, spending some binary orders of magnitude more computing power in the sieving step that dominates the computing effort for current parameterizations). That somewhat invalidates comparisons between GNFS and ECM that consider computing work, effort or runtime, rather than some attempted measure of cost [Comparatively minor related aside: ECM reportedly can take advantage of GPU; but that might not be much of an argument, since GNFS could in the future benefit from GPU, by way of using ECM internally].
Since the advent of computers, and even in this century, we have not had a precise crystal ball when it comes to future runtime (much less cost) of published factorization algorithms (and that can only be worse for their relative cost, or if we consider unpublished improvements or algorithms). Whatever comparison we make between ECM and GNFS, the more in the future we want security, the more margin we should take on the ground of these uncertainties, and shift the balance towards lower $k$ (before rounding).
AFAIK, no implementation of Multiprime-RSA has been checked for side-channel attacks by a certification lab. That's not a mere certification issue: it is not unreasonable to fear that either the smaller primes, or the final CRT step (necessary to get any speed benefit) makes an implementation more vulnerable to side-channel leakage. That's a potential issue at least in HSMs operated in non-trusted environments, and Smart Cards.
When using ECM, odds that the factorization will be found after a fraction $\epsilon$ of the expected work are about $\epsilon$ (for $2^{-20}\le\epsilon\le0.3$ and common ECM parameters). That's in contrast with GNFS and QS, where we simply can't get the factorization until the last few percents of the expected work. If we want residual risk $\epsilon$ that an adversary succeeds with a certain work, we should aim for at least that work for GNFS, and at least $1/\epsilon$ times that work for ECM; that shifts the crossover towards lower $k$ (before rounding). In security, there is no consensus on acceptable residual risk to known attacks, and I have seen such $\epsilon$ entirely ignored, or set from 5% (for an overall system) to $2^{-40}$ (for symmetric cryptography where admittedly there is no strong incentive to tune that).
When we want to generate $m$ keys, and the adversary would be content to factor any single one (as is often the case when the keys are used for authentication or signature in a machine-to-machine application), we should pay some attention to two other factorization algorithms: Pollard's p-1 and Williams' p+1. Problem is: with primes of size $n/k$ chosen randomly, these algorithms (especially the first) substantially surpass ECM on the standpoint of the ratio $\text{odds to factor}\over\text{runtime}$ for small $\text{odds to factor}$. Thus an adversary will get a benefit by trying Pollard's p-1, then Williams' p+1, on the $m$ moduli available, before using ECM; and can do so with benefit on a fraction of the expected work proportional to $m$. To confirm this: GMP-ECM practitioners use that strategy, with significant success for p-1, and to a lesser extend for p+1. Rather than assessing this risk, we can generate the primes $p$ in a way such that $p-1$ and $p+1$ have a known high prime factor, which makes these algorithms useless (that's feasible efficiently if not simply, e.g. as explained in FIPS 186-4 appendix B.3, which for $k=2$ mandates that for primes of 512 bits, but not 1024 bits).
It should also be taken into account in the balance that ECM is expected to require near $k$ times less work to factor a Multiprime-RSA $N$ than a random $N$ of comparable size with lower prime factor of size $n/k$.

References

Restricting to the current century, I know only 4 references that deal with finding a balance for $k$:

Arjen K. Lenstra: Unbelievable Security: Matching AES security using public key systems, Asiacrypt 2001 (alternate link).
Dan Boneh, Hovav Shacham: Fast variants of RSA, with abridged version in CryptoBytes, Vol. 5, No. 1, 2002.
M. Jason Hinek: On the Security of Multi-prime RSA, Technical Reports of the Centre for Applied Cryptographic Research (CACR) at the University of Waterloo, 2006 (alternate link).
Jean-Sébastien Coron, Aline Gouget, Pascal Paillier, Karine Villegas: SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, pay-walled with free extract)

A recent answer!

The later reference briefly touches the nearly identical problem of the size of $p$ in unbalanced RSA (1. differs in the rounding to get $k$, 4. may differ w.r.t. final CRT step, 7. does not apply). The authors conclude that $n=2048$, $p=560$ gives a good balance; from which it would follow that $k=3$ is fine, but $k=4$ is not. This is based on an analysis of ECM and GNFS (taking into account only 1. as far as I can tell) with reference to:

Paul Zimmermann, Bruce Dodson: 20 Years of ECM, In Proceedings of the 7th Algorithmic Number Theory Symposium, 2006 (alternate pay-walled link).
Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, Paul Zimmermann: Factorization of a 768-bit RSA modulus, in the proceedings of Crypto 2010.

A recent data point about ECM: in late 2013, Ryan Propper reported using GMP-ECM 6.4.3 + GMP 5.1.0 to find a 274-bit factor from the 787-bit composite $(7^{337}+1)/8/101020140256422276570987002251440602782290400709$ product of two unknown primes, on a commodity CPU using less than 6GB of RAM. He further reports that was a 10-day effort on Stanford's University cluster, and the factorization was found after 5000 curves. By extrapolating the log I get a runtime of 16 hours/curve and an expected $2^{21}$ curves (about $2^{12}$ core.years), and if that's any close to correct, an average of more than 300 cores have been used, and odds of finding that factorization so fast where 1/400; "this was quite the lucky find" is an understatement. The second largest of the ECM records is also quite a lucky one; which, if one considers 5. above, is to be expected!


Why RSA-KEM is more secure than Textbook-RSA? I am studying RSA-KEM but I can not see why it should be as secure as padding RSA messages (e.g with RSA-OAEP) when exchanging a key between two parties (say A and B).

It is easy to see that Textbook-RSA is problematic, as sending a key with $k_1^{e_B} \bmod n$ leaves the possibility for an attacker to analyze the message. Let's say that by coincidence A sends to B a second key $k_2^{e_B} = (42 k_1)^{e_B} = 42^{e_B} k_1^{e_B}$ (in the following $\bmod n$ is always omitted). An attacker could easily notice this as it could divide $k_2^{e_B}$ by $42^{e_B}$.

Now let us suppose that A and B are using RSA-KEM to exchange keys. An attacker cannot detect anymore if e.g. $k_2 = 42 k_1$ as a key encapsulation key is used to encrypt the shared key. However, the random integer to generate the key encapsulation key is still encrypted over Textbook-RSA.

Why is this not a problem? An attacker is still able to perform e.g. statistical analysis on the randomly exchanged integer, e.g. if A and B again perform two key exchanges and it happens that $r_2 = 6943 r_1$ an attacker may be able to notice this and eventually even find out the random integers, thus breaking the shared key as it depends on these integers.

Why is this not a problem?

Because for two different encryptions the random integers are drawn independently and uniformly at random over the whole range of the multipicative group $\mathbb Z_N^*$ (in practice this is usually approximated as $[1,n)$). The RSA assumption now literally states that it's difficult to recover the random value from its textbook RSA encryption if it is sampled in this way.

  if A and B again perform two key exchanges and it happens that $r_2 = 6943 r_1$ an attacker may be able to notice this and eventually even find out the random integers

Actually this won't happen because both $r_1,r_2$ are independently random, so is their group combination $r_1/r_2$ which has a chance of $2^{b-n}$ to be smaller than $2^b$ for $n$-bit RSA moduli, so for a really generous estimate suppose you are betting on $r_1/r_2$ to be guessable small, say smaller than $2^{60}$ and using weak 1024-bit RSA encryption, then you have a chance of $2^{60-1024}\approx 2^{-940}$ of the quotient being sufficiently small. This is a really negligible probability and likely won't ever be observed.


Why did MD4 replace MD2? MD2 was a hash function based on swapping bytes in a state array permutation, much like the RC4 stream cipher, whereas MD4 was a novel construction. MD4 replaced MD2 despite the fact that MD4 is more badly broken. Even MD5, an improvement upon MD4, is more badly broken than MD2 is! The best collision attack against MD2 has a time complexity of 263.3 compression function evaluations and a memory requirement of 252 hash values, which is only slightly better than the birthday attack and not significantly different from the collision attack against SHA-1 (263.1 time). It seems to me like people could have saved a lot of trouble by using MD2 until the collision attack became feasible, skipping MD4, MD5, and even SHA-1, but clearly this did not happen. So why was MD2 dropped for MD4 and friends?

We can get some clues from the various Internet RFCs defining or mentioning the three algorithms. There appear to have been two advantages of MD4, and subsequently MD5:

Performance
Licensing

It also appears that an attack on MD2 was expected long before one was found for MD5, even if none was actually found.

August 1989: RFC 1115 defines MD2. It is presented as part of a series of RFCs for Privacy Enhanced Mail. It states simply:

  It has been provided by Ron Rivest of RSA Data Security, Incorporated for use in
     support of privacy-enhanced electronic mail, free of licensing
     restrictions.

The "specification" is simply the source code of a reference implementation in C, dated "10/1/88" (presumably 1st October 1988)

October 1990: RFC 1186 defines MD4. Oddly, there is no mention of MD2 in the entire document.

Unlike RFC 1115, MD4 is presented as a general purpose algorithm, rather than as part of a particular framework:

  The MD4 algorithm is thus ideal for digital signature applications, where a large file
     must be "compressed" in a secure manner before being signed with the
     RSA public-key cryptosystem.

Intellectual property rights are also more clearly waived for any and all purposes:

  The MD4 algorithm is being placed in the public domain for review and
     possible adoption as a standard.

There is a clear emphasis on the algorithm's performance:

  The MD4 algorithm is designed to be quite fast on 32-bit machines.
     On a SUN Sparc station, MD4 runs at 1,450,000 bytes/second.  On a DEC
     MicroVax II, MD4 runs at approximately 70,000 bytes/second.  On a
     20MHz 80286, MD4 runs at approximately 32,000 bytes/second.  In
     addition, the MD4 algorithm does not require any large substitution
     tables; the algorithm can be coded quite compactly.

Buried in the summary is a disclaimer that this is a novel algorithm, and may need further scrutiny:

  The MD4 algorithm has been carefully scrutinized for weaknesses.  It is,
     however, a relatively new algorithm and further security analysis is
     of course justified, as is the case with any new proposal of this
     sort.

April 1992: RFCs 1319, 1320, and 1321 respectively re-define MD2 and MD4, and define MD5

Although clearly published as a series, there doesn't appear to be any comparison of MD2 against MD4 or MD5 in any of these three. All three RFCs include a reference implementation that actually implements all three algorithms.

RFC 1319's main purpose is to provide a textual description of the algorithm, and a more portable reference implementation. It also incorporates the purpose statement applied to MD4:

  The MD2 algorithm is intended for digital signature applications, where a
     large file must be "compressed" in a secure manner before being
     signed with a private (secret) key under a public-key cryptosystem
     such as RSA.

Although it goes on to say:

  License to use MD2 is granted for non-commerical Internet Privacy-Enhanced Mail

Which appears to be more restrictive than "placed in the public domain", and makes it ambiguous whether the algorithm could be used outside that realm, if it was protected by any intellectual property laws.

Under "Security Considerations", confidence in MD2's security is stated bluntly:

  The level of security discussed in this memo is considered to be
     sufficient for implementing very high security hybrid digital
     signature schemes based on MD2 and a public-key cryptosystem.

RFC 1320 is a minor revision of the previous MD4 description, with the new reference implementation.

The concerns previously mentioned in the Summary are now prominent in the Security Considerations section, with a mild recommendation to try MD5 instead:

  We do not know of any reason that MD4 would not be sufficient for
     implementing very high security digital-signature schemes, but
     because MD4 was designed to be exceptionally fast, it is "at the
     edge" in terms of risking successful cryptanalytic attack. After
     further critical review, it may be appropriate to consider MD4 for
     very high security applications. For very high security applications
     before the completion of that review, the MD5 algorithm [4] is
     recommended.

RFC 1321 is the first to define MD5. Its introduction includes most of the same claims of speed, compactness, and general applicability as MD4, along with an explanation for why a new algorithm was designed:

  The MD5 algorithm is an extension of the MD4 message-digest algorithm. MD5 is slightly slower than MD4, but is more "conservative" in
     design. MD5 was designed because it was felt that MD4 was perhaps
     being adopted for use more quickly than justified by the existing
     critical review; because MD4 was designed to be exceptionally fast,
     it is "at the edge" in terms of risking successful cryptanalytic
     attack. MD5 backs off a bit, giving up a little in speed for a much
     greater likelihood of ultimate security. It incorporates some
     suggestions made by various reviewers, and contains additional
     optimizations.

It also includes the same unambiguous licensing statement:

  The MD5 algorithm is being placed in the public domain
     for review and possible adoption as a standard.

March 1998: RFC 2313 references all three algorithms. After repeating that MD4 is "on the edge" because of its emphasis on speed, it compares MD2 and MD5:

  MD5, which has four rounds and is proportionally slower
               than MD4, is recommended until the completion of MD4's
               review. The reported "pseudocollisions" in MD5's internal
               compression function [dBB93] do not appear to have any
               practical impact on  MD5's security.

  MD2, the slowest of the three, has the most conservative
               design. No attacks on MD2 have been published.

April 2002: RFC 3279 references MD2. It includes this interesting note, which confirms my suspicion about licensing issues with MD2:

  MD2 was developed by Ron Rivest for RSA Security.  RSA Security has
     recently placed the MD2 algorithm in the public domain.  Previously,
     RSA Data Security had granted license for use of MD2 for non-
     commercial Internet Privacy-Enhanced Mail (PEM).

It doesn't give any reference for this release, so it's not clear how "recent" it was.

It also somewhat contradicts the assertion quoted above from RFC 2313, citing a partial attack on MD2 published in 1995:

  At the Selected Areas in Cryptography '95 conference in May 1995,
     Rogier and Chauvaud presented an attack on MD2 that can nearly find
     collisions.  Collisions occur when one can find two different
     messages that generate the same message digest.  A checksum operation
     in MD2 is the only remaining obstacle to the success of the attack.
     For this reason, the use of MD2 for new applications is discouraged.

March 2011: RFCs 6149, 6150, and 6151 retire or update the status of all three algorithms. 19 years after the previous series, we get some retrospective analysis.

RFC 6149 retires MD2, citing as rationale:

  MD2 was published in 1992 as an Informational RFC.  Since its
     publication, MD2 has been shown to not be collision-free [ROCH1995]
     [KNMA2005] [ROCH1997], albeit successful collision attacks for
     properly implemented MD2 are not that damaging.  Successful pre-image
     and second pre-image attacks against MD2 have been shown [KNMA2005]
     [MULL2004] [KMM2010].

It gives a list of RFCs which reference MD2; most appear to have offered it as an option alongside MD5.

More interestingly for our purposes, it notes that:

  MD2 has also fallen out of favor because it is slower than both MD4
     [MD4] and MD5 [MD5].  This is because MD2 was optimized for 8-bit
     machines, while MD4 and MD5 were optimized for 32-bit machines.  MD2
     is also slower than the Secure Hash Standard (SHS) [SHS] algorithms:
     SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512.

RFC 6150 retires MD4, with a similar, but stronger rationale. Amusingly, there are a number of accidental mentions of "MD2" instead of "MD4" in the RFC text, but there doesn't appear to be any explicit comparison.

Unlike MD2, the RFC includes extensive documentation on breaks in MD4; it seems Rivest was right to warn of its untested nature in 1992.

RFC 6151 doesn't go as far as retiring MD5, instead advising against some uses.

  Where the MD5 checksum is used inline with the protocol
     solely to protect against errors, an MD5 checksum is still an
     acceptable use.

but

  MD5 is no longer acceptable where collision resistance is required
     such as digital signatures.

It makes no mention of MD2 or MD4, other than referencing papers that covered both MD4 and MD5 in their cryptanalysis.


Should I use a self-designed Block Cipher Mode of Operation? We all know we should NOT roll our self-designed encryption algorithm, how about block cipher mode with a certificated cipher method like AES? Will a self-designed block cipher mode cause any flaws or weakness to the cipher?

I have search over the Internet but can't find a answer. Hope here is the right place to ask such a question.

Similar concerns apply as to any self-designed cryptographic algorithms. Standard block cipher modes usually have security proofs. If yours does not then even if it seems correct you may be missing some weakness.

An example of where security proofs of cipher modes are clearly important is the CCM mode (pdf). The same cipher key is used both for CBC-MAC authentication and to produce the CTR blocks used for encryption. This key-reuse is generally a bad idea and in a home-baked mode could be a weakness, but is proved safe in the particular composition used.

Very simple modes may be easy to prove secure yourself. However, I doubt those have any real advantages over using a standard mode either.


Key material leak from initialized cipher? Let's imagine that cipher (say AES256 in CBC mode) is initialized when application starts:

C = cipher.Create
K = kdf(password, iterations, salt)
C.Initialize(K, iv)
burn(K)

At this point I have initialized cipher C. Key K is burned. Cipher C will be used to encrypt/decrypt data on demand (data source is encrypted file).

If I plan to keep instance of initialized cipher C in memory for lifetime of my running application, can I assume the key material from inside initialized cipher can be captured (memory dump etc) and re-used by attacker? Or in other words, is keeping initialized cipher in memory basically equal to keeping key in memory? If so, what can be done to avoid this kind of leak?

Or in other words, is keeping initialized cipher in memory basically equal to keeping key in memory?

In the case of AES, yes, every time you encrypt (or decrypt) another block of data you need the key (or equivalent information, like the round keys), so the cipher instance must have it somewhere.

Other ciphers (like Keccak's AE mode) may allow encrypting more and more material without needing the actual key anymore. Even then knowing the cipher state would allow an attacker to at least decrypt later parts of the ciphertext, but not necessarily earlier parts.

  If so, what can be done to avoid this kind of leak?

If there is some kind of key store and encryption facility in the OS or hardware, that could make the attacker's life more difficult, as they might need root access rather than just a view of the process memory.

However, access to the running application could allow the attacker to call into that secure facility anyway, allowing them to break the encryption even if they do not get the key. So better if the attacker does not have access in the first place. I.e. avoid security bugs that would allow memory dumps or code execution. Easier said than done, of course.


Why are the outputs of the md5sum tool and Crypto++'s MD5 different? Could you please tell me what is the difference of coreutils' md5sum and sha*sum tools (sha1sum, sha224sum, etc.) compared to Crypto++'s digest functions?

I've written a piece of code using Crypto++ hash functions but the result is different from the corresponding Unix tools'.

For example if I write in command line:

 echo test123 | md5sum

I get:

4a251a2ef9bbf4ccc35f97aba2c9cbda

but the Crypto++ MD5 function results with:

cc03e747a6afbbcbf8be7668acfebee5

Similar things happens when I use another digest functions (as mentioned earlier).

Both Unix and Crypto++ manuals says it simply calculates digest, but says nothing about output format.

I can see both have the same length, both seem to be in hexadecimal form (0-f) and moreover when I type the hashes into Google, in both cases it says that it is an MD5 hash of test123.

Do you have any ideas about it?

The echo command appends a new line at the end, by default. The -n option omits this character. Compare these two executions:

> echo -n "test123" | md5sum
cc03e747a6afbbcbf8be7668acfebee5

> echo "test123" | md5sum
4a251a2ef9bbf4ccc35f97aba2c9cbda

So the difference between the hash values is simply caused by the new line character.


Retrieving correct ciphertext from additive ElGamal I have been studying additive ElGamal and I think I have the hang of it except the part where the message $M$ must be retrieved by computing the discrete log of $g^M$.

From what I've read, the result of such computations is a function of $k$ e.g. for $g=3, M=4, \pmod{17}$ we have $3^4=13 \pmod{17}$ but computing the discrete log however gives $M=4 + 16k$. How do I know that $M=4$ and not $M=20$?

Note that for $g=3,M=20 \pmod{17}$ we also get $M=4+16k$.

The answer is simple if you know the answer to this question:

  Can you use 20 instead of 4 for a plaintext?

If you can they will be the same encryption and no problem since 20 and 4 same for yo.
If you cannot, therefore, you cannot decide the plaintext after you decrypted.

To solve this issue you have to limit your message space into $\pmod{17}$ and divide your longer message block in an appropriate way. Now, you know, you have to take the smallest positive value where $k=0$.

The problem with adding homomorphically is a different issue. Before the computation, you have to consider the upper bound of your calculations and choose your modulus according to it. For example, if you are going to add 4 and 8 there is no problem, however, if you are going to add 10 and 9 you have to consider a bigger modulus.


Does a stream cipher provide perfect secrecy? From WAR10CK here:

  If I actually do create a machine using RC4 or AES-CTR and have a TRNG continually feed it a constant steady stream of random bits. Provided that the stream of bits is purged after every message, will it meet the perfect secrecy requirement for a OTP?

First, do not ever use RC4.

Second, it depends on how you use that stream...

If you use AES-CTR as a stream cipher (see more here), you will specify a key $K$ (and a nonce $IV$). The CTR mode of AES will generate a stream of bits, whose length matches the messages. All that is required is to XOR it with the message.

In order to decipher. One will require the key $K$ (or nonce $IV$), regenerate the stream and XOR to retrieve the plaintext.

If a brute force attack were to happen, it would be on the nonce + key (its size is smaller than the message).

On the other hand, if:

you were to generate a really long stream of truly random bits in advance,
send it to your partner through a secure way and
use parts of that stream to encrypt messages for him only (without any reuse of the generated stream).

Then what you are doing is a Vernam Cipher, not a stream cipher (unless I am wrong). This was the way they exchanged message between USA and URSS (exchanges disks of random bits for single use).
And yes it would be perfectly secure.

One of the requirement of the Perfect secrecy is the key space has to have the same size as message space. Hence the key and the message must have the same length. In the OTP or Vernam Cipher, this is the case. In a Stream cipher, given that the key is used to generate a stream, whose length is greater, it does not meet the Perfect Secrecy requirement (while still being reasonably secure).


How to calculate a multiple-character checksum for authentication using a tabula recta? I am not sure if this is possible to do using a tabula recta, but I would like to know how to calculate a multiple-character checksum of a text.  For a single-character checksum, it's easy.  You just begin on the table at the first letter of text, go down to the second, left/right to the third, up/down to the fourth, left/right to the fifth, etc., then make a 90-degree turn and keep going until you hit the last letter of text.

How would one calculate a double-character checksum?  In other words, the sum of the text with a modulus of 676 in base 26 [A-Z].

I just realized that you could use a 676x676 table with 2-character entries.  But hopefully there is an easier way.


Constructing Garbled Circuits I have been recently working on garbled circuits for a course and I think I don't have the the proper background for understanding them. I don't know how to approach such problems.

Here is an example of what I'm looking for. Other examples include the function for maximum of two entries each having 2 bits, the function that checks if the two entries have equal Hamming weights, etc.

How does one go about solving the question that I linked?

In order to answer this, you need to be sure to understand how garbled circuits actually work. I'll try to explain this from top to bottom:

The protocol

Let Alice and Bob be willing to compute securely a function $f(x,y)$ (in your example, it would be $f(x,y)=\min(x,y)$) while keeping their respective inputs $x$ and $y$ secret.

In order to do so, they will first model the function $f$ as a Boolean circuit, which is possible since there exists a Boolean circuit $C$ that calculates the output of $f$ for any function $f$ with fixed size inputs [1].
However, the way such a modeling is performed can depend on the function and will not be further discussed here.

Then Alice will garble the Boolean circuit:
for each wire $W_i$ of the circuit $C$, she randomly chooses two secret values $w^0_i, w^1_i$, where $w^j_i$ is the garbled value of the value $j\in \{0,1\}$ of the wire $W_i$.
Note that $w_i^j$ cannot reveal $j$ in itself, so Alice has to keep track of $i$ and $j$.
This has to be done for each and every input and output wires of every logical gates in the circuit, excepted for the circuit output gates which can be left ungarbled.

Then Alice also has to construct a garbled truth table (GTT) $T_i$ for each of the gates $G_i$ in $C$.
Those tables have to be so that given garbled values along its set of input wires, $T_i$ will allow to recover the garbled output of this $G_i$ and no other information.
This is achieved through encryption of the output values.
I will detail further the garbling of gates below.

Afterwards, Alice can translate each bit of her input into its corresponding garbled values on the circuit's input wires.
And then she can send the—now garbled—circuit where each gate is replaced by its GTT to Bob with her encrypted input.

After Bob received the garbled circuit, since all input wires are encrypted and only Alice knows the mapping of the encrypted values and the real bits, Bob need to perform an oblivious transfer (I let you google that one, since it's not useful to answer your question) with Alice for each of his input bits, so that Alice can inform him of what encrypted values correspond to his inputs bits with knowing what are his actual input bits.

So it means that for each input wire, Bob will choose one amongst the two random strings $w_i^0, w_i^1$ which correspond respectively to $0$ and $1$, but without knowing the content of the string he does not choose.
And thanks to the properties of the oblivious transfer Alice cannot learn Bob's input.

Then Bob has all the needed values to compute the output of the circuit as I will discuss it below. Once he has done so, he can tell the output values to Alice.
So Bob was able to obtain the output of $f$ without revealing his input, nor knowing Alice's input, this means that Alice and Bob successfully simulated a trusted third party and performed thus secure MPC!

Garbling Logical Gates

The notion of garbling logical gates and their truth table is crucial.
Without loss of generality, I will only consider logical gates with two input wires and one output wire.
As I quickly explained above, for a given gate $G\in C$ and its input wires $W_0,W_1$ and its output wire $W$, Alice had to choose six different random strings, $w_0^0, w_0^1,w_1^0,w_1^1,w^0,w^1$ she assigned to each values of the wires in a one-to-one mapping, where $w_i^j$ represents the random string assigned to the value $j$ of the wire $W_i$.

Then in order to garble the truth table of $G$ in a way which would not reveal any information given two input values $w_0,w_1$ excepted for its output value $w$, not even the type of the gate, Alice can encrypt the output values $w^0,w^1$ using the garbled input values as keys, using a given symmetric encryption scheme $\mathbb{E}$.
I use the notation $\mathbb{E}_{k_0,k_1}(x)=\mathbb{E}_{k_0}(\mathbb{E}_{k_1}(x))$ to denote encrypting twice with two given keys $k_0,k_1$.
As an example, let us encrypt the truth table of the AND gate from Figure 1:
$$\begin{array}{c|c|c||c}
W_0 & W_1 & W & \text{Garbled value} \\ \hline
        w_0^0 & w_1^0 & w^0 & \mathbb{E}_{w_0^0,w_1^0}(w^0) \\
        w_0^0 & w_1^1 & w^0 & \mathbb{E}_{w_0^0,w_1^1}(w^0) \\
        w_0^1 & w_1^0 & w^0 & \mathbb{E}_{w_0^1,w_1^0}(w^0)\\
        w_0^1 & w_1^1 & w^1 & \mathbb{E}_{w_0^1,w_1^1}(w^1) \\
\end{array}$$

The GTT $T$ of the gate $G$ is then simply the set $\left\lbrace\mathbb{E}_{w_0^j,w_1^k}(w^{G(j,k)}) \mid j,k \in  \left\lbrace0,1\right\rbrace \right\rbrace$ of the garbled values, where $G(j,k)$ corresponds to the output of the gate $G$ under inputs $(j,k)$.

Evaluation of a garbled circuit

Once Bob has received the garbled circuit $C$ from Alice and obtained the garbled values of his input through multiple oblivious transfers, he can evaluate the circuit.

It is important to realize that a garbled circuit differs from a regular Boolean circuit.
In a Boolean circuit, semantic and syntax are basically the same: we are assigning to each wire two possible semantic values, namely True or False, which we will syntactically denote as a signal with 1 or 0 values respectively.

Those signals were public and the same signals were associated with every wire and anybody could tell from the signal what semantic value it held.
This changes in a garbled circuit, since the semantic values of each signal—excepted for the circuit's output ones—are now secret and the signals are now varying from one wire to another wire.

Thus, in order to evaluate the circuit, for each gates $G_i$ of the circuit, Bob can try and decrypt the values in the associated truth table $T_i$ using the gate's input values as keys. One of the entries in $T_i$ will then decrypt into the output of the gate.
Hence it seems necessary to have an oracle to confirm successful decryption of the entries of $T_i$, however a trick I'll detail right now called permute-and-point first used in [2] and then clearly explained in Phillip Rogoway's dissertation [3], allows to decide which entry of the GTT is to be decrypted given the garbled inputs, enabling faster computations and still preventing the evaluator to deduce anything from the order of the truth table's entries.

Permute-and-point

This trick works as follows: for each input and output wires $W_i$, Alice will concatenate a random bit $a\in \{0,1\}$ at the end of its garbled value $w_i^0$ and concatenate its inverse $b=\overline{a}=1-a$ at the end of $w_i^1$. So it allows to associate each of the 4 permutations of 2 bits to one of the entry of the GTT, without having any correlation between the bits and the values of the ungarbled truth table. So Alice can simply order the GTT according to the natural ordering and give it to Bob which will then be able to deduce which entry he should decrypt on a given input.
To obtain a nice representation of this trick, those bits can be seen as a pair of colors, as I depict them in Figure 2, in which we see how the truth table is modified to take into account this method.

Those modifications allow Bob to simply decrypt the entry whose index corresponds with the colors associated to its input wires and thus to obtain the output wire's value and its color, allowing him to further evaluate the circuit.

Example evaluation

Let us see how one could evaluate the garbled circuit represented in Figure 3 using the permute-and-point method we discussed above.
Let us assume that the semantic input values of $(W_1,W_2,W_3,W_4)$ are $(0,0,1,0)$, which means that the actual garbled input is $({\color{green}\bullet}{}w_1^0,{\color{red}\bullet}{}w_2^0,{\color{red}\bullet}{}w_3^1,{\color{green}\bullet}{}w_4^0)$ where the $w_j^i$ are the random values that Alice chose when she garbled the circuit, as seen above.
Let us also assume that Alice already provided her garbled input, say $(W_1,W_3)$, and that Bob already obtained his garbled input $(W_2,W_4)$ from Alice through two applications of oblivious transfer as described in the protocol part.

So Bob will begin by evaluating first the AND gate using the input $({\color{green}\bullet}{}w_1^0,{\color{red}\bullet}{}w_2^0)$, since it has the colors $ \color{green}\bullet\color{red}\bullet$
he will try and decrypt the third entry of the GGT of the AND gate, which works and thus provide him with the garbled value ${\color{green}\bullet}{}w_5^0$.

Then he can continue his evaluation with the second gate, which is the OR gate. He looks at its input $({\color{red}\bullet}{}w_3^1,{\color{green}\bullet}{}w_4^0)$ and try to decrypt the entry corresponding to $ \color{red}\bullet\color{green}\bullet$ with the keys $(w_3^1,w_4^0)$, it decrypt into the garbled value ${\color{green}\bullet}{}w_6^1$.

He can now decrypt the final XOR gate using the computed input $({\color{green}\bullet}{}w_5^0,{\color{green}\bullet}{}w_6^1)$, thus decrypting the $\color{green}\bullet\color{green}\bullet$ entry which provide him with the final result: "1".

And Bob does not know what was Alice's input, he just knows the final output "1" and the randomly generated strings $w_1^0,w_2^0,w_3^1,w_4^0,w_5^0,w_6^1$. He can still for example deduce from the circuit that the semantic values of $w_5^0$ and $w_6^1$ are opposed, however it does not allow him to reverse the garbled circuit up to Alice's input values. There are circuits where no privacy is assured, like for example a circuit computing the sum of the inputs, however in this example case, Bob—knowing his semantic input values—can simply restrict Alice's inputs to a subset of the possible inputs but cannot uniquely determine the actual Alice's input values.

Now, answering your question

You must model the function as a boolean circuit using fairly basic gates.
You must garble that boolean circuit.
You can then do the drawings.

Now, in the linked question the trickiest part is to "show that the simulated circuits are indistinguishable from the actual one", but since it is a really small circuit you can simply show it behaves correctly on all inputs.
If you want to do it more formally, you can see the proof the the Yao protocol by Lindell &  Pinkas, more specifically their claim 6.

Hopefully this should address all the problems you may have with garbled circuits... (Except if you want to dig into how to get better performance, since there are many more tricks to speed things up.)

Modeling the min function

The fastest way to model a boolean function is to draw its truth table, so in your case, you have 4 bits inputs, with the numbers $a$ and $b$ being 2-bits numbers $a_1a_2$ and $b_1b_2$ respectively, and you want as output the minimum $c$ of $a$ and $b$, where $c$ is constituted of two bits: $c_1c_2$.

So you can draw the truth table:

$$\begin{array}{c|c||c|c||c|c}
 a_1 & a_2 & b_1 & b_2 & c_1 & c_2 \\ \hline
 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 1 & 0 & 0 \\
 0 & 0 & 1 & 0 & 0 & 0 \\
 0 & 0 & 1 & 1 & 0 & 0 \\
 0 & 1 & 0 & 0 & 0 & 0 \\
 0 & 1 & 0 & 1 & 0 & 1 \\
 0 & 1 & 1 & 0 & 0 & 1 \\
 0 & 1 & 1 & 1 & 0 & 1 \\
 1 & 0 & 0 & 0 & 0 & 0 \\
 1 & 0 & 0 & 1 & 0 & 1 \\
 1 & 0 & 1 & 0 & 1 & 0 \\
 1 & 0 & 1 & 1 & 1 & 0 \\
 1 & 1 & 0 & 0 & 0 & 0 \\
 1 & 1 & 0 & 1 & 0 & 1 \\
 1 & 1 & 1 & 0 & 1 & 0 \\
 1 & 1 & 1 & 1 & 1 & 1 \\
\end{array}$$
And you can model your boolean circuit by taking the true values in the results and represent them as being a boolean expression:

For $c_1$:
    $$
\begin{array}{c|c||c|c||c|c}
 a_1 & a_2 & b_1 & b_2 & c_1 & {bool. expr.} \\ \hline
 1 & 0 & 1 & 0 & 1 & a_1 \land \overline{a_2}\land b_1 \land \overline{b_2}  \\
 1 & 0 & 1 & 1 & 1 & a_1 \land \overline{a_2}\land b_1 \land {b_2} \\
 1 & 1 & 1 & 0 & 1 & a_1 \land {a_2}\land b_1 \land \overline{b_2} \\
 1 & 1 & 1 & 1 & 1 & a_1 \land {a_2}\land b_1 \land {b_2} \\
\end{array}
$$
And for $c_2$:
    $$
\begin{array}{c|c||c|c||c|c}
 a_1 & a_2 & b_1 & b_2 & c_2 & {bool. expr.}  \\ \hline
 0 & 1 & 0 & 1 & 1 & \overline{a_1} \land {a_2}\land \overline{b_1} \land {b_2}\\
 0 & 1 & 1 & 0 & 1 & \overline{a_1} \land {a_2}\land b_1 \land \overline{b_2}\\
 0 & 1 & 1 & 1 & 1 & \overline{a_1} \land {a_2}\land b_1 \land {b_2}\\
 1 & 0 & 0 & 1 & 1 & a_1 \land \overline{a_2}\land \overline{b_1} \land {b_2}\\
 1 & 1 & 0 & 1 & 1 & a_1 \land {a_2}\land \overline{b_1} \land {b_2}\\
 1 & 1 & 1 & 1 & 1 & a_1 \land {a_2}\land b_1 \land {b_2}\\
\end{array}
$$

Now, you can express $c_1$ and $c_2$ as the OR of all their respective boolean expression, this method is called the boolean Sum-of-Product:
$$
\begin{aligned}
c_1= (a_1\land \overline{a_2}\land b_1 \land \overline{b_2})
\lor(a_1\land \overline{a_2}\land b_1 \land {b_2}) \\
\lor(a_1\land {a_2}\land b_1 \land \overline{b_2})
\lor(a_1\land {a_2}\land b_1 \land {b_2})
\end{aligned}
$$

And for $c_2$:
$$
\begin{aligned}
 c_2 = (\overline{a_1} \land {a_2}\land \overline{b_1} \land {b_2})
\lor(\overline{a_1} \land {a_2}\land b_1 \land \overline{b_2})\\
\lor(\overline{a_1} \land {a_2}\land b_1 \land {b_2})
\lor(a_1 \land \overline{a_2}\land \overline{b_1} \land {b_2})\\
\lor(a_1 \land {a_2}\land \overline{b_1} \land {b_2})
\lor(a_1 \land {a_2}\land b_1 \land {b_2})\\
\end{aligned}
$$

And you have a possible circuit for your function.

Now those expression are really ugly and you may want to simplify them, it is possible to convert them into nicer forms, like DNF (this is where Karnaugh maps can help). But I won't cover this topic.

For instance, $c_1$ can be rewritten as: $c_1=a_1 \land b_1$ and $c_2$ can be rewritten as:
$c_2 = (a_1 \land \overline{b_1} \land b_2) \lor (\overline{a_1} \land a_2 \land b_1) \lor (a_2 \land b_2)$

I haven't much resources to refer you to there, but a quick search led me to this page and that one, which even has a graphical representation of the circuits.

References

[1] Goldwasser, S., Micali, S., & Wigderson, A. (1987). How to play any mental game, or a completeness theorem for protocols with an honest majority. In Proc. of the Nienteenth Annual ACM STOC (Vol. 87, pp. 218-229). [PDF]

[2] Beaver, D., Micali, S., & Rogaway, P. (1990, April). The round complexity of secure protocols. In Proceedings of the twenty-second annual ACM symposium on Theory of computing (pp. 503-513). ACM. [PDF]

[3] Rogaway, P., & Micali, S. (1991). The round complexity of secure protocols (Doctoral dissertation, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science). [PDF]


Key used by HMAC-SHAx in PBKDF2 PBKDF2 can be used to derive a key from a passphrase, having in input the passphrase, the chosen number of iterations to slow down a brute force attack, a random salt and the chosen keylength. In its implementation it needs a PRNG which can be, for example, HMAC-SHA-something; but HMAC needs itself a key together with a "message" (which I think is the passphrase in the first iteration, and then its resulting hash in the subsequent ones): so what is this key?

The key is the password.

For the first iteration, the salt concatenated with the desired output length in bytes is the input.
U1 = PRF(Password, Salt || INT_32_BE(i))

For subsequent iterations, the HMAC result is the salt.
U2 = PRF(Password, U1)
...
Uc = PRF(Password, Uc-1)


Encrypt multiple RSA keys with same passphrase I have to create and store a bunch of RSA key pairs with openssl. The private keys will be encrypted with the aes256 option and a very long, random password.

Would it be safe to use the same password for all keys? Or is it better to encrypt every key with a different password?

The openssl docs say nothing about this issue, and no answer from the community. So I tried to figure it out with a small experiment. I created a private key (not encrypted) with:

openssl genrsa -out key.pem

Then I encrypted the key twice, using the same password:

openssl rsa -aes256 -in key.pem -out key-enc-1.pem
openssl rsa -aes256 -in key.pem -out key-enc-2.pem

and compared the content of key-enc-1.pem and key-enc-2.pem

Files were completely different so it looks like the AES-encryption is done with a random salt.

So, answering my own question: using openssl genrsa with aes-encryption, it is safe to use the same password for all my private keys.


Is (AES-)GCM parallelizable? I recentely faced the issue of random access decryption while AES-GCM was being used. I said this person that the underlying CTR should allow parallelization but I have no idea how authentication comes into play.

Now I know that one of the cool features of CTR is that you can decrypt any block without needing to involve any other blocks. I also know that CTR is part of the basis for GCM.

Now my question(s) are:

Can one somehow parallelize encryption of data in GCM mode (only CTR part? Parts of the MAC as well?)
Is it possible to get random access to decrypted ciphertexts (+ fast verification?) or is at least somehow possible to parallelize decryption and authentication (do either of both in parallel or internally parallelize?)?

Contrary to what Stephen says, you absolutely can compute the tag in parallel.

Here's how it works; the tag computation is essentially "assemble the AAD, data, the length field and $Encr(Nonce)$ into a series of values $x_n, x_{n-1}, x_{n-2}, ..., x_0$", and then "compute the polynomial $x_nh^n + x_{n-1}h^{n-1} + x_{n-2}h^{n-2} + ... + x_0h^0$

This computation is evaluated within the field $GF(2^{128})$; since it is a field, all the standard ways of rearranging the polynomial work.

For example, if we wanted to convert this into a three-way parallelism, we could compute $j = h^3$, and then the three polynomials in parallel:

$$tag_2 = j^0x_2 + j^1x_5 + j^2x_8 + ...$$
$$tag_1 = j^0x_1 + j^1x_4 + j^2x_7 + ...$$
$$tag_0 = j^0x_0 + j^1x_3 + j^2x_6 + ...$$

and then combine them for the final result $tag = h^2tag_2 + h^1tag_1 + h^0tag_0$

Obviously, we can tune this to whatever degree of parallelism that suits us, and we haven't changed the tag result in any way.

Stephen also notes that the entire message needs to be scanned to compute the tag; this is trivally true of any method that has a tag that's a complex function of the entire message.


How to construct a collision resistant hash function that is not a one-way function? How to construct a CRHF (collision resistant hash function) that is not a OWF (one-way function)? Not sure but I think it probably needs another CRHF?

It is going to be pretty hard to achieve collision resistance without one-wayness. Indeed, negation of one-wayness means that for a given output, you can find a corresponding input. So a collision is easily obtained by simply choosing a random input m, hashing it into output x, then finding a preimage m' for the obtained output x. The only way for such a method not to work is to have an output space at least as large as the input space, so that, with high probability, the input m' is identical to m. However, since hash functions have a much larger input space than output space (e.g. SHA-256 output space has size 2256, but its input space has size 218446744073709551616-1, which is substantially greater), chances are that the m' you get from leveraging the non-one-wayness will be distinct from the m you started with, and that yields a collision.


RSA: Construct private / public key for given cipher and plain text message let's say we are given a classical RSA encryption scheme, though we would like to "reverse" the task:

Given two messages $c, m$ choose $p, q, e$ such that $p, q$ are prime and $c ^ d \equiv m\pmod N$ with $d \cdot e \equiv 1 \pmod{(p - 1)(q - 1)}$; $N = p \cdot q$.

I was wondering how one could approach this problem? Is it even possible for some large N?

Also does the conditioning improve if we loosen the constraints of classic RSA, i.e. $GCD(e, LCM(p-1,q-1)) \neq 1$? On another question I have read, that it is possible to construct message collisions, if the parameters are ill-formed, i.e. the condition $GCD(e, LCM(p-1,q-1)) = 1$ is not satisfied. I thought it to be related, though I could not retrieve the information of how such an collision could be achieved (or if it is even feasable).

Note: klugreuter's answer outlined a different approach to the problem, that I developed here. This obsoletes the following, except perhaps when we want a small $e$.

We can compute $\mathbin|m^e-c\mathbin|$ for various small odd $e>1$, and try to factor them (even partially). As soon as we get two distinct primes factors $p$ and $q$ for some $\mathbin|m^e-c\mathbin|$, with $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, $m<p\,q$ (and $c<p\,q$ if that's added to the problem statement), then we can compute $N$ and a $d$ matching $e$ for this $N$ by one of the methods used in RSA, and that solves the problem. That's at least sometime feasible by pulling moderate factors using ECM factoring (e.g. using GMP-ECM).

If $N$ is required to be large (including, because $m$ is; $c$ has lesser influence), it is hard to find $p$ and $q$ with large enough a product. But we can sometime find more than two distinct large primes dividing $m^e-c$, and compute $N$ and $d$ as in multi-prime RSA; that improves our chances to find $(N,e)$ passing scrutiny (but does not answer the problem as worded, since it requires $N$ to be a bi-prime).

Addition: in the question as asked, there's no requirement that $c<N$ (that's normally part of RSA). When $m\ll c$, that allows to try the above with $e=1$, that is factor $c-m$, which is much smaller than above. If we get distinct prime factors $p$ and $q$ with $m<p\,q$ that gives a solution. We can hide that we started from $e=1$ by adding a multiple of $\operatorname{lcm}(p-1,q-1)$ to $e$ and/or $d$.

Late addition/hint: if we are allowed to use $e=\operatorname{lcm}(p-1,q-1)+1$ as hypothesized above, then at least one choice of $e$ not discussed above is worth consideration.


What is the starting point of Hellman's TMTO method? I understand what is happening and how the endpoint is computed but I'm still a bit unsure of where "SP" (Staring Point) came from. Are the starting points, randomly selected keys from the key-space n?

for example...

Given the diagram, yes they are randomly selected keys, $P$ is a fixed plaintext and the projection of the output to the keyspace gives you the next input as key to the cipher, thus creating a pseudorandom walk through the keyspace.


Is HTTPS secure if someone snoops the initial handshake? Let's say I'm on an open wireless network that's being actively sniffed and I connect to an HTTPS site.  Even though my subsequent traffic is encrypted, couldn't the sniffer use the data from the initial (non-secure) handshake  to decrypt my subsequent data?

The SSL and TLS protocols (on which HTTPS is based) are designed in a way that no attacker (neither a passive nor an active one) can read anything of the encrypted part (if the cryptographic assumptions hold - and if you don't use the NONE cipher, which does no encryption).

Of course, the attacker can read the negotiation part. But this part will not contain anything which is (with current known algorithms) usable for cryptanalysis of the rest.

There are several possible algorithms to negotiate a secret session key - which one is chosen depends on which protocol suites (= set of algorithms to use) the client offers and what the server selects from these. Then we use the exchanged key to encrypt the rest of the connection using a symmetric algorithm.

Some popular key exchange mechanisms are these:

Diffie-Hellman key exchange (DHE): Here both sides select random numbers a and b, calculate and exchange $g^b$ or $g^a$, and then both calculate $(g^b)^a = (g^a)^b$, which is the same value. An attacker does not see $a$ or $b$, only $g^a$ and $g^b$, and can't derive from this the values. (All these calculations are done in some group, the multiplicative group modulo a big prime number for "normal" Diffie-Hellman, or in an elliptic curve group for ECDHE.)

In the usual case of authenticated key exchange, afterwards the server signs some hash of all the negotiation data with his private key, which the client can then check using the public key. (This avoids active man-in-the-middle attacks, where the attacker negotiates one key with the server and another one with the client, then forwarding the data.) For anonymous connections there is no such step (and MITM is possible).
asymmetric encryption based (RSA key exchange): The client generates a random pre-master-secret, encrypts it using the public key of the server, and sends this to the server. The server can decrypt it an now both know the same pre-master secret.  Applying a hash on this gives the master secret used for actual encryption (and the MAC).

The problem is that a leak of the private key here compromises all past connections (where this key was used and which where registered), while with Diffie-Hellman only future connections are affected (where the attacker can launch a MITM-attack).

These are less often used, since they are not suitable for parties which have no previous consent of common data:

password based, for example the Secure Remote Password protocol: This works similar to Diffie-Hellman (i.e. it uses exponentiation in a prime group - but addition and multiplication, too.). The server has a password verifier $v, s$ (with $s$ once selected random, and $v = g^{\operatorname{H}(s,p)}$), the client has the password $p$.

To authenticate (and exchange a key), the client sends the user name and $A = g^a$ (where $a$ is random data), the server sends back $s$ and $B = k\cdot v + g^b$ (with $b$ random and $k$ some fixed parameter). Both calculate then $u = \operatorname{H}(A,B)$. Then the client calculates $S = (B - k\cdot g^{\operatorname{H}(s,p)})^{a+u\cdot x}$, while the server calculates $S = (A\cdot v^u)^b$. If the password is right, these are identical. To obtain the key itself, both calculate $K = \operatorname{H}(S)$.
Pre-shared key, as defined in RFC 4279: This is a bunch of algorithms based on some pre-shared secret key common between both parties. (Obviously this is of no use in the anonymous internet.)

The PSK method simply transfers some key identifier (which is not nearer specified - it will depend on the application, i.e. higher level protocol which is using this), and both then derive the master session key from this shared secret.

The DHE_PSK uses a Diffie-Hellman key exchange as described above, and this key is then hashed together with the pre-shared key to form the master session key.

For RSA_PSK the client sends an RSA-encrypted random data, together with the key ID - the pre-master secret is then formed from the decrypted random data, together with the pre-shared key.


AES inversion operation in sub byes I was wondering why in the AES sub-bytes operation one can represent the inversion as computing $x^{254}$. What is the reason for this?

Moreoever, I was wondering what the text on page 212 of https://autonome-antifa.org/IMG/pdf/Rijndael.pdf means that the polynomial representation of the sub-bytes operation can be obtained by lagrange polynomial interpolation?

Thanks a lot, Peter

AES sub-bytes is defined over the finite field $GF(2^8).$ This field has 256 elements. Its multiplicative group $GF(2^8)^{\ast}$ has 255 elements. In any multiplicative group $a^N=identity$ for all $a$ in the group. This means the multiplicative order of all the group elements (the smallest power they can be raised to and obtain 1) divides $N.$ Here, by definition of AES, $x$ actually has maximal order $N=255$ Thus $x^{255}=1$ and $x^{254}=x^{-1}$ due to its maximal order. Sub-bytes is defined using the inversion $x^{-1}$ if $x\neq 0$ and $x$ if $x=0.$ The formula $x\mapsto x^{254}$ captures both cases.

All functions defined on a finite field can be represented as polynomials. Thus given any input/output table for a function on a finite field, Lagrange interpolation (definition widely available including on Wikipedia) can be used to find the polynomial corresponding to that function, assuming the table representation is a well defined function.


Winternitz One Time Signature I happened to watch Mr. Bill Buchanan lecture that explains Winternitz one time signature scheme (https://www.youtube.com/watch?v=eqMMlcN4zSc). The scheme shown in the lecture is susceptible to universal forgery, as if an Opponent query for OTS on a message composed of 32 0xFF octets, he gets back Hash(prive[i]) for i=1..32, and with this, he can sign any desired message. I understand that there should be added a checksum to prevent this attack, and my question is ;

whether the checksum: 0xFFFF-SUM(N[i]) i=1...32 will solve the problem?

The idea is that any octet in the message that is modified to be lower than 0xFF, will cause at least one byte in the checksum to increment, and thus will require the Opponent to inverse a one way hash function.

whether the checksum: 0xFFFF-SUM(N[i]) i=1...32 will solve the problem?

Yes, it does.  That's exactly how both WOTS+ in XMSS and LM-OTS in LMS work


How can I evaluate the congruency of an AKS primality test? Despite the fact primality test is a mathematical issue, it plays a part on the security of many cryptosystems such as RSA. I was trying to understand how it works until I came to the following congruency:

〖(X+a)〗^p≡X^p+a (mod X^r-1,p)

The above reduces evaluating the initial congruency 〖(X+a)〗^p≡X^p+a (mod p) to have less coefficient. How do we evaluate the above one?

This is never "evaluated" as such. The above equation must hold for the number to be prime for certain $a$, or else it's composite.

See the algorithm on Wikipedia to exactly see for which $a$ the equation is tested.


How many characters per block in an El Gamal ECC cryptosystem? Looking for the number of characters that can be encrypted using the The elliptic curve ElGamal cryptosystem of each block, I found these lines. But I cannot understand them:

  Actually in our case we need to divide into an even number of blocks. If we think in a
  character as a number < 256 (its ASCII code) and we employ $\mathbb{F}_p$ as a field then we can encode
  at most $\log_ {256} (p)$ characters in each block.

What does the notation $\log_{256} (p)$ mean?

I would like an explanation by real examples.

First: use rather ECIES or some other IND-CCA2 safe variant.

If this is a theoretical question you need to know, that any plaintext (a number) must be smaller than $p$. To reach this the bitlength $log_2(m)$ must be smaller than the bitlength $log_2(p)$. Now you can only encode the data as bytes(256 values), so we are switching from base 2 to base 256 and hence $msglen=log_{256}(m)<log_{256}(p)$.

I hope that answers your question (although a bit late)