How did SHA-1 'feed' Blum Blum Shub One of the most (in)famous hardware derived random number generators was Lavarand (patent).  It did it with funky lava lamps.  An image of the lamps was hashed and fed into Blum Blum Shub (BBS) to produce a cryptographic bit stream.

How?  The patent refers to using NIST SHS-1 (SHA-1) which outputs a 160 bit hash.  This seems to get reduced to multiple 140 bit hashes and then "The 140-byte value gets fed through the Blum Blum Shub[sic]".  I thought that the seed for BBS was computed via prime multiplication.  How can the seed (typically p.q) just be arbitrary hash output and still perform it's  integer factorisation?  BBS typically utilises a single state of 1000s of bits, not groups of 140.  They did it like this which is a little lite on detail, and steps 3 & 4 from the archived web site don't clear it up any...

I realise that this was all a long time ago.  How can above steps 600 and 605 be connected together?

I thought that the seed for BBS was computed via prime multiplication.

This is not how BBS works. To help better understand the seed, it's necessary to explain BBS.
Blum Blum Shub is realized in the form of $x_{i+1} = x^2_i \bmod N$. The initial seed, $x_0$, merely has to be co-prime to Blum primes $p$ and $q$ (where $N = p\cdot q$, making $N$ a Blum integer), and must not be $0$ or $1$. The seed is $x_0$, not $p$ and $q$ (which were likely generated once to create the hardcoded $N$ and then thrown away*). They are likely using the raw hash output as the seed, since it's unlikely that it won't be co-prime to $N$. They give you the modulus on the page you linked, but not the primes:

5360751114622011236087979022735306713592537659947455285353148181
8526455500785383194936281698585494806464721601253386562653528822
5543322562532917886396992291116815877218495559211688377961466145
0857446201926232198015028137924055146650866097197909406089918491
4133568666470293429076893274969016410915119621659901793350665953

This is a 1062-bit modulus. Unfortunately, it seems that BBS can be broken† up to $10^{54} n^3$ times faster than it takes to factor the $n$-bit modulus. This means that BBS used with their parameters can be broken $10^{54} \times 1062^3 \approx 1.20 \times 10^{63}$ times faster than it takes to factor the modulus, which is a significant enough speedup that the proof is completely useless. Additionally, the proof assumes only a single bit is extracted from each $x_i$ (officially by taking the parity of $x_i$). If more bits are extracted at a time, it becomes even weaker. Parameters that seem acceptable are terrible for BBS.
The security proof for BBS is only a reduction to a problem with no known solution. That is, a correct implementation (i.e. one where only one bit is extracted from each $x_i$, and only when the modulus is "sufficiently" large) can only be broken if the quadratic residuosity problem (QRP) is solved.‡ It is "proven secure" in the same way that RSA is "proven secure" because a proper implementation is provably reducible to the security of the RSA problem (the difficulty of finding the $e^\mathrm{th}$ root of an integer, modulo semiprime $N$), but no one thinks of RSA as having perfect security. In other words, BBS has a security reduction to a yet-unproven problem, and is not information-theoretic secure.

How can above steps 600 and 605 be connected together?

Are you asking how the 140-byte seed comes from the 160-bit hash? That is actually answered in the link you provided. There are seven SHA-1s. The seventh hashes every seventh byte, the sixth hashes every sixth byte, etc. The bytes come from an image of the lava lamp itself. The final hash values are concatenated to form a 140-byte (1120-bit) value. This value is used, directly, as $x_0$.
* The only thing you are losing by not having access to $p$ and $q$ is the ability to calculate any $x_i$ value directly from $x_0$ without having to calculate $x_1 \cdots x_{i-1}$ first. Euler's theorem can be used to do $x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N$ where $\lambda$ is the Carmichael totient function. If an attacker factors $N$, they can do this as well, breaking the security reduction.
† Broken in this context does not refer to the ability to predict the random stream or recover the seed. Instead, it means the security proof is invalidated and that the algorithm is no longer reducible to a known hard problem and that a break could exist which does not rely on solving QRP. Critically, it does not automatically imply that such a break does, in fact,  exist.
‡ Although the quadratic residuosity problem is often thought to be as difficult as integer factorization, this has not been proven. It is possible that a method to break BBS could be exist which solves QRP without solving integer factorization.


Nonce of AES-GCM generated by Counters i am trying to generate the nonce for AES-GCM. I know people usually generate it by Counters and LFSRs. I am confused about the meaning of Counters. Is that means Counter (CTR)? Why it can generate unique nonce?

Counters are storing values and have usually clear, set, and increment functions. A counter can be implemented in software very easily by using an integer with enough size or using a library like Java BigInteger or Gnu/GMP for C/C++.

clear() makes the all bits zero: unsigned int counter=0
set(y) set the counter value to y : counter = y
increment() increase the current value by 1; counter++

For GCM one needs 32 bits counter and a total 128-bit for the CTR mode's counter with the 96-bit nonce.
Take a 128-bit unsigned integer and init to zero. Then GCM will use it like
$ J_0 = IV || 0^{31} ||1 $
so during the implementation, you need to take a copy of the counter, shift 32 to left, and OR with 0x01.


Permutation of first $k$ prime powers as a one-way function? Let $a_1$ through $a_k$ be some permutation of the first $k$ primes. Let $n \in [1,k!]$ be a parameter specifying the exact ordering by taking the $n$th permutation in a sorted list or by some other simple mechanism.

Then define $f(n,k)=a_1^{p_1}+a_2^{p_2}+\ldots+a_k^{p_k}$, where $p_i$ is the $i$th prime, and the $a_i$ are the permutation of the primes indicated by $n$.

e.g. $f(5,4)=2^2+7^3+3^5+5^7=78715$.

I conjectured that all such sums may be distinct. Supposing that were true, this appears like it could potentially serve as a bijective one-way function using a suitably high value of $k$ and an effectively randomized permutation.

For very small $k$ (up to $20$ or so), the $f(n,k)$ sums are spread far apart and have little opportunity for individual terms to overlap, making it easy to greedily home in on the correct inputs. Beyond that, it quickly becomes more difficult. Barring some tidy solution that I cannot see, finding $f^{-1}(f(n,k))$ seems totally intractable once it's extended to $k>1000$ or more, while $f(n,k)$ is trivial to calculate to very large values. Accordingly, my question:

  Could $f(n,k)$ conceivably make a suitable one-way function?

In particular, I'm looking for advice on whether there is likely to be some way to efficiently find $f^{-1}(f(n,k))$ after all, and also whether $f$ looks like it has other properties that would make it either a strong or poor choice for this purpose.

As this stands this is a hard to evaluate and inefficient proposal.

Firstly key size is effectively  $\log n\!=O(n (\log n-1))$ but the largest value (attained for the identity permutation) is $\sum_{i\leq k} p_i^{p_i}$
which is larger than

$$(n \log n)^{n \log n}=O(e^{n (\log n)^2}).$$

You would need to look at reduction modulo so elarge integer to make it efficient.

While it may be that the type of diophantine equation that needs to be solvable (for prime arguments) for the original function to have collisions is unsolvable, such things are almost impossible to prove. I am not an expert but I know of no such results even for few terms.

And once you do a modular reduction, all bets are off.

Computationally, you probably cannot check much beyond the first 20 or so primes for no collisions.

One idea is to check the differences of the values the set of functions for a fixed $k$ give, since there are quadratically many differences,  they’d be more likely to repeat. If this happens this means that you might be able to find a modular reduction that will yield a collision.


Definition of a CSPRNG I am interested in what conditions are necessary and sufficient to define a cryptographically secure pseudo-random number generator (CSPRNG).

Wikipedia lists two defining characteristics:

It satisfies the next-bit test.
It withstands 'state compromise extensions' - part of all of the state being compromised does not allow for reconstruction of the prior stream of random numbers.

I understand that condition 1 is equivalent to saying there does not exist a polynomial-time algorithm which can distinguish the output stream from random (with success probability 1/2 + $\epsilon$), due to Yao (1982). I cannot, however, find any formal justification for the second criteria, which Wikipedia surmises as 'they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.' Does anyone have a reliable source for this?

Moreover, is this condition even sensible? If you consider something like RC4 (okay, not the best example of a CSPRNG I know), if you know the whole state at any point then it is possible to step the PRGA forward or backwards completely deterministically and independent of knowledge of the key, right? So, this means that RC4 does not satisfy Wikipedia's second condition for being a CSPRNG?

Does anyone have a reliable source for this?

Well, you are asking about the definition of a CSPRNG, and whether this second criteria is a necessary part.

Well, it comes down the to exact definition of the term 'CSPRNG'.

If we define a CSPRNG as something that generates output which is indistinguishable from random (your first criteria), then a CSPRNG need not meet the second criteria.  This can be seen by the observation that this definition relies only on the output, while the second criteria is also defined in terms of the internal state.  It would be easy to take a CSPRNG (which meets the first criteria), and add internal state that would allow someone to reconstruct previous outputs; this modified generator would continue to meet the first criteria (we haven't changed the output), but it would prevent it from meeting the second criteria.

On the other hand, if the term 'CSPRNG' includes the second criteria, well, that's obviously a necessary part.

When I use the term 'CSPRNG', I personally mean something that meets the first criteria (and if I also need the second criteria, I use an additional term such as 'backtracking resistance' to describe it).

The wikipedia article appears to use this as its source.  I would point out that in its list of standardized CSPRNGs, it includes the X9.31 generator, whose obvious implementation does not meet their criteria (if the attacker recovers the internal key, and has a good guess about previous timestamps).

  Is this condition even sensible?

Of course it is; it is useful if you're in a scenario where there is a danger that, at some point, the internal state may actually be exposed.

  If you consider something like RC4; this means that RC4 does not satisfy Wikipedia's second condition for being a CSPRNG?

Well, RC4 is known not to meet the first criteria, and so it's not the best example.  However, ignoring that point, it is certainly true that the obvious implementation of RC4 would certainly not meet the second criteria; it is conceivable (that is, I don't know of a disproof) that there is an alternate implementation of RC4 that generates the same output, and would meet the second criteria.


Why does DH-EKE require that public keys be indistinguishable from random? The introduction to SPAKE pre-authentication states:

  Diffie-Hellman Encrypted Key Exchange (DH-EKE) is the earliest widely deployed PAKE. It works by encrypting the public keys of a Diffie-Hellman key exchange with a shared secret. However, it requires both that unauthenticated encryption be used and that the public keys be indistinguishable from random data. This last requirement makes it impossible to use this form of PAKE with elliptic curve cryptography. For these reasons, DH-EKE is not a good fit.

I'm curious about the sentence in bold--why does DH-EKE require that the public keys be indistinguishable from random data? After all, the public keys are public, and furthermore, they will be encrypted with the shared password.

I'm guessing that if the public keys are in fact distinguishable from random data, that that reveals some information about the shared password, but I don't know how.

In DH-EKE, Alice needs to encrypt her chosen public key with the shared password. If the public keys do not look random, an attacker can try to decrypt Alice's first encrypted message to recover a small set of possible passwords, merely by checking if the decrypted message belongs to the public key space or not. Note that this is an offline attack, which is the type of attacks that PAKE protocols aim to prevent.


