gistfile1.txt

I had a chat with a buddy of mine (Topi Talvitie) who's a postdoc researcher here at Helsinki Uni.
He reverse engineered the logic on how a fake solver algorithm, such as the one by Grant's, can be created. 
I've tried to to translate it the best I can:

-------------

The goal is to find integers p and q so that pq = N [N being the public key].

The problem is then rephrased so that the goal is to find a single integer C = (p+q) / 2. 
This is because finding the value of a single variable appears easier than solving an equation with two variables.

This works because if C is known, then evidently 

    p = C - A, and
    q = C + A

with some A which is easy to find:

N
  = pq 
  = (C-A) * (C+A) 
  = C² - A²

and then,

A² = C² - N
A  = √(C² - N)

The only requirement for C is, A needs to be an integer.
Because the requirement resembles the Pythagorean Theorem, a new value is defined: B = √(N), 

The goal is now to find C in a situation where A = √(C² - B²) and where A is an integer.

So again, the goal is to find hypotenuse C in an equation where one cathetus is B, and the other cathetus A is an integer.
The next step is to add further obfuscation with binomial square rule: C² - B² = (C - B) (C + B) 
But this obfuscation is too easy, so the variable, that needs to be solved, is swapped. Instead of C, the goal now is to solve w = C - B. 
Now, the C²-B² can be swapped to less suspicious form w * (2B + w).
Now the goal is to find w so that the variable C = w+B and A = √(w * (2B + w)) where both A and C are integers.
The requirement "w+B needs to be an integer" seems out of place, so it is fixed by defining r = ceil(B) - B, and by switching the variable x = w-r.
Thus, w = x+r. Now, 

w+B 
= x +       r     + B 
= x + ceil(B) - B + B
= x + ceil(B)

x+ceil(B) is an integer iff x is an integer.

Now the goal is to find x so that A = √( (x+r) * ((2B) + (x+r))  ) where A is an integer.

------------------

The rest is my own handwriting based on Topi's work:

One thing that needs doing is to fix Grant's mistake of saying (x+r) * ((2B) + (x+r)) solves A, it actually solves A².

So there you have it, the bullshit algorithm can trivially be expanded from the intial problem, 
but only if you have the prime factors ready, creating the algorithm started from 89*137=12193.


-----------------

To show this step by step with real numbers:

12193

  = 89 * 137             Since we're designing the scam algorithm, we can be clever and start with the solution p=89, q=137.
                         This is simply because we know it's impossible to factor semiprimes in constant time. The only
                         way that can be done is if we know the answer beforehand.
                         
                         But for our scam to succeed, we need to obfuscate the fact we knew the prime factors. The 
                         obfuscation is done in the next step, and for that we'll need to define two values:
  
                         Middle point between the two primes = (89+137) / 2
                                                             = 226      / 2
                                                             = 113

                         The distance of each prime from middle point (113)
                                      |137 - 113| = 24
                                      |89  - 113| = 24

  = (113-24) * (113+24)  Now, to obfuscate that the algorithm has the values of the primes baked in, we express 
                         them with the two values defined above: middle point +- distance from middle point.

                         This single layer of obfuscation is trivial to detect. For next obfuscation we realize
                         the current representation of the primes is aching to the binomial square rule:
                             a²-b² = (a+b)(a-b)

                         So we'll use the rule to hide the middlepoint+distance data inside two perfect square values:
                            
  = 113² - 24²           On this line, the binomial square obfuscation is in place.
  
                         Furthermore, now the equation is of form
                             12193 = 113² - 24²
                           
                         This form reminds us of the Pythagorean theorem (A² + B² = C²) and more specifically, 
                         how a single cathetus is solved from the hypothenuse and the other cathetus:
                             B²    =  C²  - A²

                         We can now draw the triangle, and write down the sides:
                             * cathetus   A = 24 
                             * cathetus   B = √(12193) = 110.421918114
                             * hypotenuse C = 113

                         We also do a quick check for constraints for value A, i.e. that it must be an integer:
                             A² =   C² - N
                             A  = √(C² - N)

