What's the truth about this "absolutely unbreakable" cipher? A story appeared on Forbes today claiming that we now have an absolutely unbreakable cipher. It cites a paper published in Nature Communications. However, I'm skeptical:

  But what if there were a method of enabling data to be sent using an "absolutely unbreakable" one-time communication technique? What if that technique could achieve perfect secrecy cryptography via correlated mixing of chaotic waves in an irreversible time-varying silicon chip?

That seems like a lot of buzzwords and doesn't sound convincing.

  With no software or code to manipulate, traditional methods of cracking computer encryption are irrelevant

  Again, Dr. Cruz reiterated that there is no code to manipulate, and the limited software is ROM based, so traditional methods of hacking encryption are irrelevant.

Don't ciphers and their weaknesses exist independent of software and code? Solitaire has neither software nor code, but has weaknesses.

  The cryptographic keys generated by the chip, which are used to unlock each message, are never stored

You need the keys to decrypt the message, so even if they're never stored, something good enough to reconstruct them must necessarily be stored.

  It is claimed that even facing an attacker with "unlimited" technological power, even if they could access the system and copy the chips, would be unable to break the encryption because it is protected by the second law of thermodynamics and the "exponential sensitivity of chaos."

I really don't like the sound of this.

  Professor Andrea di Falco of the School of Physics and Astronomy at the University of St. Andrews, another author of the study, said that "this new technique is absolutely unbreakable, as we rigorously demonstrated in our article."

A really extraordinary claim.

  The second law of thermodynamics prevents this attack. Every time Alice and Bob change the chip with an irreversible process, they increase the total entropy of the system and the environment, creating new chaotic structures exponentially different from the ones used in the communication (conditions 3 and 4). If Eve accesses the system, it is impossible to recreate the initial chips and to perform any search, as this requires reverting the transformation of Alice and Bob with an entropy decrease, thus violating the second law.

This is contrary to my understanding of the second law of thermodynamics. Can't you easily decrease entropy in systems that aren't closed (such as the chips), just by increasing it more outside the system (exhaust heat somewhere)?

So is this new cryptosystem legit, or is it just more snake oil? If it's legit, then what are the explanations for my above concerns? If it's snake oil, how did it manage to dupe both Nature Communications and Forbes?

I will go out on a limb here and say that it reeks of snake oil. I have seen the answer by @dirdi, but I am very skeptical. It is clear from the paper that the authors have almost no understanding of cryptography: they refer to algorithms used as DES, AES and RSA, and that quantum computers break them all.

We know that quantum computers only have quadratic speedup to break symmetric ciphers, to the best of everyone's knowledge. Also the reference to DES, AES and RSA together is very suspect. I quote: "Conventional cryptographic schemes based on DES, AES and RSA encode messages with public and private keys of short length." Huh???

There is no theoretical model for this, like one has for quantum computation (with all of the problems that exist there). Rather, it is more experimental in nature - and we know where that tends to end. Bottom line, this looks really bad and like a lot of other cases where people from other fields think that they can solve all of the world's hard cryptographic problems without knowing anything about cryptography.

There is exactly one unbreakable cipher and that is the gamma_pad using completely random numbers exactly once so the key is equal to the message length and every character is randomly ciphered.  Any other cipher could theoretically, with enough computing power and time, be broken.

The real question is how long do you need to keep your message safe from the 'enemy'.

During WW2 they used pencil and paper ciphers such as playfair that could be broken in a matter of hours, but used them to send things like attack now , so by the time they were broken the message had no value.


Shortest Path for Certificate Network I was reading an example from my textbook about verifying a certificate from a client using a certificate network. The example in the book is as follows:

  A issues a certificate to B.
      A issues a certificate to C.
      A issues a certificate to D.
      B issues a certificate to D.
      C issues a certificate to A.
      C issues a certificate to Alice.
      B issues a certificate to Bob.

  Bob wants to verify Alice's key. What is the path in the certificate network to do so?

I've drawn out the diagram but I don't see anyway such a verification possible as Bob's certificate provider is B, which has a one directional relationship with A, such that A "trusts" B, but not the other way around. Is there even a path that would solve the problem?

Quoting SEJPM's (now removed) comments:

For the convenience of any answerer, I've rendered the graph and answerers may use it (and any derivatives) at their will. If required I can also provide vector graphic versions of it.

In this case one could argue that A issued both bob's and alice's cert indirectly and thus either party seems to trust A to certify CAs and thus they trust each other's cert. (But this doesn't really sound convincing to me -> no answer)

Thanks to @SEJPM for adding the graph. With what you stated you were give, it would not be possible for Bob to verify Alice's certificate.


How to attack a general polyalphabetic cipher? I am able to decrypt Vigenere ciphertext using the index of coincidence and chi-squared test.

However, out of interest, how do you go about attacking ciphertext that was encrypted using a mixed alphabet shifted 26 times?

Also, what about a ciphertext that has been encrypted with 26 random alphabets? (so each line in the tableau is random)

Googling seems to bring up the basic Vigenere, but either an example or a link to a more detailed resource would be good.

A general polyalphabetical cipher is just a combination of several general monoalphabetical ciphers, each applied on every $n$-th letter of the message.

So the first thing is to find out what $n$ is (i.e. the key length). For this we can use the index of coincidence just like for Vigenere.

Then we can split the message into $n$ parts (columns), and try to break each of it as an individual monoalphabetic cipher, starting with frequency analysis. (We'll have to correlate information from the individual columns to do bigram frequency analysis, too.)

Also what about a ciphertext that has been encrypted with 26 random alphabets? so each line in the tableau is random.

As @user874 mentioned: It would be secure. This type of encryption essentially is what you would do when using the One Time Pad. As far as I know, it's actually the only perfectly secure cipher.


What happens to entropy after hashing? What happens to entropy after hashing?

Suppose you have a key with entropy $k$. Can entropy $k$ be increased by hashing the key?

The answer rather depends on what you mean by 'entropy'; if you mean 'Shannon Entropy', then no, a deterministic function cannot increase entropy.

For example, if the unhashed password has only 7 different possible values, then the hashed version of the password will also have (at most) 7 different possible values; you've made things look more obscure, but you haven't actually changed anything as far as entropy is concerned.

The standard definition of Shannon entropy is:

$H(X) = \sum -p_i\  log_2 p_i$

Where $p_i$ is the probability of the $i$th possible sample value.  That is, the Shannon entropy is defined solely in terms of probability distribution, and not how that probability distribution appears.

If we have a Hash function $SHA$ which doesn't have any collisions, then it has no effect on entropy; that is, $H(X) = H(SHA(X))$; that's because the probabilities involved in the probability distributions are precisely the same; if a specific password $x_i$ had a certain probability, then the hashed form of that password $SHA(x_i)$ will appear with that exact probability in the hashed distribution.

And, if the Hash function $SHA$ does have a collision, that is, if $SHA(x_i) = SHA(x_j)$, then (assuming both $x_i$ and $x_j$ have nonzero probability), then $SHA$ will actually reduce the entropy.  And, this is not a violation of collision resistance; collision resistance only states that it is hard to find such a collision, not that one does not exist.

This is easier to see in the extreme case; suppose we have two possible passwords ("Mary" and "Susan"), and both of those passwords have probability $0.5$; this means that the entropy of the password is 1 bit; an attacker can perform go through all possible values by checking on two different passwords.  If you hash the password, you may come up with two images (39e74b4e80ba656f773669ed60315a and 98e15403b2b1ea5022fc42b3490cc76e in hex) that look different, however there are still only two possible values, and so the effort an attacker would have in trying those two values in unchanged.

If the hash function is collision resistant, hashing does not change the entropy of the key. It will be $k$ after hashing.


Reusing a one-time pad? I have an embedded device. It produces larges files (200 MB).
I want the device to encrypt the file before writing to disk, so I gave them all a 16-byte random key.

How can I transform the large file with the small key, with the least amount of CPU?

If I XOR the data with the 16byte key, its almost good enough. But it will show repeated patterns from which you can distract the key (for example if the input is 16 zeroes), but can I make it better without sacrificing on performance?

Use AES-128, the instruction set in most CPU's (AES-NI) speeds up the encryption and does not put to much load on your CPU. I would use CBC but there might be better mode operations for encrypting files. Also don't forget to use a MAC.

Using a one time pad (OTP) is nice but what you're doing is not an OTP it's more a Vigenère cipher. If you were to use OTP the key should be as long as the file which requires you to store a (approximately) 200MB key.

Thanks @CodesInChaos I missed the "I have an embedded device", but than it's not a CPU it's a MCU (most likely) even than, AES is designed to be fast on any platform so i would still give it a try, just see how much it takes i think you'll be surprised as to it's efficiency.

Take a look at the list of validated AES implementations, see if there's something which resembles your embedded device.

In your case I'd recommend you to try TripleDES, maybe with a paired ARM MCU - it's cheap and fast enough... Try to take a look at STM chips, I used them before and I have a very good recommendations due to price/perfomance. Also you can try to implement DES physically if you have a hi-speed requirement in your device's spec list.


Estimated entropy per bit given P-value of a statistical test, and number of bits tested? Assume that a certain statistical RNG test (say from the NIST Statistical Test Suite, Dieharder, etc..) gives us a certain P-value (per the definition [*] used in NIST Special Publication 800-22), after testing $n$ bits of a RNG; say, $P=0.001$ (indicative of failure of the test with high confidence) and $n=2^{20}$.

Based on that information alone, what can we say about the (maximum) entropy per bit $H$ of the RNG tested, with some prescribed confidence? By this I mean, more precisely: the hypothesis that the tested generator has at least entropy rate $H$ can be rejected with fair confidence; perhaps, as associated with some P-value (possibly higher than the $P$ obtained in the test, say twice that).

How can we refine this, given P-values $P_i$ for that experiment repeated $k$ times?

Update: if that's not answerable as it, does it remain so when we add some very general hypothesis on the structure of the RNG under test, like: it outputs independent bits with some unknown constant bias? Refine this additional hypothesis as needed to obtain some relation between $P$, $n$ and $H$ !

Update: I do realize that if any statistical test RNG pass, that gives no insurance at all about the entropy per bit of the RNG tested; and that if it fails with values as in my numerical example, any hint that it may give in term of entropy per bit will be that it is at most $H$, with that $H$ dangerously close to 1, thus not very telling (even with the now-reduced P-value).

[*] My understanding is that the correct definition of the P-value used for statistical RNG test is that the statistical test promises that for any $\alpha$ with $0\le\alpha\le 1$, it outputs a P-value at most $\alpha$ with odds at most $\alpha$ when applied to a perfect TRNG.

Further, I believe only the second sentence is right in this quote of NIST SP 800-22 page 1-4

  For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%. For a P-value < 0.001, a sequence would be considered to be nonrandom with a confidence of 99.9%.

Correct me if necessary!

Firstly, the way (if at all) the "$P$-value" depends on $H$ depends (of course) on the statistical test that is being used. For each test, the result will be different and I cannot really give a meaningful general discussion here because different tests consider completely different aspects of the stochastic process of output bits.

In general, indeed, the $P$-value doesn't have to depend on $H$.
Originally I (probably incorrectly) thought you were referring only to a particular test (the monobit frequency test), which is what my comment was referring to.
I'll use this particular test in my answer to illustrate that the $P$-value can depend on $H$ and hopefully you'll be able to generalize my approach to other tests that are of interest to you. The analysis will be the same for many tests, but it will often be impossible to get any closed-form expressions relating the $P$-value and $H$.

Before I start with the analysis of the monobit frequency test, I'll also answer your question about the truth of the sentence

  For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%.

A $P$ value larger than 0.001 means that we cannot reject the hypothesis that the sequence is random at a significance level of 0.001. In this sense the sentence is imprecise: it is not because our test would have produced our observation with high probability that the observation was produced by a TRNG. At all times one should remember that the formula for computing the $P$-value is derived under the assumption that the hypothesis is true.

Analysis of the monobit frequency test

I'll now discuss the monobit frequency test, which is defined in NIST SP 800-22 (section 2.1). My notation is a little different sometimes, but I think it should be clear enough (if not, please comment).

In the most general sense, even this analysis would be difficult: at most one can say that the probability distribution of the $P$-value depends on the entropy $H$, but you should probably forget about getting a simple relation (formula of some kind) in the general case.

The following part of your question (applied to the monobit frequency test) has a reasonably "nice" answer though:

  If that's not answerable as it, does it remain so when we add
  some very general hypothesis on the structure of the RNG under test,
  like: it outputs independent bits with some unknown constant bias?
  Refine this additional hypothesis as needed to obtain some relation
  between $P$, $n$ and $H$!

So we've already made the assumption of working with a particular statistical test, because we can't answer the question otherwise. Now I'll make the following assumptions about the RNG:

There is no dependence whatsoever between the output bits of the random number generator.
The RNG is outputs a $1$ with a fixed probability $q$ and a zero with probability $1-q$. To get a a nice formula, I'll assume $q = 1/2 + \epsilon$ with $\epsilon$ sufficiently small such that $\epsilon^4 \approx 0$. I'll refer to $\epsilon$ as the bias.
$n$ is sufficiently large, but this assumption is implicit in the test anyway.

What I will show is that, under these assumptions, the probability distribution of $P_n$ (this is just $P$ for a specific value of $n$) depends on the entropy $H$. Note that I'm going to use $P_n$ as a random variable and $p_n$ for an instantiation of this test statistic. Once the distribution of $P_n$ is known, we can answer the following question:

  What is the probability that the source entropy is $H$ given that the observed value of the $P$-statistic is $p_n$?

To obtain an answer to this question, we need to take the following steps

Write the bias $\epsilon$ in terms of the entropy $H$.
Compute the probability distribution of the test statistic for the biased RNG.
Compute the probability distribution of the $P$-value for the biased RNG.

Entropy and bias

The entropy $H$ of one bit of the RNG is given by

$$
H
= q \log_2\left(\frac{1}{q}\right) + (1-q)\log_2\left(\frac{1}{1 - q}\right)
= 1 - \frac{2\epsilon^2}{\log 2} + \mathcal{O}(\epsilon^4),
$$
where $\log$ is the natural logarithm.
Hence, we have approximately:

$$\epsilon \approx \pm\sqrt{\frac{\log 2}{2}(1 - H)}.$$

It shouldn't be surprising that there are two biases corresponding to the same entropy. For convenience, I'll use the positive value in the remainder of this answer. This means I assume that it is known that the RNG is positively biased.

Test-statistic

Let's call our sequence of output bits $X_i$. We're looking for the distribution of the following sum:

$$S_n = \sum_{i = 1}^n (-1) ^ {X_i} = 2\left[\sum_{i = 1}^n X_i\right] - n$$

Since the $X_i$ are assumed to be i.i.d. we have, asymptotically as $n \to \infty$:

$$S_n \sim \mathcal{N}\left(\epsilon \, n, 4p(1 - p) \, n\right).$$

Both the mean and the variance can then be rewritten in terms of the entropy $H$ (recall that for the mean, there are actually two possibilities). To express the variance in terms of $H$, note that

$$p(1 - p) = 1/4 - \epsilon^2 \approx 1/4 - \frac{\log 2}{2} (1 - H).$$

$P$-value

The $P_n$-value for our test can be computed as

$$P_n = 2\Phi\left(\frac{-S_n}{\sqrt{n}}\right).$$

So we can compute the probability that $P_n \le p_n$ for some value $p_n$:

$$
\Pr[P_n \le p_n]
= \Pr\left[2\Phi\left(\frac{-S_n}{\sqrt{n}}\right) \le p_n\right]
= \Pr\left[S_n \ge -\sqrt{n}\Phi^{-1}(p_n/2)\right].
$$

Now we can use the distribution of $S_n$ which we derived earlier:

$$\Pr[S_n \le s_n] = \Phi\left(\frac{s_n/\sqrt{n} - \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H)\log 2}}\right).$$

So we get

$$
\Pr[P_n \le p_n]
= \Phi\left(\frac{\Phi^{-1}(p_n/2) + \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H) \log 2}}\right)
$$