DCT Steganography Problem I'm creating an implementation of the DCT Steganography algorithm in Java and I'm having a slight problem. When I embed a message into a cover-image, I am doing so by initially obtaining the DC Coefficients of that image for a particular 8*8 block and then replacing the last coefficient equal to either a 0 or 1 depending on the binary message I am embedding. Once this has been embedded into the 8x8 blocks, I then pass it through the inverse DCT to re-create my Stego-object.

However, when I pass the Stego-object through DCT and recover the last coefficient of each block, sometimes the coefficient has changed and therefore doesn't produce the correct message that I originally embedded into it.

Does anyone have know/understand why this might be happening and how I can solve it?

E.g. Embedded message = 00 0 1001000 0 0111101 0 01 1 0101100101 Recovered message = 00 1 1001000 1 0111001 1 01 0 0101100101

This only happens on some images but not all and I am not sure what's happening. My program checks to see if the last coefficient is equal to 0 before it decided to embed on it or not.

The inverse DCT is used to decompress the image, but you do not have to decompress the image.  If you decompress the image, I suppose that you also compress it again for reading the DCT coefficients, and as far as JPEG is a lossy format, some DCT coefficients could change their value.

But JPEG does not work in this way. In JPEG the DCT coefficients are compressed and saved into the file. It is the visualization tool that decompresses the image to show it to the user.


RFC 6979 - Why not simply hash the message & the private key for deterministic ECDSA? Why go through the trouble of using the HMAC_DRBG process, instead of simply hashing [message | private key] to calculate $k$ for deterministic ECDSA?

If the resulting $k$ or the signature is invalid, then a known byte value can be appended to the input, and re-hashed, until an acceptable result is achieved:
k=h([message|privateKey|0x00 … 0x00])

As many 0x00 bytes as the number of iterations it takes.

Am I missing an inherent weakness here?

Edit: If the hash function output length is smaller than the curve order, multiple hash outputs (produced by appending a known byte, similar to what was described above) can be concatenated as necessary:
k=[ h([message|privateKey]) | h([message|privateKey|0x00]) ... ]
Once you have enough output, you can then truncate it to match the curve order bit length.

And if the resulting $k$ or the signature is no good, then restart with the known byte appended:
k=[ h([message|privateKey|0x00]) | h([message|privateKey|0x00 0x00]) ... ]

And so on, until an acceptable $k$ is produced.

Deterministic signatures are safe in the random oracle model. Using HMAC_DRBG allowed me to rely on existing research on the safety of that construction and how close it comes to a "true" random oracle. If I had used any other "handmade" construction, then I would have had to provide extensive analysis on why it is secure. Being naturally lazy, I chose HMAC_DRBG.

Moreover, this use of HMAC_DRBG makes the end result more "convincing" -- and a large part of specifying a cryptographic algorithm as a RFC is to get other people to use it.

(If I had been aware of its existence at that time, I might have considered HKDF instead of HMAC_DRBG, but that does not matter much in practice.)


JWTs vs Capability Tokens One of the primary advantages of JWTs is that they serve as capability tokens, allowing for a portable verification of capabilities/ privileges. However, JWTs are often criticized for a number of weaknesses.

What is the disadvantage of simply applying an HMAC to a JSON object yourself and avoiding the rest of the baggage of the JWT spec?

Disadvantage: You don't get the thrill of playing Russian roulette with a dumpster fire of an implementation ecosystem and underspecified protocol!

Disadvantage: You might accidentally reinvent JWT and repeat its errors anew if you're not careful.  (On the other hand, advantage: you might not.)


Understanding SSL Certificate Signing Original thread: Why hash the message before signing it with RSA?

Please correct the diagram below so I can better understand how certificates are created and signed by a third party CA:

https://imgur.com/a/g4F0zKw

The CSR (which contains the RSA public key, Subject Name (CN), etc) is hashed+padded then encrypted by the third party CA. Then the same original CSR (or just "certificate") is then combined together with the certificate signature to produce the digitally signed SSL certificate?

Added comment 2018-05-26:

Thanks for the response, I appreciate you taking the time to discuss this.

  "The signature of the CSR - which is also signed - is by the private key that is part of the key pair of which the public key is within the CSR. This signature value is verified and disposed."
  How does the CSR signing work? Does it use SHA to hash the CSR contents and then encrypt the hash using a temporary private key that was created by the web server during the CSR generation?

How does the CSR signature verification work? Does the CA decrypt the encrypted hash value of the CSR and then verify that the hash values are identical, at which point the CSR signature is verified and disposed of?

  "It is not possible to encrypt with a private key because anybody can "decrypt" with the public key; the private key is used for RSA modular exponentiation though."

When does RSA modular exponentiation occur (when calculating the padding)?

Here is a revised diagram for your review:

The certificates are generated in full by the CA, combining the data from the CSR (e.g. CN) with data from the CA (e.g. serial number, issue date etc.).

The signature of the CSR - which is also signed - is by the private key that is part of the key pair of which the public key is within the CSR. This signature value is verified and disposed.

The CSR, which is mostly kept in a key store together with the private key gets replaced by the returned certificate, which is signed by the CA, which is identified as the issuer in the certificate.

Notes / discrepancies:

The hashing and padding is specific and internal to the PKCS#1 v1.5 RSA signature generation (some libraries also accept hash values or hash functions though).
It is not possible to encrypt with a private key because anybody can "decrypt" with the public key; the private key is used for RSA modular exponentiation though.
The certificate signature value is the value after modular exponentiation, it is of course not just the hash value.
The CSR is a certificate signing request which is/was defined in PKCS#10, it is not a certificate by itself even if it has a lot in common with a certificate.
As mentioned, the CSR is signed.
SHA-256 has an output size of 256 bits, not 160 bits (are you kidding me?)
Using SHA-512 and PSS signature generation would increase security, but not as much as increasing the key size: a 2048 bit key pair is relatively  small nowadays.

All and all, the general idea and the components of the TBS Certificate part of the certificate are correct but all the details are wrong in that picture.


Top notation as exponent In cryptography, what does the Top notation mean? It resembles a capital T: T

In particular, I saw it in the follwing context:

$c = (c_1,c_2)^\top$

where $c_1$ and $c_2$ are homomorphic ciphertexts

Usually, $^\top$ denotes the transpose of a matrix or vector.
Common variants include $^t$ and $^T$.

Hence $(c_1,c_2)^\top$ is just $\begin{pmatrix}c_1\\c_2\end{pmatrix}$. Such notation is often used to fit column vectors neatly into text.


Are there shortcuts for computing ECC Point multiplication? I'm trying to learn about elliptic curve cryptography.

Let's say you have point $P$ and 256 bit number $n$ and you want to compute $nP$. It sounds like computing additions one at a time is not computationally feasible. Is there an algorithmic "shortcut" to compute this? If so, how does it work?

It is called "double-and-add". For instance, take a point, and add it to itself. Then take the result, and add it to itself. Do that again. And again. After ten additions, what you get is $2^{10} = 1024$ times the original point: in just 10 additions, not 1023. That's the "shortcut".

More generally, with $k$ successive doublings (a "doubling" is the addition of a point with itself), starting from a point $P$, you get $2^k P$. Now, all you have to do is to consider your multiplier $n$ in binary: this is about writing it as a sum of powers of two. For instance, if $n = 224965$, then, in binary, it becomes $110110111011000101$, which means that:
$$ n = 2^0 + 2^2 + 2^6 + 2^7 + 2^9 + 2^{10} + 2^{11} + 2^{13} + 2^{14} + 2^{16} + 2^{17} $$
And therefore:
$$ nP = 2^0P + 2^2P + 2^6P + 2^7P + 2^9P + 2^{10}P + 2^{11}P + 2^{13}P + 2^{14}P + 2^{16}P + 2^{17}P $$
So all you have to do to compute $nP$ is to compute these $2^kP$ (with successive doublings) and then add them together.

$2^0P$ is just $P$, so you already have it. Double it twice, and you get $2^2P$. Double that one four times, and you get $2^6P$. And so on. With $17$ doublings, you'll get all $2^kP$ for $k$ up to $17$, so in particular you'll get all the values you are interested in. As the formulas above show, ten extra additions, between the eleven $2^kP$ that are needed, will yield the result. In total, you got $224965 P$ with $17$ doublings and $10$ additions, i.e. much fewer than $224964$.

In all generality, if $n$ is a number of $t$ bits (i.e. less than $2^t$), then $t-1$ doublings and at most $t-1$ extra additions are enough.

There are many variations upon this mechanism, depending on how you interleave the doublings and the additions, and possibly reuse some addition results. You'll still need to compute the $t-1$ doublings, but you may save on some of the extra additions. How many intermediate results you need to keep in RAM is also a consideration. Moreover, if $n$ is a secret value, then you'll want to avoid side-channel attacks that may result in leaking some of the bits of $n$, and this impacts the kinds of double-and-add algorithms you can tolerate.


What is 'security margin'? I have been academic papers about Rijndael, Serpent, and Twofish, and there is this term that is vague to me. I cannot find a tangible definition in google. Can someone briefly define, describe, and/or give examples about security margin and where it is used.

In this context 'security margin' is a measure for how much better we need to get at analyzing a cipher to break it. Such advances in cryptoanalysis require new ideas of how one might attack a cipher. Thus estimating how strong a cipher is, is hard.

Ultimately we can only tell something is broken, after we've broken it.

We typically look at a few properties to estimate the security margin:

How much effort was put into analyzing this cipher?

AES has seen a lot, finalists in a popular competition (Serpent etc.) have seen quite a bit, but less than AES, and some random guy's cipher has probably seen almost no effort at all.
How well do we understand it?

We have a decent understanding of certain block-cipher constructions with a clear iterated round structure. But we might not understand some new innovative cipher very well.

For example NIST eliminated some candidates in the SHA-3 competition because their design was unusual and not understood very well.
How many rounds are broken so far?

For example a cipher where we've broken 2.5 out of 10 rounds is probably stronger than a cipher where 60 out of 80 rounds are broken if we understand both of them equally well.

Ciphers with a clear round structure are often preferred. Typically breaking more rounds becomes a lot harder, and it provides at least some way to quantify how much progress was made in breaking the cipher.

Lack of clear round structure makes sudden breaks more likely.

So if we put a lot of effort into analyzing some cipher, think we understand it well, and still only broke a few rounds, then we believe the security margin is large.

Resistance to brute-force can be easily quantified, estimating resistance to cryptoanalysis is full of guesswork and pretty subjective. So it's not surprising that you only find pretty vague statements.


RSA: Why must e be relative prime to phi(n) I've got a question concerning fields used in RSA.

Let's use the following symbols for my example:

{p,q} = primes
{e,n} = public key
{d,n] = private key

I learnt that an inverse element exists if a is coprime to m.

Applied to RSA I would have guessed that e needs to be coprime to n in order to find it's inverse element, because n is used as mod. But according to the rules of RSA it has to be coprime to ϕ(n) (gcd(ϕ(n),e)=1). Why?

Because RSA takes advantage of the fact that:

