Code Poetry
and Text Adventures

by catid posted (>30 days ago) 6:05pm Wed. May 22nd 2013 PDT
If you have physical access to the device and can change the public key stored on the device with all FFFFFF's here's how you could generate valid-looking RSA-encrypted messages in 20 minutes with just access to a web browser.

Background: http://en.wikipedia.org/wiki/RSA_(algorithm)

The public key consists of {n, e}.  Assume e is fixed at 2^^16+1 = 65537.  So the effect of overwriting the public key is to change n = 2^^2048-1.

Assume that RSA is being used like this to validate some input on the device:
ASSERT( c == m ^ e (mod n) ).  We want that assertion to be valid.

Assume we know what 'c' should be.  It's a big 2048-bit number.

To generate m with RSA: m = c ^ d (mod n).  We know n, how do we get d to generate the right m to make the assertion above pass?

First factor n into its prime factors to get Euler's totient function of n.
Using http://www.alpertron.com.ar/ECM.HTM it is easy:

2^^2048-1 =

32317 006071 311007 300714 876688 669951 960444 102669 715484 032130 345427
524655 138867 890893 197201 411522 913463 688717 960921 898019 494119 559150
490921 095088 152386 448283 120630 877367 300996 091750 197750 389652 106796
057638 384067 568276 792218 642619 756161 838094 338476 170470 581645 852036
305042 887575 891541 065808 607552 399123 930385 521914 333389 668342 420684
974786 564569 494856 176035 326322 058077 805659 331026 192708 460314 150258
592864 177116 725943 603718 461857 357598 351152 301645 904403 697613 233287
231227 125684 710820 209725 157101 726931 323469 678542 580656 697935 045997
268352 998638 215525 166389 437335 543602 135433 229604 645318 478604 952148
193555 853611 059596 230655

=
3 x
5 x
17 x
257 x
641 x
65537 x
274177 x
2 424833 x
6 700417 x
45 592577 x
6487 031809 x
67 280421 310721 x
1238 926361 552897 x
59649 589127 497217 x
5704 689200 685129 054721 x
4659 775785 220018 543264 560743 076778 192897 x
7 455602 825647 884208 337395 736200 454918 783366 342657 x
93 461639 715357 977769 163558 199606 896584 051237 541638 188580 280321 x
741 640062 627530 801524 787141 901937 474059 940781 097519 023905 821316 144415 759504 705008 092818 711693 940737 x
130439 874405 488189 727484 768796 509903 946608 530841 611892 186895 295776 832416 251471 863574 140227 977573 104895 898783 928842 923844 831149 032913 798729 088601 617946 094119 449010 595906 710130 531906 171018 354491 609619 193912 488538 116080 712299 672322 806217 820753 127014 424577

The totient(n) is the product of the factors of n less 1:
Using https://defuse.ca/big-number-calculator.htm this takes a bit of typing but it's also easy:

totient(n) = prod(factor[i] - 1) =

(3-1) * (5-1) * (17-1) * (257-1) * (641-1) * (65537-1) * (274177-1) * (2424833-1) * (6700417-1) * (45592577-1) * (6487031809-1) * (67280421310721-1) * (1238926361552897-1) * (59649589127497217-1) * (5704689200685129054721-1) * (4659775785220018543264560743076778192897-1) * (7455602825647884208337395736200454918783366342657-1) * (93461639715357977769163558199606896584051237541638188580280321-1) * (741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737-1) * (130439874405488189727484768796509903946608530841611892186895295776832416251471863574140227977573104895898783928842923844831149032913798729088601617946094119449010595906710130531906171018354491609619193912488538116080712299672322806217820753127014424577-1)

=
16133226506241450091276541231338869878558886282063241995828556793226071982851023253532837130718601474144994122910945077215170809780761577431616687940360519713012377894569274169201126758151597210416998419176556211910555584551283805145317277895583654289824153073898586565722228599431046183356317073922262290325490388420194847781165221882947284029580330927543234885554537071215382107608387147201847704872873271029913489043226500242979820299754405608030104024808840767786213985796348701872706857965553404399929576059837702412080173493953276756207360607802454536825528012831783005031619665426778819748340361967970549760000

We can check using an online calculator like http://www.mobilefish.com/services/big_number_equation/big_number_equation.php that gcd(2^16-1=65537, totient(n)) = 1 so this 'n' works with the fixed 'e'.

Now to compute 'd' with the same calculator is simply:

d = multInverse(e, totient) = inverseMod(e, totient)
=
15446412920749077145388545899916384153530592452212067160722255414568203285288511162998381546930742736136471706521401204815910444501784437784788017733399477095875424199315474408271100305075579751316590625266206457859707207590207133702385266889149450779309338738848507121768965285693575459161371857689552343425142215881135329870527704617075746997941270194097309296487335972161551201704433653134478812543420955144635575278015978924062053257681762800968383313924658309905573477070410485625016970822048300439177580741056751350394351987809729719421750401418749940067311689902740256904024278598869197594475070454922381033473


Summary

We calculated d above.  n = 2^^2048-1.  So you can calculate m for any given c.

Now you just need to know what the correct 'c' is, and the protection scheme will generate m ^ e (mod n) and get it back.

We assumed e = 65537.  If it's something else you can just use that big number equation website to calculate inverseMod(other_e, totient) to get a new d to try.
last edit by catid edited (>30 days ago) 6:25pm Wed. May 22nd 2013 PDT