blocks|key|2018325|text|迟回复，但希望能有所帮助。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2018326|你还可以看到这篇论文:肯尼斯·G·帕特森(+Kenneth+G.+Paterson+)和安蒂戈尼·波尔(+Antigoni+Polychroniadou+)和戴尔·L·西伯恩(+Dale+L.+Sibborn+)撰写的一种基于编码理论的RSA密钥恢复方法。|offset|length|2018327|他们提供了许多攻击，但他们给出的答案是，边界或多或少是相同的铜匠的logN/4+bits。好的是，即使在随机比特的情况下，边界仍然存在。该算法的一个优点是，即使有时给出了错误的位值(允许错误更正)，也可以检索正确的因式分解。然而，它可能会更低。|style|CODE|entityMap|0|LINK|mutability|MUTABLE|url|http://eprint.iacr.org/2012/724^0|0|31|I|0|0|X|B^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@$D|S|E|T|1|U]]|A|$]]|$1|F|3|G|5|6|7|V|8|@$D|W|E|X|H|I]]|9|@]|A|$]]]|J|$K|$5|L|M|N|A|$O|P]]]]

Late reply but hope it helps. 

You could also see this paper: <a href="http://eprint.iacr.org/2012/724" rel="noreferrer">"A Coding-Theoretic Approach to Recovering Noisy RSA Keys"</a> by Kenneth G. Paterson and Antigoni Polychroniadou and Dale L. Sibborn.

They provide many attack, however answer that they give is that the bound is more or less the same as Coppermith's <code>logN/4 bits</code>. The nice thing is that the bound remains even for the case of random bits. A nice thing about the algorithm is that you can retrieve the correct factorization even if sometimes you are given the wrong bit value (allows error correction).
However, it can go even lower.

blocks|key|878355|text|我认为最有效的方法是泄漏适当西格玛的位，它描述了光滑的椭圆曲线，这将导致在一定工作量之后进行因式分解。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|entityMap^0^^$0|@$1|2|3|4|5|6|7|C|8|@]|9|@]|A|$]]]|B|$]]

I imagine that it would be most efficient to leak bits of an appropriate sigma which describes an elliptic curve of smooth order which would lead to a factorization after a tolerable amount of work

blocks|key|2018361|text|如果您想要故意泄漏信息，以便特定实体可以考虑N，但它通常是安全的，因为这是我可以从您的下一篇文章中了解到的，您必须查看设置(带有通用保护的秘密嵌入陷阱门)。最初的作品来自于Young+&+Yung，参见：http://dl.acm.org/citation.cfm?id=706030|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|entityMap|0|LINK|mutability|MUTABLE|url|http://dl.acm.org/citation.cfm?id=706030^0|2U|14|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@$A|L|B|M|1|N]]|C|$]]]|D|$E|$5|F|G|H|C|$I|J]]]]

If you want to deliberately leak information, so that specific entities can factor N, but it is generally secure, because this is what I can understand from your next post the you have to look into SETUPs (Secretly Embedded Trapdoor with Universal Protection). The original work is from Young &amp; Yung see this: <a href="http://dl.acm.org/citation.cfm?id=706030" rel="nofollow">http://dl.acm.org/citation.cfm?id=706030</a>

blocks|key|878516|text|从数论和计算机科学的角度来看，这是一个非常有趣的问题.|type|unstyled|depth|inlineStyleRanges|entityRanges|data|878517|然而，如果你在考虑实用的方法，你可以“后门”一个系统，让后门把很少的信息传回给植入机，以便允许因式分解，也许还有另一种方式来看待它。您可以使用一个带有256位的PRNG来生成p，q.然后你可以泄漏256位或其中的某个子集。或者您完全可以避免泄漏:在生成了PRNG种子的熵之后，您可以用硬编码值或在攻击场景中可以推断的内容(从用户id、硬件序列号等)替换一些比特(例如，64位以外的所有位)。通过散列(如果PRNG是安全的话，可能没有必要)运行它，并使用它作为PRNG生成p，q的种子。然后您就可以强行执行到p，q只需使用2%5E64操作，即使系统似乎具有更高的安全性。如果在硬件(即硬件RNG)中不能提取硬编码值，那么您就有了这个优势--对于其他人来说，它确实需要2%5E256操作。|878518|发现别人的后门是可能的，本质上是“蛮横的”--强迫RNG，耗尽它映射到的子空间，注意到你得到的复制比预期的要多。你可以试着避开这种情况。因此，如果你比那些对系统进行审计的人拥有更高的蛮力能力，那么这种攻击效果最好。|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|H|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|I|8|@]|9|@]|A|$]]]|F|$]]

This is a very interesting question from a number-theoretic and computer scientific point-of-view. 

However if you were thinking about practical ways one could 'backdoor' a system and have the backdoor transmit as little information back to the implanter, so as to allow factorization, there might be another way to look at it though. You could generate p,q using a PRNG seeded with, say, 256-bits. Then you could leak the 256-bits or some subset thereof. Or you could avoid leaking at all: Having generated the entropy of seeding the PRNG, you could replace some of the bits (say all except for 64 bits) with a hardcoded value or something that could be inferred in an attack scenario (derived from user-id, hardware serial numbers etc). Run that through a hash (probably not necessary if the PRNG is secure) and use that as the seed for the PRNG for generating p,q. Then you would be able to brute-force your way to p,q using only 2^64 operations even though the system seemingly has a much higher level of security. If this was embedded in hardware (i.e. a hardware RNG) where the hardcoded value could not be extracted, you would have this advantage to yourself - for everyone else it truly would require 2^256 operations.

Discovering the backdoor by others, would be possible by essentially 'brute-forcing' the RNG, exhausting the subspace it maps into and notice that you get duplicates more often than expected. You could try circumventions against that. So the attack works best if you have a much higher capacity for brute-force than is available to those who would audit the system.

Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q.

Then, you would like to actually let me factor N, except you should tell me as few bits of information as possible. Say p and q are 4096 bits, then how many bits do you need to tell me in order for me to factor N in feasible amount of time?

Note that you can arbitrarily design how these bits are derived, as long as there is a PPT algorithm to compute these bits and there is a PPT algorithm to use these bits to factor N.

RSA leak bits to factor N

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

假设你随机生成大素数p和q，就像在RSA中一样，然后告诉我N=pq，而不是p或q。然后，你想让我考虑因素N，除了你应该告诉我尽可能少的信息。假设p和q是4096位，那么您需要告诉我多少位才能使我在可行的时间内考虑N？请注意，只要有一个PPT算法来计算这些比特，并且有一个PPT算法来使用这些比特来因子N，您就可以任意地设计这些比特的派生方式。

问RSA泄漏比特到因子N
EN

回答 4

Cryptography用户

Cryptography用户

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问RSA泄漏比特到因子NEN

回答 4

Cryptography用户

Cryptography用户

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问RSA泄漏比特到因子N
EN