At this point we've succeeded in hiding the prime factors inside the values 24 and 113.
We realize we can e.g. use the two values to define the shape of a right-angle triangle.
We now need to be able to claim we can factor the semiprime B² with the help of Pythagoras.
That will season our scam with some ancient rules of mathematics and is intuitive for 
everyone who learned the Pythagorean Theorem at the basic school.

But there's a problem: Just like how the attacker can't deduce primes p and q from public key, 
the attacker can't define the shape of the triangle from just the length of one cathetus 
B = sqrt(public key)).

But if we can make it appear we have a solver for e.g. the cathetus A, that works when 
given just the cathetus B, we can then retrieve from the triangle the values we hid there
in the first place, and claim we've solved the semiprime factoring problem! 

    So let's create a fake algorithm for solving A, by starting from the obvious Pythagorean cathetus solver:

             A  = √(  C² -  B²)
             A² =     C² -  B²
                =   113² - 24²

     The binomial square obfuscation we used to hide the primes p and q is too easy to detect, so we 
     add further obfuscation by swapping variables, first by defining 
         w =  C  - B
           = 113 - 110.421918114
           = 2.578081885886448

     We then can express the hypotenuse as sum of two long floating point numbers:
         C = 113
           = B + w
           = 110.421918114 + 2.578081885886448

     Now, that we can replace C with B+w, the very revealing A² = C²-B² can be obfuscated to less suspicious form:
      
         A² =       C²           - B²
            =    (B + w)²        - B²
            = (B + w)(B + w)     - B²
            = B² + wB + wB + w²  - B² 

            = wB+wB + w² + B²-B²
            = wB+wB + w²  
            = w(B+B + w)
            = w(2B  + w) <--- This final reduced form (pay attention to this we'll come back to it in just a moment):
            
            = 2.578081885886448 * (2*110.421918114 + 2.578081885886448)

            We can double-check our scam solver algorithm works by copy-pasting the equation to e.g. wolframalpha.com
                24² == 2.578081885886448 * (2*110.421918114 + 2.578081885886448)

     ---
     
     Next, to hide the seemingly weird requirement that w+B (=C) must be an integer, we introduce another variable
         r = ceil(B) - B
         r = 111 - 110.421918114
         r = 0.5780818858864478

     We then craft yet another variable x that depends on r:
         x = w-r
         x = 2.5780818 - 0.5780818
         x = 2

     Now we've moved the decimals from w to separate variable r, and x has become the the integer part of w.
         w = x +       r
           = x + (ceil(B) - B)
           = 2 + (111 - 110.421918114)
           = 2.5780818

     We'll then use these variables to replace the "w" in the reduced form (the one you were asked to pay attention to above).
        A² =    w      (2B +    w   )
           = (x + r) * (2B + (x + r))   <-- Our scam algorithm is ready, it's here. If you look at Grant's side-A solver description:
                                            https://preview.redd.it/fqhf1mqd0b761.jpg?width=598&format=pjpg&auto=webp&s=3ab97efb7bb1d4be8ce07c9020384fdbed169e2b
                                            You'll notice it's identical.

        A² =  (x +     r)     * (2*B             + (x +      r  ))
           =  (2 + 0.5780818) * (2*110.421918114 + (2 + 0.5780818))                     
        A  = √(2 + 0.5780818) * (2*110.421918114 + (2 + 0.5780818))
           = 24

So again, the reason the algorithm pushes out A when given square root of the public key (B), as one of its cathetuses, 
is the shape of the triangle was pre-baked into the form that depends on knowing the length of the side A and the 
hypothenuse, that represent the private values.

The reason it works on paper is because the triangle was drawn beforehand. If I give you only the public key, you can get
side B by taking square root of it, and draw the first cathetus. But what you have is only a line. That line alone doesn't 
help you in drawing the rest of the triangle, unless you know the length of at least one other side of that triangle. And 
asking for one additional side of the triangle is the same as asking for just one of the secret primes p or q.
If you know public key N (=p*q) and one of the two secret values, e.g. q, you can get the another one trivially: p = N/q.

The pre-baked triangle shape only works with one specific public key, because we got the shape of the triangle when we 
started to obfuscate the prime factors we knew beforehand. That's the only way to draw the triangle.

To explain
    Length of side B is the square root of the public key. We know that already
    Lenght of side C is the middle point between the two secret primes p and q, i.e. something we as attacker don't know.
    Length of side A is the distance of both primes from the secret C (that again, we don't know), so we don't know A either.

So in order to be able to draw the triangle, we need to know the private key, and if we already know the private key, we're 
wasting our time if we're drawing triangles when we could be breaking the encryption instead.

The only way to use the algorithm to try to factor semi-primes, is to try values for A in order in a program such as

import math
public_key = ...
B = math.sqrt(public_key)
for A in range(0, 2**1024)):
    C = math.sqrt(A**2 + B**2)
    p = C-A
    q = C+A
    if p*q == public_key:
        print(f"{p}, {q}")
        exit(0)

This is literally trial division (=brute force attack) that runs in exponential time. It takes on average 2^1024 =
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000 operations. 

The universe will have reached heat death before a a single key is broken, it is therefore completely useless.

tl;dr: The algorithm only works if you know the private key beforehand. It's a scam.

Hej Markus. I read your comments on Schneier.com with great interest. Very comprehensive. Thank you.

Have you seen the video here, where Grant explains the way he obtained the triangle? If you have the time, I'd be interested to know your thoughts on that. The relevant part of the discussion starts around 55mins in, here, with the actual triangle discussion being at around 62 mins in, here.

UPDATE: I've logged into Instagram and I see the specific part of that YT video is available here. (If you have access to Instagram.)

Actually, it looks like I may have stumbled across the answer to my question, here.

Have you seen the video

The moment Gomez says "It looks like gibberish to me" is either the kindest way to call out Grant's bullshit, or the the interview is the polar opposite of adversarial journalism.

The number of factual errors on the video is out of this world. Calling the semiprime the public key itself, saying integer factorization is discrete logarithm, saying bitcoin depends on RSA... At 1:07:53 he says AES is used for encrypting stored data and asymmetric encryption is used to encrypt data in transit. He then claims there's no other approved types of "encryptions", and then contradicts himself by introducing OTPs. He then gives the impression only OTP is secure from quantum computers ignoring limitations of Grover... And then he claims he's able to expand OTPs from short seeds.

Grant explains the way he obtained the triangle

Yeah on 1:00:00 he says "the algorithm pops out a value I can put into Pythagorean Theory"
That's consistent with Talvitie's conjecture where one starts with the N=pq

N
  = pq 
  = (C-A) * (C+A)   (which is then obfuscated by expressing the primes as center point C between primes +- distance A)
  = C² - A²

and then,

A² = C² - N
A  = √(C² - N)

Because the requirement resembles the Pythagorean Theorem. You decide that B² = N, and thus B = √(N).

The ruler theory he spouts about values for A is hilarious considering A is defined as half the distance between the two primes which is always an integer.

The Wolframalpha equations again picked prime factors that are very close to one another.

BTW: I had a look at the range of values X really gets with RSA key sizes (512..896 bits):
https://gist.github.com/maqp/c4c86007122e93414436475a328e044f

You might find that interesting too.

Thanks very much. All very interesting and revealing. And, yes, the write up at https://gist.github.com/maqp/c4c86007122e93414436475a328e044f was also very interesting.

It would seem Grant either: 1) greatly over-estimates the value and significance of what he's coming up with and sharing, due a lack of even remotely full comprehension and understanding of the relevant topics; or, 2) he is hiding something he's not yet revealed (something that makes his work in this area far more significant that it currently appears to be); or, 3) he is actively trying to misled people.

