// Numbas version: exam_results_page_options
{"name": "RSA Encryption", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "RSA Encryption", "tags": [], "metadata": {"description": "<p>A question which asks students to encrypt a number using RSA, then to factor a small public key and find the decryption exponent.</p>", "licence": "None specified"}, "statement": "<p>In this question you will be asked to encrypt a number using the provided RSA public key. You will also be asked to factor the public key and provide the decryption key.</p>\n<p>The public key is given by $(n,e) = (\\var{modulus},\\var{key})$.</p>", "advice": "<p>For larger message sizes and larger encryption exponents, you may need to use some technology to help you, such as the Excel spreadsheet we made in order to repeatedly square and reduce numbers in order to obtain large powers.</p>\n<p>In this question we had the message value of $m = \\var{message}$, meaning that we needed to find $m^e = \\var{message}^\\var{key} \\operatorname{mod} \\var{modulus}$. Now $m^e = \\var{message}^\\var{key} = \\var{m_to_e} = \\var{encrypted} \\operatorname{mod} \\var{modulus}$.</p>\n<p>To find the private key, we can start by factoring the modulus $n = \\var{modulus}$ into two primes. This should not be difficult since the numbers involved are so low. If we can't spot a sensible factor, then we just have to try dividing the modulus $n$ by prime numbers up to $\\sqrt{n} = \\sqrt{\\var{modulus}} = \\var{sqrt_mod}$ until we find one that divides it exactly: this will be the lower of the two primes. In order to find the decryption exponent $d$, we must use the extended Euclidean algorithm in order to find the value of $d$ such that $de \\equiv 1 \\operatorname{mod} \\varphi(n)$, i.e., $d \\times \\var{key} \\equiv 1 \\operatorname{mod} \\var{modulus}$. This works out to be $d = \\var{d_key}$.</p>", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"prime1": {"name": "prime1", "group": "Ungrouped variables", "definition": "random(7,11,13)", "description": "", "templateType": "anything", "can_override": false}, "prime2": {"name": "prime2", "group": "Ungrouped variables", "definition": "random(17,19,23)", "description": "", "templateType": "anything", "can_override": false}, "modulus": {"name": "modulus", "group": "Ungrouped variables", "definition": "prime1*prime2", "description": "", "templateType": "anything", "can_override": false}, "key": {"name": "key", "group": "Ungrouped variables", "definition": "if(mod(totient,3)=0,\n  if(mod(totient,5)=0,7,5),3)", "description": "", "templateType": "anything", "can_override": false}, "totient": {"name": "totient", "group": "Ungrouped variables", "definition": "(prime1-1)*(prime2-1)", "description": "", "templateType": "anything", "can_override": false}, "e_check": {"name": "e_check", "group": "Ungrouped variables", "definition": "not(mod(totient,key)=0)", "description": "", "templateType": "anything", "can_override": false}, "d_key": {"name": "d_key", "group": "Ungrouped variables", "definition": "if(prime1=7 and prime2=17,77,\nif(prime1=7 and prime2=19,65,\nif(prime1=7 and prime2=23,53,\nif(prime1=11 and prime2=17,107,\nif(prime1=11 and prime2=19,103,\nif(prime1=11 and prime2=23,147,\nif(prime1=13 and prime2=17,77,\nif(prime1=13 and prime2=19,173,53))))))))", "description": "", "templateType": "anything", "can_override": false}, "message": {"name": "message", "group": "Ungrouped variables", "definition": "random(18..30)", "description": "", "templateType": "anything", "can_override": false}, "encrypted": {"name": "encrypted", "group": "Ungrouped variables", "definition": "mod(message^key,modulus)", "description": "", "templateType": "anything", "can_override": false}, "decrypted": {"name": "decrypted", "group": "Ungrouped variables", "definition": "mod(encrypted^d_key,modulus)", "description": "", "templateType": "anything", "can_override": false}, "decrypt_check": {"name": "decrypt_check", "group": "Ungrouped variables", "definition": "message = decrypted", "description": "", "templateType": "anything", "can_override": false}, "bin_d_key": {"name": "bin_d_key", "group": "Ungrouped variables", "definition": "tobinary(d_key)", "description": "", "templateType": "anything", "can_override": false}, "binlength": {"name": "binlength", "group": "Ungrouped variables", "definition": "len(bin_d_key)", "description": "", "templateType": "anything", "can_override": false}, "d_key8": {"name": "d_key8", "group": "Ungrouped variables", "definition": "if(binlength=6,join([\"00\",bin_d_key],\"\"),if(binlength=7,join([\"0\",bin_d_key],\"\"),bin_d_key))", "description": "", "templateType": "anything", "can_override": false}, "key_check": {"name": "key_check", "group": "Ungrouped variables", "definition": "mod(d_key*key,totient)", "description": "", "templateType": "anything", "can_override": false}, "m_to_e": {"name": "m_to_e", "group": "Ungrouped variables", "definition": "message^key", "description": "", "templateType": "anything", "can_override": false}, "sqrt_mod": {"name": "sqrt_mod", "group": "Ungrouped variables", "definition": "siground(sqrt(modulus),3)", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["prime1", "prime2", "modulus", "totient", "key", "e_check", "d_key", "message", "encrypted", "decrypted", "decrypt_check", "bin_d_key", "binlength", "d_key8", "key_check", "m_to_e", "sqrt_mod"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>The message you are to encrypt is $m = \\var{message}$. Encrypt this using the given public key above using the RSA algorithm.</p>", "minValue": "encrypted", "maxValue": "encrypted", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Now you are asked to factorise the public key and find the decryption exponent, $d$. The private key is established using two prime numbers, $p$ and $q$. For the purposes of this question, the lower of the two primes will be $p$ and the higher will be $q$.</p>\n<p>$p = $[[0]]</p>\n<p>$q = $[[1]]</p>\n<p>$\\varphi(n) = $[[3]]</p>\n<p>$d = $[[2]]</p>", "gaps": [{"type": "numberentry", "useCustomName": true, "customName": "p", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "prime1", "maxValue": "prime1", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "q", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "prime2", "maxValue": "prime2", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "d", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "d_key", "maxValue": "d_key", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "phi(n)", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "totient", "maxValue": "totient", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Alexander Corner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/5328/"}]}]}], "contributors": [{"name": "Alexander Corner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/5328/"}]}