$a^{\phi(n)} \equiv 1 \mod n$

Which means:

$a^{\phi(n)+1} \equiv a \mod n$

So, in order to encrypt and decrypt using $e$ and $d$, we need:

$ed \equiv 1 \mod \phi(n)$

Which can only be true if $gcd(e,\phi(n)) = gcd(d,\phi(n)) = 1$


Verifying dealer parameters in 1-2 oblivious transfer I read the description of 1-2 oblivious transfer algorithm in wikipedia.
In the algorithm described Alice has two messages $m_0, m_1$. Bob picks value $b \in {0,1}$, and the protocol allows Bob to obtain $m_b$, while Alice does not know which value was sent to Bob.

The protocol requires that Alice creates an RSA private,public key pair, and also a value for e. I was wondering if Bob has to perform any verification over there values. It seems to me that Alice can craft special values for N=pq, and e such that it is easier for Alice to find out what was the value of Bob's b.

An edge case would be for Alice to pick e=0. In that case, $k^e = 1$, and therefore the blinding performed by Bob does nothing, and Alice can always discover b.

What if Alice chooses an N that is not really a multiplication of two large primes, with a combination of a specially crafted value of e?

Is there a way for Bob to defend himself against such behavior from Alice?

There are many proof systems achieving this goal, i.e. Alice can prove to Bob, that her public parameters were chosen in a "right way". What does "right way" mean?

Typically, what we want for public parameters $(N,e)$ is that the map $x\rightarrow x^e$ over $\mathbb{Z}^{*}_{N}$ defines a permutation to deter certain attacks, for example the attack mentioned in OP's question. The state of the art for such a proof system is proposed by Goldberg et al. It is a non-interactive Honest-Verifier Zero-knowledge proof system allowing one to certify that public RSA parameters were generated in a non-adversarial manner without leaking any information about the factors of $N$. Such a certification contains $\lambda/\log_{2} e'$ group elements from $\mathbb{Z}^{*}_{N}$, where $\lambda$ is the bit-security one wants for the soundness of the certificate proof and $e'$ is the smallest prime which divides the public exponent $e$. In a typical parameter setting, where $e=e'=65537$, with $\lambda=128$, the proof consists of $9$ integers from $\mathbb{Z}^{*}_{N}$ and also proof generation and verification is super lightweight. For more details, see the paper linked above.

There are also many proof systems allowing one to prove that an integer is a product of two primes. This is quite an old paper by van de Graaf and Peralta but might suffice for your needs. One could even prove more about a semiprime! For instance one could prove that a (committed) number is a product of two safe primes due to Camenisch and Michels. Additionally, one could prove that a number is a product of two primes AND also a Blum-integer. Lastly, there is an efficient, non-interactive, statistical zero-knowledge proof system for quasi-safe prime products by Gennaro, Micciancio and Rabin.


Is this encryption scheme perfectly secure? Let $m = 6$, and let $\mathbb{Z}_m$ denote the set $\{0,…,m-1\}$. Let $X \mod m$ denote the remainder obtained when dividing $X$ by $m$.

  (a) Consider the symmetric encryption scheme in which the encryption of message $M \in \mathbb{Z}_m$ under key $K \in \mathbb{Z}_m$ is $M+K \mod m$. Is this encryption scheme perfectly secure? Why or Why not?

I'm having a lot of trouble understanding why the "X mod m" and all of the other modulo operations are relevant. I know it says let it denote the remainder obtained when dividing $X$ by $m$, but… the remainder of what? Why would the remainder be relevant?

The modulo operator keeps the result of the addition of $M$ and $K$ within the set $Z$.

For example, if $m$ is 10, $M$ is 6 and $K$ is 5, $M + K$ would be 11 which is no longer in the set $Z$.  Taking 11 mod 10 results in 1 which is in the set $Z$.

The definition of perfect security is:

  An interesting special case is perfect security: an encryption
  algorithm is perfectly secure if a ciphertext produced using it
  provides no information about the plaintext without knowledge of the
  key. If E is a perfectly secure encryption function, for any fixed
  message m there must exist for each ciphertext c at least one key k
  such that $c = E_{k}(m)$. It has been proved that any cipher with the
  perfect secrecy property must use keys with effectively the same
  requirements as one-time pad keys.


Is my password entropy calculation correct? I have a password with a prescribed format:

111 + (2 Random lowercase letters) + (random digit)

As you can see, it starts with a fixed value of 111, followed by two random lower case letters, and then lastly a random digit. Now, I would like to calculate the password entropy. To do so, I am calculating:

Fixed value 111  $\rightarrow \log_2(1) = 0\text{ bits}$
Two random lowercase letters $\rightarrow \log_2(26)\times2 = 9.4\text{ bits}$
One random digit $\rightarrow \log_2(10) = 3.3\text{ bits}$

This results in a total password entropy of $0 + 9.4 + 3.3 \text{ bits} = 12.7\text{ bits}$

Is this approach to calculate the password entropy correct, or am I missing something somewhere?

Yes, the computation is correct: the passwords will have an entropy of $\log_2(26^2\cdot10)\approx {12.7}$, which means that they are weaker than a randomly chosen secret key with 13 bits.


Do we need symmetric cryptosystems? One question I had to answer in my crypto exam today was:

  Do we need symmetric cryptosystems?

As it stands, that's probably a debatable question, so I'd like to reformulate this as:

  Are there any situations where symmetric cryptosystems could not be replaced by asymmetric cryptosystems without serious downsides?

I'm not thinking of performance-related issues here; rather, I'm looking for things that would be impossible to achieve in an asymmetric-only model, or at least that would require prohibitively complex or costly implementations.

I would be interested to hear of any answer, since my teacher seemed to suggest that I was missing something, but he wouldn't say what (this was an oral examination).

Here's my personal thinking and answer:

I'd tend to say that symmetric crypto is not absolutely necessary, since:

For two-party communication, using two asymmetric key pairs should be enough to make do without symmetric crypto.
Generalizing to broadcasting or more-than-two-party communication, the sender would need to have keys for all recipients, but that should be sufficient.
Signatures should be able to emulate MACs (with the requirement that every group member who would have shared the MAC key now needs to have every group member's public key)
For encrypting data for personal use (single party), asymmetric encryption should be fine.

The only situation where I can think of difficulties is the distribution of public keys in the absence of a trusted party: in the contrived setting where Alice can securely send data to Bob, but Bob can't securely reply, Alice could transmit a symmetric key to use for subsequent exchanges, while in a fully asymmetric context Bob wouldn't be able to reliably send his public key to Alice. But this sounds like a somewhat contrived example, and I have no doubts that their are good ways of circumventing this (for example, Alice could generate a key pair for Bob, and send it to him).

Other weaknesses that I could think of were encryption & decryption speeds, and resistance to an hypothetical quantum computer, since current symmetric systems just need a doubling of the key length to maintain security, while asymmetric systems based on factoring would be brought to their knees. But then again we have lattice-based cryptography, so that's not a definitive reason why symmetric systems are needed.

Yes, we need symmetric cryptosystems, for many reasons; to give three of these:

We need a hash function to make most asymmetric cryptosystems secure (e.g. we simply do not have a secure signature system based on RSA without a hash), and current hash functions are (or are built from) symmetric cryptosystems.
All asymmetric encryption cryptosystems are bound to output ciphertext larger than the plaintext, and there are situations where this is a major drawback (e.g. bulk disk encryption).
The best asymmetric encryption cryptosystems we have around are some orders of magnitude slower/more energy-hungry than state-of-the-art symmetric ones; it turns out this worsens, badly, if we want to minimize the ciphertext expansion ratio by using huge parameters.

Note: Point 1 has the appearance of being sufficient to prove my assertion, but it is debatable to a degree: perhaps in this question we want the big picture only, and disregard the symmetric internals of all existing asymmetric cryptosystems; and/or perhaps we could devise asymmetric-based hashes (though these would be symmetric cryptosystems in disguise).
Also: we could live with 2, if there was not 3, which in the end is the real killer.


Selection of the noise application position in differential privacy In DP-SGD proposed by M Abadi in 2016, noise is applied to the gradient, so every round of training needs to be applied. My questions are:
Can I choose to apply noise that meets the DP requirements to the final model after the model training is completed? Will the total amount of noises applied by this operation be less?

Noise addition is not the only thing that needs to be done to obtain differential privacy: you also need to bound the contribution from each user's gradient update, and calibrate the noise accordingly.
If a user can have an arbitrarily large influence on the ML model, because the gradient update from this user is unbounded, then you can't know how much noise needs to be added afterwards to hide this arbitrarily large contribution. So no, you can't add noise to the model after training is completed and obtain DP, or at least not in a straightforward way.
Alternative approaches to DP-SGD exist, like PATE, which kinds of corresponds to your idea of "adding noise after the training is completed", but that method involves multiple "teacher" ML models "voting" in a private way to train a "student" model, so it's more complicated than simply adding noise to the model.


Equivalent security of KMAC and different HMAC instances? In the August 2016 draft of SP 800-185, SHA-3 Derived Functions (pdf) there is a table for equivalent security settings for KMAC, the MAC derived from SHA-3, and some previous MACs (Table 1 on pages 19-20). According to that table, both HMAC-SHA256 and HMAC-SHA512 have security equivalent to that of KMAC256, just with two different output lengths – 256 and 512 bits, respectively.

Why is this?

According to SP 800-107 (pdf, see 5.3.4) HMAC-SHA512 can have up to 1024-bit security if the key is exactly that long, while HMAC-SHA256 tops out at 512 bits.

Does KMAC256 really match the security of HMAC-SHA512? And if KMAC256 is meant to have that security, would KMAC128 not be sufficient to match HMAC-SHA256? What is the actual security strength of these KMAC variants?

Yep, this is confusing indeed!  I think you're misreading SP 800-107.  If we go back a little bit from the part you refer to, to section 5.3.1, we have this (p. 13):

  The security strength provided by the HMAC algorithm depends on the security strength of the HMAC key, the underlying hash algorithm and the length of the MacTag.

Now, you've focused on section 5.3.4 ("Security Effect of the HMAC Key", my boldface), which says (p. 14, my boldface again):

  The effective security strength of the HMAC key is the minimum of the security strength of $K$ and the value of $2C$.

Reading this in the context of the first quote I provided, I think that this section is saying that if you use HMAC-SHA-512 with a 1024-bit key, then the effort for a key recovery attack is $2^{1024}$.  But there are other attacks on HMAC-SHA-512 than key recovery.  Since the output length is 512 bits, you can always generically forge a (message, tag) pair in $2^{512}$ attempts with guaranteed success.

So even though HMAC-SHA-512 supports a "security key strength" of up to 1024 bits, the output length always allows a cheaper attack than that.

I'm still confused by section 8.4 of the SP 800-185 draft, though.  They talk about the effects of key size and tag length on the security of KMAC, but they just don't explain how the capacity affects the security.  Earlier in section 4.1 (p. 10) they say this:

  [KMAC128 and KMAC256] differ somewhat in their technical security properties. Nonetheless, for most applications, both variants can support any security level up to 256 bits of security, provided that a long enough key is used, as discussed in Sec. 8.4.1 below.

So apparently the 256-bit capacity of KMAC128 doesn't always translate to a 128-bit cap on its security level.  But on the other hand this text would seem to imply that neither can support security levels above 256 bits, where HMAC-SHA-512 does, and then the equivalence table you point out would be false. (Not that it matters practically, of course—$2^{256}$ is a notably large number.)

The other source that might hold some answers is Bertoni et al's "Cryptographic Sponge Functions" paper, which discusses generic attacks against keyed modes of sponge functions (section 5.1, pp. 50ff).

Now, I'm not going to pretend I understand this one, but I'll highlight the bits that jumped out at me.  Section 5.11.2 (p. 51):

  As in the case of stream ciphers, the adversary can attempt state recovery [of the MAC] using tags. In total she needs at least $b$ bits of output to fully determine the state.

Here $b$ is the width of the sponge construction's transformation—in the case of Keccak, this is 1600 bits, which is longer than the 512 bit output size for the HMAC-SHA-512 replacement suggested in the draft.  Does this mean that the state recovery attacks are impossible, or that they become much more difficult?

They also mention in the same paragraph that if the tag length $n$ is smaller than the sponge's bitrate $r$, the state recovery attack's difficulty is unrelated to the capacity, $2^{b - n}/(m - 1)$ instead of $2^c / (m - 1)$.  In the case of KMAC256, the bitrate is 1088, which is larger than 512.

But they do also mention attacks whose effort is related to the capacity $c$ on p. 52.


Does there exist a cryptographic algorithm for comparing 2 encrypted strings I would like to know if there exists algorithms A and B such that the following is possible.

Say Alice has 2 binary strings S1 and S2 both of length n and 2 keys k1 and k2. She encrypts each string with the corresponding key resulting in S1' and S2' respectively and gives these to Bob. Via algorithm A on S1' and S2' Bob produces R which he returns to Alice. Alice then uses algorithm B to determine x, which is 0 if S1≠S2 and 1 if S1=S2.

Additionally, algorithm B must have constant time complexity with respect to n (the lengths of S1 and S2). Also, at no point should Bob be able to determine the values of S1, S2 or x.

If no such algorithm exists or no such algorithm is known to exist, I would be happy to weaken the time complexity condition so that algorithm B need only be sub linear in terms of n.

Note that I have no particular encryption algorithm in mind, the process of
encrypting S1 and S2 can be anything so long as Bob is unable to decrypt S1' and S2' in addition to not being able to determine x.

Just as with most encryption schemes by "unable to decrypt" I mean "unable to decrypt consistently in a reasonable amount of time".

This is a special case of the more general problem of having another individual do computations on some data without ever seeing the data or the resulting output. This is a problem I have been interested in for some time. If you know of any resources on this topic I would be interested to know about them.

Thanks

The simplest solution appears to be to:

eliminate the requirement to use two different keys

it will probably be impossible otherwise

use a randomized homomorphic encryption algorithm that can compute XOR

XOR computes differences, while you technically want equality; You could invert the output with a NOT gate to obtain the result of CMP (comparison), or you could simply check for a null string which would indicate equality.

With this solution, Alice would encrypt both messages under one key using a randomized homomorphic encryption algorithm.

Bob would compute XOR on the two ciphertexts and return the result to Alice.

Alice would then decrypt the ciphertext to obtain the result of the XOR of the two plaintexts, which indicates whether or not the two were different. This can be changed to indicate whether the two plaintexts were equivalent by inverting the result with a NOT gate, or simply checking for a null string.

If XOR was computed on the ciphertexts and $s_1$ and $s_2$ are equivalent, then the output will be a null string of 0s.

I mention CMP because it technically computes what you want (equality), while XOR computes the inverse of what you want (difference). They are effectively both the same, and you will likely want to find a cipher that offers XOR as one that offers CMP will probably not be directly available.

Ciphers for computing XOR

You could use the Paillier cryptosystem; It technically computes the addition of ciphertexts, but the least significant bit of addition happens to be equivalent to XOR. You would need to encode your message one-bit per ciphertext, which would probably take up a decent amount of space.

There is also the cipher from Fully Homomorphic Encryption Over The Integers; It also stores 1 bit per plaintext, but it relies on the hardness of the AGCD problem, which may not be as secure as we would like.


Why are $\{0,1\}$-matrices almost-MDS only when n is 2, 3, or 4? In this paper authors claim that $\{0,1\}$-matrices are almost-MDS (have branch number $n - 1$) on when $n$ is $2, 3,$ or $4$.
For example, how can this two matrices have the same branch number?
$$\begin{pmatrix}0&1&1&1\\
1&0&1&1\\
1&1&0&1\\
1&1&1&0\end{pmatrix}$$
$$\begin{pmatrix}0&1&1&1&1\\
1&0&1&1&1\\
1&1&0&1&1\\
1&1&1&0&1\\
1&1&1&1&0\end{pmatrix}$$
Why branch number doesn't scale up with matrix size?
I'm math dummy. It seems to me that bigger (more 1s) should be better for diffusion. Is there simple logical plain English explanation?

From the article on page 5;

Theorem 1 Let $A:{GF(2^m)}^n \to {GF(2^m)}^n$ be an $n\times n \{0,1\}$-matrix over $GF(2^m)$. Then the branch number of $A$ is at most $\frac{2n+4}{3}$.

Let $A$ be the almost-MDS matrix. So its branch number is $n$. Using above theorem we have
$$n \leq \frac{2n+4}{3} $$
So $n=2,3$ or $4$.
The size of matrix is a tool for finding upper bound of branch number. The branch number of $n\times n$ matrix is at most $n+1$ and equality occur, when matrix be MDS.
Also matrix $A$ is MDS if determinant of all its sub matrices be not $0$.


Search Over Encrypted Data I'm doing a research about how to search over encrypted data as the title said. And, I saw cryptDB used a cryptographic scheme from Song et.al's article Practical Techniques for Searches on Encrypted Data to search for words on encrypted data. But why they don't use DET encryption for each word and to search for a word just encrypt a word and compare it?

If you encrypt the words with the ECB mode then it will reveal information which we call frequency attack. The attacker can see which words are repeating among the rows and try to extract information especially if the attackers have some knowledge of the data contained in the database.

We can see this in a small SEARCH column if encrypted with ECB mode;

| ID  |...| SEARCH                                         |
| x01 |...| 0xF41, 0x650, 0x086, 0x331 ....                |
| x02 |...| 0xF41, 0x165, 0x086, 0x63f, 0x754 ....         |
| x03 |...| 0x650, 0x331, 0x1E6, 0x12f, 0x004 ....         |

As you can see, if you use the ECB mode directly, you can extract information from the SEARCH rows. Using ECB column in CryptDB is your choice. If you think that the data is vulnerable to attack, don't use the ECB mode.

Instead of using ECB, they choose to Song's work and modified as;

They split the words with standard delimiters, removed the repetitions, randomly permuted the repeated words, padded each word into the same size then encrypted.

They claim that their SEARCH nearly as secure as their RND mode, CBC mode with randomized IV for each encryption. They also claim that DBMS server cannot distinguish whether a word repeats in multiple rows and it only leaks the number of distinct words by comparing the size of RND column and SEARCH column.

It is not clear from their article that how this effect the performance. Actually, it is clear that the encryptions with different keys for each row are not performed on the Database. The whole burden of the system is based on the Proxy-Server, and the overhead to the proxy server is not measured for the article.


What's the probable usage of Interlock Protocol I've recently read some articles about the Interlock Protocol, Article by Ron Rivest and Adi Shamir.

I'm wondering if it is possible to protect Key-exchange under Public-Key cryptography from the MITM attack by using this protocol?

There's a method here.Suppose Alice & Bob has exchange their public key, but replaced by Mallory's public key. So Alice have Pkm, Bob have Pkm, Mallory have Pka, Pkb.

Alice.................Mallory.......................Bob

           A->Pkm(1:1)    M->Pkb(1:1)........1

M->Pka(1:1)....B->Pkm(1:1)................................................2

           A->Pkm(1:2)    M->Pkb(1:2)........3

M->Pka(1:2)....B->Pkm(1:2)................................................4

           A->Pkm(2:1)    A->Pkb(1:1)........5

B->Pka(1:1)....B->Pkm(2:1)................................................6

           A->Pkm(2:2)    A->Pkb(1:2)........7

B->Pka(1:2)....B->Pkm(2:2).................................................8

Then Mallory could cheat both Alice and Bob, and they will not recognize. Interlock-protocol seems insecure.

Of course Alice and Bob can ask a question when they're comunicating. Alice sent A->Pkm(1:1), and need a response 'B->Pka(2:1)' after she sent A->(2:1), but she just received the B->(1:1) as step 6, Alice know there's a Man In The Middle.

This method need Alice and Bob know each other very well, and both have a question they can answer but Mallory can't. So if they have such pre-shared questions & answers, why don't they use these question's hash value as a pre-shared key? Alice Just notice Bob the key is the 1st/2nd/3rd... one from the 'Pre-Question-Table', and they don't need public-key cryptographic's help.

Is it true? So what's the area when we can use the Interlock-protocol?

The interlock protocol still relies on an external verification mechanism, otherwise the eavesdropper can replace the challenge with his own challenge.  In the example in the paper, they mention recognizing the voice of the person reading you half the challenge.  That's the external verification.  Without a pre-shared piece of information, a computer network or protocol has no external frame of reference, and can't "challenge the challenge."

Thus, we still need entities like certificate authorities (only better.)


Encrypting or HMACing password digests Assuming I'm using bcrypt to digest passwords, is any additional security gained by either encrypting or HMACing the resulting digests? By requiring a key to compare password hashes, I would expect that this would prevent any attempt at brute forcing sans the key.

The keys for this operation are actually stored somewhere other than our application servers, and all cryptographic operations are performed there via API calls. The service is designed to never divulge keys themselves, and only operate on keys by an opaque ID. So it should be considered somewhat less likely that our keys would be compromised in an attack than in typical webapp scenarios. Keys are also unique per customer of our application.

I would normally only consider HMAC for this operation, but this would require extracting (and storing separately) the salt from the bcrypt digest. So simply encrypting the crypt digests seems to be the simplest approach, and intuitively should produce the same desired security properties.

Is this approach reasonable and sane? We already have the cryptography infrastructure in place, so it's not considerably more difficult to encrypt/HMAC our hashes than it is to compute them in the first place. Is there a reason to prefer an HMAC over AES-128-GCM?

Either is safe, but I would prefer encryption for two reasons:

As noted in the comments, you can change the key without needing to know the original password.
Encryption doesn't add to collisions, while HMAC can. The probability is tiny, but it adds to the probability that the password hash caused a collision. Not worth worrying about, but since it's avoidable...

On the other hand, HMAC does have one advantage: no IV, so no extra space. (GCM even adds an authentication tag.) If you can use something like a user ID as a counter, even that advantage could be lost. If not, that could be important in some cases.


Difference left-or-right CPA security, IND-CPA security I am trying to understand the notion of left-or-right-CPA (LOR-CPA) security for private-key encryption schemes introduced in my lecture. If I understood it correctly so far, the only difference to the standard IND-CPA game is that the encryption oracle always encrypts either the left or the right given message and that the attacker can query the oracle as often as it likes.

I am given the following game definition:

Generate key by running KeyGen $k \leftarrow KeyGen(1^n)$
Choose random hidden bit $h \leftarrow \{0,1\}$
Prepare an oracle $O_{LOR}$ called left-or-right oracle. When called with $m_0, m_1 \in M$ returns $c \leftarrow Enc_k(m_h)$
Call attacker A with $1^n$, attacker outputs two messages $m_0, m_1$ of same length
Call $O_{LOR}$ that returns $c \leftarrow Enc_k(m_h)$, give c to A, and await guess h'
If h' = h ACCEPT, else REJECT

My questions are:

In what sense is this security notion stronger than the notion of IND-CPA security?
Doesn't the standard IND-CPA game also always encrypts the left or the right message, dependent on the hidden bit?

As you are giving your adversary an access to an encryption oracle, I suppose that you implicitly consider the security of a symmetric encryption scheme. In the asymmetric setting, the definitions are slightly different. Here is my understanding of it (disclaimer: I'm by no mean a specialist on security for symmetric encryption scheme).

IND-CPA is the standard name for asymmetric semantic security. The adversary chooses two messages, the challenger encrypts one of them at random and the adversary tries to guess which one was encrypted. An important difference with the symmetric setting is that one does not have to define precisely the kind of oracle access given to the adversary, as he can just encrypt whatever he wants by himself (he is given the public key of the scheme).

Hence, when it comes to symmetric security, one has to be more precise as the oracle access to an encryption oracle is necessary (the adversary cannot encrypt by himself), and can come in different flavors.

So, to me, if one refers to IND-CPA security for a symmetric scheme, it's essentially a shorthand for "one of the security definitions in the CPA model" which are "essentially equivalent". More precisely, here are the four security definitions considered in this seminal paper:

-Left-or-Right CPA security. The oracle always encrypts the left ciphertext or he always encrypts the right ciphertext; you try to guess whether you see a left oracle or a right oracle.

-Real-or-Random CPA security. The oracle always encrypts the message you sent, or always encrypt a uniformly random message (independently of your message). You try to guess whether it's a real oracle or a random oracle.

-Find-Then-Guess CPA security. That one is the closest to the IND-CPA security notion in the asymmetric case: you give two plaintexts to the oracle, who encrypts one of them chosen at random, you have to guess which one.

-Semantic security. Given an encryption of some x drawn according to a distribution D you've chosen, find "some information" about x, id est, some f(x) for a function f of your choice.

Now, to answer your question, here are the security comparisons:

-Left-or-Right CPA security and Real-or-Random CPA security are equivalent (there is a security preserving reduction in both direction)

-Semantic security and Find-Then-Guess CPA security are equivalent

-There is a security preserving reduction from Left-or-Right CPA security to Find-Then-Guess CPA security. This does not hold in the other direction. This means that if an adversary breaks one of the two last security properties, he must also break the two first, but the convert is not true.

EDIT: if by IND-CPA, you mean the security notion I defined with the name Find-then-Guess CPA, then as stated above, if one can break IND-CPA, one can break LOR-CPA, but the converse is not true. Hence, LoR-CPA security is a stronger security notion than IND-CPA (and the proof for this statement is in this paper) Doesn't that answer your question?

For your last question: if IND-CPA is indeed find-then-guess CPA, then the difference is the following. In LOR, the oracle picks a bit once and always answer with an encryption of the plaintext indexed by this bit, for all the encryption requests. In IND-CPA, each time you submit a pair of plaintext to the oracle, the oracle picks a random bit and encrypts the corresponding plaintext.


TLS 1.3: the key_share in a ClientHello after a HelloRetryRequest In TLS 1.3 draft-21, if there is a ClientHello with a key_share, say, $(G_1, g^x)$, the server can send a HelloRetryRequest to request a new key_share value, e.g. ($G_2, g^y)$.

My questions are:

When the client send the second ClientHello, does it replace the old key_share with the new one? i.e, does the new key_share in the second ClientHello becomes $(G_2, g^x)$ or becomes $[(G_1, g^x), (G_2, g^y)]$?
When the server ask for a new key_share in the HelloRetryRequest, does it send its public value with $(G_2, g^y)$ it or just the Group $(G_2)$?
What does the key_share contain? it is confusing. In some cases I get the impression it is the group and the public-key $(G_1, g^x)$, in others, like in the HelloRetryRequest, I get the impression it is only the group $(G_2)$.

Need more clarification on what is supposed to be sent in the key_share in both: ClientHello, HelloRetryRequest, and the second ClientHello after the HelloRetryRequest.

Yes. When the client sends a new ClientHello after a HelloRetryRequest, it replaces the old KeyShare with the one the server requested in the HelloRetryRequest. This is according to my interpretation for the following text in the TLS 1.3 draft 21 here:

  the new ClientHello, the client MUST    replace the original
  "key_share" extension with one containing only a    new KeyShareEntry
  for the group indicated in the selected_group field    of the
  triggering HelloRetryRequest.

If you have any comments to confirm or correct me, please post before I accept my answer.


Why isn't there a final permutation on SPN-based ciphers? I am doing some research on differential cryptanalysis. Most people who are familiar with that cryptanalysis technique do know the tutorial from Heys (Heys Tutorial). I came currently to the question, why is the in the final round no permutation, as in the other rounds? Heys says in the tutorial, that there would no purpose for that. I don't understand why there is no purpose, as in the other rounds. Can somebody clarify that to me?

Because a fixed and published permutation is known, linear and ever so reversible. It's very much like a bait & switch move, but without the switch(substitution). Security is built piecemeal from units of permutation & substitution(rounds). We can undo a singular publically published permutation, and it doesn't take any notice of a key(as it's fixed), thus it adds nothing security wise. Nobody really gets confused and the diffusion effects can easily be reversed.

As a kiddie, slightly similar example, think about ROT13 so called encryption.


Can an altered RSA private key still work as the original? I am interested in understanding public-key encryption using RSA. On the Khan Academy website, I noticed an anomaly when testing out the tutorial.
I created the following public/private keys:
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCYIpH5BT9+1MPf+xqI7khDJZmhMLVltXPf0JJY0mk3gXMQtOar
IocOlKmtWDhz+24KZHa6LuK6edpehKoBjdlhGf1GK+IwSR2uc9TnduuaDB2ETByZ
ZA/4Cbdcw9uroeF2IQV9/MNBUJsV8WHDzMefEhf3cVgdIvhw4IUjbCcOlwIDAQAB
AoGAfzEn6ZJBq8AmozRE0wak076z2tfmUMqLviuarzf7T7Sihu03jQyo7b/MvGht
ikpDjdzAhph8ZntJ3ov7tqDpg8Cm/Un/JvTfk1TGvR5okD2qX0Ww0143+oPC7EWC
1HNq+fcls80mr9XtH0fsPSByBxSOyn7nkdCqDxgiNYVMogECQQDfvMhdTmnpSyT6
9b/4RUHF5ggh+WHagpUL7mUNmeMkBYVyegLtXy2Vy6idVeW6Noaa7Ga1H5sdFDcf
ZdDidexhAkEArhKZ6Q6rG22ULeHfvipU9LiaGpaFstbLCI/RItfrmPXuDjIr6wxU
CQTHMrnzBQCrl0ANg0jp0eGJGNd+Tzkd9wJAOoxuamxgrtopPTseF1wYUC9YJXvb
LZFKa6rg6uRAWmbPexuOtItZpH99Cl82FLq8EsKWRgOVVdC6dA7y0LBHQQJBAIMW
ywVx4HW1XeP3uBFzu6rX4mWneWQm0ZvPAoYk6O22NuJF8kD+dcKc8I5I7rSTvqUW
vZZisIM4P5CPqDVtJB0CQCuh0H2k4nb1MYbgpRmEELDhtNBE6canR/DM8G8M0V7J
BXH1XyyzVP/nxNYH7wyAZlBgCPbMYGLIWDT2EojBgZI=
-----END RSA PRIVATE KEY-----

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCYIpH5BT9+1MPf+xqI7khDJZmh
MLVltXPf0JJY0mk3gXMQtOarIocOlKmtWDhz+24KZHa6LuK6edpehKoBjdlhGf1G
K+IwSR2uc9TnduuaDB2ETByZZA/4Cbdcw9uroeF2IQV9/MNBUJsV8WHDzMefEhf3
cVgdIvhw4IUjbCcOlwIDAQAB
-----END PUBLIC KEY-----

My secret message was Hey What's up dafpunk.
So, I encrypted the above message using the public key, which looks like this:
KBevdNKidVNPFufMxVQ9o3Roq+NeieEEo7KjPyJaeQ01uRtosJ6SeXb72Hola/3DegYLgXiVBvbgIQupmcbNH2xw0GfwQ1NZpLPypuJnYgZQC2oH/OtKKmChA+EHnbFQeIo+zGIJpmD3+mTLwtE6v3ZCAcQrDdAb8CEZ/wd27pQ=

When I tried to decrypt the message using the private key, I got the expected Hey What's up dafpunk. This can be verified in the tutorial's web plugin.
But when I changed four values in the private key, the secret message still was decrypted. I didn't think the private key could be allowed to be changed and the secret message to be decoded. What gives?
Here is an example of the change (it's a bit hard to see so I spaced out the change to be more obvious). You can compare it with the actual private key to verify the length is the same as long as you remove the added spaces near the asdf change.
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCYIpH5BT9+1MPf+xqI7khDJZmhMLVltXPf0JJY0mk3gXMQtOar
IocOlKmtWDhz+ asdf Ha6LuK6edpehKoBjdlhGf1GK+IwSR2uc9TnduuaDB2ETByZ
ZA/4Cbdcw9uroeF2IQV9/MNBUJsV8WHDzMefEhf3cVgdIvhw4IUjbCcOlwIDAQAB
AoGAfzEn6ZJBq8AmozRE0wak076z2tfmUMqLviuarzf7T7Sihu03jQyo7b/MvGht
ikpDjdzAhph8ZntJ3ov7tqDpg8Cm/Un/JvTfk1TGvR5okD2qX0Ww0143+oPC7EWC
1HNq+fcls80mr9XtH0fsPSByBxSOyn7nkdCqDxgiNYVMogECQQDfvMhdTmnpSyT6
9b/4RUHF5ggh+WHagpUL7mUNmeMkBYVyegLtXy2Vy6idVeW6Noaa7Ga1H5sdFDcf
ZdDidexhAkEArhKZ6Q6rG22ULeHfvipU9LiaGpaFstbLCI/RItfrmPXuDjIr6wxU
CQTHMrnzBQCrl0ANg0jp0eGJGNd+Tzkd9wJAOoxuamxgrtopPTseF1wYUC9YJXvb
LZFKa6rg6uRAWmbPexuOtItZpH99Cl82FLq8EsKWRgOVVdC6dA7y0LBHQQJBAIMW
ywVx4HW1XeP3uBFzu6rX4mWneWQm0ZvPAoYk6O22NuJF8kD+dcKc8I5I7rSTvqUW
vZZisIM4P5CPqDVtJB0CQCuh0H2k4nb1MYbgpRmEELDhtNBE6canR/DM8G8M0V7J
BXH1XyyzVP/nxNYH7wyAZlBgCPbMYGLIWDT2EojBgZI=
-----END RSA PRIVATE KEY-----

That change does nothing to the pub/private protocol, which is concerning. What am I missing?

I would be surprised that a proper system will work with this;

It fails in openssl check.

    openssl rsa -in sample_rsa_prv_mod.key -check RSA key
    error: n does not equal p q

If you look at an ASN1 parser like ASN.1 JavaScript decoder you will see that your modifications change the modulus. Why the rest didn't corrupt, since the ASN.1 format uses delimiters.

The modulus is not correct. The Khan Academy provides no warning about this i.e. doesn't check as OpenSSL and this implies not a good library. Their implementation may use CRT and from the modulus with $n = p \cdot q$. This is the only plausible explanation since I've tested for some other plaintexts, too.
How the OpenSSL command line behaves with these two private keys;
$cat input.txt
1234567890

$ openssl rsautl -encrypt -pubin -inkey sample_rsa_pub.key -in input.txt

$ openssl rsautl -decrypt -inkey sample_rsa_prv.key -in encrypted.txt
1234567890

$ openssl rsautl -decrypt -inkey sample_rsa_prv_mod.key -in encrypted.txt
RSA operation error
140083785925952:error:0407109F:rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error:../crypto/rsa/rsa_pk1.c:251:
140083785925952:error:04065072:rsa routines:rsa_ossl_private_decrypt:padding check failed:../crypto/rsa/rsa_ossl.c:491:

As we can see, it fails to decrypt. So, the only plausible explanation is again they construct the $n$ from $p$ and $q$. They don't use $n$ in the file.

Note: They use various sources in their JS and probably one fails on their usage.

Textbook RSA little 101

Select target security $t$, today  $t> 2048$
Select public exponent $e$, $e= \{3, 5, 17, 257,65537\}$ are possible candidates;
Generate two unifrom random prime $p$ and $q$ where each has 1024-bit
Form the modulus $n = p \cdot q$
Calculate Euler's totient function $\phi(n) = (p-1)\cdot(q-1)$ ( Actually use Carmichael Function $\lambda(n) = \text{LCM}(p-1,q-1)$ that can produce shorter private exponent $d$)
Check $\gcd(e,\phi(n))=1$, if not 1 return to step 3.
Find $d$ with Ext-GCD such that $e \cdot d = 1 \bmod \phi n$.
Publish the public key as the pair $(n,e)$, the RSA modulus, and the public exponent.
Keep secret the private key $(n,e,d,p,q)$ ( possible more: $n,e,d, p, q, d_p,d_q,d_{inv}$. The values $d_p,d_q,d_{inv}$ are used for CRT based calculation that can speed up modular exponentiation up to 4-time s)

Now encrypt a message $m$ as $c = m^e \bmod n$ and decrypt with $m = c^d \bmod n$.
TextBook RSA as the name suggests should never be used in practice. If you want to use RSA to encrypt some small messages use PKCS#1 v1.5 or OAEP padding to mitigate the attacks, see 20 years of RSA.
If you want to use RSA for signature, use it with PSS padding.
Today RSA mostly used in signatures. For encryption, we prefer hybrid-cryptosystem like key exchange with DHKE (better the ephemeral elliptic curve version ECHKE) and encrypt with authenticated encryption modes like AES-GCM(-SIV) and ChaCha20-Poly1305. It is possible to use RSA-KEM to send the key, too.


Computational indistinguishability with Example Based on computational indistinguishability definition no PPT
  algorithm can distinguish $X$ from $Y$, where $X=\{X_n\}_{n \in N}$
  and $Y=\{Y_n\}_{n \in N}$ are ensembles of probability distributions
  and $X_n$, $Y_n$ are probability distributions over $\{0,1\}^{p(n)}$
  for some polynomial $p(.)$.

The above definition is not clear to me. Can anyone explain that with a clear example (e.g. roll a die or flip a coin). As the examples for the pevious posts about the same topic are not very clear.

Side note: I believe there is a lack of clear explanation and examples in the literature about this topic. So any good example would help the other learners too!

For any $n \in \mathbf{N}$, let $X_n$ be a random variable which always equals $n$, and $Y_n$ be a random variable which equals $n$ or $n+1$ each with probability $1/2$. Then the probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are not computationally indisinguishable. A possible distinguisher is an algorithm $D$ which, on input $(y, 1^n)$, outputs $1$ if $y = n$ and $0$ otherwise. We then have $\mathsf{Pr}[D(X_n, 1^n) = 1] = 1$ for all $n$ because $X_n$ always equals $n$. On the other hand, we have $\mathsf{Pr}[D(Y_n, 1^n) = 1] = 1/2$, hence
$$\left| \mathsf{Pr}\left[D\left(X_n, 1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n, 1^n\right) = 1\right]\right| = \frac{1}{2},$$
which is constant and thus not negligible. I can't think of any simple example of probability ensembles which are computationally indistinguishable, except trivially if they are identical or just assumed to be indistinguishable. Indeed, constructing probability ensembles which are non-trivially computationally indistinguishable is in a way what cryptography is all about...

Actually, here's an example (although it could reasonably be considered trivial as well). As above, $X_n$ always equals $1^n$. $Y_n$ is the output of the following algorithm on input $1^n$:

Throw $n$ coins.
If the coins are all $0$, output $0^n$. Otherwise output $1^n$.

Thus $Y_n$ equals $0^n$ with probability $2^{-n}$ and $1^n$ with probability $1-2^{-n}$. I claim that they are computationally indistinguishable. Intuitively, $X_n$ and $Y_n$ are identical except when $Y_n = 0^n$, but because this happens with negligible probability, no algorithm is able to distinguish them with non-negligible probability. (Note that this applies to all algorithms, not just PPT ones.)

Let $D$ be any algorithm, we want to estimate
$$\left|\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right]\right|.$$
We remark that, conditioned on $Y_n \ne 0^n$, $(X_n,1^n)$ and $(Y_n,1^n)$ are identically distributed: they always equal $(1^n,1^n)$. Hence,
$$\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\middle|Y_n \ne 0^n\right] = \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right].$$
Using this, we obtain
$$
\begin{align*}
\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right]
  &= \underbrace{\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n = 0^n\right]}_{\ge 0}
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\ge \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\ge \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \middle| Y_n \ne 0^n\right] \cdot \mathsf{Pr}\left[Y_n \ne 0^n\right] \\
  &\ge \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] \cdot \left(1-2^{-n}\right), \\