Looking into his past, and his network of connections, etc., I would be very surprised if he was actively trying to dupe/con/mislead people. He stands to lose too much in terms of social status and kudos, and, what's more, it would appear to greatly contradict what I understand to be his personal values (based on a great deal of other things I've been able to dig up online). So, to me, that makes #3 highly unlikely.

#1 also seems unlikely, as he has more than enough money and connections, social clout, business expertise, product development expertise, etc., to not mistakenly put himself out on a limb believing something (a potential business product, etc.) is more significant than it really is. He could effortlessly call on, and pay for if necessary, any number of experts in cryptography and mathematics, to review his theories, and let if know if they have any merit.

So that leaves us with #2. That he is, for whatever reason, sitting on something that is in fact the crux of what he's come up with. I can't think of any meaningful reasons for doing this. Also, as you've pointed out in so many ways, what he has presented is so full of holes and errors, that it doesn't simply look like he's presenting a partial picture (and waiting to release the rest of the picture). The picture he has released or shared is, for the most part, a complete mess.

So, to me, I've yet to get a sense of why he's shared what he has, and has set up a business around it (i.e., c. sterling).

he is actively trying to misled people.

My money's on this one. The thing is, he's actively misrepresenting information. E.g., his claims constantly gloss over the important details such as can one really iterate up until X, or guess X (neither of which is the case as per the Gist I linked to in the comment above).

I have personally told him about the NIST requirement for |p-q| distance requirement checks in RSA keygen implementation, and I've told him about Fermat's factorization algorithm that is based on the same vulnerability where p and q are close to one another, but he won't hear it.

• He continues to claim discrete log is factorization despite having been told they're not the same.
• He claims Bitcoin "is now broken" because he can factor weak keys with an O(2^N) attack, but he's unable to demonstrate an actual attack on Bitcoin account.
• He claimed on Instagram AES has been broken without sourcing his claim, which is hilarious considering their front page says CrownEncrypt uses AES256.
• He also says discrete log is broken by his algorithm, yet according to the front page, the CrownEncrypt uses 512-bit ECDHE key exchange that's based on elliptic curve discrete log problem.
• The front page also talks about "The looming threat of quantum computing power", but fails to address the issue that Shor's quantum algorithm breaks 512-bit ECDHE before it breaks e.g. RSA-4096.).

He thus constantly contradicts himself and lies by omission.

When confronted, his tactic is effectively to argue the same point (in this case about the space of keys with small X) ad nauseam to make it seem its the other person "who's just not getting it". He spouts techno babble such as "it's a wave function" which is hard to address because there's no winning strategy: saying "now you're just faking it, that's not how any of this works" doesn't convince his audience.

His proofs about the algorithms runtime (which he claims is constant time) ignore worst case and average case scenarios. He can't even express his algorithm with pseudo-code or something as trivial as Python. Either because he lacks all basic skills of a computer scientist, or because he knows it's trivial to point out failures in his reasoning when the algorithm has to have an actual structure (such as loops) instead of displaying circular proofs with pre-determined X. It's also too easy to plug in an actual RSA keygen to show the algorithm runs into trouble with even trivial 512-bit RSA keys (as I showed)

He claims Excel can handle numbers larger than 47 bits, which is bullshit, as anyone who bothers to check will learn Excel's Double data type stores values up to 2^1024. Even floating point data can fit 64-bit values. But as running the brute force algorithm with keys that "large" takes in the order of hours / days / years to solve, he won't show it.

If you watch Grant's videos, you'll notice the emphasis in what he says, always loses authority when something's off: Either he tries to quickly skip over the part or he over-emhasizes something that omits something important. The goal here seems to be to steer your attention away away from the trick (stage magic 101). Maybe it's because he knows he's lying, or maybe he knows he doesn't know what he's talking about. It's funny and a bit sad at the same time.

