This paper presents algorithms for local inversion of maps and shows how several important computational problems such as cryptanalysis of symmetric encryption algorithms, RSA algorithm and solving the elliptic curve discrete log problem (ECDLP) can be addressed as local inversion problems. The methodology is termed as the \emph{Local Inversion Attack}. It utilizes the concept of \emph{Linear Complexity} (LC) of a recurrence sequence generated by the map defined by the cryptanalysis problem and the given data. It is shown that when the LC of the recurrence is bounded by a bound of polynomial order in the bit length of the input to the map, the local inversion can be accomplished in polynomial time. Hence an incomplete local inversion algorithm which searches a solution within a specified bound on computation can estimate the density of weak cases of cryptanalysis defined by such data causing low LC. Such cases can happen accidentally but cannot be avoided in practice and are fatal insecurity flaws of cryptographic primitives which are wrongly assumed to be secure on the basis of exponential average case complexity. An incomplete algorithm is proposed for solving problems such as key recovery of symmetric encryption algorithms, decryption of RSA ciphertext without factoring the modulus, decrypting any ciphertext of RSA given one plaintext ciphertext pair created with same private key in chosen ciphertext attack and solving the discrete logarithm on elliptic curves over finite fields (ECDLP) as local inversion problems. It is shown that when the LCs of the respective recurrences for given data are small, solutions of these problems are possible in practically feasible time and memory resources.


翻译:本文展示了地图本地翻转的算法, 并展示了几个重要的计算问题, 如对称加密算法的加密分析、 RSA 算法和解决椭圆曲线离散日志问题( ECDLP) 的加密分析, 可以作为本地反转问题处理 。 这种方法被称为 emph{ 本地反转攻击} 。 它使用由低 LC 数据定义的地图生成的复现序列的 emph{Linaear complility (LC) 概念 。 这种案例可能发生意外, 但无法在实践中避免, 重复的LC 由对地图输入的略长的混合顺序捆绑起来, 本地反倒转也可以在多时完成 。 在指数平均的 RIS 轨迹中, 以不完全的 RIS 轨算算算法问题, 以直径解的 RIS 数据解算法, 以直径解的正确性 解算法, 以直径解的正确性 。

0
下载
关闭预览

相关内容

RSA( RSA (algorithm), Ron Rivest, Adi Shamir and Leonard Adleman )以三位创始人的名字命名。安全性基于有效的素数分解算法的不存在。以安全的非对称加密充当了现代密码体系的骨干。
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Warped Dynamic Linear Models for Time Series of Counts
Arxiv
0+阅读 · 2022年4月15日
VIP会员
相关资讯
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
相关基金
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员