Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let's pretend that all digits of pi are known and arbitrarily long sequences of digits are trivial to get. Further, some mathematician proves that there are no patterns in pi. We could create a stream cipher by grabbing a piece of pi as long as our plaintext and combining the two with some function (such as XOR or modulus addition.) The key would be the starting position in pi.

Would this be equivalent (in terms of security) to a one-time pad? To what sort of attacks would it be vulnerable?

share|improve this question
    
Your assumption that there are no patterns in the digits of pi, surprisingly, turns out to be false. Amazing, but true! –  D.W. Sep 22 '13 at 5:58

2 Answers 2

up vote 10 down vote accepted

The problem with this approach is that it literally gains you nothing. In order to choose a random subsequence of a needed length from $\pi$, you need to generate a cryptographically random number of at least the same length of the desired key to use as the offset. But then you may as well just use that number as your secret key.

Other than that, yes, it's exactly the same as a one-time pad. Just with a silly and pointless key derivation protocol which cannot mathematically increase the security of the system, but could conceivably weaken it.

Edit: As Thomas points out in the comments, the distribution of digits of $\pi$ are not random, and so this mechanism of key generation actually discards a significant amount of entropy that had been generated while choosing a random offset.

share|improve this answer
2  
The $n$th digit of $\pi$ is most certainly not a uniform random variable over $\mathbb{Z}_{10}$, therefore claiming that this scheme is equivalent to an OTP is incorrect (it may seem that choosing a random "starting position" is enough, but it's not - the underlying distribution of $\pi$ actually matters and if it is not uniformly random, it will destroy entropy encoded in said starting position). –  Thomas Jan 26 '13 at 5:30
1  
One of the original stated assumptions was "there are no patterns in $\pi$", from which I (perhaps incorrectly) assumed he meant something along the lines of "the distribution of digits in $\pi$ is random". Certainly if the the digits of $\pi$ are not random (as you've correctly stated is the case), this mechanism is significantly weaker than a true OTP. –  Stephen Touset Jan 26 '13 at 5:48
1  
Ah, I did not see Joshua's assumption - sorry! That'll teach me to comment without reading the entire thread.. –  Thomas Jan 26 '13 at 5:52
1  
Nothing we've not all been guilty of at some point. Regardless, it was absolutely worth pointing out. –  Stephen Touset Jan 26 '13 at 5:57
    
@Thomas: I know not result hinting at any bias in the digits of $π$ in any base; or at a distinguisher that would, in time independent of $n$, recognize with sizable advantage a fixed-length uniform random sequence from an equal length extract of the digits of $π$ starting at the $n$th. Is there such a thing? –  fgrieu Jan 26 '13 at 14:08

If it were possible to compute digits of pi from an arbitrary location (to generate the stream) in constant time, then it would be an excellent cipher. Unfortunately, this isn't possible.

Maurer suggested using the surface of the moon for a source of random information instead: link

share|improve this answer
    
Actually you can calculate the (binary) digits of pi at an arbitrary position (without having to compute all the prior digits). Search wikipedia for the article on the Bailey–Borwein–Plouffe formula (link didn't work). –  J.D. Sep 21 '13 at 18:10
1  
-1 Sorry, but this is utter bullshit. It is possible to compute digits of pi from an arbitrary location, and the resulting "cipher" is rubbish. –  orlp Sep 22 '13 at 1:30
1  
@nightcracker - in fairness to Ummon Karpe, he did say compute arbitrary digits in constant time, which I missed the first time I read his answer. The fastest method I have heard of requires quadratic time. That said, the 'pi cipher' still doesn't sound like a good idea even if it were efficient. –  J.D. Sep 22 '13 at 3:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.