#7123: cryptanalysis of the shift cipher
----------------------------+-----------------------------------------------
Reporter: mvngu | Owner: somebody
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.1.3
Component: cryptography | Keywords:
Work_issues: | Author: Minh Van Nguyen
Reviewer: | Merged:
----------------------------+-----------------------------------------------
Comment(by mvngu):
Replying to [comment:2 rbeezer]:
> 1. Is there any infrastructure planned for frequency tables - ie
perhaps given an alphabet and a language, a dictionary from "letters" to
their probabilities in that language? I could see this being veryuseful
for some of the cryptanalysis, especially of the classical ciphers.
Frequency distribution is already implemented for the following alphabets:
`AlphabeticStrings`, `BinaryStrings`, `HexadecimalStrings`,
`OctalStrings`, `Radix64Strings`. The relevant method is
`frequency_distribution()` in the class `StringMonoidElement` of the
module `sage/monoids/string_monoid_element.py`. Here is an example:
{{{
[mv...@sage sage-4.1.2.rc0-7123-shift]$ sage
----------------------------------------------------------------------
| Sage Version 4.1.1, Release Date: 2009-08-14 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: A = AlphabeticStrings()
sage: M = A.encoding("abcd")
sage: M.frequency_distribution()
Discrete probability space defined by {A: 0.250000000000000, C:
0.250000000000000, B: 0.250000000000000, D: 0.250000000000000}
}}}
As you can see, the default behaviour is to return the string
representation of a frequency distribution. This can be difficult to
parse, especially if one wants to do further processing with the returned
distribution.
[[BR]][[BR]]
> 2. Could you build on the exhaustive search in this patch, together
with frequency information, to rank more likely keys first, and present
more likely decipherments first?
Is there a way to determine likely keys? One way I can think of is to use
an existing frequency distribution table T of the letters of the English
alphabet. Given the frequency distribution of the ciphertext, sort the
ciphertext letters in non-descending order in terms of probability values.
Do the same sorting for the table T. Then map the ciphertext letter with
the highest probability to its counterpart in T, etc. Can use the
frequency table from the text:
* Robert Edward Lewand. "Cryptological Mathematics". The Mathematical
Association of America, 2000, p.36.
The same table can also be found on
[http://en.wikipedia.org/wiki/Letter_frequencies wikipedia]. For digrams,
trigrams, etc., one can use the US Army's field manual at
http://www.umich.edu/~umich/fm-34-40-2/
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7123#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