(in the somewhat unlikely case that my calculations contain no errors, I'll check them later).

Note that as $n \to \infty$, the above probability goes to $1$ (for $H \neq 1$) so given enough sample bits we'll eventually conclude that the sequence isn't random.
So that should also answer your question

  How can we refine this, given $P$-values $P_i$ for that experiment repeated
  $k$ times?

(at least in this specific case)

Nothing.
Unless you have a bad RNG, your 1 million bits will in all likelihood (99.999999999%) have a entropy of virtually 1 bit /bit. This is the ent output for 1GB of good random data:-

Entropy = 1.000000 bits per bit

Similarly, this is for a source with exactly 7 bits /byte of entropy.  The p value = 0.

Entropy = 7.000000 bits per byte.
Chi square distribution for 1000000000 samples is 1000000238.08, and randomly would exceed this value less than 0.01 percent of the times.

This doesn't really tell you  anything useful.  The entropy calculation is too lossy to be useful.  The min-entropy will be a bit lower.  You'll just be left with a few decimal places of difference, perhaps.  You'd be splitting very thin hairs.
The two following random walks are from a good true random number generator.  Clearly the p scores for each will be different.  The first might get p << 0.05.  The p score is a group operation and is only valid for that block.  So the p score will vastly vary over the whole data.  You might then amalgamate all the p scores together with a KS test, but then you're averaging an average and so on.

Further I don't think that anyone has studied how many ways you can park a car in a car park with that kind of focus.  This test is in Diehard and only works due to computer simulation of the expected results.  There may not be any simple linear relationship between car positions and entropy.  It isn't a simple chi square comparison of byte values, but one of actual parked cars which have little direct relation to a p value.
Some of the other tests will be similar with mathematical simulation so the p scores relationships will be dependant on the type of test.  There probably isn't the academic imperative to study this much as I'm not sure what the benefit would be.
The monobit test shows this futility.  The sequence "10101010..." will be identified as a perfect source of entropy according to the monobit test.  Entropy is 1 bit /bit resulting in a p of 0.5.  A compression test will reduce this sequence to effectively zero length however, giving a p ≈ 0 or 1.  So we'd have:-
Monobit.  H = 1, p = 0.5 (optimal pass)
Compression. H ≈ 0, p ≈ 0 or 1 (absolute failure)
And this would be for the same block of data, so what can be inferred as one test directly contradicts the other to the greatest  possible degree?  Nothing.
The output function of RC4 (my favourite PRNG) passes all general statistical randomness tests averaging a H ≈ 1 bit /bit.  Yet specialised distinguishers can spot it's long run output from a random sequence to the extent that it is not recommended for new implementations.  So again nothing is learnt from a rigorous analysis of any single randomness test type and it's corresponding p value.


How can I send a secure public message using ECC? I want to know how to send a secure message protected with elliptic curve private and public keys.

In this case, the private key will be included in the site code and anyone can read it.

No, the private key is not in the "site" code, it is not send. It is just used to authenticate the TLS session, by placing a signature that can be verified with the public key in the X.509 certificate. This certificate has been exchanged before in the handshake and it has been verified & validated in the browser. The private key must be kept private, as the name implies.

  How can I send a secret message encoded with a key (key1) and only able to be decoded with another secret key (key2), which I only know it, (using ECDSA).

The ECDSA encryption method cannot be used to encrypt messages to keep them confidential. But it can authenticate the handshake. This handshake establishes the session keys, commonly by performing (EC)DH key agreement using two temporary (ephemeral) key pairs generated both by the client and server. These symmetric session keys can then be used to protect the messages.

If you want to perform encryption with Elliptic Curves then you should have a look at the Elliptic Curve Integrated Encryption Scheme or ECIES.

Minimal description of ECIES

For ECIES the sender generates an message specific EC key pair.

The sender then performs key agreement with the generated private key and the (trusted) public key of the receiver. The sender then uses the resulting key material for normal symmetric encryption. The message specific private key of the sender can be discarded after the symmetric key has been derived; it is just needed to calculate the symmetric key once.

The established symmetric key can be used with any block cipher mode of operation - or indeed with a stream cipher to create the ciphertext. It would of course be a good idea to use authenticated encryption to do this. The message specific public key and ciphertext can be combined and send to the receiver.

The receiver then performs his own key agreement with the receivers static private key and the senders message specific public key. This should derive the same symmetric key, which can finally be used to decrypt the ciphertext.

if we have a string message , and want to send this message using secure elliptic curve method (ECIES) , we can do this:

encode our string message to a number (msg) , it can be any big unlimited number

note: suppose G.xy means that G is a point not a number

Fixed public variables: (can use it many times and still secure)

Choose a private-key k (k is secret Number, receiver only know it)
Find any random Generator point G.xy (G.xy is public, everyone can know it)
Calculate public-key point K.xy = k * G.xy (K.xy is public, everyone can know it)

Sender has to do this:

Find any temporary random number r (used only once)
Calculate point P1.xy = r * G.xy
Calculate point P2.xy = r * K.xy
Calculate value P2msg = P2.x + msg (normal add, not curve add)
Send values P1.x and P2msg to the receiver

Receiver has to do this:

From P1.x calc P1.y (no matter if P1.y is + or -)
Now We Have P1.xy point and P2msg number
Calculate the trick point P2.xy = k * P1.xy , Why?
Because: k * (P1.xy) = k * (r * G.xy) = k * G.xy * r = K.xy * r = r * K.xy = P2.xy
Calculate number msg = P2msg - P2.x (normal sub not curve sub)

now we know the msg number, then decode it to the original string message


How to use "mod" related words in technical paper？ Modular reduction is a widely used arithmetic operation. I found many "mod" related words such as

modulo
modulus
modular

Can anyone explains the difference among these words?  Please give examples or idioms.

A modular operation is an operation done modulo some modulus.

"modular" is an adjective: modular inverse, modular operation, modular reduction, ...
"modulo" is indeed the Latin ablative of modulus, and that makes it an adverb: I walk modulo $n$, just like I walk fast.
"modulus" is a noun: the number $n$ is the modulus that you would use in some system.

"The word modulo...is the Latin ablative of modulus " -- Wikipedia


Encrypting a JPG, where the output is a scrambled JPG Is there an algorithm or program that can take an image, be encrypted, still be opened by an image viewer, but is restored when decrypted?

Basically I want the ability to secure images but still have them seen as "image files".

I wrote several papers on such a topic. I called it end-to-display encryption. But it is more commonly called "pixel-domain encryption" There are several easy ways to do this. My way included adding a header with RSA encrypted AES Keys.

In essence, you take the picture, extract the pixels, XOR with the bitstream created through AES in Countermode, increase the counter with every iteration, convert that to pixels, save as PNG (important, not jpeg or any other lossy compression, you lose bits with that, and decryption needs every bit to work properly). Thats it. And the same way back.

But sorry, no tool available. But its easy to implement.

I may extend on the thing with the JPEG in the question. Encrypting JPEG in the pixel domain will not work properly. The compression is lossy, so you lose information. There are compression methods on JPG, but they are much more complex, because they work mostly on the DCT factors, not on the pixels itself. These can also be viewed as pictures. That said, its another application field, as i wanted to decrypt pixel streams in the HDMI cable, that would not have worked as intended, or only with much more complex systems.

This might come in handy :
https://github.com/AtheMathmo/ImageEncryptor

It uses AES in CCB mode so with a key of long enough bitlength, you should have a fairly secure encryption.


Energy consumption by mobile or sensor node when executing xor / encryption / decryption I try to estimate the energy consumption by a sensor node when executing an authentication algorithm witch contains operations (hashing, XOR, Encryption / decryption by public/private key, addition,...).

The algorithm is named MDA (Message Digest Based Authentication). It contains:

(SN:sensor node; CH: cluster head; Th: hash operation ; Tx: transmit;
 Touex: XOR; Trec: reception; Tenc: encryption; Tdec: decryption)
**-Registration Phase :**
*SN-->CH:
2Th+Tx+Touex
*CH-->SN:
Trec+Touex+3Th+Tenc+Tx
**- Authentication Phase :**
*SN-->Ch
Th+2Tenc+Tx
*CH-->SN
Trec+Touex+2Tdec+Th
**- Numeric Certif**
*CH-->SN
Th+Tenc+Tx
*SN:
Trec+Tdec

So I ask if there are measurements that I can use to calculate energy.

There's a degree of electronics twiddling necessary for this.  You start with:-

A stiff power supply passing through a shunt resistor is typically used, which is then monitored with a storage oscilloscope. A low resistance is necessary, say 0.1 Ohms, but that really depends on the operating point consumption of your sensor device. You can't have the power supply dipping below operational thresholds as that will nullify the experiment.  Control the device to perform your required operations, and you'll read a voltage off the scope.  Then simply $consumption = \frac{voltage}{resistance}$.

This is called power analysis, and Wiki has an entry level article. You'll see from the graphic on the RHS that the power signature is not really as simple as I implied.  That's where a lot of statistics and probability matching will become necessary.  Some don't even bother with power consumption (amps) calculations and go with purely graphical approaches.  A wibbly waveform might indicate a correct key, and a wobbly waveform might indicate a bad key. This part is entirely characteristic of the individual device under test. And how you intend to exactly distinguish various cryptographic operations within the sensors.

Also one of the challenges will be in managing to grab and isolate the power consumption at the point of cryptographic operation, rather than simply running the status LEDs. You may need additional wiring between the control inputs and the oscilloscope's trigger input.

But it's a start...


What is the point at infinity on secp256k1 and how to calculate it? I hear that there should be a point at infinity on secp256k1. I wounder how to calculate it and what does it even mean. I tried to calculate it as $P_{inf}=P+(-P)$ but this gives different results for different P. Are there more than one point at infinity?

Geometrically thinking on an elliptic curve, adding two points that are symmetric against x-axis, should not be feasible because any vertical line on x-y plane will only intersect the curve at TWO points not THREE.

Point at Infinity
Yes, there is a point at infinity $O$ (or denoted as $\infty$) on Elliptic Curves (EC) as the identity element of the Elliptic curve group. Let the EC be given in Weierstrass equation;
$$y^2 = x^3 +a x + b$$
$O$,  the point at infinity can have different values according to the underlying coordinate system;
Coordinate Systems
For an elliptic curve over $\mathbb{F}_p$;

In Homogeneous Coordinates (also known as Projective Coordinate), the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z},\frac{y}{z})$. The point at infinity  is $(0:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$
In Jacobian Coordinate the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z^2},\frac{y}{z^3})$. The point at infinity  is $(1:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$

Now, what is $O$ in affine coordinates? Try to convert $O$ back into an affine coordinate! Well, we cannot represent it! See this answer Thus, we simply say it is $O$. But, magically, it can be encoded in implementations.
The Group Law
The points on an elliptic curve form an additive group with an identity $O$. For geometrical meaning please see the below image from Wikipedia Elliptic Curves The group law.

The Group Law on Affine Coordinates
Arithmetically can define the addition rules in affine coordinates. These are derived from the line intersection and tangent equations. The formulas are;
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

$P+O=O+P=P$
If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align}
x_3 = & \lambda^2 -x_1 - x_2  \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1},  & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1},  & \text{if $P = Q$} \\[2ex]
\end{cases}$$
The Group Law on projective Coordinates
Let $P_i = (x_i : y_i : z_i ), i = 1, 2$, be points on the elliptic curve $$y^2 z = x^3 + Axz^2 + Bz^3.$$ Then
$$(x_1 : y_1 : z_1 ) + (x_2 : y_2 : z_2 ) = (x_3 : y_3 : z_3 ).$$ The formulas are;

$P_1 \neq \pm P_2$

$u = y_2 z_1 − y_1 z_2,$
$v = x_2 z_1 − x_1 z_2,$
$w = u^2 z_1 z_2 − v^3 − 2v^2 x_1 z_2,$ then

$$x_3 = vw, \quad y_3 = u(v^2 x_1 z_2 − w) − v^3 y_1z_2, \quad z_3 = v^3 z_1 z_2$$

$P_1 = P_2$

$t = a z_1^2 + 3x_1^2,$
$u = y_1 z_1,$
$v = u x_1 y_1,$
$w = t^2 − 8 v,$

$$x_3 = 2uw, \quad y_3 = t(4v − w) − 8y_1^2 u^2 , \quad z_3 = 8 u^3.$$
For Jacobian Coordinate operations see this link.

For the secp256k1 curve, there is a point of infinity which is N the total points for this curve. To calculate use scalar multiplication  of N and the base generator point for the curve. Another way is to go 2coin.org, go to the private key hex tab, enter the number 1 for the private key press enter. Then subtract  by pressing -1  you  will be at infinity,  press one more time, you are at N-1.


Is a continuous stream of encrypted data embedded in garbage more or less secure than only encrypting the data? Consider a communication channel that needs to be secure (Encryption can not use full "volume" encryption, since future messages are not known). Would it be better to

only transmit encrypted messages and remain silent the rest of the time (therefore letting eavesdroppers know when a message is passed),
or sending encrypted pseudo-random data (or almost-meaningful garbage messages) during the remaining time - yielding a continuously encrypted stream which on the one hand hides the information of message transmission times, but otherwise adds the risk of a Known-plaintext attack should the garbage-generator (or the way separating actual message) be predicted.

Does the answer also depend on whether the messages shall be secure "forever" or if it is sufficient to maintain secrecy for a limited amount of time?

It depends on what your requirements are. In general, it is accepted that an observer knows when meaningful data is exchanged - even if he can't read it - because, well, we simply don't care. But in some cases this may be unacceptable, such as in p2p protocols where anonymity is very desirable and a fuzzy network can add a decent amount of secrecy.

