TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Verifying the Substitution Cipher Folklore

27 点作者 nazri1超过 8 年前

10 条评论

unlikelymordant超过 8 年前
You <i>can</i> break substitution ciphers pretty trivially, just using a simple hill climbing algorithm see <a href="http:&#x2F;&#x2F;practicalcryptography.com&#x2F;cryptanalysis&#x2F;stochastic-searching&#x2F;cryptanalysis-simple-substitution-cipher&#x2F;" rel="nofollow">http:&#x2F;&#x2F;practicalcryptography.com&#x2F;cryptanalysis&#x2F;stochastic-se...</a><p>If your cipher is at least 100 characters this will solve it very quickly.
arnarbi超过 8 年前
Many misunderstand the classical lesson as &quot;substitution ciphers are trivially broken by symbol frequency analysis&quot;, which isn&#x27;t the point.<p>The point is to illustrate a property of a cipher that leaks information, in this case the symbol frequencies because the cipher preserves them. This is information that we don&#x27;t normally consider valuable when working with plaintexts, but for crypto it&#x27;s enormously valuable (i.e. it leaks a lot of information).
grzm超过 8 年前
<i>&quot;I was expecting that this would yield an almost perfect result. In fact, the result still needs significant guesswork to decrypt.&quot;</i><p>I&#x27;ve never heard that substitution ciphers are simple to break using <i>only</i> letter frequencies. It does get you to a point where it makes the guessing a lot easier.
tptacek超过 8 年前
If you&#x27;d like to play with this yourself, it&#x27;s #6 in the cryptopals challenges:<p><a href="http:&#x2F;&#x2F;cryptopals.com&#x2F;sets&#x2F;1&#x2F;challenges&#x2F;6" rel="nofollow">http:&#x2F;&#x2F;cryptopals.com&#x2F;sets&#x2F;1&#x2F;challenges&#x2F;6</a><p>I agree with the author: it&#x27;s conceptually very simple, but a little tricky to code, even in the simplest case where you&#x27;re relying on simple letter frequencies. You could probably do 10 good challenges on different ways to attack this problem, and towards the end you&#x27;d be getting into somewhat serious cryptanalysis: for instance, look at what Patterson and Al Fardan did with RC4.
评论 #12889278 未加载
empath75超过 8 年前
He wrote like half the algorithm and then said it didn&#x27;t work.
评论 #12883670 未加载
评论 #12883053 未加载
stevetrewick超过 8 年前
&gt;<i>&quot;In fact, the result still needs significant guesswork to decrypt.&quot;</i><p>I have never heard anyone other than the author of this piece suggest otherwise. Ironically, this result is trivial. That said, I have a pretty serious classical crypto habit, so my conception of what constitutes &#x27;crypto folklore&#x27; may be poorly calibrated.
Smaug123超过 8 年前
I used simulated annealing, which is a non-obvious but fairly easy algorithm: <a href="https:&#x2F;&#x2F;github.com&#x2F;Smaug123&#x2F;ClassicalCiphers.jl&#x2F;blob&#x2F;master&#x2F;src&#x2F;monoalphabetic.jl" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;Smaug123&#x2F;ClassicalCiphers.jl&#x2F;blob&#x2F;master&#x2F;...</a>
benchaney超过 8 年前
I know plenty of CS undergrads who have broken the substitution cipher a part of a assignment. Saying it isn&#x27;t trivial just because you couldn&#x27;t do it foolish.
评论 #12883123 未加载
nullc超过 8 年前
<a href="http:&#x2F;&#x2F;www-i6.informatik.rwth-aachen.de&#x2F;unravel&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www-i6.informatik.rwth-aachen.de&#x2F;unravel&#x2F;</a>
jakewins超过 8 年前
Does anyone know the history of where the word &quot;trivial&quot; started being used to mean &quot;easy&quot; instead of as &quot;unimportant&quot;, like the author does here?<p>It drives me crazy - but perhaps I&#x27;m the one that&#x27;s wrong. Is it correct to use &quot;trivial&quot; to mean &quot;easy&quot;?<p>I keep thinking it comes from people misunderstanding the meaning of &quot;non-trivial&quot;, as in complex
评论 #12884119 未加载
评论 #12884752 未加载
评论 #12884005 未加载
评论 #12884658 未加载