Is it possible to generate an Ed25519 keypair that has a very similar public key as another keypair (fooling a casual visual comparison) or is this
\nas hard as solving one of SHA-512 or the discrete logarithm problem?
\n
\nThe core of the problem is finding a near first pre-image on the function $A = aB$ on an elliptic curve, where $A$ is the public key, and $a$ the private key\u00b9.<\/p>\n
For a normal hash function you $ 2^m $ operations to fix $m$ specific bits.\u00b2 In particular a full pre-image takes $ 2^n $ hash function calls.<\/p>\n
A full pre-image on $A = aB$ is equivalent to solving the discrete logarithm problem on that curve. This problem only needs $ 2^{n\/2} $ operations, which is something around $ 2^{126} $ for Ed25519\u00b3. i.e. much faster than for a hash function, but still prohibitively slow.<\/p>\n
Now the interesting question is, if you want to find only $ m < 126 $ matching bits, how much work do you need? And I can't answer that, so this doesn't really answer your question. I know of no way to do this faster than brute-force, but I'm certainly no expert on this matter.\n\n\u00b9 The standard implementation of Ed25519 does use a different private key $k$ from which $a$ is derived via hashing, but an attacker would simply skip that step, so we can ignore it. It does not affect security.\n\n\u00b2 If you don't care about which bits you fix, then the problem becomes a bit easier than $ 2^m $ but it doesn't matter that much.\n\n\u00b3 I believe Curve25519 has a small subgroup, reducing security by a few bits, so I assumed a 126 bit security level. A few bits more or less don't matter, especially since one \"operation\" can be much more expensive for some primitives than for others.\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Is it possible to generate an Ed25519 keypair that has a very similar public key as another keypair (fooling a casual visual comparison) or is this<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"","_seopress_titles_title":"","_seopress_titles_desc":"","_seopress_robots_index":"","jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[93,139],"tags":[2864],"class_list":["post-13210","post","type-post","status-publish","format-standard","hentry","category-privacy","category-tools","tag-crypto"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p4bBYZ-3r4","_links":{"self":[{"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/posts\/13210","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/comments?post=13210"}],"version-history":[{"count":1,"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/posts\/13210\/revisions"}],"predecessor-version":[{"id":13211,"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/posts\/13210\/revisions\/13211"}],"wp:attachment":[{"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/media?parent=13210"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/categories?post=13210"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/deepquest.code511.com\/blog\/wp-json\/wp\/v2\/tags?post=13210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}