On the other hand, continuously streaming is quite heavyweight, as it is in general not possible to keep streaming indefinitely (and intercepting all the garbage data and interpreting it as meaningless probably isn't free either, although that depends on your transmission protocol).

  or sending encrypted pseudo-random data

Huh? Why would you encrypt pseudorandom data? This is actually a bad idea - by doing that and encrypting your pseudorandom stream with the same key, you will have tainted all the garbage data with your key material - the same key used to encrypt your precious ciphertext - thereby giving the attacker orders of magnitude more stuff to work with. If the underlying pseudorandom data that you originally encrypted is broken, boom, you just gave your opponent lots of plaintext/ciphertext pairs, and your key (and therefore, your ciphertext) is now potentially compromised.

No, just send pseudorandom data that's independent of all other information you might rely on, so just grab a few hundred bits of entropy and run some cipher in CTR mode or something to produce a nice pseudorandom bitstream - this way, even if this part of your scheme is broken, your ciphertext remains safe (even if the attacker now knows its size and roughly when it was sent).

  but otherwise adds the risk of a Known-plaintext attack should the
  garbage-generator (or the way separating actual message) be predicted.

How so? If your cryptography is sound, and the garbage data does not leak any information about the plaintext or any key material (which it shouldn't, since it's just random bits), the two methods should provide equally optimal privacy. Even if an attacker somehow managed to distinguish the relevant ciphertext, he still wouldn't be able to decrypt it.

  Does the answer also depend on whether the messages shall be secure
  "forever" or if it is sufficient to maintain secrecy for a limited
  amount of time?

Again, it depends on your requirements. There is no "one size fits all" cryptography, and every application needs its own version of it, that's why there are so many different protocols and schemes around. You need to figure out yours and implement it.

So basically, define your use of the word "secure" in your first sentence. Secure against what, and how secure should it be (should it provide only privacy? privacy and anonymity? perhaps integrity too, what about authenticity? etc...)

No, sending a constant stream of garbage does nothing to improve security. A basic principle of secure system design is Kerckhoff's principle: essentially, that the enemy knows the system. An adversary that knows the system will know when you send a message, so you gain nothing from all the junk data before and after.


Radioactive Decay, Gaussian or Uniform? I'm trying to understand the nature of true randomness. I'm building an RNG using a radioactive source. Basically, I'm measuring the time between consecutive decays which in theory should be unpredictable. The distribution of these time measurements shows a Gaussian-like distribution as I predicted. Now my understanding of true randomness requires a uniform distribution of variables, which is all variables are equally likely. How can I transform a Gaussian Distribution to uniform distribution and is it really necessary to have uniformly distributed random bits to have a good generator?

You can just follow the instructions on HotBits, which is exactly what you're trying to build. It's been running for years and is the only radioactive TRNG on the internet. It goes into great depth regarding underlying nuclear physics, sample distributions and extractor mechanism.
Although not really within the realms of strict cryptography, there is also a good counting analysis here from Caltech. In a nutshell, at low count rates the click rate follows a Poisson distribution. But as the mean click rate $(\mu$) increases, it morphs into a nice symmetrical Gaussian shape which is typical behaviour of Poisson if $\mu > \approx 20$.
If you can get a good tube and a decent/safe source, it'll be pretty simple if you follow the instructions.  Don't worry about the tick distribution. Simply detect the ticks and follow the de-biasing procedure in the sections featuring this:-

It's a reversing von Neumann extractor. It's written up so I won't repeat the details. If tube dead times and saturation levels are met (so that there is no autocorrelation), you'll get uniformly distributed random bits popping out of the de-biasing algorithm. So that we can see HotBits' quality, I downloaded their 91 Mbit data set and ran ent over it:-
Entropy = 1.000000 bits per bit.

Optimum compression would reduce the size
of this 91750400 bit file by 0 percent.

Chi square distribution for 91750400 samples is 0.05, and randomly
would exceed this value 81.93 percent of the times.

Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141486168 (error 0.00 percent).
Serial correlation coefficient is -0.000773 (totally uncorrelated = 0.0).

They have other more stringent testing on their site, but it's a clean pass at this level. Chi square also answers your "is it really necessary to have uniformly distributed random bits to have good generator?" mini question. Yes, they do have to be uniformly random for cryptographic use.
So do what HotBits does.

Please note this though:-

the increased sensitivity of the RM-80 and its immunity from saturation increased the rate of HotBits generation from about 30 bytes per second to more than 100.

It's not fast. And there's all that high voltage stuff.

Use a Zenner diode as noise generator, take sample of the noise voltage on the diode (through a capacitor), amplify it and measure the voltage with a ADC. After this process, extract the square root of this value and keep only the mantisa (numeric part after decimal point). It should deliver absolute true random numbers.


why can't use only one way function to construct a PRG, and don't use the hard core predicate? The one-way function can expose some of the input and stay one-way, but still, that doesn't give the input.

As I read, we can't just construct a PRG from a OWF, but we need to use the hard core predicate of the OWF. Why is that?
Assuming $|f(s)| > |s|$, why is constructing a PRG in the following way wrong? $G(s) = f(s)$
Suppose $f$ is a permutation function. If $f$ gets a random $x$, then is $f(x)$ also random?

The first one is really simple, you already said it yourself:

  as i read , we can't just construct a PRG from just OWF , but we need to use the hard core predicate of the OWF, why is that?

I guess you're familiar with the formal statements, but informally speaking we have:

A function $f:\{0,1\}^* \rightarrow \{0,1\}^*$ is one-way, if we give the adversary $y = f(x)$ and the length $|x|$, and he has a negligible probability of finding $x'$, s.t. $f(x') = y$.
a PRG is a function $g:\{0,1\}^n \rightarrow \{0,1\}^m$, where the output is indisinguishable from $U^m$, denoting the uniform distribution over $m$ bits, and $m > n$

Now consider the following construction: $f'(x) = f(x)|1$, with $f$ being a OWF. Just concatenating a $1$ doesn't change much w.r.t. the security property of an OWF. And in fact, any adversary able to break $f(x)$ can easily be turned into an adversary for $f'(x)$ and vice versa. So $f'$ is a OWF iff $f$ is a OWF.

But it is quite obvious, that $f'$ is not a PRG, because the output of $f'$ can easily be distinguished from a uniform distribution, by just looking at the lowest ordered bit (always $1$ vs uniform).

