Search code examples
encryptionencryption-symmetric

Why is it impossible to implement an "infinite" one time pad algorithm?


I've done some research into this, but I'm still not sure why this cannot be implemented. Provided we share an initial OTP, possibly via USB or some other physically secure method, surely we can include the next one in the messages that follow.

[Edit: More specifically, if I were to take a pad of double length, splitting it into x and y. Then using x to encrypt the message, and using y twice to encrypt the next pad, would that be insecure?]


Solution

  • You have to pair each bit of message with a same size bit of OTP. There's a limited amount of OTP.

    If you pair up all of the OTP bits with bits for the next OTP...

    a b c d e ...
    q w e r t ...
    

    There's no room for a message. And if you keep spending your OTP transferring another OTP, there never will be room for a message.

    You can't compress the OTP, because the strength of the OTP is that it's completely random - that's what makes it impossible for codebreakers, because there's no pattern to latch onto.

    Compression is a technology that works by finding patterns and replacing them with shorter "that large repetitive block goes here and here and there" signals - and by definition there are no patterns in complete randomness, so OTPs are not compressible.

    If you can compress it a bit, you could do this but it's not right to describe it as OTP anymore, it's weak - and also massively wasteful of bandwidth. If you can compress it a lot, throw your random number generator away it's terrible.


    Quick test demonstration of concept on a linux machine:

    $ dd if=/dev/urandom of=/tmp/test count=10k
        -> 5Mb file of randomness
    
    $ bzip2 /tmp/test 
        -> 5.1Mb file
    $ gzip /tmp/test
        -> 5.1Mb file
    

    Compressing a pad makes it bigger, by adding all the bzip/gzip file format information and doing nothing else.