MMSC-RSA: Miller-Rabin, Montgomery, Sliding Window, and Shamir’s Chinese Remainder Theorem Optimization-based RSA

MMSC-RSA: Miller-Rabin, Montgomery, Sliding Window, and Shamir’s Chinese Remainder Theorem Optimization-based RSA | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article MMSC-RSA: Miller-Rabin, Montgomery, Sliding Window, and Shamir’s Chinese Remainder Theorem Optimization-based RSA Getaneh Awulachew Zimbele, Baye Yemataw Adane, Sofonias Yitagesu Techan This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8730094/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract RSA is still a popular way to encrypt data asymmetrically, although it has performance problems in applications with limited resources. In this paper, we propose an improved version called MMSC-RSA that uses Miller-Rabin, Montgomery multiplication, sliding-window exponentiation, and Shamir's CRT-based modifications to remedy the issue. This better version of RSA is substantially faster and still works on existing infrastructure. Our MMSC-RSA generates keys using segmented sieving and Miller-Rabin testing methods. This feature improves the key generation performance of our MMSC-RSA cryptosystem by 79% for 4096-bit keys. During encryption, when compared to normal RSA and HRM-RSA at 3072-bit lengths, Montgomery multiplication and sliding-window approaches used by MMSC-RSA lower latency by 62.2% and 31.3%, respectively. Our MMSC-RSA efficiency increases from 74.8% up to 85.9% compared to a 4096-bit key RSA and SNA-RSA, attributable to CRT parallelism and Shamir's optimization techniques in decryption. Our MMSC-RSA cryptosystem is basically engineered based on the core functional strengths of conventional RSA, like prime number security, modular exponentiation, and factorization difficulty. We proposed MMSC-RSA for scalability, making it suitable for extensive systems like IoT and blockchain. It also establishes a basis for future integration with systolic hardware or hybrid post-quantum models to enhance protection against quantum threats. The source code is accessible to the public at the Zenodo Repository , facilitating repeatability and additional research. Systems and Networking Information Theory Computational Mathematics CRT Miller-Rabin Test Montgomery RSA Sliding-Window Full Text Additional Declarations The authors declare no competing interests. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8730094","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":592840648,"identity":"c86a28a0-dd46-4cee-860f-57d51e663383","order_by":0,"name":"Getaneh Awulachew Zimbele","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA/ElEQVRIiWNgGAWjYBADGQYGHiBVAcTMzA0EFDODSR6IljMgAUZStDC2gdgEtMi79x9g+Nl2mIe//ezBx7zzaqP524FaflRsw6nF8MxhBsZeoBaJM3nJxrzbjufOOMzYwNhz5jZuLTOSGRh4tx3mYbjBYyadu+1YbgNQCzNjGx4t8x8zMP4FapG/wWP+O3fOsdz5hLTISzAzMINsMQDawpzbUJO7gZAWA55kg8Oy/9J5DM/kGEv/OXYgdyNQy0F8fpFvP/jw4Zsz1nJyx88YfpxRU5c77/zhgw9+VOCx5QADwwEk/mEweQCLSoQtDaj8OnyKR8EoGAWjYIQCABPBWeTldbHWAAAAAElFTkSuQmCC","orcid":"","institution":"Debre Berhan University","correspondingAuthor":true,"prefix":"","firstName":"Getaneh","middleName":"Awulachew","lastName":"Zimbele","suffix":""},{"id":592842876,"identity":"877ca366-b3c3-454c-b0bf-2f55087017e9","order_by":1,"name":"Baye Yemataw Adane","email":"","orcid":"","institution":"Debre Berhan University","correspondingAuthor":false,"prefix":"","firstName":"Baye","middleName":"Yemataw","lastName":"Adane","suffix":""},{"id":592843716,"identity":"418e1c8a-ee85-4e38-af6f-f668d1fab726","order_by":2,"name":"Sofonias Yitagesu Techan","email":"","orcid":"","institution":"Debre Berhan University","correspondingAuthor":false,"prefix":"","firstName":"Sofonias","middleName":"Yitagesu","lastName":"Techan","suffix":""}],"badges":[],"createdAt":"2026-01-29 10:18:23","currentVersionCode":1,"declarations":{"humanSubjects":false,"vertebrateSubjects":false,"conflictsOfInterestStatement":false,"humanSubjectEthicalGuidelines":false,"humanSubjectConsent":false,"humanSubjectClinicalTrial":false,"humanSubjectCaseReport":false,"vertebrateSubjectEthicalGuidelines":false},"doi":"10.21203/rs.3.rs-8730094/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8730094/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[],"financialInterests":"The authors declare no competing interests.","formattedTitle":"\u003cp\u003eMMSC-RSA: Miller-Rabin, Montgomery, Sliding Window, and Shamir’s Chinese Remainder Theorem Optimization-based RSA\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"Tianjin University","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"CRT, Miller-Rabin Test, Montgomery, RSA, Sliding-Window","lastPublishedDoi":"10.21203/rs.3.rs-8730094/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8730094/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eRSA is still a popular way to encrypt data asymmetrically, although it has performance problems in applications with limited resources. In this paper, we propose an improved version called MMSC-RSA that uses Miller-Rabin, Montgomery multiplication, sliding-window exponentiation, and Shamir's CRT-based modifications to remedy the issue. This better version of RSA is substantially faster and still works on existing infrastructure. Our MMSC-RSA generates keys using segmented sieving and Miller-Rabin testing methods. This feature improves the key generation performance of our MMSC-RSA cryptosystem by 79% for 4096-bit keys. During encryption, when compared to normal RSA and HRM-RSA at 3072-bit lengths, Montgomery multiplication and sliding-window approaches used by MMSC-RSA lower latency by 62.2% and 31.3%, respectively. Our MMSC-RSA efficiency increases from 74.8% up to 85.9% compared to a 4096-bit key RSA and SNA-RSA, attributable to CRT parallelism and Shamir's optimization techniques in decryption. Our MMSC-RSA cryptosystem is basically engineered based on the core functional strengths of conventional RSA, like prime number security, modular exponentiation, and factorization difficulty. We proposed MMSC-RSA for scalability, making it suitable for extensive systems like IoT and blockchain. It also establishes a basis for future integration with systolic hardware or hybrid post-quantum models to enhance protection against quantum threats. The source code is accessible to the public at the \u003cspan type=\"Underline\" class=\"Underline\" name=\"Emphasis\"\u003eZenodo Repository\u003c/span\u003e, facilitating repeatability and additional research.\u003c/p\u003e","manuscriptTitle":"MMSC-RSA: Miller-Rabin, Montgomery, Sliding Window, and Shamir’s Chinese Remainder Theorem Optimization-based RSA","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-02-19 05:17:51","doi":"10.21203/rs.3.rs-8730094/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"09b76370-c107-4988-9015-2d651d664256","owner":[],"postedDate":"February 19th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":63082658,"name":"Systems and Networking"},{"id":63082659,"name":"Information Theory"},{"id":63082660,"name":"Computational Mathematics"}],"tags":[],"updatedAt":"2026-02-19T05:17:51+00:00","versionOfRecord":[],"versionCreatedAt":"2026-02-19 05:17:51","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8730094","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8730094","identity":"rs-8730094","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}