More factored RSA keys, and assorted other considerations

Wednesday, 20 May, Year 7 d.Tr. | Author: Mircea Popescu

This is going to be a lengthy article that - like pretty much everything elsei on Trilema - deals with complex matter broadly unfamiliar to most certified experts in the respective fields, let alone the general public. To avoid personal injury, tread softly, mutter to yourself quietly and re-read insistently.

Part One : The Conundrum

The verbiage on Phuctor's theory page reads in relevant part :

We do not display factored keys, at all, nor do we display factored moduli per se (but an attacker keeping close tabs on the universal product might, conceivably, obtain some sort of a guess). Should your key prove to be weak we will try to email you a notification. We will also remove your key from the site, so your previously working url would no longer work. Thus you have two ready ways to identify such an emergency : either by receiving an email warning, if your email address quoted in the key works, or by failing to find your key after you had introduced it.

When Phuctor was originally released, back in October 2013, it was intended and consequently designed as a user-powered, one signature at a time sort of affair. This changed later on, when we decided to allocate actual computational resources to the task. At that time the approach changed in tandem, from "wait for users to post a key" to simply churning the entire keyserver set. This evolution leaves that verbiage in the lurch, or as Stan put it, "I still can't fathom why you threw that in there."

I obviously can fathom - after all, I'm the one that put it in. The admittedly parochial logic behind it was based on some presuppositions meanwhile invalidated : 1) that the set of tested keys will at all points be a minor fraction of the total visible keys ; 2) that the set of weak keys found will at all points be so tiny as to not raise significant problems with emailing the owners and 3) that we are acting in a world that is both larger than us and more important than us, a sleeping giant that we do not wish to upset.

Experience hence has shown the folly of all these presuppositions, as experience always does. Specifically :

As far as the first is concerned, there are strictly insurmountable problems with keeping information secret. "Information wants to be free" may not be sensu stricto correct, and may certainly be entirely nonsensical as used by the derps that came up with it. Nevertheless, there is something there : how would I keep anyone who feels like it from running the same very basic math on the same publicly accessible set of numbers ? Upon meditation, the "for all we know others unknown are at the current time in possession of the same information we have" problem can not actually be resolved through increasing the paranoia level with regards to server security from just under nine thousand to well over nine thousand. One doesn't need to root my computer in order to add two and two, he can do that on his own computer just as well.

This aside, how exactly is one going to implement the "we won't tell on your key" policy ? Do we show all keys as "passed" even if they aren't ? ♫But you don't want to lie, not to the young...♪ Yet if we don't, what is the difference between the key not being displayed and the key getting a big fat red warning ? Obviously, some naive observers might be fooled. Cui bono, fooling the naive observers ? The entire point of this entire exercise is to reduce the disadvantage of the naive, after all.

As far as the second is concerned, we went in with the expectation, and I quote,

Since there's about 4 million keys (a little under) in the bundle of publicly known keys that it is processing, if you're even vaguely mathematically literate and even marginally aware of what exactly theoretical RSA promises, you would on the strength of this introduction expect a key to be factored just a little before Elvis comes back as the Queen of England. So did we. So did everyone else.

There was absolutely no expectation any key will ever be factored through this mechanism. Ever. This is the truth.

As far as the third is concerned, well... let's give the mic over to Naggum for a moment :

The problem is that "exploitation" happens only to people stupider (and consequently less informed) than the "exploiter".

The root cause of this whole world problem is that some people are smarter than others. There are two basic solutions to this problem: Kill all the morons, or kill all the brains. If you look at how several political regimes have behaved throughout history, you might get the impression that they are precisely adopting one of those two options. (Social democracy is a little more advanced: Kill everything outside 2 sigma.) World history and evolution and nature in general keep telling us something we humans do not want to hear: Some people _have_ to die for the rest of us to live better. The only question that political systems can answer is _who_ gets to live or die. Those who do not realize this will not live well before they die young. Our current political systems have created a world where people are afraid that we are not "sustainable". Of course we are not. But instead of killing contemporary people, we are killing future people. It is definitely not sustainable to keep everybody alive forever. We will, eventually, resort to killing a lot of people, and I mean a _lot_, like probably half of the planet's population, because, like fruit flies in a laboratory jar that runs out of sugar, we will be too many before we get the point. And that is OK with me, I do not plan to hang around forever, and neither do I want children to make things worse. But in the end, nature exploited us, not vice versa, because people are generally stupid and ill-informed about the choices they make. (Which is probably what some people _really_ mean when they say people are not rational.)