Something that's also off, is the fact Crown Sterling first started with sub-exponential GNFS (a plagiarized version of CADO-NFS), they then moved to random trial division (the reciprocal factorization algo), and from there to the Pythagorean factorization crap that runs in O(2^N) time. Even key sizes suddenly dropped, they started by factoring 256-bit RSA key (Comparable to 40-bit symmetric key). But with the new reciprocal/pythagorean algorithms key sizes dropped to something like 13..47-bit RSA keys. Which is totally expected if you want the factoring to happen in seconds. Each time Grant et. al. have claimed to have done it, yet each time they fail to provide evidence that's credible in academic circles. All they need to do to prove their method works, is to factor the public RSA-2048 challenge, yet they don't, simply because the algorithm doesn't actually work.

Grant's story also keeps changing. At Blackhat Grant was adamant about not factoring large numbers because that would put e.g. online banks' certificates in danger. Now he's revealing the algorithm that can break all encryption in its entirety, in an Instagram post? For free. The value of such a method would be insane. He could sell the method to NSA or any near-peer adversarial nation for tens of billions of dollars. But does he write an academic paper and upload it on Arxiv's pre-print server for peer review? No. He makes an Instagram post. Something Squeamish Ossifrage emphasized too https://crypto.stackexchange.com/a/74620 (a wonderful read although I admit it goes a bit over my head).

Other things that scream bullshit: Grant is not speaking the language of cryptographers, his discourse is all wrong, but it's wound around seeds of truth. What unites the reciprocal factoring and Pythagorean factoring algorithms is the fact these algorithms are really easy to grasp for a layman. In both cases the demonstrations skip the computationall hard part, and appear to give instant results. Both of them are based on basic school math. Yet professional cryptographers with decades of expertise who have much broader intuitive grasp on mathematical concepts than the Pythagorean theorem, somehow can't see the problem can be solved in such trivial way. One example of this intuition is, it was trivial for Talvitie to reverse engineer how a scam solver algorithm can be created by obfuscating the N=pq with a few basic operations like the binomial expansion formulas.

There's a million ways to reach the same conclusion: It's bullshit. Math doesn't lie. If it worked, it would be trivial to prove it works. Proving it doesn't work shouldn't require paragraph after paragraph why it is bullshit. Yet it's really easy to do because none of it holds water.

He stands to lose too much in terms of social status and kudos

I wouldn't be too sure about that. If you look at his ventures in other contexts at https://strathspeycrown.com/subsidiary-companies-investments/ you'll find same people like Nassim Haramein working in pretty much all of them. Grant's lies have been called out in infosec circles ever since the Blackhat talk in July 2019, but that doesn't stop gullible investors and numerology fans from buying into it. Grant doesn't really enjoy prestige in academic circles. His publications aren't peer reviewed, and some have been refuted (see below).

