Problem 44956. Determine RSA keys (public and private) given two prime number character strings (p and q)

Created by David Hill

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given two prime number character strings (p and q), generate the RSA public and private keys (n and d) with e = 65537. The more difficult part is doing this without the use of symbolic numbers. Example: p = '3355335697481001330501721', q = '5955344080483688912855719' n='19982178584029090861856118769095354822153154192399' d='3270348772331599380262578849367006078599068947553'</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"https://simple.wikipedia.org/wiki/RSA_algorithm\"><w:r><w:t>&lt;https://simple.wikipedia.org/wiki/RSA_algorithm</w:t></w:r></w:hyperlink><w:r><w:t>&gt;</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

129 Solutions
13 Solvers

Last Solution submitted on Jan 11, 2023

Last 200 Solutions

Problem Comments

6 Comments

6 Comments

Show 3 older comments

Tim on 28 Aug 2019

I get different results for d in test cases 2, 3, and 4 (in particular, d=929660805638728623653 for test case 2).

Tim on 28 Aug 2019

If I understand correctly, we should have mod(d*e,phi)=1, where phi=(p-1)*(q-1). My answers seem to satisfy that condition, but test cases 2, 3, and 4 do not.

Joel Hottinger on 9 Jul 2021

Could someone help me out with the modular inversion. I can't seem to get it to work for any large numbers. I've been stuck for a while

Joel Hottinger on 9 Jul 2021

I think my main issue is that I cannot use the mod function with large numbers, what is a way around this?

Joel Hottinger on 28 Jul 2021

@David Hill. Thanks, that worked a lot better for me

Jeremy Perez on 6 Aug 2021

One should first consider if MATLAB is even adapted for these kinds of calculations. Still, I had a lot of fun.

Solution Comments

Solution 1915449

2 Comments

2 Comments

Tim on 29 Aug 2019

Googling can supplant programming sometimes.

Khanh Dao on 12 Mar 2022

:<<

Problem Recent Solvers13

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 44956. Determine RSA keys (public and private) given two prime number character strings (p and q)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers13

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 44956. Determine RSA keys (public and private) given two prime number character strings (p and q)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers13

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players