The fact of the matter is that we're people well outside two sigmaii, which means both that "the world" is roughly the size of half a chickenshit in comparison, and already as hostile as it can ever get.

Seriously, I should care that "the Internet community" will get upset, for reasons ? Fuck "the Internet community", I wouldn't trade away a strand of chewed gum for the whole lot of it. Moreover, it's already upset. It'll never get more upset. The mere fact that we exist punctures its ever-paramount narrative, and that's really all it takes and all there is.

The "Internet community" of dullards, normies and business majors is fundamentally lazy, fundamentally stupid, and already penned and handled by the exact people who should be handling it. Not our problem, not our interest and not a valid point of consideration or concern or in other words - If you're not in the WoT, you are not a person.

So therefore, for the aforestated reasons and after very careful deliberationiii, the original policy is rescinded. We will be publishing broken keys freely, periodically, and without any attempt to insulate their owners or anyone else from the fallout. That's it.

Part Two : The Broken Keys

We have thirteeniv fifteen keys so far.v Here they are :

  1. 51EAB526D87542022AA1BC85E99EF4B451221121vi [H. Peter Anvin <>; H. Peter Anvin (hpa) <>; H. Peter Anvin <>;], divisible by 231.
  2. 1482E27395532CEC191ADD937765EA7193E6924Cvii [Tony Pelaez (HarryGuerilla) <>;], divisible by 21.
  3. EF010E6F351E447C96C91AF1293987A8466F60E1viii, [Debarshi Ray <>; Debarshi Ray (GNU Developer) <>; Debarshi Ray (GMail Account) <>; Debarshi Ray (Red Hat Employee) <>; Debarshi Ray (Fedora Packager) <>; Debarshi Ray (GNOME Developer) <>; Debarshi Ray (GNOME Foundation Member) <>; Debarshi Ray ( Developer) <>; Debarshi Ray (Student at University of Helsinki) <>;], divisible by 9.
  4. A50591247C8E37A64117B74F78AB527059E13694 and B01584E9F6CB9E76DEA61E2A73786CA0F4EACC4Fix [grenzenlosnaiv <>;], divisible by 17742509903907 and 4294967297 respectively.x
  5. 1F75CF2DD19ABC516D58454B0846265183C9F86F and 29A9D31313C5E0E8B73F8D155CF76C1F591D4EFFxi [Saeid <>;], divisible by 73014444049 and 270582939711 respectively.
  6. 89FAD5E452080D47B11508148CA2B56B92E193C9xii [Lou Anschuetz <>;], divisible by 4294967297.
  7. C1FEDFCEADA4849AFE940D192979698801093DA6 and 51D1FBC806EBF7EFA78D74092E271AF5D8322944xiii [Christopher Winterbottom <>;], divisible by 98784247831 and 30064771079 respectively.
  8. F353FA51752FD981FE926C60E863669BEC4DA8F3 and F1573FEF30BE4BE50CD109AC3CAC41B5194C8916xiv [Li-Wen Kuo <>;], divisible by 12884901891 and 21474836485 respectively.
  9. F1D9FE5073EC39F3558905668C97B382AC1729F4xv [Tobias Michelis <>;], divisible by 4294967297.
  10. 1A5E4C59222FF18F2D5E2406E1548C609A6137AA and C8749C423CCE71A1230B138D2342919EC10A9C5Cxvi [Sebastian Heberer <>;], divisible by 4294967297 and 12884901891 respectively.

Part Three : Discussion

First off, and to get this out of the way : Hanno Böck just got caught lying. Specifically :

Last year I started a project to analyze the data on the PGP key servers. And at some point I thought I had found a large number of vulnerable PGP keys – including the key in question here. In a rush I wrote a mail to all people affected. Only later I found out that something was not right and I wrote to all affected people again apologizing. Most of the keys I thought I had found were just faulty keys on the key servers.