it would appear to greatly contradict what I understand to be his personal values (based on a great deal of other things I've been able to dig up online)

Drawing conclusions from his posturing doesn't really prove anything from his intention to the correctness of his methods. There doesn't have to exist a video where he rubs his hands together and exposes his evil plot to scam people, to tell the methods are bullshit and motives to insist on them not to be, are questionable. The "he means good but is too emotionally invested to accept proofs he's wrong" narrative is the best plausiable deniability theory I can think of, and given how his actions have contradicted the very basic values of science like the pursuit of truth, shows this.

Math is an exact science with absolute proofs; his ignorance of e.g. Shannon's bad news lemma shows he's either ignorant or malicious wrt. the real world damage to people his implementation can cause: Cryptography is the equivalent of structural integrity engineering, and should not be left for Instagram influencers who take interest in numerology. (IIUC software engineering in the US requires basic competence, it'll be interesting to see if they'll actually find someone to write, and to release a product that relies on the bullshit crypto.)

Another aspect is lack of sincerity: Personally I would be devastated to learn my work that applies cryptography is insecure because I glossed over some trivial thing. I'd work overtime to make sure it's fixed. Similarly, were I in Grant's boots, I wouldn't hesitate for a second to refute all of my claims about RSA being insecure, when I was shown the p-q diff requirement ensures enough computational headroom against Fermat. The fact Grant doesn't admit being wrong is obvious proof he doesn't re-trace his steps to ensure his conjecture is right proves he's not sincere. He has also deleted youtube comments that quoted e.g. Schneier's assertion that Crown Sterling is snake oil.

He could effortlessly call on, and pay for if necessary, any number of experts in cryptography and mathematics, to review his theories,

His methods have been refuted with academic papers. See e.g. https://unprovable.github.io/drafts/Prime_Generation_For_Breaking_Crypto-5e.pdf

Also, if you read Schneier's blog post, you noticed he said

I poked around at the [TimeAI] website, and sent back: “That screams ‘snake oil.’ Bet you a gazillion dollars they have absolutely nothing of value — and that none of their tech people have any cryptography expertise.”

And that's what every cryptographer who's bothered to comment it (Matt Green, JPA) has said so far, and no-one has claimed the opposite.

Personally I'd be extremely interested in seeing a cryptographer peer-review and confirm their findings, and I would've posted it just about everywhere. After all, as someone who works on FOSS secure comms system, I have extremely high self-interest in knowing the algorithms I choose are secure ones.

That he is, for whatever reason, sitting on something that is in fact the crux of what he's come up with.

As I mentioned earlier in this comment, the fact Grant keeps changing his algorithm already proves he has nothing of value. If the reciprocal factoring had actually worked, he wouldn't have had to introduce another method. He'd be a billionare, (or he'd been killed by the CIA to protect national security information the delivery of which relies on RSA).

The Pythagorean algorithm was completely described, he went through the entire algorithm in the video. He even made a second video as a response to my comments where he carefully explained all the formulae in his Excel spreadsheet. The thing is, the structure of the attack wasn't unclear or anything. It is a "valid" attack. But Grant ignores the context: it has been known for a long time: Fermat's factorization method is centuries old; Fermat himself died in 1665 AD. There was no magic sauce other than the fact the semiprimes he chose were cherry picked to be weak. His argument to defend the validity of the attack was literally "there's a massive number of semiprimes with small X" which I've shown in multiple ways to be of no significance: having too small x is 1. extremely improbable 2. verified to not be the case, for every single individual key).

So Grant' isn't sitting on anything. If he were, he could keep the algorithm to himself, and just release the factors for the RSA-2048 challenge. Again, he doesn't because he hasn't got anything of value.

So, to me, I've yet to get a sense of why he's shared what he has, and has set up a business around it (i.e., c. sterling).

If you take a look at the video at the top of https://www.crownsterling.io/, you'll see the company is working on its own "post quantum" cryptocurrency. So my money's on them trying to claim Bitcoin is insecure, to con people into investing in their cryptocurrency instead. Given how Grant falsely claims his crap stream cipher is OTP* it's clear he doesn't know how to implement cryptography. So that alone makes his cryptocurrency insecure. Cryptocurrency design is AFAIK unregulated so his method is insecure just from the perspective of CSPRF design.

*See https://www.reddit.com/r/crypto/comments/iu73om/crown_sterling_reinvents_onetime_pads_defeats/ for discussion about the "CrownOTP".

So I'm not saying the cryptocurrency itself is an investment scam, I'm just saying it's extremely likely the implementation will have a massive hole due to ignorance towards implementing secure cryptography.

One weird aspect is the primitives of using ECDHE and AES256 aren't bad in themselves. Quite the contrary. So why babble about OTPs? One reason could be they're trying to distinguish themselves with crypto that's associated with math proofs (perfect secrecy is a selling point for people afraid to lose their money), but Grant et. al. know they can't risk putting in snake oil in practice, and that they have to stick to standard crypto to retain FIPS validation. Also given how the term "TimeAI" has disappeared, and how CrownOTP has been replaced with CrownEncrypt etc., it might be it's just marketing bullshit to draw attention, and what you're left with is just another cryptocurrency, which I bet will be just a fork of some pre-existing dual-licenceable coin.