But as you stated yourself: With a hardcore predicate, you can get a length extension. Maybe these lecture notes make it more clear how to achieve that (and why it's necessary). Informally speaking: A OWF does not need to be impossible to invert for all parts of its output - while a PRG needs to be indistinguishable from randomness over all its output.

  why constructing prg in the following way is wrong G(s) = f(s) assuming |f(s)| > |s|?

If we specify $f(x):\{0,1\}^n \rightarrow \{0,1\}^n$ a length preserving OWF, and use the construction above, we get $f':\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, which is also a OWF. This fulfills the length criteria of a PRG, but it is distinguishable. Being a OWF is not sufficient to be a PRG.

  f is a permutation function , if f gets a random x then is f(x) also random?

A permutation is a bijection from a set, e.g. $\{0,1\}^n$ into itself. This means, there are no collisions and every element has a single preimage. Thus, if we consider an input drawn uniformly at random from $\{0,1\}^n$, then the output is also uniformly distributed over $\{0,1\}^n$ - because the permutation has a 1-to-1 relationship between inputs and outputs. But that is also fullfilled for example by $p(x) = x + 1 \mod n$ over $\mathbb{Z}_n$, and I don't think that's what you meant. But this is entirely unrelated to the concept of one-way functions and PRGs.

the OWF can expose some of the input and stay OWF

Not really, no. Parts of the input in the output lead to a non-negligible change of guessing the whole input.

  as i read , we can't just construct a PRG from just OWF , but we need
  to use the hard core predicate of the OWF, why is that?

I guess you're referring to G: n->n+1, G(x) = f(x)b(x) , ie. G gets a true random value with n bit, calculates OWF f(x) which has n bit too, and adds one bit b(x) with b being a HPC of f.

If we remove b(x), a bit is missing, so G transforms a true random value (x) with n bit to another value with n bit. Meaning, G is no pseudo-random generator, it generates nothing and is not better than using x directly.

If we modify f to output more bit than x has, it's not really pseudo-random anymore. Extreme example: x has 1 bit, ie. a true random stream of 0/1, and f(x) has 100 bit. The problem is, whatever 100bit-values f(0) and f(1) are, they are always the same two values. G can now generate endless pseudorandom occurances of two fixed 100bit values, instead of an endless stream of 200 pseudorandom single bits.

And how does a HCP as added bit helps?
b(x) is easy to calculate from x, that's trivial.
If b were not to be a HPC, it's also easy to calculate from f(x), and that means it doesn't add something (pseudo)random to the output. The output should contain something looking random, not something that can be calculated from previous output bits.
So, b is a HCP, meaning it can be calculated form x (of course), but not from f(x).

  why constructing prg in the following way is wrong G(s) = f(s)
  assuming |f(s)| > |s|?

See above.


How is the key shared in symmetric key cryptography? Symmetric key cryptography is an encryption system in which the sender and receiver of a message share a single, common key that is used to encrypt and decrypt the message.

Is the key public or it is secret? How can the sender and the receiver both know the key?

Handing keys, in general, is known as key management.

Symmetric keys should be kept secret from other parties than the participants in the scheme. The term "secret key" is often used as a synonym for the symmetric key. The private keys for asymmetric schemes are not shared, but are of course also kept secret, as privacy implies secrecy.

The establishment of symmetric keys between parties can be performed in several ways:

(Authenticated) Key Agreement (KA)
Sending of an (authenticated) encrypted key, also known as key wrapping
Derivation from a base key using a Key Derivation Function (KDF), using other data as input, for instance, a unique number. If the derivation is performed so the resulting keys can be used in different schemes it is often called key diversification. If keys are derived in an iteration we talk about a key ratchet.
Any kind of "out of band" procedure (after random key generation),

by a previous telephone call
sending a letter
meeting in a pub (handing over a USB stick or other data carrier)

Creating a key from key parts held by different persons (key sharing schemes)
Quantum key distribution

There are other methods for establishing symmetric keys, but these are some of the most commonly used ones. The security of these schemes depends of course on the implementation.

An increasingly common way is to send a key directly via  photons in a general technique called quantum key distribution. This is of course an entirely hardware solution. The two main protocols are E91, whereby the candidate key is initiated midpoint utilising quantum entanglement:-

and the slightly older protocol of  polarisation encoding from one end of the communication link, called BB84:-

Both techniques leverage either spooky action or the observer effect to be (theoretically) 100% secure.  Even in 2011, the sifted key exchange rate was 128 kbps (1000 AES-128 keys per second).   This has now been built upon, but even then, the transfer rate was sufficient to allow encryption via distributed one time pads (the holy grail).

Quantum mechanics - "That means we don't really understand it."
- Richard Feynman


One time pad key exchange If two parties want to communicate with securely using OTP , how is the key ( that is lengthy as plain text) shared with other party for decryption ?

That's a well-known disadvantage of using OTP. Like in the ancient times, you could e.g. employ a trusted courier for that transfer.

One way of sharing a OTP is to draw a random sequence (a huge list of randomly chosen characters or btis) in advance and to disclose it beforehand to the other party (physical meeting). The obvious disadvantage is the need to keep secret a big amount of information.

Another way is to share a short secret (key) in advance (e.g. during a physical meeting). This is much more practical in the sense that the information to be kept secret is much shorter. In order to share a random sequence as long a the plaintext to be transmitted, a cryptographic primitive is then used such as a stream cipher (or, e.g. a block cipher or hash function running in counter mode). An IV (a public short string) is used to derive a random sequence anew for each plaintext. The drawback compared to sharing a long random sequence before hand is that the random sequences thus genereated are "only" pseudo-random (i.e. in the best case scenario, they appear random to a computationally bounded adversary provided some hard computational assumption holds, such as the hardness of computing quadratic residues for instance; sometimes, the security is even more ad-hoc, like when using hash functions in counter mode).

Finally, an additional way is provided by quantum key distribution (Bennett and Brassard, 1984). The key is distributed through a quantum channel and it is assumed that tampering will be detected due to the physical properties of the channel. The advantage is that the whole system can be made to rely on inconditionally secure primitives only. The disadvantage is that the rate of random sequence generation is pretty low nowadays and do not compete at all with the previous solution. Also, it is highly susceptible to denial of service attacks.


Components of Cryptanalysis What are different components of Cryptanalysis. I can't seem to find them. Are they the same as Cryptosystem or is there any difference.

Disclaimer: this answer is opinion based.

TL;DR: The question does not really make sense. Because you cannot put things into boxes like that.

The best way to make you understand it is to make an analogy. Cryptosystem is to Chess what Cryptanalysis is to Chess Games Strategy/Reviewing.

As you define a Cryptosystem with the following components:

Plaintext
Encryption Algorithm
Ciphertext
Decryption Algorithm
Encryption Key
Decryption Key

You can define Chess with:

a 8x8 board
16 white pieces (King, Queen, 2 Rooks, 2 Bishops, 2 Knights, 8 pawns)
16 black pieces idem.
a set of rules

And you can see the review and strategy as:

Openings moves and tactics (Alekhine's Defence, Caro-Kann Defence, King's Gambit...),
Midgames moves and tactics,
Endgames  and tactics,
Mat in 3 (and more),
pinning,
forks,
discovered attacks
etc.

Cryptanalysis will be the art to look at a cryptosystem, find it's weaknesses and how to improve it:

differential/linear/integral Cryptanalysis,
boomerang attacks, related key attacks, impossible differentials,
birthday bounds,
Meat-in-the-middle attack,
Game-based proofs,
Shor's/Simon's/Grover's algorithm
etc

A cryptanalysis is somewhat reverse process of cryptography like in cryptography we try to hide the information and in the cryptanalysis, we test weakness of a cryptosystem.
so components of cryptanalysis can be said

Passive cryptanalysis: where only observation is done of the cryptosystem to find the weakness.

Active cryptanalysis: where a mathematical approach is used to overcome (or to reduce) the difficulty to solve the crypto problem.


Consequences of AES without any one of its operations Suppose AES-$128$. There are $4$ operations in AES's encryption, they are SubByte, Shift Row, MixColumns and AddRoundKey.

Question: If I remove one of the following opearations, what will happen to the AES?
SubByte, Shift Row, MixColumns

If Shift Row is removed, then attacker can treat input block ($128$ bits) as $4$ independent $32$ bits block. Hence, attacker can attack these $4$ blocks one by one to recover key.

If MixColumn is removed, then attacker can treat input block ($128$ bits) as $16$ independent $8$ bits block. Hence, attacker can attack these $16$ blocks separately.

If SubByte is removed, then the non-linearity of AES is gone. But I don't know how an attacker can attack the AES?

Can anyone give some hint?

As poncho notes in the comments above, viewing the input block as a 128-element vector over ${\rm GF}(2)$, the AES ShiftRows and MixColumns operations are both linear transformations, and AddRoundKey is just vector addition.

Both linear transformations and addition of a constant are kinds of affine transformations, and since the composition of any two affine transformations is itself an affine transformation, it follows that, if the non-affine SubBytes step is removed from AES, the whole cipher becomes affine.

In particular, every affine transformation can be represented in the form $c = Ap + k$, where $p$ is the plaintext input (a vector of 128 bits), $c$ is the corresponding ciphertext output, $k$ is a constant vector and $A$ is a 128 × 128 bit matrix.  Furthermore, the inverse of this transformation is then simply $p = A^{-1}(c - k)$, where $A^{-1}$ is the matrix inverse of $A$, and (for vectors over ${\rm GF}(2)$) both vector addition "$+$" and subtraction "$-$" simply mean bitwise XOR.

The constant $k$ obviously depends on the key, but the matrix $A$ actually does not — it is fully determined by the ShiftRows and MixColumns steps, neither of which are key-dependent.  Thus, you can precalculate it e.g. by implementing this affine AES variant yourself, leaving out the AddRoundKey step as well to make it linear, and using this to encrypt (or decrypt) all the 128 blocks with a single bit set to one and all other bits zero, which will directly give you the columns of $A$ (or of its inverse $A^{-1}$).

Once you've precalculated $A$, even just a single known plaintext/ciphertext block pair $(p,c)$ encrypted using the actual affine cipher will let you determine the key-dependent the additive constant $k = c - Ap$.  Knowing $A$ and $k$ will then let you encrypt (or decrypt, using $A^{-1}$) any arbitrary plaintext (or ciphertext) block.

Every block cipher is a proper mixture of substitution and permutation operations which these proper mixtures,in entire rounds unanimously gives the algorithm resistance against different crypt-analytic analysis.

In AES cipher, which it is arranged in SP structure, Round function is consist of substitution operation("Sub Byte") and permutation operation("Mix Column" , "Shift Row"). But we should consider that the Round function itself in One Round is not giving enough strength to the structure. In fact the right number of proper arrangement of Round functions make the structure resistance against cryptographic attacks.

Besides, "Sub Byte" in AES does not let the attacker to run the cipher in reverse,means able to  reach the Plain-text from reverse running the cipher from the cipher-text and get the keys(because Sboxes are resistance against Linear and Differential attack).

Moreover, other magic which gives stamina to the cipher is using  Galois Field(Finite Field) in its arithmetic. Finite fields are abstract algebra structures that used in this cipher and we can model them with polynomials. Whenever you want to encrypt a plain-text, this plain-text converts to GF(2^8) and then the arithmetic in round functions is done based on that. Even "Sub Byte" in AES, which is a SBox, is built based on this Abstract Algebra.
In conclusion, proper mixture of Linear elements ("Mix Column" , "Shift Row") and nonlinear element("Sub Bytes") together in 10 rounds alongside "Finite Fields in GF(2^8)" makes it strengthen.

If we want to explain GF(2^8) in simple:  a byte(8 bits) which every bit can have 0 or 1 in it. But when we want to do arithmetic on them like sum or multiplication, the arithmetic rules are different from our conventional way and are based on Galois Field arithmetic rules.


Is modern encryption needlessly complicated? RSA, DES, AES, etc., all use (relatively) complicated mathematics to encrypt some message with some key. For each of these methods, there have been several documented vulnerabilities found over the years. Some even believe that there is a vulnerability in AES known only to the NSA.

On the other hand, the one-time pad is not only ridiculously simple, but also has been shown to be impossible to crack (if used appropriately).

Say you have some message to be encrypted with length n. Simply generate a random string with length m where m is at least as large as n, and perform modular addition of the random string onto the message.

As long as the random string is generated with a high-enough-quality random number generator, and as long as the same one-time pad isn't reused, it should be impossible to crack.

If this is true, all we would need to perfect are fast, cryptographically secure deterministic random number generators. Use the key as a starting seed for the RNG and you have a powerful uncrackable encryption scheme which is simple to understand and implement.

Blum-Blum-Shub is a fast, cryptographically secure PRNG, and there are others too.

I have written a C++ program which uses two 2048-bit primes (which match the necessary criteria) for Blum-Blum-Shub and uses a password which the user enters - converted into a starting seed - to run byte-wise modular addition. The process is fast, deterministic, and if the literature I have read is correct then it should be very secure.

So why is so much time and effort invested in coming up with convoluted encryption cyphers when mathematics shows that the simplest is often the best?

The main difficulty with the one-time pad is that it requires pre-arrangement. In order for me to use a one-time pad to communicate with you, we must either have arranged ahead of time for a one-time pad that we will use (which must be as large as our communication will be), or else we must have some secure way of communicating that will allow us to agree on a one-time-pad for use.

If we have a secure channel to communicate so we can agree on a one-time-pad, then why bother? Let's just communicate through the secure channel.

If we don't have a secure channel, then we cannot engage in secret communication ex-nihilo, since we will not have a one-time-pad agreed on.

Now, if you are going to generate the one-time-pad via a pseudo-random number generator, how are you going to get that one-time pad to me? You must tell me your seed (so that I can generate the same pseudo-random sequence and I can decode the message), in which case we are back to the problem of how you tell me what your seed is without a secure channel to communicate with. So now we have two points of vulnerability: the channel we use to communicate so you can give me the seed; and the fact that a pseudo-random number generator is not truly a random number generator, and so may be susceptible to attack as well.

There is also the problem of distribution; to use one-time pads effectively, no pad can be used more than once. There were intercepts that the NSA had from back in the 50s; when the Soviets mistakenly used the same one-time-pads to encode some messages in the 80s, this was enough to break the encryption in both cases. That means that each message will need a new seed and a new password; so each time you want to communicate you need a new seed/key and a new password. It is just too easy to lose the information, or to re-use it by mistake and thus make the entire thing a wash.

One time pads are effective for pre-established channels of communication with low bandwidth; they are almost useless for initiating remote secret communication with someone you have never communicated with before, and they require a lot of bandwidth to use correctly.

You are right One Time Pad with Blum Blum Shub are the most secure proofed ciphers combine.
But you just forgot the main problem: Key Exchange problem and One Time Pad key should be used once, and here asymmetric (RSA;DH) ciphers with AES solve this problem.

But, again Key Exchange problem for one time pad is solved with quantum cryptography. Many companies such as IdQuatic, MagicQ had developed, real random generators devices (PCI) and routers that support quantum cryptography. The main limit for the moment of quantum cryptography is distance coverage (experiments has shown it is effective till 100 km). Lately have been made some experiments of quantum bit exchange on optic fibber showing good results....
Hope this short description helps.


Webcam random number generator I have a question about random number generators.

I have read from a real random number generator, based on a webcam ("randcam"). My problem is, that I do not really understand how the generation of the random numbers works. Has anyone heard of this principle before and can give some hints how it could be implemented? And how randomly is this method, I've read it should give real random numbers, but is this true? I've found an implementation in C++, but I did not really understand how this implementation works, I am not that familiar with C++.

A video camera can obtain entropy, but only at a fairly low rate and only if allowed to see "unusual" scenes… like someone making funny faces, unusual movements, etc. Of course, this only works in a room with no video bugs.

Theoretical explanations…

Depending on your knowledge-range, the following sources may be able to explain ways webcams can be used for random number generation:

Patent US 5732138 A — "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system."
Inventors: Robert G. Mende, Landon Curt Noll, Sanjeev Sisodiya
Original Assignee: Silicon Graphics, Inc., Filing date: 1996-01-29, Publication date: 1998-03-24
Random Numbers Generated from Audio and Video Sources
2013, I-Te Chen, Department of Healthcare Administration & Medical Informatics,  Taiwan
Random Number Generated from White Noise of Webcam
Jer-Min Tsai, I-Te Chen, Jengnan Tzeng
2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing
ISBN: 978-0-7695-3762-7

Getting more practical…

If the above is too theoretical for you and you want a more practical explanation of how it can be done, there's a cool "how-to" article at inventgeek.com that shows how to create an "alpha radiation visualizer" from scratch within an hour… using a webcam and a regular smoke-alarm device as radiation source.

EDIT

Sometimes I stumble upon a wave of disinformation wobbling through the internet (and I’m not talking about Crypto.SE in this case, which seems to have escaped this particular wave so far). Most of the time I manage to keep my mouth shut, but this is one of those rare occasions where I felt the urge to draw a clear line between amateur chit-chat and actual cryptographic security. After all, when creating your own “randomness” thingy, you do not want to step into the most obvious pitfalls… do you?

Always remember that it only takes a tiny glitch to make your “randomness” thingy as insecure as leaving your key stuck in your front-door.

For example: I repeatedly have to disagree with people telling the world it‘s OK to rely on JPEGs provided via their webcam software, which are auto-stored on their disks and later fetched to extract “randomness” from those images. Let’s be clear on something: when doing so you are actively ignoring several issues, both from a cryptographic as well as from an infosec point of view.

Time to dive into some stuff, just for the fun of providing some food for thought…

Trust

How trustworthy is that 3rd-party webcam software you are relying on?

Think about it for a second before we simply skip this rather tin-foil hatted question, assuming you absolutely trust your webcam software because (for example) you coded it yourself.

To further limit the scope of my edit, I’m also skipping the talk about the potential issues arising from storing those images to HDs, USB sticks, or whatever storage medium you might be using. Besides the fact that this would quickly wander off into InfoSec realms, only you can know if we can or should assume your disks and system to be safe from any 3rd party access at all times because (for example) you’re the best sysadmin known to humanity and never sleep anyway.
JPEG is not even close to raw signal data!

Do not just jump for the next image format available, unless you know what the specific image format (read: file format) actually contains, how that format may influence the security of your implementation, and how potential implications of individually chosen image/file formats can be secured.

If you don‘t plug into the webcam hardware directly, at least be smart enough to use as much raw signal data as you can get… and one thing is for sure: using JPEG is not the smartest choice. Remember that JPEGs (like most image formats) introduce a repeated and predictable data block (the image header), and lose some of the wanted entropy (due to the lossy data compression – among other things) while all that post-processing takes time. To lift related issues, you‘ld have to post-process the already software-processed “random data” which created the (to stay with the example) JPEGs. By now, your own logic should already be screaming at you that using raw image data extracted directly from your webcam hardware is the smarter, safer, and faster choice.

Personally, I’ld advise you to either use raw signal data (available via hardware modification), or to grab raw image data directly from your webcam (using appropriate software and/or drivers).
“Webcams only offer JPEG” and “Webcams don’t offer raw image data” are blunt lies!

Sooner or later, you will stumble upon some people that try to tell you it’s not possible to grab raw image data from webcams and that webcams only provide JPEG output. While I somewhat admire the boldness of people pushing out such balony into the digital voids, I honestly can’t help feeling the need to explicitly state that they are absolutely wrong.

What those people are forgetting (or actively ignore) is the fact that it‘s not the webcam itself, but the webcam software which produces those JPEG images from raw image date that software grabs from the webcam. Besides potential licensing restrictions related to individual hardware, there is no reason why you wouldn’t be able to do the same raw image data such webcam proggies use – without applying JPEG compression or other image processing.

For your convenience, here are some hints of software projects which are able to grab raw image data from webcams… just in case you ever feel like proving such claims wrong:

fswebcam (quote: RAW - Reads images straight from a device or file.)
AviRaw - read raw webcam AVIs (which is – among other things – used to look at the stars)
An Image Grabber for the Creative WebCam Go

Please feel motivated to do your own research. Search engines tend to spit out truckloads of alike software solutions and sourcecodes which practically enable you to grab the raw image data from various webcams and related systems.

From this point on, be confident that anyone claiming it can‘t be done is either not informed, or bluntly hiding his/her ignorance behind an easy to uncover lie. Don’t waste your time on such people – simply turn around, take a deep breath, and try to find someone smarter to talk to.
Always “Combine & Hash”

It doesn’t take a 3-letter agency sitting in a black-windowed van to ruin your “randomness”. In fact, even that old microwave oven your neighbour uses might be that ill-placed that it influences the noise which you hope to gain from your hardware. Badly shielded speakers also tend to do their badness. And 3rd-party wifi activity as well as mobile phones outside of your home also have a good chance to skew your noisy pattern. Shielding your webcam as well as the rest of your hardware might be an option, but to keep it short: one should always assume raw signal data can and will be messed with actively and/or passively… and it’s pretty unlikely you will be able to detect such influences ad-hoc, if at all.

Due to that, I heartly recomend to generally push the captured (raw) signal data – preferrably combined with additional random data from other sources – through a cryptographically secure hash. Sure, a cryptographically secure hash takes its time to be computed… but it‘s much better to invest time in a good hash than in some superfluous image format processing (and post-processing to lift related issues) as described above in #2.

Depending in your individual setup and scenario, a HMAC might be even more applicable as it can help protect you in some of the extremer “failing randomness” situations where a regular (cryptographically secure) hash might fail to protect you.

Or you could get a bit crazy like I did when I created something related as a hobby project a few years decade ago. I ended up feeding some randomness sources to AES in CTR mode, while pulling random IVs and keys from a hashed combination of other randomness sources… think: encrypting combined random sources with IVs and passwords generated from hashes of other combined random sources, where all random sources are absolutely independent of eachother. Most of you will surely agree that this setup was more of a “crypto-overkill”… still, it was able to blow “blindly trusting what webcam & co. provided” out of the water. To my defence: I was young and über-motivated… ever since, I’ve learned to create smarter things with less overhead. ;)

