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.

I have a question which arised by analyzing the one-time pad cipher. I encrypt a binary sequence $a_1,a_2,..,a_N$ using a one-time pad with key sequence $k_1,k_2,k_3,...$, so I send $a_1+k_1, a_2+k_2,\dotsc,a_n+k_N$.

Now I make mistake and instead of sending the above sequence I transmit $a_1+k_2,...,a_N+k_{N+1}$. Assuming now that you know that I made this error and that my message makes sense, can you find the message?

Remark: Using a one-time pad means I encipher a message as $b_1b_2\dots b_N$ where $b_j\equiv a_j+k_j \pmod q$ where $q$ is the size of the alphabet, in our case $q=2$.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

Assuming that you have not used the one-time pad bits $k_2, ..., k_{N+1}$ to encrypt another message, then the answer is no, the attacker cannot determine the message.

This can be seen by using the normal proof of One Time Pad's security; the bits $k_2, ..., k_{N+1}$ are random and uncorrelated to any other bits the attacker has access to; hence the attacker gets no information on the values of $a_1, ..., a_N$ from the sequence $a_1+k_2, ..., a_N+k_{N+1}$. That those random uncorrelated bits are not the precise ones that you intended to use is irrelevant.

On the other hand, if the sender realized his mistake, and then sent $a_1+k_1, a_2+k_2, ..., a_N+k_N$, at that point, the attacker could deduce information about the message. This violates the restriction that "bits from the one time pad are used only once", and this actually allow the attacker to deduce the original message (or its complement).

share|improve this answer
    
Thanks for your answer. How would the attacker proceed at the point he has access to both sequences? –  TI Jones Jan 18 at 18:49
    
@TIJones: Well, he has both $a_1+k_2$ (from the first message) and $a_2+k_2$ (from the second); that gives him $a_1+a_2$. From that, he can (with $a_2+k_3$ and $a_3+k_3$) compute $a_1+a_3$. Continuing, he can reconstruct $a_1+a_i$ for all $i$. That, plus a guess of $a_1$, gives him the entire message. –  poncho Jan 18 at 19:03
add comment

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.