Security and Cryptography
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsSystem AdministrationSecurity and Cryptography

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old December 20th, 2009, 04:51 PM
Number1Brat Number1Brat is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Dec 2009
Posts: 1 Number1Brat User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 10 m 36 sec
Reputation Power: 0
Crypto Algorithm Question - Simple XOR theory

Hey guys I have always wondered this but no one's been able to answer me. I know how to crack a simple XOR (not a one-time pad, but one where the key length is smaller than the plain text).
According to Applied Cryptography Second Edition you are supposed to...

Quote:
1. Discover the length of the key by a procedure known as counting coincidences. XOR the cipher text against itself shifted carious numbers of bytes and count those bytes that are equal. If the displacement is a multiple of the keylength, then something over 6 percent of the bytes will be equal. If it is not, then less than 0.4 percent will be equal (assuming a random key encrypting normal ASCII text; other plaintext will have different numbers).This is called the index of coincidence. The smallest displacement that indicates a multiple of the key length is the length of the key.

2. Shift the ciphertext by that length and XOR it with itself. This removes the key and leaves you with plaintext XORed with the plaintext shifted the length of the key. Since english has 1.3 bits of real information per byte, there is plenty of redundancy for determining a unique decryption.


How does this actually work? What's the mathematical theory behind it?

Reply With Quote
  #2  
Old December 21st, 2009, 12:27 AM
fishtoprecords's Avatar
fishtoprecords fishtoprecords is offline
Contributing User
Dev Shed Frequenter (2500 - 2999 posts)
 
Join Date: Sep 2007
Location: outside Washington DC
Posts: 2,642 fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)fishtoprecords User rank is General 41st Grade (Above 100000 Reputation Level)  Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6Folding Points: 2568392 Folding Title: Super Ultimate Folder - Level 6
Time spent in forums: 3 Weeks 4 Days 23 h 21 m 56 sec
Reputation Power: 3682
Yes it works, XOR is the simplest cipher.

Thing XOR key => ciphertext

ciphertext XOR key => plain text again.

The technique simply helps you find the key. If the key is shorter than the clear text, then it repeats. Find that, and you are done.

Reply With Quote
  #3  
Old December 22nd, 2009, 01:59 PM
Jeff Dege Jeff Dege is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Sep 2008
Posts: 31 Jeff Dege User rank is Sergeant Major (2000 - 5000 Reputation Level)Jeff Dege User rank is Sergeant Major (2000 - 5000 Reputation Level)Jeff Dege User rank is Sergeant Major (2000 - 5000 Reputation Level)Jeff Dege User rank is Sergeant Major (2000 - 5000 Reputation Level)Jeff Dege User rank is Sergeant Major (2000 - 5000 Reputation Level)Jeff Dege User rank is Sergeant Major (2000 - 5000 Reputation Level) 
Time spent in forums: 4 h 58 m 9 sec
Reputation Power: 29
Quote:
Originally Posted by Number1Brat
Hey guys I have always wondered this but no one's been able to answer me. I know how to crack a simple XOR (not a one-time pad, but one where the key length is smaller than the plain text).
According to Applied Cryptography Second Edition you are supposed to...



How does this actually work? What's the mathematical theory behind it?


Take two random characters from a text. Compare them. What is the probability that they will be the same character? One divided by the number of characters in the alphabet.

If, for example, your text was WWI-era English telegraph cipher interceptions, you'd have an alphabet of 26 characters (upper-case A-Z with no spaces), so with random text you'd expect a match - a coincidence - 1/26, or 3.85% of the time.

Now, suppose your text is standard English in the same alphabet. What would be the odds? Much higher. The precise value, like the value for random text, depends upon the alphabet, and it also depends on the language. Ordinary English, written as a telegraphic cipher (upper-case A-Z with no spaces), yields a coincidence 6.65% of the time.

These values are referred to as the Indices of Coincidence of random text and of plain text.
http://en.wikipedia.org/wiki/Index_of_coincidence

Now the interesting thing about monoalphabetic ciphers is that they don't change the index of coincidence (IC). Substituting 'X' for 'A' throughout a text doesn't change the likelihood that the two characters will be the same. So a monoalphabetic cipher will have the same IC as plaintext.

But polyalphabetic ciphers are very different. Each of the individual alphabets will have the same IC as plaintext, but because the different alphabets are all muddled together, their combined IC will be much closer to that of random text than of plain text. In other words, the IC of the cipher text will be close to 0.0385.

Now, what happens when you subtract the text from itself, shifted by one or more places. If the amount of the shift is unrelated to the length of the keyword, each letter is being subtracted from a letter in a different alphabet, and the result is still pretty much random, so you should see 0 about 3.85% of the time. But when the shift is a multiple of the length of the keyword, each letter is being subtracted from a letter that is in the same alphabet it is. So you'd expect to see 0 about as often as two random characters from plaintext would match. That is, 6.65% of the time.

Think about it. You have two ciphertext letters, each of which is the sum of a key letter and a plaintext letter:

C1 = P1 + K1
C2 = P2 + K2

When you subtract the two ciphertext letters, you get:

C2-C1 = P2-P1 + K2-K1

But when the two letters are separated by a multiple of the keylength, K1 and K2 are the same, and you get:

C2-C1 = P2-P1 + K1-K1
C2-C1 = P2-P1

A value that is independent of the key.

When you're done with the process, you have determined the length of the key. With that, you can split the message into its separate alphabets, and attack each as an ordinary monoalphabetic substitution. Or, you might recognize that the result of your subtract is the plaintext subtracted from itself, shifted by the length of the key. In other words, it's an autokey cipher, which has known methods of attack.

http://en.wikipedia.org/wiki/Autokey_cipher
Comments on this post
marwis agrees: Nice decompression of the six lines above .
B-Con agrees!

Reply With Quote
  #4  
Old September 6th, 2011, 05:40 PM
debaj debaj is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Dec 2009
Posts: 9 debaj User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 6 h 3 m 20 sec
Reputation Power: 0
please . can I uses these ways ..if I have plaintext in hex xor key in hexa and the result naturally in hex..in this case can I separate the key from plaintext and return the original text

Reply With Quote
Reply

Viewing: Dev Shed ForumsSystem AdministrationSecurity and Cryptography > Crypto Algorithm Question - Simple XOR theory

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap