最近为了产品应用在实作一些小型的加密 发现有个怪怪的地方 我先把要讨论的对称加密写成数学语言: ------------------------------------- S_n:={0,1}^n f_k:S_n→S_n 是可逆函数, for each k€S_m (m可能等於n, 无所谓, key长度而已) ------------------------------------- 对称性加密的原理就是f_k的演算法是公开的, 但是k是自己/信赖的人保留的 也就是说, 今天自己选择一个k, 把明文 x€{0,1}^n 转到暗文 y=f_k(x)€S_n後 没有k的人拿到y也没用, 因为随便一个k'都能还原出x', 但是可能不是x 只有正确的k才会保证还原正确的x 而如果要暴力破解, 就要尝试2^m个key, 这对於m=256来说就是天文数字 但是不暴力破解的话, 会不会因为f_k太简单而导致不用尝试到2^m个key就破解了 原本我猜测是肯定的, 就是f_k要复杂, 如AES加密算法, 可能现今对他还没想到除了 暴力破解外的解法 但是突然出现一个矛盾...我今天设计一个非常简单的f_k, 就单纯是xor(互斥逻辑运算) 举例来说, m=n=2, k=(0,0), x=(1,0),则f_k(x) = (1,0) 然後拿这个f_k机制来进行对称性加密, k自己保留 我目前发现对方除了暴力破解外也无他法 即便他知道我用的是最简单的xor, 但是没拿到真正的k, 他解出来的明文不一定是对的 但是如果xor就可以了, 也不必存在AES这些运算量高的算法 至此我再用原始函数条件去想, 确实可能存在不同的k', 但是可以得到真正的明文x 也就是说, 如果我私有k满足f_k(x) = y, 其实存在其他k'满足f_k'(x) = y 这是否就是AES之类对称加密防护的机制? 也就是说, 一个robus的对称性加密需要额外满足: 对所有x€S_n, F(k) := f_k(x), F要是一对一 也就是说, 如果f_k(x) = f_k'(x), 则k=k' (大致上看起来m>=n才有机会让绿色成立) ---------------------------------------------------------------------- 总之想请问的是, 对称性加密关键是否就真的在於绿色以至於只剩暴力破解来保障安全性 谢谢帮忙~~ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.102.225.191 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1651397705.A.5AD.html int大你意思是AES的f_k可以完全给别人运作(比如某个包好的程式档) 但是使用的人无法知道里面的k是什麽? 这确实是xor做不到的事情, 如果拿的到xor的f_k, 他只要输入一个input就知道是k是什麽了 不过我刚刚发现xor会满足绿色的式子耶... 今天看你叙述xor的缺点, 好像是针对"方便性"以及"泛用性" 但是单纯论安全性的话, 是不是很安全? 因为只能暴力破解 证明如下: 我选了一个k€S_n, 用xor加密了明文x€S_n, 得到y = x xor k, y€S_n 骇客偷看到y, 想要得到x的话就必须去穷举所有的k'€S_n 假设存在另外一个k'使得y = x xor k' 那由xor的性质可以得到k=k', 也就是说他必须选到我当初选的k 我有少考虑到什麽吗? 看wiki好像在叙述一些"因为讯息不足, 即便时间无限也永远无法被破解"的加密算法 但是我从接触加密相关的资料以来, 每一种方法如果目前仍在用, 都是可以暴力破解的 只是时间如果长到夸张就归纳为现在无法破解 想额外问一下, 有对於"可/不可破解"的数学定义或是实务定义吗? 数学定义之前是看过一些用"机率加运算时间"的定义方式 而实务定义的话, 是否只能说"到目前为止只能用暴力破解"来当不可破解的定义? 只是不排除未来某一天有人刚好想到很快的演算法, 或是猜到key, 或是简化出数学式 举例来说, Σ_{k=1~N} (-1)^k 的答案是多少, 当N=2^1000时 我声称这个在数十年电脑都跑不完(无法暴力破解) 但是任何一个小学生都能告诉这个答案是多少(简化数学式了) 我这个例子是想表达是否实务上的加密方式都有这个危险, 只是目前没发生而已? (然後information theoretic security就是说这件事绝对不能发生, 即无解) ※ 编辑: znmkhxrw (59.102.225.191 台湾), 05/02/2022 02:13:22 c大你应该是指如果对方有f_k的程式, 那这样当然别人随便一个input输入後就知道k是什 麽了 可是我的意思是对方只知道我的y, 而y是我自己由某个f_k产生的, 即便让他知道f_k的设 计只是跟某个k做xor, 他也猜不到这个k是什麽 这应该就是我看到的用机率测度加上时间复杂度所下的定义了 嗨L大, 读了#1GPBcQPe这篇受益良多, 里面确实还有一个变因是"计算模型" 这些关键字以我现有的密码学知识来说有点难串起来... 有点像是读了reference 1 & 2後, 觉得他们好像有点关系, 又好像是在讲不同的东西 我用对称性加密叙述一下我发问的动机: 1. 想设计简单的f_k, 对於每个k€S_n都存在在S_n的可逆函数f_k 2. 直觉的拿xor跟permutation这两个去做组合, 但是马上发现几件事: (1) 肉眼看起来复杂的加密结果, 对电脑而言却不一定 (2) 肉眼看起来复杂的加密程式, 对破解而言却不一定 以xor跟permutation所做的f_k为例, 因为证明了: (a) 多个xor可以合并成一个xor (b) 多个permutation可以合并成一个permutation (c) xor跟permutation可交换, 只是差别在xor的值做个改变罢了 所以得出了如果f_k的设计是数以千计的xor跟permutation所组成 那对破解者来说仅是一次的xor跟permutation所组成 这个问题也让我特别留意所设计的算法有没有白做事 这也是为什麽我举了Σ_{k=1~N} (-1)^k当例子, 实际算运算量很高 但是根本不用算就可以得到答案, 只要你找到快速的破解法 3. 承2.-(2), 我无法穷举所有的破解方式, 说不定只是我以为只能暴力解 但是有其他破解者能找到很快的破解法 这也是为什麽我猜测RSA, AES...之类的加密算法是迄今没有速解 但是不能保证未来没有 也就是因为1.~3., 让我去好奇跟搜寻加密破解性的定义 然後就得到一些统计测度论以及时间复杂度数学上的定义... 之後越查越觉得复杂, 因为我起初的问题听起来很简单: 破解难易度 还是就是因为很难一致定义破解难易度, 才有以不同切入点所得到的定义? (有些用时间复杂度, 有些用资讯商...any other) ---------------------------------------------------- 以上就是我的发问动机以及思考细项, 有点乱不好意思 总结一问的话, 就是今天我设计了一个对称性加密f_k後 下列的自问自答是否正确 Q1: 请问这个算法的破解难易度? A1: 请先告诉我所采用的破解难易度的定义 Q2: 请问这个算法是否只能暴力破解 A2: 目前我这个设计者只想到暴力破解的方式, 但不代表别人或是未来没有破解法 (请给我"只能暴力破解"的定义?) Q3: 加密算法越复杂破解难度越高, 像是xor一定比AES更容易破解? A3: 不一定, 因为: (1) 算法设计复杂有可能未来某一天可以化简成简单的数学形式 (2) 算法设计复杂有可能未来找到快速的演算法破解 (3) 算法设计复杂有可能白做工, 像是Σ_{k=1~N} (-1)^k 或者可以说, 我最初就是因为这些QA才去查资料 结果查出一堆有帮助但是好像不是正面回答QA的资料(其他密码学定义/词汇blabla) 还是说因为我这些QA确实都是case by case的实务问题, 难以穷举全部 所以密码学为了抽象与一致化才会去下各种定义... 问题有点多, 不好意思@@ 先谢谢回答了~^^ 嗨int大, 以上觉得认同! 我就是认为无法穷举出这世界上所有的破解法 又或是说目前没有模型跟定义去规范所有的"破解法": for any cracking method€set of all cracking methods 所以现有加密法都仅限於"迄今"无破解法 这部分分享想请问一下, 是指所有的对称性加密都能"化约"成这种讨论模式吗? 以我的"f_k(x) := x xor k"为例, 攻击者只能拿到output y = f_k(x)而已 我不理解这中间存在什麽黑箱的f_k, f_k^-1以及什麽F, F^-1 还是说这些词汇还要基於某些"攻击者能拿到什麽资讯"的假设? 在我的例子中, 攻击者只能拿到y, 无法拿到我的f_k, 所以他永远不知道我的k是什麽 ※ 编辑: znmkhxrw (61.231.69.250 台湾), 05/03/2022 13:38:32