\end{align*}
$$
hence
$$\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] \le \underbrace{\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right]}_{\le 1}\cdot 2^{-n} \le 2^{-n}.$$
On the other hand,
$$
\begin{align*}
\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right]
  &= \underbrace{\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n = 0^n\right]}_{\le \mathsf{Pr}\left[Y_n = 0^n\right]}
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\le \mathsf{Pr}\left[Y_n = 0^n\right]
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\le \mathsf{Pr}\left[Y_n = 0^n\right]
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \middle| Y_n \ne 0^n\right] \cdot \mathsf{Pr}\left[Y_n \ne 0^n\right] \\
  &\le 2^{-n} + \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] \cdot \left(1-2^{-n}\right), \\
\end{align*}
$$
hence
$$\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] \ge \underbrace{\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right]}_{\ge 0}\cdot 2^{-n} - 2^{-n} \ge -2^{-n}.$$

(For those studying the book of Katz-Lindell, this is similar to Exercise 7.1.)


What is the “Walsh Function” about? I'm currently dealing on the so called “Walsh Function” (WF) that is written like:
$$f^W(a)=\sum_{x\in{F^n_2}}(-1)^{f(x)+(a,x)}$$
What I know is that this function is used to approximate an arbitrary function like $f: F^n_2  \to F_2$ and that the $a$ in the upper function is the so called Walsh Coefficient.