Cryptography is only as smart as you implement it.

It should be noted that hashing data (either via a hash or a hmac) surely won’t save you from breaking your neck in every potential scenario, but when you watch your steps by combining raw webcam data with other independent randomness sources, hashing the lot holds the potential to increases the chances of (cryptographic) survival of your home-made “randomness” thingy.

Nevertheless, things like “still images” hold the potential of providing not enough entropy. Which is one of the main reasons why you shouldn’t generally assume ”any pic is OK” and – whenever possible – mix randomness extracted from your webcam with other randomness providers (either hardware or software based). If you don’t know what other randomness source to use, here’s a hint: at the time of writing, all major operating systems provide their own way of extracting cryptographically secure data via software. If that’s news to you, RTFM.

/* Nota Bene: Since point #4 might inspire some cool Crypt.SE questions, I’ll leave it standing as unspecific as-is. */
To build a new car, you don’t have to reinvent the wheel.

Be sure not to get caught up in an “I‘ll create my own…” mantra just because you‘re fiddling with your own hardware. There are dozens of well-vetted solutions in the realms of cryptography that may be able to fit your individual setup, implementation, and/or needs – which practically means there might be no need for you to “create your own”. In case of doubt, click that “ASK” link and throw in your question with a short but on-point description of what you’re trying to achieve. There are ample experts around here at Crypto.SE who are able to answer near to any crypto-related question you might have. It’s always better to ask for help and infos, than to be sorry later on.

Yes absolutely.  I believe that web cams make excellent true random number generators, but.  The camera has to be operated within a visually managed environment.  This is necessary to determine and control entropy of the resultant images for quality control purposes.    The trick is not to rely on the scene the camera sees, but the image noise.  Only God himself can predict this noise, hence true entropy.  Consider this - all low light web cam images generated in the world are unique.

As mentioned, they can be slow.  A webcam's no beam spitter.  I estimate that you'll get 0.5Mb/s of true randomness from a VGA camera.  That's still orders of magnitude faster than /dev/random.  It's probably the simplest way to generate true entropy though.  Your subsequent issue will be randomness extraction.  This means converting the image noise to bytes ranging uniformly between 0 - and 255.  There are those that will tell you to shove it up a cryptographic function, which will work but is boring.  There are other ways.  The following shows proper web cam entropy, with a blown up and equalised view too.  You don't need to, indeed shouldn't, pull funny faces at the camera:-

An entropy generator based on this exact web cam principle is now on line here.  The three channel lines represent about ~11 bits of total entropy, based on a very very conservative measure.


