RCR - Technical Analysis of US Patent No. 11,456,863

Technical Analysis of US Patent No. 11,456,863

by Raine Conor

This is an explanation of the factorization algorithm outlined in US Patent No. 11,456,863. Each step will elaborate upon a corresponding claim in the patent, using a real RSA public key as an example throughout.

In March 2022, vulnerabilities in the cryptographic modules of several Fujifilm and Canon printers were discovered. They generate weak RSA keys, one of which we are going to break with the RCR Factoring Method. NIST assigned this vulnerability CVE-2022-26320, and Fujifilm released an official statement.

Claims

1. A non-transitory program storage medium on which are stored instructions executable by a processor or programmable circuit to perform operations for cracking a private key of an asymmetric cryptosystem, the operations comprising:

extracting a modulus and a public key exponent from a public key;
calculating the digital root of the modulus;
deriving a set of candidate base pairs corresponding to the digital root and the last digit of the modulus, each of the candidate base pairs including a first candidate base and a second candidate base;
iteratively testing values of a multiplier until a sum of one of the candidate bases with ninety times the multiplier is a factor of the modulus; and
determining the private key using the public key exponent and the factor of the modulus.

A non-transitory program storage medium is a term officially stated by the USPTO (page 15-17) to be an acceptable description of a computer-readable storage. The operations described in the bullet points introduce us to the concepts in the next 19 claims.

2. The non-transitory program storage medium of claim 1, wherein said extracting includes parsing an encoded data structure containing the public key.

Examples of obtaining encoded data structures are downloading an SSL certificate from a website, intercepting a packet on a wireless network, using data in a dump from a data breach, etc. The key we will use for this example is one generated by a Fujifilm printer as mentioned previously:

It is encoded according to the standard as specified in RFC 3447 (A1.1).

3. The non-transitory program storage medium of claim 2, wherein said parsing is performed using an ASN.1 parser.

Using this open-source ASN.1 parser we can extract the modulus $n$ from the public key in decimal:

18229021800499389179810999984147294316694481152259999178780074391429829111773881276038281122549654793695493293264207027376776682362226410733793123117211189262610875849497690435072434819643299230953875973012904516275649075242502330535166202977871076698326460570645695302887174347984232777274357996755103073370058925661345782916623908813122753869187282565276059526610380429671250747371523249129041042163813118053400537221212684975928016171244322844087003229657728793172722938168054943184764356498974298899669556165909647342688587153673679901583046195388386919521461435059782679160323429508745816818692733354205358568651

4. The non-transitory program storage medium of claim 1, wherein said deriving includes referencing one or more lookup tables associating possible combinations of the digital root and the last digit of the modulus with possible candidate base pairs.

We will use the small lookup table below for the example, where LDDict is the last digit dictionary and DRDict is the digital root dictionary.

 const LDDict = { 1: [[1, 1], [3, 7], [9, 9]], 3: [[1, 3], [7, 9]], 7: [[1, 7], [3, 9]], 9: [[1, 9], [3, 3], [7, 7]], }; const DRDict = { 1: [[1, 1], [2, 5], [4, 7], [5, 2], [7, 4], [8, 8]], 2: [[1, 2], [2, 1], [4, 5], [5, 4], [7, 8], [8, 7]], 4: [[1, 4], [2, 2], [4, 1], [5, 8], [7, 7], [8, 5]], 5: [[1, 5], [2, 7], [4, 8], [5, 1], [7, 2], [8, 4]], 7: [[1, 7], [2, 8], [4, 4], [5, 5], [7, 1], [8, 2]], 8: [[1, 8], [2, 4], [4, 2], [5, 7], [7, 5], [8, 1]], }

The last digit of $n$ is 1, so the corresponding lookup value from LDDict is:

 [[1, 1], [3, 7], [9, 9]]

The digital root of $n$ is 8, so the corresponding lookup value from DRDict is:

 [[1, 8], [2, 4], [4, 2], [5, 7], [7, 5], [8, 1]]