But whats in detail about the WF? What can I do with it exactly? How do the elements in the set of the WF look like? As far as I know is this set called the Walsh Spectrum!?
How can an arbitrary function be approximated by the WF?

And what exactly is the the Walsh Transformation (WT). I know there is a method to conduct the WT, the so called Fast-Fourier-Transformation. Why do I do a WT?

The function $L_a(x)=\langle a,x\rangle=a_1 x_1+\cdots+a_n x_n$ is a linear multivariate function of $(x_1,\ldots,x_n)$.

The function $$f(x)+\langle a,x\rangle=f(x_1,\ldots,x_n)+a_1 x_1+\cdots+a_n x_n$$
equals $0$ mod 2 if $f(x)=\langle a,x\rangle$ and $1$ mod 2 otherwise.

The sum
$$
\hat{f}(a)=\sum_{(x_1,\ldots,x_n) \in \mathbb{F}_2^n} (-1)^{f(x)+\langle a,x\rangle},
$$
is equal to $2^n-2 d_H(f,L_a)$ and computes the correlation between the function $f$ and the linear function $L_a$. Here $d_H(f,L_a)$ is the Hamming distance between those two functions as $x$ varies over $\mathbb{F}_2^n.$ Each one of these $2^n$ correlations (for different $a$) can be obtained by a matrix multiplication.

Since the mapping is invertible, a $2^n\times 2^n$ Hadamard matrix appears as below: $$\left[(-1)^{\langle a,x \rangle}\right]$$
where $a$ indexes rows and $x$ indexes the columns in the standard order.

Due to the kronecker structure of the Hadamard matrix, a fast transform and inverse transform exist. The functions that have the maximum hadamard coefficient $\hat{f}(a)$ minimized are called bent functions and are important in coding theory and cryptography. By Parseval's relation, $$\sum_{a \in \mathbb{F}_2^n} |\hat{f}(a)|^2 =2^{2n},$$
and bent functions have $|\hat{f}(a)|=2^{n/2}.$ Note $f(0)=0$ means a function is balanced, bent functions are not.


RSA: given (N,e,dP), is it possible to find d? Assuming that you are given the public modulus $N$, the public exponent $e$, and the private number $d_P = d\mod (p-1)$, is it possible to recover $d$?

If not, is it possible to recover $m$, also given a $c$?

is it possible to recover $d$?

Yes, with $N, e, d_P$, you can factor $N$ (and from there, recover $d$)

If we select an arbitrary $r$, $r^{e \cdot d_P} - r \bmod n$ will have $p$ as a  factor. This is because $r^{e \cdot d_P} = r \bmod p$ (as $e$ and $d_P = d \bmod (p-1)$ are inverses of each other modulo $p-1$).

In contrast, $r^{e \cdot d_P} - r$ is unlikely to have $q$ as a factor.

So, if we select a random $r$, and compute $\gcd( n, r^{e \cdot d_P} - r\bmod n )$, we will (with high probability) recover $p$, and from there, factoring $n$ and reconstructing $d$ is straight-forward.


What is the purpose of Pseudorandom Function Families (PRFs)? I'm currently in a course in Cryptography, and was wondering why pseudorandom function families exist at all. If there existed one pseudorandom function f(x), based on its definition, could that not be used in all cases where a pseudorandom function is needed? Why would pseudorandom functions ever need to be sampled from a family of functions?

By definition, a family of functions (with a given domain and codomain) is a PRF if no efficient algorithm can (with non-negligible advantage) distinguish a randomly chosen member of the function family from a function chosen at random from the entire set of functions with the same domain and codomain.

Obviously, if the family contained just one function, distinguishing it from a random function would be trivial: just feed a couple of values into the function, and check if the outputs match those from the function you're trying to distinguish from random.

For example, let's say that we have an unknown hash function $f$ with a 256-bit output, and we're trying to decide whether it is a) SHA-256, or b) a randomly chosen hash function with a 256-bit output.  We can just feed the ASCII string Hello to the function, and check if the output in hexadecimal equals 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969.  If it doesn't, the function definitely isn't SHA-256; if it does, it almost certainly is.

However, if we're instead trying to tell whether $f$ is HMAC-SHA-256, we can't do this unless we know the HMAC key.  In this case, the set of all possible HMAC-SHA-256 functions forms a pseudorandom function family, where each function in the family is defined by a different HMAC key.


Is it possible to construct a PRNG where the output numbers have a certain distribution of hamming weights? I am in need of a non-uniform random number generator where each n-bit output has a hamming weight with a certain binomial distribution.

For example, I would like a non-uniform PRNG which generates 32-bit outputs with a hamming weight whose binomial distribution is n=32, p=0.1. For instance, 0xFF should be output with significantly less probability than 0x200, which in turn should have the same probability as 0x1.

Perhaps I can modify the output of a PRNG like xorshift or a LFSR to accomodate for this? I thought about rejection sampling the output, but the distribution of hamming weights for a uniform PRNG does not necessarily envelope a given binominal distribution with a variable parameter p, especially when p << 0.5.

I am not concerned about the cryptographic quality of the output. However, I am working on a 8 bit microcontroller with 2 KB SRAM, so memory and speed are both my primary concern. In the most naive case, I would just generate an array of random numbers and convert each element to 0 and 1 given a threshold probability, and finally convert this resulting array of 0's and 1's to an integer. But I would really, really like to avoid this memory overhead of an n-element array.

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the individual bits are uncorrelated).

In the simplest case, you could generate 3 words, and just AND them together into a single one.  In C, this would be:

     r1 = rand();
     r2 = rand();
     r3 = rand();
     return r1 & r2 & r3;

This gives each bit set with probability 0.125, which is close to 0.1

If that's not quite close enough, you can get a closer approximation by using more bits; for example, r1 & r2 & r3 & ~(r4 & r5) results with bits set with probability $3/32 = 0.09375$

With this technique, you use $n$ random words to generate bits set with probability $k 2^{-n}$ for some integer $k$; this can be made arbitrarily close to 0.1.

This obviously uses minimal memory; the computation time isn't too bad (assuming your rand implementation is cheap), unless you insist on a quite good approximation to your target probability.

And, while I said 'words', your implementation would use whatever size it finds most convenient; for an 8 bit CPU, each word might be 8 bits (and you just do it 4 times to generate the required 32 bits).


Roots of polynomial in Shamir secret sharing I need to know whether one can obtain any roots of the polynomial in Shamir secret sharing if he possesses less than threshold shares.

For instance in (t,n) if he has t-1 shares can he obtain any roots of the original polynomial?

** Here we assume that the polynomial has some roots.

If you have $t-1$ shares of an $(t,n)$ system, you have a chance at learning of the roots of the system... as long as some of your shares have a 0 for the $y$ coordinate.  You can't learn any other roots.

Demonstration that the possession of a share with a $y$ coordinate of 0 gives you knowledge of a root (and forgive me if this is too obvious):

A share in Shamir's scheme is a pair $(x, P(x))$, where $x$ is a nonzero coordinate, and $P(x)$ is the secret polynomial evaluated at that coordinate.  If the $y$ coordindate listed happens to be 0, we have $P(x) = 0$, which is pretty much the definition of $P$ has a root at $x$.

Demonstration that the attacker cannot learn any roots at locations other than the $x$ coordinates for the shares he has:

