#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:
----------------------------+-----------------------------------------------
Changes (by mvngu):
* status: needs_review => needs_work
Comment:
{{{
22:11 < rbeezer> found the problem - you are decrypting/shifting too much
22:12 < rbeezer> try this - change AlphShifted = self.enciphering(key,
Alph)
22:12 < rbeezer> to AlphShifted = self.enciphering(0, Alph)
22:22 -!- homerj [[email protected]] has
left #sage-devel ["Leaving"]
22:41 < rbeezer> mvngu: any luck?
23:00 < mvngu> rbeezer: I'm not convinced about the change.
23:01 < rbeezer> mvngu: Ideally, I think you want RMk =
[(OM[AlphShifted[StrAlph.index(e)]] - EA[e])**2 / EA[e] for e in StrAlph]
23:01 < rbeezer> to read more like: RMk = [(OM[e] - EA[e])**2 / EA[e] for
e in StrAlph]
23:01 < rbeezer> but when I made this change, the indices of OM and EM
were different types and I got errors
23:02 < mvngu> rbeezer: That's what I thought, and originally implemented
for the method at
http://starbase.trincoll.edu/~crypto/historical/caesar.html
23:03 < rbeezer> changing the statement before (key -> 0) was just a
hack to negate the whole shifting in AlphShifted
23:03 < rbeezer> With key->0 I was getting good results with short test
phrases
23:05 < mvngu> rbeezer: Have you looked at the formula for RMk? See the
formula at
http://sage.math.washington.edu/home/mvngu/reference-7123-shift/sage/crypto/classical.html#sage.crypto.classical.ShiftCryptosystem.rank_by_chi_square
I was following that formula.
23:06 < mvngu> In particular, this formula
http://sage.math.washington.edu/home/mvngu/reference-7123-shift/_images/math/d8a2fd0995ed8152cfa73a6e16fcab0ef367a993.png
23:06 < rbeezer> mvngu: the formula in that doc shouldn't have the +k, I
think
23:07 < rbeezer> mvngu: the starbase stuff is using the +k to decrypt, I
think
23:07 < rbeezer> mvngu: while you have the brute_force output as an input
to your routine, so the decryption has already happened
23:08 < rbeezer> the starbase stuff is not complete enough, or careful
enough, to give me any confidence
23:09 < mvngu> rbeezer: What's "starbase stuff"?
23:09 < rbeezer> did you test my original hackish change?
23:09 < mvngu> rbeezer: "*="
23:09 < mvngu> ?
23:09 < rbeezer> the link at starbase.trincoll.edu ;-)
23:10 < mvngu> rbeezer: testing your change now...
23:14 < williamstein> I made a lot of progress on the notebook "rewrite"
today...
23:14 < williamstein> and finally those VirtualBox machines are working!
23:14 < williamstein> There are also now 8949 sagenb.org users.
23:15 < williamstein> Only 51 more to 9000.
23:18 < mvngu> rbeezer: Your change certainly gives better results now.
See my transcript at http://sage.math.washington.edu/home/mvngu/chi-
square-rbeezer-hack.txt
23:19 -!- wormsxulla [i=chatz...@unaffiliated/wormsxulla] has quit [Read
error: 110 (Connection timed out)]
23:19 -!- wormsxulla_ [i=chatz...@unaffiliated/wormsxulla] has joined
#sage-devel
23:19 -!- wormsxulla_ is now known as wormsxulla
23:19 < rbeezer> mvngu: that's what I was seeing
23:19 < mvngu> rbeezer: Now for a text file...
23:20 < rbeezer> mvngu: your strings from brute_force() have already been
shifted, you just want the one whose letter distribution most closely
matches that of English
23:21 < rbeezer> but right now OM and EM are indexed by letters versus
one-character stings, or somthing like that
23:21 < rbeezer> s/strings/stings/
23:23 < mvngu> rbeezer: Result from using a file... Looks good. See
transcript at http://sage.pastebin.com/m6e4d8df4
23:24 < rbeezer> yep, that's it - the Pearson chi-square should give good
results for short and long messages
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7123#comment:12>
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
-~----------~----~----~----~------~----~------~--~---