Difference between Pseudorandom Function vs randomly chosen function I am currently going through a course in cryptography.
In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string.
However, I do not understand the pseudorandomness in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

  Since the notion of choosing a function at random is less familiar than the
  notion of choosing a string at random, it is worth spending a bit more time on
  this idea. From a mathematical point of view, we can consider the set $\operatorname{Func}n$
  of all functions mapping $n$-bit strings to $n$-bit strings; this set is finite (as we
  will see in a moment), and so randomly selecting a function mapping $n$-bit
  strings to $n$-bit strings corresponds exactly to choosing an element uniformly
  at random from this set.

  How large is the set $\operatorname{Func}n$? A function $f$ is exactly
  specified by its value on each point in its domain; in fact, we can view any
  function (over a finite domain) as a large look-up table that stores $f(x)$ in
  the row of the table labeled by $x$. For $f_n\in\operatorname{Func}n$, the look-up table for $f_n$
  has $2^n$ rows (one for each point of the domain $\{0,1\}^n$) and each row contains
  an $n$-bit string (since the range of $f_n$ is $\{0,1\}^n$). Any such table can thus be
  represented using exactly $n\cdot2^n$ bits.

  Moreover, the functions in $\operatorname{Func}n$ are
  in one-to-one correspondence with look-up tables of this form; meaning that
  they are in one-to-one correspondence
   with all strings of length $n\cdot2^n$.

  We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ .
  Viewing a function as a look-up table provides another useful way to think
  about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly
  at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely
  independent and uniformly distributed.

  Coming back to our discussion of pseudorandom functions, recall that we
  wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen
  uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen
  uniformly at random). Note that the former is chosen from a distribution over
  (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$
   functions in $\operatorname{Func}n$. Despite this, the "behavior" of these
  functions must look the same to any polynomial-time distinguisher.

Can anyone please explain me this concept in easier terms?

Random function -- function $F$, that is selected randomly from the set $Func$ of all possible functions (with given domain and range).

Pseudo-random function --- family $\{F_k\}$ of functions, that is indexed by the parameter $k$ (which serves as a number). It is pseudo-random, because if someone picks $k$ secretly and lets you interact with $F_k$, it should look like you are working with a random function, whereas in fact it is chosen from a much smaller set, not from the set of all possible functions.

Random function:
(Pseudo)randomly pick a function from the set of all possible functions mapping an input to
an output, where the input and output are the lengths/types you want.


For Diffie-Hellman key exchange method, what are examples of very poor a and b values? For Diffie-Hellman key exchange method, what are examples of very poor $a$ and $b$ values? Given that $g$ and $p$ values are both large prime number and the formula is

$$g^{a . b} \bmod p$$

In Diffie-Hellman key exchange, the values of the secret exponent like $a$ (or equivalently $b$) must be generated in a way such that from $g$, $p$, and $g^a\bmod p$ (which will get public), it can not be found $a'$ with $g^{a'}\equiv g^a\pmod p$, or equivalently $a'\equiv a\pmod q$ where $q$ is the order of $g$. This condition is necessary, because guessing $a'$ is as good as guessing $a$, and breaks the DH protocol.

This condition implies that some ways to generate $a$ are bad. In particular, any value of $a$ known or guessable by the adversary is bad, including small values of $a$.

As an illustration of the above, and that choosing $a$ randomly in a large set is not good enough, it would be bad to generate $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$: in this setup, DH could be attacked with algorithms requiring only $\sqrt{2^{80}}=2^{40}$ effort (including a simple variant of baby-step giant-step, now detailed in the last section).

Also, if it happened that the order $q_a$ of $g^a\bmod p$ was small (which is possible if the order $q$ of $g$ has small divisors), DH would be vulnerable; for example, to computing ${(g^a)}^j\bmod p$ for increasing values of $j$, allowing a guess of ${(g^a)}^b\bmod p$, as soon as $j\equiv b\bmod q_a$. Thus for maximum safety, $a$ should be such that the order $q_a$ of $g^a\bmod p$ is large. This explains why $q$ is often chosen to be a large prime: $0<a<q$ then insures $\gcd(a,q)=1$ and that $q_a$ is $q$ (thus large) without any explicit check.