Consider what would happen if he could.  By learning of a value $x'$ which does not appear as an $x$ coordinate for any of the shares he has, and for which $P(x')=0$, he could treat that as another share $(x', 0)$, and use that, and his $t-1$ existing shares, and learn the entire polynomial.  We know he can't do that, and so he can't learn such an $x'$


What is the public key length of RSA and Ed25519? I have made some research but doesn't understand fully:

In this link, it says ed25519 has a length of 64 characters.
Questions:

Is this base64 encoded characters?
And does ed25519 limit to only 64 characters?

In the same link, it says rsa 3072 has 544 characters. I tried to generate a public private key pair here but:

rsa515 produces a public key with 128 characters
rsa1024 produces a public key with  216 characters
rsa2048 produces a public key with  392 characters
rsa3072 produces a public key with  564 characters
rsa4096 produces a public key with  736 characters

Question:

I would like to ask why?

Note that this isn't really a cryptography question; it's about how various kinds of data representations work. The data in this case happens to be cryptographic, but the same or similar methods, operations, and issues can occur with any kind of data.

In this link, it says ed25519 has a length of 64 characters
Is this base64 encoded characters?
And does ed25519 limit to only 64 characters?

That webpage is about keys used in SSH, and more specifically in OpenSSH which is the only SSH implementation most people know about even though there are (many) others.
A0. That link says ed25519 publickey is 68 chars, not 64, and is correct; see below.
A1. Yes, OpenSSH stores publickeys in base64, or more exactly as a line containing two or three space-separated fields: a type or algorithm name, a base64 encoded 'blob' which itself can contain multiple subfields, and an optional comment string; with in some cases one more field preceding those (nothing in key.pub files, always a hostname (or hash thereof) in the known_hosts file, optionally a set of special options in the authorized_keys file).
For ed25519 the 'blob' data in binary is (always) 51 bytes: a 4-byte length, a 15-byte string containing (again) the algorithm name, another 4-byte length, and a 32-byte value which is the actual publickey value. 51 bytes is base64-encoded to 68 chars (exactly).
A2: yes, ed25519 keys are fixed length 32 bytes (as kelalak commented), and the added metadata in the 'blob' is also fixed length, so the base64-encoded blob is fixed length. This isn't true of other algorithms used by OpenSSH.
An RSA-3072 key (with e=F4, see below) in OpenSSH format has a blob of 23+384=407 bytes encoded as 544 chars.

I tried to generate a public private key pair here but: ...

That webpage produces (and uses) keys in the formats used by many but not all other programs, including Java, (plus base64 encoding) which are different from those used by OpenSSH. In particular for publickey Java uses the ASN.1 structure SubjectPublicKeyInfo defined in X.509 and more conveniently copied in RFC5280 section 4.1. Thus the encoded key contains ASN.1-level metadata (tag and length octets) and 'application' metadata (the AlgorithmIdentifier structure) in addition to the actual publickey values -- which as also commented contains both the modulus n and the public exponent e as required by the standard format, although that site like many but not all systems makes e a constant value 65537 chosen because it is a Fermat prime: prime is good because it eases generation of p,q with p-1,q-1 coprime e as required, and Fermat primes have minimal Hamming weight making encryption or verification operation cheaper.
515 there is a typo; it actually does 512 bits. Although mathematically RSA works for any number of bits, a nearly universal convention quickly developed of using only powers of 2 or values halfway between such powers: 512, 768, 1024, 1536, 2048, 3072, 4096. (There are some exceptions; for example some smartcard interfaces use message formats with a single-byte length field allowing up to 1016 bits if signed or 2040 bits if unsigned, making that the maximum size RSA they can readily support.)
The 'standard' RSA sizes with e=65537 represented as SubjectPublicKeyInfo in DER and base64 are:

modulus bits
DER bytes
base64 chars

512
30+64=94
128

768
30+96=126
168

1024
34+128=162
216

1536
34+192=226
304

2048
38+256=294
392

3072
38+384=422
564

4096
38+512=546
736

I would like to ask why?

The 'real' info in a RSA-3072 publickey is the modulus n, which is 384 bytes in both representations, but the added metadata varies in format and size, resulting in base64 encodings of different lengths.


What's the point of OAEP? I can't seem to wrap my head around what benefit OAEP provides (specifically with RSA). Lets consider really small numbers for a moment. If the random source in the padding algorithm gave a random value in the range of 1-100, then each unique message value could be represented by 100 different padded values. Isn't this the same as a homophonic encryption scheme? It doesn't prevent frequency analysis, CPAs, CCAs, etc, it just makes them more difficult to perform?

I know that in real world applications the values and ranges involved are extremely large. Do we consider RSA+OAEP secure because the number of possible padded representations of a message is some insanely large number, and thus not feasible to bruteforce with current hardware?

If an adversary had unlimited computing power, or if we are using a very small modulus, does OAEP actually matter?

Do we consider RSA+OAEP secure because the number of possible padded representations of a message is some insanely large number, and thus not feasible to bruteforce with current hardware?

No. But a related proposition holds: we would consider RSA+OAEP insecure if the number of possible padded representations of a message was less than some large number, like $2^{80}$ at the very least (which is not "insanely large" by today's measure).

In many practical cases, textbook RSA encryption per $C=M^e\bmod N$ would be insecure if $M$ was directly the plaintext, without some random added in the padding process transforming plaintext to $M$. This is because the adversary is assumed to hold the public key $(N,e)$ and could trivially use it to verify a guess of the plaintext, which matters (e.g. when the goal is to mask from adversaries the result of a coin toss, the name of someone on the class roll, a PIN number..). To resist that, the randomness added by the encryption padding process needs to be kept secret from attackers, and have at least $b$-bit entropy for $b$-bit security. RSAES-OAEP does that (it injects $2b$-bit, typically 256 bits nowadays), as well as other RSA encryption padding schemes like RSAES-PKCS1-v1_5.

But there are other objectives met by OAEP:

Allowing a security reduction to the RSA problem (which is of finding $M$ from $M^e\bmod N$ for random $M$ with $0\le M<N$). In a nutshell, OAEP padding transforms the plaintext into an $M$ that covers a large fraction of the $[0,N)$ in a random-like way, and allows a strong argument that if we could break RSA+OAEP under CPA or CCA (by this account: CCA1, or CCA2 under the Random Oracle model), we could break RSA or the pseudo-random functions (hash or Mask Generation Function) used in OAEP.
Mitigating the risk of attacks using side channels in the decryption operation when fed malformed ciphertext (information leak by timing to get an error code, or value thereof). These have the potential to transform something performing the decryption into a decryption engine (see Bleichenbacher's attack on PKCS#1 v1.5 encryption). In a nutshell, OAEP is better protected because the comparison done to decide if a padded plaintext $M$ is valid involves comparing hashes (it also helps that it is CCA-secure).

Conclusion: we consider RSA+OAEP secure because OAEP provides a security reduction to the RSA problem under CPA and CCA, and it helps mitigate implementation attacks.


Correlation of an approximation over a random permutation I read a paper of linear cryptanalysis that is J.Daemen et al's Probability distribution of correlation and differentials in block cipher.

In this paper's lemma 8's proof, I can't understand this formula (page.13).

  The number of balanced Boolean functions $g(a)$ for a given value of $x$ is :

  $$ {{2^{n-1}} \choose {2^{n-2}+x}} {{2^{n-1}} \choose {2^{n-2}-x}} = {{2^{n-1}} \choose {2^{n-2}+x}}^2$$
  and

  If we divide this by the total number of balanced Boolean functions,..."

Please, tell me how this formula is derived.

So $x$ measures the departure from balance in the left half of the truth table, say it is the excess number of 1's in the left half of length $2^{n-1}$. By the definition of binomial coefficients there are $$\binom{2^{n-1}}{2^{n-2}+x}$$ such vectors. This is the first factor. The second factor is the count of vectors missing $x$ 1's, since the overall truth table is balanced.

Using $$\binom{a}{b}=\binom{a}{a-b}$$ completes the argument.


Where can I download a database of RSA keys? I'm looking to do some research into how RSA is used in the wild. I've read through a few papers and it seems other researchers have had no trouble collecting millions of keys to perform analysis on.

I've done some preliminary research but can't seem to find any one site from which to download other people's public keys.

I assume that given the nature of public keys that it would not be a privacy risk to have this sort of database available to the public.

If RSA keys in PGP format are fine, you can download them from any keyserver.

Many keyservers, at least MIT, have a robots.txt that disallows automated downloads, so be sure to check that before attempting to bulk download anything.

If you need a large collection, you could download a keyserver dump and filter out what you need.


Elliptic Curve Crypto, is a distributed signing method possible using Shamir's Secret Sharing? Note: A distributed signature scheme exists for RSA:
Practical Threshold Signatures, Victor Shoup.
Is it possible to adapt such scheme for ECC?

A centralized signing machine is vulnerable to attackers

In the situation where a private key has been distributed over R number of machines, which each hold a part of the secret, these R machines can send their share to the signing machine, which will recombine the private key, using the R parts received, in order to sign messages.

This is not satisfactory, because the attacker now only has to attack the signing machine, and wait until it has recombined the private key in order to steal it.

Partial signatures

If sig=sign(sk,m) is the elliptic curve cryptography function to sign a message m with private key sk, yielding signature sig, and if shamir(sk) = [shsk1, shsk2, shsk3, ..., shskR] the function that produces a vector of Shamir secret parts, then the partial signatures would be:

shsig1=sign(shsk1,m)
shsig2=sign(shsk2,m)
...
shsigR=sign(shskR,m)

Since it is not practically possible to retrieve the private key from a ECC signature, it is also not practically possible to retrieve the shamir secret from a partial ECC signature. Therefore, it would be safe to send on such partial signature to the signing machine.

How to recombine the partial signatures?

Now we need a function combineShamirPartialSigs, where:

sig=combineShamirPartialSigs(shsig1, shsig2, ... , shsigR)=sign(sk,m)

In other words, the combination of partial signatures should be equivalent to the signature of the combined private key sk.

Progressive signing

Preferably, such function would even be able to sign progressively:

shsigP1=sign(shsk1,m)
shsigP2=combinePartialSigsProgressively(shsig1,shsk2,m)
shsigP3=combinePartialSigsProgressively(shsigP2,shsk3,m)
shsigPR=combinePartialSigsProgressively(shsigP[R-1],shskR,m)

=sig

The last machine R to sign progressively would then automatically produce the final signature sig.

Security value of this function

This kind of functions would solve a serious security problem. The R machines would not send their secret parts to the signing machine, but produce partial signatures by themselves and send those instead, or even gradually combine the signature by themselves. It would be pointless for the attacker to attack any centralized signing machine, because at no point in time it would know the private key. This function would protect a distributed signing infrastructure from attackers, by keeping its core secrets distributed at all times.

Question

Does such function exist? Would it be possible to construct such function?

You can do it with two machines. https://www.iacr.org/archive/crypto2001/21390136.pdf (this paper is for DSA; it's easy to adapt for ECDSA).

Here's an open-source JavaScript implementation of two-party ECDSA signing, using Bitcoin parameters: http://www.jpaulgossip.com/demo/split-key.html

Unfortunately the protocol requires at least three rounds of interactive communication so it is probably not suitable for what you call progressive signing.

I believe splitting a key among more than two machines remains an open problem. ECDSA is not well suited for split signatures. I assume your application is something like Bitcoin which requires ECDSA. If only Bitcoin had used BLS signatures, then it would be easy to implement multiparty signing.

Update (4/5/15): A group of researchers at Princeton have solved the problem of multiparty (more than two parties) Bitcoin signatures: https://freedom-to-tinker.com/blog/stevenag/threshold-signatures-for-bitcoin-wallets-are-finally-here/


Embed message on Elliptic curve Can anyone answer me, if I can embed a message when I convert it to ASCII value to points on Elliptic curve $E(Fp)$ , by multiplied the ASCII value with a base point B?

For example, I have  $E(F_{31}): y^2=x^3+x+3 \bmod 31$, a base point $B=(1,6)$ and the order of the the elliptic curve is $N= 41.$

To convert the text "Hello" to ASCII values we get $\{72,101,108,108,111\}$ and embedding them to get points lie on $E(F_{31})$ by following:

$72 B=72 (1,6)=(26,11)$ and so on.

Is that true to do that??

Can anyone answer me, if I can embed a message when I convert it to ASCII value to points on Elliptic curve $E(Fp)$ , by multiplied the ASCII value with a base point B?

This is probably a rather more extensive answer than what you were looking for; however here it goes:

There are a number of reasons why we might need to convert a 'value' to a curve point, that is, define a function $F(x)$ that takes a value $x$, and maps it to a point on $E(\mathbb{F}_p)$; there are also a number of ways to do so.  Which one is best depends on the requirements that the use case demands.  Some on the requirements to consider:

Does it need to be invertable?  That is, if you're given a point $F(x)$, do you need to be able to recover $x$ (or, do you need that the problem of recovering $x$ to be difficult)?  Some use cases need it to be invertable, others don't care.
Do you need to obscure the relationship between two mapped points?  That is, if someone knows $x, y$, is it a problem if they can deduce the discrete log of $F(y)$ to the base $F(x)$; that is, if that can find the value $n$ s.t. $n \cdot F(y) = F(x)$?  For some use cases, it is critical that this be a hard problem; for others, it isn't important.
How important is side channel resistance?  If someone can listen into the computer evaluating $F(x)$ (e.g. by monitoring the timing), how important is that they not be able to get information on $x$?  Again, for some use cases, this is critical.

Within those three requirements, there are three obvious strategies to implement $F(x)$:

Use simple point multiplication, which is your original idea, define $F(x) = x \cdot G$, for the curve generator point $G$.  This is moderately efficient (using code you probably have lying around anyways) and (depending on your point multiplication routine) potentially side channel resistant; however it obviously makes the discrete log problem fairly easy.  And, it is potentially invertable with some work if the range of possible $x$'s are small - if we know that $0 < x < n$, this we can recover $x$ with $O(\sqrt{n})$ steps.
Use a 'hunt and peck' approach, as suggested by Koblitz.  You map the $x$ value into a potential $x$ coordinate, and then search for near-by values for which is the $x$ coordinate of an actual point (and then pick the $y$ coordinate somehow).  This can obviously be made either invertible or noninvertible as required, and it disguises any relationship between mapped points.  On the other hand, this isn't that efficient, and side channel resistance can be tricky (at least, I've seen people get it wrong).
Use a Hash2Curve algorithm, such as one found here.  These algorithms are quite efficient, and they obscure any relationship between mapped points.  On the downside, these algorithms are noninvertible, and the algorithms that can be used depend on the actual curve (generally, the value of $p$).

One last note: you appear to be asking how to embed messages in points so to use ECElGamal.  In practice, we never use ECElGamal; it is rather more practical to use ECIES, where we use the Elliptic Curve to share a point that only the encryptor and decryptor know, and use that point to derive a symmetric key that encryptions the actual message.  This solves the problem, without any need to map the message to a point.


Encrypting the same message using different schemes $E_1$ and $E_2$ are IND-CPA secure encryption schemes.
$E$ is defined as:
$k_1,k_2 \leftarrow K_1 \times K_2$ .
$E_{k_1,k_2}(m) \leftarrow E_{1,k_1}(m)||E_{2,k_2}(m)$.

Hope the notations are in an obvious manner.
$\leftarrow$ means randomly choosing an element from the corresponding distribution. || stands for concatenation.

My question is whether the encryption scheme $E$ is IND-CPA secure.

Intuitively, this would be secure. If you can not get any information from either $E_1$ or $E_2$, should you get no information given both. (Of course there is a loophole here: $E_1$ or $E_2$ by itself may not leak information, however the combination of them may give some information away.)

When I tried to prove it I can not reduce the break of  $E$ to either $E_1$ or $E_2$. Neither can I find a counter example.

Yes, $E$ will be always be secure.  This follows from a standard type of proof called a hybrid argument.  Giving the full details would be tedious, so here is a sketch in case you are familiar with hybrid arguments:

We define games $H_0,H_1,H_2$.
We let $H_0$ be the IND-CPA game, but with the game's secret bit hardcoded to $0$.  So the game always outputs $E_{1,k_1}(m_0)\|E_{2,k_2}(m_0)$ when the adversary submits $(m_0,m_1)$ as its challenge.

Next define $H_1$ to always return $E_{1,k_1}(m_1)\|E_{2,k_2}(m_0)$ always, and finally $H_2$ to always return $E_{1,k_1}(m_1)\|E_{2,k_2}(m_1)$.

A successful IND-CPA adversary $\mathcal{A}$ against $E$ is one that distinguishes $H_0$ and $H_2$.  The games $H_0,H_1,H_2$ are chosen so that we can use $\mathcal{A}$ to build adversaries $\mathcal{A}_0, \mathcal{A}_1$ to distinguish between $H_0$ and $H_1$ or between $H_1$ and $H_2$. But this will mean that at least one of the adversaries breaks the IND-CPA security of $E_1$ or $E_2$ respectively.


Consuming of entropy When I put:

sudo watch tail /proc/sys/kernel/random/entropy_avail && dd if=/dev/random of=/dev/zero

It shows that available entropy is "consumed".

What I can't understand is:

Why does generating random consume entropy? Why does generating random bits cause that entropy to become useless?

Why generating random consumes an entropy?

For the same reason that to generate true random bits using coin throws, one needs to throw a coin for each bit generated. Any attempt to use less throws is doomed (against a computationally unbounded adversary, or if the technique relies on few simple bit combinations).

  Why generating a random bit causes that entropy to become useless?

Revealing a generated random bit is what makes it useless towards generating further secure random bits.

There's a solution: generate a sufficient number of random bits (like 256 or more) and use these, exclusively, to seed a Cryptographically Secure Pseudo Random Number Generator which will supply an endless stream of bits that have all testable properties of truly random bits. That's part of the strategy of Unix's /dev/urandom