He did no such thing. Had he done such a thing, or anything even remotely similar to it, he would know about all thisxvii. That he has absolutely no idea about any of it, yet finds it within himself to make all-knowing statements of a certain tendency is all the smoking gun anyone could ever need.xviii

I hold Paul Graham personally responsible for the fraudulent shenanigans dissected in On how the factored 4096 RSA keys story was handled, and what it means to you, and I expect an apology. Let me also underscore that I smushed the last too-big-for-his-britches schmuck that owed me an apology and failed to make good. Don't make me Karpeles you, Graham.

Second off, you will notice the heterogenity of these vulnerable keys. For instance : not all of them are "signed" by simply copying the signature block off a valid key, like it was the case with the first one found. Some are not signed at all - which notably means that yes gpg will import, and yes gpg will use. A few are actually validly self-signed. There goes that "cosmic ray" theory, as entertaining as it was.

Third off, what do you make of this :

rsa-mystery-one rsa-mystery-two

rsa-mystery-three rsa-mystery-four

Here's what Stan made of it :


import pgpdump
import sys
import os
from shutil import copy


def get_rsa(pgpasc):
    mods = []
    exps = []
        packets = list(pgpdump.AsciiData(pgpasc).packets())
        for p in packets:
            if hasattr(p, 'modulus') and (p.modulus != None):
                mods += [p.modulus]
            if hasattr(p, 'exponent') and (p.exponent != None):
                exps += [p.exponent]
    except Exception, e:
        print e
    return [mods, exps]

## Litmus for Shitgnomancy
def litmus(path):
    mods, exps = get_rsa(open(path, 'r').read())
    ## Heuristic: at least one absurdly large exponent?
    for e in exps:
        if e > 65537:
            return True
    ## Heuristic: at least one possibly-shitgnomiferous modulus?
    for m in mods:
        if (m & 0xFFFFFFFF) == ( (m >> 32) & 0xFFFFFFFF):
            return True


indir = sys.argv[1]
outdir = sys.argv[2]
pgpfiles = [os.path.join(indir,fn) for fn in next(os.walk(indir))[2]]
keys = sorted(filter(lambda x: x.endswith('.gpg.asc'), pgpfiles))

## Test each key in indir and if heuristic positive, copy to outdir.
for k in keys:
    if litmus(k):
        print "Result: {0}".format(k)
        copy(k, outdir)

To let him explain :

Dear MP,