Assume that the order of $g$ is a large prime $q$; perhaps $q=(p-1)/2$, or some other large prime dividing $p-1$, with $q>2^{2k}$ for $k$-bit security. It is then safe to generate $a$ uniformly randomly in range $[1\dots q[$. That criteria is used in the weakest form of the Diffie-Hellman assumption (thus the safest, and common).

It is demonstrably very nearly as safe to allow $a=0$, or/and generate $a$ uniformly randomly in range $[1\dots p[$ (which is also common and safe if the order of $g$ is $p-1$ with $(p-1)/2$ a large prime, rather than $g$ of prime order).

Another common method is generating $a$ as a string of at least $2k$ random bits; that's relying on a stronger form of the Diffie-Hellman assumption (thus less demonstrably safe, but still conjecturally safe).

Following (now gone) comments, here is how a choice of $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$ (where $q$ is the order of $g$) could be attacked, with $\sqrt{2^{80}}=2^{40}$ work (essentially that many pairs of modular multiplications modulo $p$, and searches in a huge table):

Giant steps: tabulate $g^a\cdot{(g^{-(2^{40})})}^i\bmod p$ for all $i$ with $0\le i<2^{40}$, requiring about $2^{40}$ modular multiplications and comparatively negligible extra work.
Baby steps: for $j$ increasing from $0$, compute $g^j\bmod p$ and search it in the previous table until it is found; that will happen precisely for $j=r_{80}\bmod 2^{40}$, and the match will be with the value tabulated for $i=\lfloor r_{80}/2^{40}\rfloor$ (the proof uses that $g^q\bmod p=1$); it thus requires at most $2^{40}$ modular multiplications and searches.
We thus know $r_{80}=i\cdot2^{40}+j$. This is enough to compute $g^{a\cdot b}\bmod p$ as ${(g^b)}^{r_{80}}\bmod p$ and break DH.

Techniques exist to considerably reduce the amount of memory needed.

Note: $r_{256}$ is there as an (admittedly artificial) way to make the set of allowable $a$ large, but brings no actual security; the constant 256 is entirely arbitrary.

I'm completely guessing here, but following bkjvbx's answer, it seems that if you take a,b such that:

a * b = p - 1 (since all non-prime numbers can be written as factors of prime numbers), we fall into the second case of bkjvbx
a * b = 1 (i.e. a & b are inverses) we fall into the first case.


If classical ciphers are used with compressed plaintext, how much does it make frequency analysis attack harder? Classical ciphers, such as the Vigenère cipher, are weak and no longer used. They can be broken by using frequency analysis, which is a well-known fact.
However, frequency analysis often depends on the number of captured ciphertexts and/or their duplication. What if the ciphertext was compressed by an algorithm such as Huffman encoding，zlib, or lzma before encrypting the plaintext? For better security, assume there is no constant header, magic number, or any identifier in the plaintext.
How much more difficult does compression make attack by frequency analysis?

Compression works by approximating an optimal code—one where if the probability of a given message is $p$, its encoded length is $-log(p)$. This means that the lengths of the encryptions of compressed messages potentially leak information about the plaintexts.

Also, the way a scheme like Huffman coding works is by outputting shorter code words for more frequent source symbols than for less frequent ones. This means that the relative frequencies of Huffman code words will be the same as that of the frequencies of the source symbols. It does nothing to disguise those frequencies.

A good real-life example to consider is attacks tht break the confidentiality of some encrypted voice-over-IP codecs that use variable bit rate encoding (which is a form of compression):

  Despite the rapid adoption of Voice over IP (VoIP), its security implications are not yet fully understood. Since VoIP calls may traverse untrusted networks, packets should be encrypted to ensure confidentiality. However, we show that when the audio is encoded using variable bit rate codecs, the lengths of encrypted VoIP packets can be used to identify the phrases spoken within a call. Our results indicate that a passive observer can identify phrases from a standard speech corpus within encrypted calls with an average accuracy of 50%, and with accuracy greater than 90% for some phrases.

Traditional encryption is weak and no longer be used. They can be easily broken by using frequency analysis is a well-known fact.

Im no crypto expert, so I cannot answer the full of your question-- but this part is not correct.  Encryption using algorithms such as 3DES, RC4, AES, etc is secure to the point where it is not possible to determine from looking at a block of data whether it is random or encrypted.  Further, if properly designed there will be an avalanche effect:  a very minor change in key or plaintext will have a drastic effect on the encrypted text.

If an algorithm's output is attackable by frequency analysis, it is not suitable for production.  I will note that there are some historical computer crypto algorithms (such as AES ECB) which HAVE been susceptible to frequency analysis; and when they are, they are marked as "not safe" and they fall out of use.

Regarding compression, if changing the plaintext increases the difficulty of cracking your encryption, then your algorithm is not secure.  I will leave explanations for why that is to others with more knowledge on the topic.


Can you fake messages from recorded message-history? Lets assume Eve has a lot of PGP conversation with Alice and records all those messages. Bob is also regularly communicating with PGP with Alice.

If Bob doesn't care about not having a signature from Alice, could Eve send any of those recorded messages unchanged but without signature to Bob pretending it came from Alice?

If Bob does NOT care to check signatures (as in the question), Eve can send ANY message she wants to Bob pretending to be Alice, including but not limited to messages Eve got from Alice; all Eve needs is Bob's public key (which, as the name implies, is assumed public knowledge thus known to Eve) and straight use of PGP.

Therefore the right question is: Can Eve reuse signatures she got from Alice, so that Bob concludes that a message sent by Eve is from Alice, even though Bob DOES care to check signatures?

The answer is YES, if Eve sends to Bob a message with exactly the content the message had when signed by Alice. So if Alice sent to Eve a message like "Let's meet at the bar at 11 pm", Eve can impersonate Alice and send that same message to Bob, who might conclude he has an invitation from Alice, when that invitation really was for Eve, perhaps another bar than the one he expects, and/or a past day. PGP gives insurance to Bob that the message was signed by Alice, and gives him a chance to detect a change of day (for PGP signatures include a "signature time stamp"). PGP does NOT give insurance to Bob that the message was for him.

Note: having an history of many recorded messages only helps Eve by giving her a wider choice of messages she can send to Bob pretending they came from Alice; Eve can not cut and paste fragments from past messages to compose a new one.

To be sure that the message is from A, A has to encrypt it with his private key. Anyone can decrypt it using A's public key.

To be sure that the message is for B, A has to encrypt it with B's public key. Only B can decrypt it using his private key.

If you use both methods combined, you can be sure that the message is from A and for B.

But this does still not rule out Delay or Replay attacks. Against these, you would include a timestamp into the encrypted part of the message.

And then, still some messages could have been dropped by malicious third party...


One time pad: why is it useless in practice? The symmetric cryptosystem one-time pad (OTP) seems to be very beautiful since it is perfectly secret according to Shannon. Many books, however, point out the main drawback: one must create a secret key the same length as the plaintext. For this reason, the concept of perfect secrecy has these days been abandoned, and we prefer other cryptosystems.

Now, for example, suppose I want to encode my text message with the ASCII scheme, and moreover suppose that this plaintext is 10 gigabytes long, therefore (using an OTP) the key must be the same length, 10 gigabytes. I think, however, this is a ''sustainable price'' because I'm sure that the ciphertext can't be attacked.

Practically, I don't understand why having such long keys with an OTP is a big disadvantage if we reach "the dream"-- namely, perfect secrecy. Nowadays the storage of information is very easy, so what is the real problem? I can, for example, share the "long key" in person.

Actually, the problem with OTP isn't the storage of the pad (although secure erasure of the parts of the pad you used is trickier than it looks), and it isn't the pad generation (although, again, that's trickier than it looks), but the secure transport.

After all, it's not enough for you (Alice) to have the secure pad, you also have to give a copy to the guy (Bob) you're sending the message to, and you need to send it in a way that's secure.

That's the real reason OTP's aren't used that often; OTP's would require meeting with the other side directly, or alternatively using a trusted courier; we rarely want to put up with the expense with either, especially since there are cheaper alternatives available.

A stream cypher uses a password to create a unique key of same length as the plaintext, so it can be thought of as like a one-time-pad.

Some problems are:
1. ensuring that a particular key is never re-used,
2. ensuring that there are no patterns in the generated keys which make it possible to guess or predict.

These problems were part of the downfall of the RC4 cypher.


Please help a complete noob with deniable encryption! I am completely new to cryptography and am interested in encrypting two basic text strings into one encrypted text that can be accessed separately with two different keys (preferably using something easily accessible like 256bit AES). For example:

Text1= I like peanut butter

Key1= Password1

Text2= I'm allergic to peanut butter

Key2= Password2

Output: 5UniWN0MjkPvUbLImrQUP68W4tpwOBMp2nrDqV73xeY

This output is just Text1+Key1, but is there a way that I can get both to work simultaneously so if Key1 is used, Text1 is returned, but if Key2 is used, Text2 is returned?

From my understanding, this is called deniable encryption and I was wondering where I could find a generator.

Thanks so much in advance!

If you aren't concerned with integrity guarantees, one easy way of accomplishing this is via AES-CTR encryption. For a given ciphertext, decrypting with any AES key results in a valid plaintext.

That being said, you should be concerned with integrity guarantees. I'm not recommending deploying any crypto which does not meet standard security notions like IND-CCA2.


What is the relationship between entropy conditioning and final output bias in a TRNG? This question concerns the conditioning and output of true random number generators.  It refers to NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions. It defines an $ n $ length bit string as having full entropy (ideally random) as:-

  ...if that bit string is estimated to contain at least
  $ (1-\epsilon) n $ bits of entropy, where $ 0 \leq \epsilon \leq 2^{-64} $.

Now to obtain a bit string containing full entropy, the document recommends a conditioning operation listed in Appendix C.  The smallest internal block width of any of these functions is 64 bits for treble DES.

And the document also says that if you follow this recommendation, you'll get a full entropy $ t $ length bit string from the conditioner's output:-

  If $ t \leq \frac{n}{2} $, then the output string has full entropy output .

This is the common rule of thumb for outputting half of the hashed input entropy in a TRNG.  My question therefore is what is the relationship between $ \frac{n}{2} $ and $ 2^{-64} $?  More specifically, what would the maximum of $ \epsilon $ be for $ \frac{n}{4} $?

The notation is a little confusing because it uses the same letter $n$ for two purposes, so let's change it to be a bit clearer:

  An entropy source output string containing $2t$ bits of entropy can be conditioned into a string of $t$ bits that contains full entropy output using an approved conditioning function, where $t$ is the length of the output block of the approved derivation function (see SP 800-90B).

(Replaced $n$ by $t$.)

In other words, if we have a physical device that produces a string $\sigma$ with $2t$ bits of entropy, which is necessarily at least $2t$ bits long, and we can pick a conditioning function $C\colon \{0,1\}^* \to \{0,1\}^t$, then the string $C(\sigma)$ is $t$ bits long and has nearly $t$ bits of entropy—in particular, $(1 - \varepsilon) t$, where $\varepsilon < 2^{-64}$.

This is a statement of an assumption (in §4.2 ‘Assumptions’) about the entropy source, having at least $2t$ bits of entropy where $t$ is the length of the output block.

  The derivation functions in SP 800-90A distribute the entropy provided by the input string is $n$ bits (so that the length of the input string is $r$ bits for some $r \geq n$), and the length of the output string is $t$ bits, then the following is true:

  If $t \leq n/2$, then the output string has full entropy output (i.e., the output string has $(1 - \varepsilon) t$ bits of entropy, for some $\varepsilon \leq 2^{-64}$).

($t$ is the same as above now.)

In other words, if we have a string $\sigma$ with $n$ bits of entropy, which is necessarily at least $n$ bits long ($r \geq n$), then for any choice of derivation function $C\colon \{0,1\}^* \to \{0,1\}^t$ in SP 800-90A with $t \leq n/2$, the $t$-bit string $C(\sigma)$ has nearly $t$ bits of entropy—in particular, $(1 - \varepsilon) t$, where $\varepsilon < 2^{-64}$.

This is a statement of an assumption about the derivation function, like Hash_df, used as a conditioning function.  An example of a function that would fail to satisfy this property is one that, say, just gives the first $t$ bits of the input string.

Why should these relations hold?  See an earlier answer for some details.  The quick summary is that a rough approximation for expected entropy of the output $F(\sigma)$ of a uniform random function $F\colon \{0,1\}^* \to \{0,1\}^t$ on a string $\sigma$ with $t + k$ bits of entropy is $\lg 2^t (1 - e^{-2^k}) = t + \lg (1 - e^{-2^k}) \approx t - e^{-2^k}/\log 2$, so as long as $k$ is reasonably large we easily attain ‘full entropy’ in this model with $\varepsilon \approx e^{-2^k}/(t\log 2)$.

Picking $k \geq 64$ is plenty—and we are required to do that because the block size of every approved derivation function is at least 64.  We don't have a uniform random function in the real world, but the derivation functions of SP 800-90A don't seem to have any interesting properties that let us distinguish them from one, so it's a pretty good model.

What if you chose a string $\sigma$ with $n = 256$ bits of entropy, and a 3DES-based derivation function with an output block of $t = 64 = n/4$ bits?  Then $k = 192$, so $\varepsilon$ is really quite tiny, and we get ‘full entropy’ in a 64-bit string—although that's only just under 64 bits of entropy.

What if you chose a string $\sigma$ with $n = 130$ bits of entropy, and an AES-based derivation function with an output block of $t = 128$ bits?  The margin is smaller in this case: since $k = 2$, the approximation above (a) is not a very good approximation and (b) gives an $\varepsilon$ nowhere near $2^{-64}$.  Maybe we get more than 64 bits of entropy in the end, but that's not ‘full entropy’ for a 128-bit string.

At what $k$ do we draw the line?  To give a comfortable margin without having to think hard about it, we just say that you should use twice as much the entropy in the input as the ${\geq}64$-bit output is long, in order to reliably get ‘full entropy’ in the output.

Found it.

The relationship of input & output entropies to the bias is simply bounded by:-

$$ \epsilon = 2^{-(sn-k)/2} $$

where $s$ = input entropy rate, $n$ = number of input bits and $k$ = internal block width. If you take AESy like conditioning components of a 128 bit width, $\epsilon = 2^{-64}$. This exactly tallies with NIST. Note then that $t \leq \frac{n}{2}$ only holds for a $k$ of 128.  The NIST recommendation does not hold for a DES /TDEA conditioner which would produce a larger bias of $2^{-32}$. Such would not have full entropy as defined by NIST using their stated criteria for $t$. Curious.

And so finally to my questionanswer.  If n = 4 and I use AES, $\epsilon = 2^{-192}$.

References:-

ID Quantique,
Technical Paper on
Randomness Extractor.
Version 1.0
September 2012

Bruno Sanguinetti, Anthony Martin, Hugo Zbinden, and Nicolas Gisin,
Quantum random number generation on a mobile phone.
Group of Applied Physics, University of Geneva, Switzerland.


Why are elliptic curves better than cyclic groups? The set of points of an elliptic curve over a finite field is isomorphic to the direct product of two cyclic groups (i.e. $E(F_{p^n}) \cong Z_{s} \times Z_{t})$.
What is the advantage of representing or conceiving the group as an Elliptic Curve instead of as a product of cyclic groups?

The first assumption: $E(F_q) \simeq Z_s \times Z_t$ is always true!! (see Handbook of Elliptic and HyperElliptic Curve Cryptography)
It is never said that coordinates of points lie on $Z_s \times Z_t$ which has no sense except if $s=t$.

But the isomorphism is not trivial to compute (it is in fact hard to compute, since it is related to the discrete logarithm for the left-to-right part).

And working only with the representation $Z_s \times Z_t$ will weaken the discrete logarithm so useful for cryptographic purposes.

In brief, if you can exhibit a curve (or demonstrate that there is a NIST curve) for which the computation of the left-to-right part of the isomorphism is easy, then this curve MUST be considered as weak and must never be used for any cryptographic purpose.

Concerning quantum computers, EC-DLOG will be solved as easily as for any cyclic group, since the Shor algorithm can be adapted to solve it, but don't ask me about details, I don't understand them...

Your first assumption is not entirely correct. They are not isomorphic to the direct product of two cyclic groups but rather a subset of all points in $\mathbb{Z}_q^2$, which fulfill a certain equation. Elliptic curves over $\mathbb{C}$ are closely related to the torus (genus 1 curve). Since the addition and multiplication (defined via multiple additions) are defined in a different way, you can not just use the product of two cyclic groups.

But what is the advantage?

First, we do not know any subexponential algorithm like Index Calculus for the discrete logarithm in elliptic curves. Therefore, elliptic curves can be chosen much smaller than other groups. Although the computations for the EC-addition are quite complex compared to modular multiplication and exponentiation, they are much faster due to the smaller modulus.

And then, EC-crypto might still be viable in a world with quantum computers, where the traditional DLOG and factorization are easy. As of now, there are no algorithms based on quantum computers which would make EC-DLOG easy.