Calculating the possible combinations by multiplying the length of each array yields a result of 18 combinations. Normally this would require iterating through to find the correct values, but for brevity, we will use the correct values, which are [3, 7] from LDDict and [5, 7] from DRDict.

This means that the two factors of $n$ have a last digit of 3 and 7, and a digital root of 5 and 7 respectively. To calculate the base pair, we can use this congruence relation:

$$B\equiv 10D-9L+90 \mod{90}$$

where $D$ is the digital root and $L$ is the last digit.

Inserting $D_1=3, L_1=5$ and $D_1=7, L_1=7$, we get $B_1 = 23 \text{ and } B_2 = 7$

5. The non-transitory program storage medium of claim 1, wherein said iteratively testing includes incrementing an integer $t$ and testing, for each of the candidate base pairs, the sum of the second candidate base with ninety times the multiplier $p$, the multiplier $p$ being equal to the expression $$p=\frac{±\sqrt{\big(B_1+B_2+90(t_0+t)\big)^2-4n}+B_1-B_2+90(t_0+t)}{180}$$ where $n$ is the modulus, $B_1$ is the first candidate base, $B_2$ is the second candidate base, and $t_0$ is a starting value offset.

This expression is derived from $n=(B_1+90(t-p))*(B_2+90p)$. Values of $t$ must be iterated through until a multiplier $p$ is found to correspond to a factor of $n$.

6. The non-transitory program storage medium of claim 5, wherein the starting value offset $t_0$ is a function of the modulus $n$.

An initial $t$ value, $t_0$, is initialized with a custom value calculated from the value of $n$. Claims 7-9 describe some ways to choose an initial value.

7. The non-transitory program storage medium of claim 6, wherein the starting value offset $t_0$ is approximately equal to twice the square root of the modulus divided by ninety.

When iterating through multiple base pairs, it is best to choose this option.

8. The non-transitory program storage medium of claim 7, wherein the starting value offset $t_0$ is equal to the expression $$\frac{2\sqrt{n}-B_1-B_2}{90}$$

When testing a specific base pair, it is best to choose this option. This expression is derived by setting the inner contents of the square root from the previous expression equal to 0, then solving for $t$.

Since we have a specific base pair, we can calculate our $t_0$, rounded up to the nearest integer:

3000330994127262288766211669430057922948507708209832612494062092480889050838506361917410162479725961292814955122802089615251379801707469313884881256566299410672220220258048375939215287783023513543745980996502341262610409412161647003735972679899152088990864934040906601383371931710972662409910221239768681855

9. The non-transitory program storage medium of claim 6, wherein the starting value offset $t_0$ is equal to the expression $$\frac{\sqrt{d^2+4n}-B_1-B_2}{90}$$ where $d$ is a minimum difference between factors of the modulus $n$.

When information about the difference between the factors of $n$ is known, it is best to choose this option. Information about moduli can be inferred from the standards for the cryptosystem it was generated for. The optimal distance between factors is outlined in FIPS 186-4 (page 62). Assuming a modulus was generated according to standard, $t_0$ can be chosen to start at that value.

10. The non-transitory program storage medium of claim 5, wherein said iteratively testing includes checking whether the multiplier $p$ is an integer.

Since $n$ and its factors are integers, $p$ must be an integer.

This is beneficial because if $p$ is not an integer then the iterative search can be continued without wasting computing resources on testing whether $p$ corresponds to a factor of $n$.

11. The non-transitory program storage medium of claim 5, wherein said iteratively testing includes checking whether the expression $\big(B_1+B_2+90(t_0+t)\big)^2−4n$ is a perfect square.

Since $p$ must be an integer, its equivalent expression must be an integer. Therefore the value of the radicand must be an integer, which implies a perfect square.

This is even more beneficial because if the square root is not an integer, then computing resources need not be wasted on calculating the rest of the expression.

We now have all the required context to factor our modulus. If we plug our value of $t_0$ that we calculated in claim 8 into $$\big(B_1+B_2+90(t_0+t)\big)^2−4n$$ and begin iterating through $t$ values starting at 0, we get a perfect square on the first iteration:

t=0: 45796

From here we can plug it into the equation from claim 5: $$p=\frac{±\sqrt{\big(B_1+B_2+90(t_0+t)\big)^2-4n}+B_1-B_2+90(t_0+t)}{180}$$

and we get two values as a result of having a positive and negative square root:

1500165497063631144383105834715028961474253854104916306247031046240444525419253180958705081239862980646407477561401044807625689900853734656942440628283149705336110110129024187969607643891511756771872990498251170631305204706080823501867986339949576044495432467020453300691685965855486331204955110619884340926

1500165497063631144383105834715028961474253854104916306247031046240444525419253180958705081239862980646407477561401044807625689900853734656942440628283149705336110110129024187969607643891511756771872990498251170631305204706080823501867986339949576044495432467020453300691685965855486331204955110619884340928

If we plug each of these into $F_2=B_2+90p$, we can confirm if either of the resulting values are a factor of $n$ by testing if $n$ modulo $F_2$ is equal to 0. The value corresponding to the negative value of the square root ends up being the correct answer, yielding factors:

135014894735726802994479525124352606532682846869442467562232794161640007287732786286283457311587668258176672980526094032686312091076836119124819656545483473480249909911612176917264687950236058109468569144842605356817468423547274115168118770595461844004588922031840797062251736926993769808445959955789590683383

135014894735726802994479525124352606532682846869442467562232794161640007287732786286283457311587668258176672980526094032686312091076836119124819656545483473480249909911612176917264687950236058109468569144842605356817468423547274115168118770595461844004588922031840797062251736926993769808445959955789590683597

12. The non-transitory program storage medium of claim 5, wherein said iteratively testing includes, for each of the candidate base pairs, comparing the modulus $n$ to the product of the candidate base pair $B_1*B_2$.

Claims 12-14 outline ways to reduce the number of iterations required to find the correct value of $t$.

13. The non-transitory program storage medium of claim 12, wherein said comparing includes checking whether the second-to-last digit of the modulus $n$ and the second-to-last digit of the product $B_1*B_2$ have the same parity.

Comparing the second-to-last digit of the modulus and base pair product is beneficial because only odd or even values of $t$ need to be iterated depending on the outcome of the comparison, reducing the required computational resources and time by 50%.

14. The non-transitory program storage medium of claim 13, wherein said iteratively testing includes, for each of the candidate base pairs, checking whether the sum of the candidate base pair $B_1+B_2$ is divisible by 4.

Checking whether the sum of the base pair is divisible by 4 is beneficial because only odd or even values of $t$ need to be iterated depending on the outcome of the comparison to the remainder of $n \div 40$, further reducing the required computational resources and time by 50% compared to iterating $t$ values 1 at a time.

15. The non-transitory program storage medium of claim 1, wherein said determining includes determining a private key exponent of the private key such that the product of the private key exponent and the public key exponent is congruent to one modulo $\Phi$, where $\Phi$ is equal to $(F_1−1)*(F_2−1)$, $F_2$ is the factor of the modulus, and $F_1$ is a value equal to the modulus divided by $F_2$.

Now that we have the factors of $n$, we can calculate the private key exponent $d$ from the public key exponent $e$ and factors $F_1, F_2$. Using the ASN.1 parser from claim 3 we can extract $e$ from our RSA public key example, $e=65537$.

Then calculate $\Phi$ by plugging in the factors we found:

18229021800499389179810999984147294316694481152259999178780074391429829111773881276038281122549654793695493293264207027376776682362226410733793123117211189262610875849497690435072434819643299230953875973012904516275649075242502330535166202977871076698326460570645695302887174347984232777274357996755103073369788895871874329310634949762874048656121916871537174591485914841347970732796057676556474127540637781537047191260160496910555391989090650605837363916566761846212223118344830589350234980598502182680732417876224436629053650306579131671246808654197463231512283590996101085035819955654758277201800813442626177201672

Now we can calculate $d$ by taking the modular inverse of $e$ and $\Phi$:

15550451222981206812574478174370550732615749237520786335780667699187748236140537108800710785028053626976119498093016498764872575504295160670982378413932983781753608436728372967233694149286630912384429315092733155185966901896372702339587361488683313013615780873752062000068865774642637012360613585067786861206414510910003175744536187747272524500935471665426077176041061400968018062444561034579593192370942161716155718476307931409408735522439095524979011924309900583429005872671993587726072097598615461909024021334606093941140156364952919943610408340787914870747169365729572964296467434591003112799198591286401600451865

16. The non-transitory program storage medium of claim 1, wherein the operations further comprise decrypting an encrypted message using the private key.

We will use this encrypted message as an example. Let our ciphertext $c$ be:

968679899872097544258024197426539744955113484402734553024890561906194499613956444848577993111412807039618692389424774681877937907495683249028719745430723692696139372583123165780023090038335457524186697756437784484579724610530840616356778426880397234803293887590092372586563423166440844532951307528256261542677818623004162295790134929324424831897933144709093836278251873408034126271320200006555187477028032671995825322879951776267653261111193030971992523781503288657246058657887993323661434850754387257595495899169016046565254846628682795839758238665260811073178604708383672179613787409627750550022265940416705195741

17. The non-transitory program storage medium of claim 16, wherein said decrypting includes decrypting an encrypted symmetric key using the private key and decrypting the message using the symmetric key.

Public-key systems like RSA can be used in a hybrid cryptosystem comprised of a key encapsulation mechanism (public-key system) and a data encapsulation scheme (private-key system) to increase performance of encrypting long messages.

18. The non-transitory program storage medium of claim 16, wherein said decrypting includes parsing an encoded data structure including the encrypted message.

Encrypted messages can be encoded into a structure such as ASN.1, for example the standard described in RFC 2315 Section 7. The encrypted message would then need to be parsed from the structure so that decryption calculations can be performed on it.

19. The non-transitory program storage medium of claim 18, wherein said parsing is performed using an ASN.1 parser.

ASN.1 is an example of an encoded data structure mentioned in claim 18.

20. The non-transitory program storage medium of claim 16, wherein said decrypting includes determining a plaintext $m$ such that a ciphertext $c$ of the encrypted message raised to the power of the private key exponent is congruent to $m$ modulo $n$.

We can take our ciphertext example $c$ and plug it into the formula with our value $d$ that we calculated in claim 15:

$$c^d\equiv m\mod n$$

The result is $m=11456863$, which is the number assigned to this patent.

21. A method of cracking a private key of an asymmetric cryptosystem, the method comprising:

extracting a modulus and a public key exponent from a public key;
calculating the digital root of the modulus;
deriving a set of candidate base pairs corresponding to the digital root and the last digit of the modulus, each of the candidate base pairs including a first candidate base and a second candidate base;
iteratively testing values of a multiplier until a sum of one of the candidate bases with ninety times the multiplier is a factor of the modulus; and
determining the private key using the public key exponent and the factor of the modulus.

22. The method of claim 21, further comprising decrypting an encrypted message using the private key.

Claims 21-22 further protect this invention by expanding the scope from operations to a method.

23. A system for cracking a private key of an asymmetric cryptosystem, the system comprising:

an n/e extractor for extracting a modulus and a public key exponent from a public key;
a digital root calculator for calculating the digital root of the modulus;
a candidate base pair deriving engine for deriving a set of candidate base pairs corresponding to the digital root and the last digit of the modulus, each of the candidate base pairs including a first candidate base and a second candidate base;
an iterator for iteratively testing values of a multiplier until a sum of one of the candidate bases with ninety times the multiplier is a factor of the modulus; and
a private key determiner for determining the private key using the public key exponent and the factor of the modulus.

24. The system of claim 23, further comprising a decryptor for decrypting an encrypted message using the private key.

Claims 23-24 further protect this invention by expanding the scope from operations or a method to a system.