11
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Your assumption that there are no patterns in the digits of pi, surprisingly, turns out to be false. Amazing, but true! $\endgroup$
    – D.W.
    Commented Sep 22, 2013 at 5:58
  • $\begingroup$ @D.W. link(s) please? All I'm finding is conspiracy theories(?), though I have found a claim that (if I understand correctly...) the distribution of digits is statistically random: thestarman.pcministry.com/math/pi/PiStats.htm $\endgroup$
    – Code Jockey
    Commented Sep 8, 2015 at 15:35
  • 2
    $\begingroup$ @CodeJockey, see mathoverflow.net/a/26970/37212 and rec-puzzles.org/index.php/Pi%20Solution. $\endgroup$
    – D.W.
    Commented Sep 8, 2015 at 15:49
  • $\begingroup$ angio.net/pi with 200 Million digits search. $\endgroup$
    – kelalaka
    Commented Oct 3, 2018 at 1:12

4 Answers 4

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • 5
    $\begingroup$ 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). $\endgroup$
    – Thomas
    Commented Jan 26, 2013 at 5:30
  • 3
    $\begingroup$ 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. $\endgroup$
    – Stephen Touset
    Commented Jan 26, 2013 at 5:48
  • 1
    $\begingroup$ Ah, I did not see Joshua's assumption - sorry! That'll teach me to comment without reading the entire thread.. $\endgroup$
    – Thomas
    Commented Jan 26, 2013 at 5:52
  • 1
    $\begingroup$ Nothing we've not all been guilty of at some point. Regardless, it was absolutely worth pointing out. $\endgroup$
    – Stephen Touset
    Commented Jan 26, 2013 at 5:57
  • 1
    $\begingroup$ @fgrieu The question mentions a one-time-pad, but if we downgrade to stream cipher security, I know not of any such result either. It could work, but we're relying on unproven assumptions here (that it isn't possible to efficiently match an $n$-digit long string in base $b$ with its first occurrence in $\pi$, for all we know an algorithm exists to do it in time faster than $O(b^n)$). $\endgroup$
    – Thomas
    Commented Jan 26, 2013 at 23:02
3
$\begingroup$

I have a strong interest in one time pads, and I would suggest that your scheme is a poor substitute for two reasons:-

1.

What is the key to decode the message? It would have to be related (however indirectly) to the start position in the $\pi$ sequence. For example, you can decode my "Hello Joshua" message by starting XORing from (say) the 20,503rd digit of $\pi$. So the key is 20503.

A bit short eh? It's only 14 bits. For shortish messages we'd accept 96 bit keys (counter modes), but really want to keep them to at least 128 bits. That's $340 \times 10^{36}$. Timothy Mullican has just computed 50 trillion digits of $\pi$ using y-cruncher. It took a while, needed a few servers and that 'key' would still only be 46 bits long.

So yes, while you can compute individual $\pi$ digits, it gets progressively harder the further downstream you go. Frankly, it's hopeless.

2.

Repudiation. If you destroy the OPT used to encrypt the message, no one will ever recover the plain text. Most of the the cold war OTP messages have never been decrypted for this reason. Your OPT will always exist and it's only a matter before someone stumbles upon the key /pointer.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Your second point is that the key could be recovered at some point in the future. If the the plaintext contained identifying information, that would then be exposed. Sure. You mean "repudiation" in a specific case, not as a cryptographic service. $\endgroup$
    – Patriot
    Commented Jul 30, 2021 at 4:56
-1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ 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). $\endgroup$
    – J.D.
    Commented Sep 21, 2013 at 18:10
  • 5
    $\begingroup$ -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. $\endgroup$
    – orlp
    Commented Sep 22, 2013 at 1:30
  • 3
    $\begingroup$ @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. $\endgroup$
    – J.D.
    Commented Sep 22, 2013 at 3:57
  • 1
    $\begingroup$ This is what happens when I create an account just to make a drive-by comment on an interesting question, then forget about it. So to clarify, as @J.D. subsequently noted, I was focused on computing arbitrary digits in constant time (actually, logN time should be okay too), as being able to calculate the Nth digit in O(N) or worse doesn't really allow you to make use of a sufficiently large key. Additionally, I was of course answering the question subject to the hypothetical that "some mathematician proves that there are no patterns in pi." $\endgroup$
    – Ummon Karpe
    Commented Aug 28, 2017 at 0:14
-1
$\begingroup$

Your algorithm is vulnerabel to brute force attacks. XOR the ciphertext with parts of the PI fraction starting with n and then with n+1 and so on. Today's fast computers won't take long to crack it. :)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ How would you brute force it if the key was e.g. 128 bits long? Brute force would take about as long as for a normal 128-bit cipher. $\endgroup$
    – otus
    Commented May 5, 2016 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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