It appears that we have... something. Heuristic worked as follows (see :

1. Flag RSA keys with outlandishly large exponents. This yielded up many things but no clear pattern thus far. We table it for later.
2. Flag RSA keys which appear to have the repeating 32-bit word pattern seen in the earlier curios. This ended up hitting pay dirt.

litmus_mod_only contains the keys themselves. lusers.txt contains the parsed-out emails claimed in the keys. Start by reading these.


Would you like to see the paydirt ? Sure. Here you go :

  1. Ludwig Hügelschäfer <>
  2. Ludwig Hügelschäfer <>
  3. Ludwig Hügelschäfer <>
  4. Ludwig Hügelschäfer <>
  5. grenzenlosnaiv <>
  6. Saeid <>
  7. Lou Anschuetz <>
  8. Christopher Winterbottom <>
  9. Li-Wen Kuo <>
  10. Tobias Michelis <>
  11. Sebastian Heberer <>
  12. Kosta <>
  13. Christoph Giesel <>
  14. Christoph Giesel <>
  15. Christoph Giesel <>
  16. Raymond Häb <>
  17. Raymond Häb <>
  18. Raymond Häb <>
  19. Kristof Koerner <>
  20. Kristof Koerner <>
  21. Kristof Koerner <>
  22. Daniel Düngel <>
  23. PGP Global Directory Verification Key
  24. Philippe Baeriswyl <>
  25. Charly Avital(RSA4096) <>
  26. Charly Avital (RSA-AES256) <>
  27. Matthias <>
  28. Ismael de Moura Costa (email pessoal) <>
  29. Tim Fiedler <>
  30. Marcus Benjamin <>
  31. Stefan Thöne <>
  32. Thomas Scholz <>
  33. Thomas Scholz <>
  34. Thomas Scholz <>
  35. Thomas Scholz <>
  36. Thomas Scholz <>
  37. Thomas Scholz <>
  38. Thomas Scholz <>
  39. Thomas Scholz <>
  40. Thomas Scholz <>
  41. Thomas Scholz RUM-CA <>
  42. Thomas Scholz <>
  43. Thomas Scholz <>
  44. Thomas Scholz <>
  45. Thomas Scholz INTERN <>
  46. Thomas Scholz <>
  47. (official homepage)
  48. Shumitsu Muryokoin <>
  49. Martin M. Stoppler <>
  50. 4D Admilon Consulting <>
  51. Felix Arndt <>
  52. Dominik Rapp <>
  53. Henry Hertz Hobbit <>
  54. Henry Hertz Hobbit <>
  55. Henry Hertz Hobbit <>
  56. Henry Hertz Hobbit <>
  57. Michael Starck <>
  58. Robert Manigk <>
  59. Shingondo <>
  60. Ben Donnachie <>
  61. Ben Donnachie <>
  62. Ben Donnachie <>
  63. Benjamin Donnachie <>
  64. Ben Donnachie <>
  65. Ben Donnachie <>
  66. Benjamin Donnachie <>
  67. Matthias Klein <>
  68. Matthias Klein <>
  69. Matthias Klein <>
  70. Matthias Klein <>
  71. Matthias Klein <>
  72. Matthias Klein <>
  73. Matthias Klein <>
  74. Matthias Klein <>
  75. Thomas Weitzel <>
  76. Tim Fiedler <>
  77. Christopher Hart <>
  78. Jeremy Low <>
  79. Axel Rau (Computing -squee- Chaos Claudius) <Axel.Rau-squee-Chaos1.DE>
  80. Carl Christoph Leimbrock <>
  81. <>
  82. Jürgen Neuwirth <>
  83. Charly Avital (Test2) <>
  84. Vincent Thenhart <>
  85. Vincent Thenhart <>
  86. Charly Avital <>
  87. Charly Avital (GnuPG) <>
  88. Charly Avital <>
  89. SlowFax <>
  90. Christian Vögl <>
  91. Robert L. Vaessen (MobileMe key generated with gpg) <>
  92. Robert J. Hansen
  93. Robert J. Hansen <>
  94. Karsten Krüger (Privater Key von Karsten Krüger) <>
  95. Martin Weinelt <>
  96. Martin Weinelt <>
  97. Martin Weinelt <>
  98. Martin Weinelt (BP DART-Racing WS2010/11) <>
  99. Archive Automatic Signing Key (sur5r) <>
  100. Leonardo Zillo Monte Xillo <>
  101. Piraten | Martin Letzel <>
  102. Stefan Körner <>
  103. Apple Product Security <>
  104. Torsten Ennenbach <>
  105. Paul Karrer <>
  106. Konstantin Pisarenko <>
  107. Andreas Heimann <>
  108. Henry Irish <>
  109. Lukas D. Jacobs <>
  110. Lukas D. Jacobs <>
  111. Lukas David Jacobs <>
  112. Lukas David Jacobs <>
  113. Kristian Biss (Mfr Voll Name) <>
  114. Trotzik (Bei Zeus die Dicken schon wieder) <>
  115. Stephen Domorod III (Stephen at Domorod dot Org) <>
  116. Matthias Pannek <>
  117. Jeffrey Rolland <>
  118. Christian Busch <>
  119. Christian Busch (Jabber) <>
  120. Charly Avital (1.0.7) <>
  121. Charly Avital (1.0.7) <>
  122. Charly Avital (1.0.7) <>
  123. Larry B. Macy, Ph.D. <>
  124. <>
  125. Andrew Orr <>
  126. Jochen Schäfer <>
  127. Jochen Schäfer <>
  128. Jochen Schäfer <>
  129. Luciano Buszmicz (Never forget: 2 + 2 = 5 for extremely large values of 2.) <>
  130. Herbert Saurugg <>
  131. Herbert Saurugg (aufgrund der Umstellung auf BMLVS - 2009) <>
  132. Karsten Krüger (für die vertraulichen Dinge des Lebens) <>
  133. Marco Hien <>
  134. M_Schmidt Admilon <>
  135. PGP Corporation Update Signing Key
  136. PGP Corporation Update Signing Key <>
  137. Sven Arnold <>
  138. Julia Reda <>
  139. Kai Schmalenbach <>
  140. Kai Schmalenbach <>
  141. Kai Schmalenbach <>
  142. Thomas Hofmann <>
  143. Andreas Heimann <>
  144. Matthias_Schmidt <>
  145. Paul Okkerse (Hoofd ICT) <>
  146. Simon Lange <>
  147. Andreas Fleig <>
  148. Carl Christoph Leimbrock <>
  149. Carsten Lenz <>
  150. Matthias Schmidt <>
  151. Stephan Urbach <>
  152. Herr Urbach <>
  153. Tim Fiedler <>
  154. Raphael Randschau <>
  155. Raphael Nicolai Fabian Randschau (Uni Kiel) <>
  156. Marcus Benjamin <>
  157. Marcus Benjamin <>
  158. Christoph Giesel <>
  159. Heiko <>
  160. <>
  161. Shell Arkell <>
  162. Ralf Oltmanns <>
  163. Ralf Oltmanns <>
  164. Ralf Oltmanns <>
  165. Ralf Oltmanns (Piratenpartei Deutschland Landesverband Bayern) <>

Are you on this list ? We probably have your private key.xix

And the best part ? I'm not even sure this was actually what the shitgnomes were trying to cover up. Stay tuned, the saga of Phuctor continues.

PS. I am really looking forward to more "oh, we did this last year and forgot to mention it to anyone" + "oh nothing really happened, it's just how the Internet works" + assorted nonsense. Go for it boys, the comedy goldmines await your labour!

  1. I am aware most articles are written in a manner that makes them superficially appear approachable, easy and fun. This is absolutely never the case. I would know, because I write them. They are fun to write, yes, but they're not supposed to be fun to read. []
  2. I don't mean him, or me, I mean us. This is what the entire point of the Republic is : a place for the only people who matter, that "just so happen" to be the people everyone's trying to murder. []
  3. I seriously lost two nights' sleep over this, which is rare with me. []
  4. Fuck me it found two more while I was doing the write-up. []
  5. So far in this context means that Phuctor has processed 159`336 keys. []
  6. Numeric value : 8170230239603769466339755071101546492494075988067987304148498844617761721719
    92099083804597481699305852902662863062054067183925164590726103552998367994727700722491707. []
  7. Numeric value : 3031874832053583743418292416372595502099634576341315290167303447940896540435
    4263519. []
  8. Numeric value : 8197390857930122495849886562470137189068756241045853345396708829779573185913
    15342770779317932920084062741642010198566264962129579715127047847615770686855802050721189. []
  9. Numeric values : 25526728199009057709398989586453690214904358229000555691738418155709599299


    86307186831172171955343555350038959105541680962601456297155387993164183508343. []

  10. Noting that 17742509903907 / 4294967297 = 4131 and the German meaning of the "grenzenlosnaiv" string, it is very likely this key exists as a training exercise for parties unknown. []
  11. Numeric values : 16672257823521270371961164662125862296899812729169425291114489871863688113


    6521547118378104303751147008586189340679520589366968743556304798004917247994251759. []

  12. Numeric value : 117964043832425833134470740787358129784114456283752419342645582340953251431
    54500851. []
  13. Numeric values : 816708949049219316249137802707618040343445921615851995965391153505370824748


    5009854277225103956061247800498802170252261111710555365880816565908566722983. []

  14. Numeric values : 753231629734215095039311089646892853049081111032594923534482075739340266016


    7126620137630199683458747749046869956250863673881944589932269914259206065385. []

  15. Numeric value : 231036427461512813069782326469186742089206935382435884936326148373384936826
    63937409. []
  16. Numeric values : 222567807409507066819438199932606490824445396425529801468396492110367893


    58454923247735276780281924575559176175868196226600684019529354735523015770359339135. []

  17. Not to mention he wouldn't feel the need to use eight heaps of vague in the shape of "at some point" "large number" "something was not right" "most of the keys" bla bla in a four line paragraph.

    Seriously bitch, you did shit at some point last year ? What did you do, other than father a large number of Angelina Jolie's children, until you discovered that something was not right with most of her tits ?

    Dumbass. []

  18. Also, the claim that "keyservers will just accept any random data" is rank nonsense. If they did, I could just store fifty terrabytes worth of broken keys on their drives. But we'll leave this discussion for when the #b-a keyserver actually comes online. []
  19. You will notice that most but not all the names in the first list are also in the second list. Of the ones that are on both lists, some have a surviving key (so far). Others, like for instance Sebastian Heberer, do not.

    Of the names that are only on the first list, all seem to be sharing the "divisible by very low factors" and "fake key with pasted over signature block" characteristics of the original HPA key.

    It would appear then that there are at least two different classes of diddled keys visible in the public keyset. (Three if you count obvious exercises like EF010E6F351E447C96C91AF1293987A8466F60E1 separately). []

Category: Breaking News
Comments feed : RSS 2.0. Leave your own comment below, or send a trackback.

18 Responses

  1. grenzenlosnaive`s avatar
    Thursday, 21 May 2015

    > grenzenlosnaiv


  2. grenzenlosnaive`s avatar
    Thursday, 21 May 2015

    Even if the 'obscure German mail client' thing was bullshit, it strikes how well represented Germany is in the list of lusers.

  3. Mircea Popescu`s avatar
    Mircea Popescu 
    Thursday, 21 May 2015

    This it does.

    Care to share the story of the Grepunzel key ?

  4. Out of curiosity, did you obtain complete factorizations of any of the RSA moduli above?
    Computing \phi(n), and thus the secret exponent d is unfeasible without knowing the complete factorization of n and even in the case of an ill formed (e.g. random large number) n significantly large factors are most likely to be in.
    In case you got complete factorizations, did you check whether the self-signature on the pubkey packet was correctly reproducible with your private key? Otherwise, this may just be the result of a corruption of key material (not good on the functional standpoint, but not a broken keypair).

  5. Mircea Popescu`s avatar
    Mircea Popescu 
    Friday, 22 May 2015

    The assumption that "large factors are likely to be in a random large n" is incorrect. The probabilty is computable and not very high. The rest of your questions are actually covered in the source material - reading which is both a required by your declared curiosity and unavoidable from a comprehension standpoint. There really is nothing one can do to understand something other than read.

  6. lobbes`s avatar
    Friday, 22 May 2015

    Thank you for spelling this shit out for me. I know enough to know I understand roughly none of it, but also know enough to know that I should put in the time to educate myself.

    The problem is usually having no way of knowing what source material is a) relevant and b) valid

  7. Mircea Popescu`s avatar
    Mircea Popescu 
    Friday, 22 May 2015

    So it is. The meagre counterpart to that problem being that as one attempts to educate himself, the differences between relevant and irrelevant, valid and invalid become more and more apparent, and readily observable. So it's not all midnight black.

  8. Concerning the b-smoothness of large n: can you provide a quantitative estimate of the largest factors as a function of the size of n instead of "not very high"?

    Having read the source material again, I could not find any evidence of validation of the correct retrieval of the secret keys.
    The only claim explicitly made is that some of them are divisible by a known factor, but nothing is said on the primality of the remaining cofactor.
    If the remaining cofactor is not prime, n has not been factored, and thus the secret exponent cannot be computed.

    For instance, take the modulus of:
    EF010E6F351E447C96C91AF1293987A8466F60E1 Debarshi Ray
    In the provided material you note that it's divisible by nine, but the result of the division is not prime.
    In particular, the cofactor is divisible by 110923,199974947 (obtained via a run of Pollard's p-1) and the
    remaining cofactor from these divisions is still not prime (Miller-Rabin primality test, which yields
    no false positives for compositeness).
    Similarly, the modulus of Peter Anvin's key is also divisible by 19 and 7704959, in addition to 3, 7 and 11 as
    you pointed out, and the cofactor is still composite in this case too.
    Thus, given the provided material, there is no evidence in the provided material that you know the complete
    factorization of the modulus of the key.

    I would regard as non deniable evidence something as text file signed by the private key corresponding to one of the keypairs
    claimed to be broken containing, e.g., this post.

  9. Alex,

    Take a look at precisely how this class of mutilated keys (which include your example) was created. Specifically,

    1) 64-bit window over the legit modulus is taken, where upper 32 are set to equal the lower. Then move 64 upwards, repeat.

    2) The public exponent is changed to 281479271743489.

    I have not yet taken the time to work out the number-theoretic implications of (1). However, my current conjecture is that it has essentially the same effect as choosing an entirely random integer for the modulus.

    As for (2), the enemy (it is abundantly clear that we are looking at the work of human hands) may very well be relying on possession of known signatures to make use of (2).

    In short, we do not yet know for how many of the samples the private key may be obtained with reasonable effort, publicly-known methods, and while lacking any samples of material signed with these keys.

    Plenty of work to be done here!

  10. Mircea Popescu`s avatar
    Mircea Popescu 
    Friday, 22 May 2015

    @Alex It is difficult to estimate how much you know about the topic on the basis of what you've said so far, but perhaps might be interesting ?

    In particular, the cofactor is divisible by 110923,199974947

    The full factorization of the found keys was deliberately left as an exercise to the reader, for now. See here.

    What you would regard or wouldn't regard as whatever is a matter about as interesting as what any other "Alex" thinks about the weather and the Queen of England. Ye ken ?

  11. Obama
    Obama's Red Stapler 
    Friday, 22 May 2015

    > Miller-Rabin primality test, which yields
    > no false positives for compositeness

    This is incorrect. The original Miller algorithm was deterministic, but it relied on an unproven assertion about the zeros of a certain L-function. The Rabin upgrade removed that problem and also made it probabilistic, which means that both the quality of your RNG and the count of runs are important in estimating the likeliness of corectness of your result. This becomes especially relevant with large numbers, as Apocalyptic correctly points out here.

  12. Mircea Popescu`s avatar
    Mircea Popescu 
    Friday, 22 May 2015

    What he literally says is that M-R yields no false composites, which IS correct : if you get a factor of n, you've most definitely got a factor of n (also trivial to check).

    Meanwhile he is apparently turning around and using that as if it meant that M-R yielding no factor means n is prime, which indeed is incorrect.

  13. Peru Ana`s avatar
    Peru Ana 
    Friday, 22 May 2015

    Not my field, but I have been trying to follow the discussions. I read the tree Trilema articles on the topic and most of the #bitcoin-assets discussions. There is one thing I don't understand: if the large number N is the product of two primes, p and q, and someone obtains two other numbers, p' and q' which while prime or not nevertheless multiply to the same N, are not they now able to do anything the owner (who has p and q) can do, whatever that may be?

    .p = 7 and q = 12, mistakenly believed by owner to be prime. So N = 84.
    .Phuctor finds that 84 is divisible by 3.
    .p'=28 and q' = 3 can now be constructed, so that N' = N = 84.
    Why does it matter whether p' is a prime or is not a prime? Apparently somehow RSA worked with q not being prime, so why wouldn't it work with p' not being prime?


  14. Mircea Popescu`s avatar
    Mircea Popescu 
    Friday, 22 April 2016

    If N is the product of two prime numbers, there exist no other numbers that multiplied yield the same N.

  15. CTRL-Fing phuctor stats pages for my name is the only news I need "on the inside".

    Hope everybody is happy with the MPExplosion! Fireworks are the best, forget the rest, I'm a pyromaniac under test//////////

  1. [...] discussed prior (principally having to do with how the part of the world made up by you sucks irredeemably, by the way) Phuctor now very conveniently links broken keys straight off its stats page. Let's [...]

  2. [...] of course, is not without its own pitfalls. [↩]Such as perhaps an overflow of some kind, as the most obvious, banal example. [↩] [...]

  3. [...] might remember Hanno Böck getting caught lying back in 2015 : Hanno Böck just got caught lying. Specifically : Last year I started a project to [...]

Add your cents! »
    If this is your first comment, it will wait to be approved. This usually takes a few hours. Subsequent comments are not delayed.