{"id":34230,"date":"2025-11-05T04:51:30","date_gmt":"2025-11-05T03:51:30","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=34230"},"modified":"2025-11-05T15:33:15","modified_gmt":"2025-11-05T14:33:15","slug":"rsa-non-e-piu-quello-di-una-volta-ii","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2025\/11\/05\/rsa-non-e-piu-quello-di-una-volta-ii\/","title":{"rendered":"RSA non \u00e8 pi\u00f9 quello di una volta (II)"},"content":{"rendered":"<p>La scorsa settimana <a href=\"https:\/\/xmau.com\/notiziole\/2025\/10\/29\/rsa-non-e-piu-quello-di-una-volta-i\/\">ho scritto<\/a> che anche se la struttura logica dell&#8217;algoritmo RSA ha cinque parametri, la chiave di cifratura <i>e<\/i> \u00e8 quasi sempre settata a 65537, per ragioni di efficienza computazionale e perch\u00e9 non dovrebbe dare problemi di sicurezza (almeno nei casi normali). Ma c&#8217;\u00e8 anche un&#8217;altra modifica che \u00e8 stata fatta negli anni, sempre per ridurre il costo computazionale (che nel caso della crittografia a chiave pubblica \u00e8 molto pi\u00f9 alto che nei sistemi di crittografia simmetrici).<\/p>\n<p>Ricordo che nell&#8217;algoritmo RSA viene calcolato \u03c6(<i>n<\/i>) = (<i>p<\/i>&minus;1)(<i>q<\/i>&minus;1), dove <i>p<\/i> e q sono i numeri primi di partenza, il cui prodotto \u00e8 <i>n<\/i>, e \u03c6(<i>n<\/i>) \u00e8 la funzione \u03c6 di Eulero, cio\u00e8 quanti sono i numeri minori di <i>n<\/i> e che non hanno fattori primi in comune con <i>n<\/i>. Nel nostro caso \u00e8 facile calcolare il &#8220;toziente&#8221; (altro nome con cui \u00e8 nota la funzione \u03c6 di Eulero), proprio perch\u00e9 <i>p<\/i> e <i>q<\/i> sono primi. <\/p>\n<p>Non \u00e8 per\u00f2 necessario usare \u03c6(<i>n<\/i>) per scegliere un <i>d<\/i> tale che <i>ed<\/i> = 1 (mod \u03c6(<i>n<\/i>)). \u00c8 infatti sufficiente usare la funzione di Carmichael \u03bb(<i>n<\/i>), definita come il pi\u00f9 piccolo intero positivo <i>m<\/i> tale che <i>a<sup>m<\/sup><\/i> \u2261 1 (mod <i>n<\/i>) per ogni <i>a<\/i> coprimo con <i>n<\/i>. Si pu\u00f2 dimostrare che \u03bb(<i>n<\/i>) \u00e8 un divisore di \u03c6(<i>n<\/i>), e quindi \u00e8 un numero pi\u00f9 piccolo e pertanto le operazioni di computazione sono pi\u00f9 brevi. Ma di quanto lo sono? Di un fattore MCD(<i>p<\/i>&minus;1, <i>q<\/i>&minus;1). Chiaramente entrambi i numeri sono pari e quindi c&#8217;\u00e8 un fattore 2, ma si potrebbe sperare che ci sia qualcosa in pi\u00f9. John Cook <a href=\"https:\/\/www.johndcook.com\/blog\/2025\/10\/06\/a-quiet-change-to-rsa\/\">ha fatto qualche prova<\/a>, e ha trovato che su 100 coppie di numeri generati casualmente, la mediana del MCM \u00e8 2 (quindi in almeno met\u00e0 dei casi il fattore \u00e8 effettivamente 2); c&#8217;\u00e8 stato un caso in cui si \u00e8 arrivati a 2370, mentre il valore medio (poco utile in questo caso, perch\u00e9 a noi serve una sola coppia) \u00e8 stato 35,44. In pratica, insomma, abbiamo quasi sempre 2 o 4 come fattore comune, In altri termini, se dobbiamo usare spesso una chiave pu\u00f2 valer la pena di cercare una coppia di primi per cui \u03bb(<i>n<\/i>) \u00e8 effettivamente molto minore di \u03c6(<i>n<\/i>), altrimenti possiamo far finta di niente.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La phi di Eulero non \u00e8 davvero necessaria, anche se cambia in realt\u00e0 poco.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"federated","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1005,214],"tags":[],"class_list":["post-34230","post","type-post","status-publish","format-standard","hentry","category-matelight-2025","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-8U6","jetpack-related-posts":[{"id":34160,"url":"https:\/\/xmau.com\/notiziole\/2025\/10\/29\/rsa-non-e-piu-quello-di-una-volta-i\/","url_meta":{"origin":34230,"position":0},"title":"RSA non \u00e8 pi\u00f9 quello di una volta (I)","author":".mau.","date":"2025-10-29","format":false,"excerpt":"da un bel po' di tempo, ma non cambia in realt\u00e0 molto.","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":33876,"url":"https:\/\/xmau.com\/notiziole\/2025\/10\/01\/base-fibonacci-insieme-di-shevelev-e-congettura-di-kimberling\/","url_meta":{"origin":34230,"position":1},"title":"Base Fibonacci, insieme di Shevelev e congettura di Kimberling","author":".mau.","date":"2025-10-01","format":false,"excerpt":"Un'ennesima strana caratteristica dei numeri di Fibonacci","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":36233,"url":"https:\/\/xmau.com\/notiziole\/2026\/03\/11\/numeri-primoriali-e-compositoriali\/","url_meta":{"origin":34230,"position":2},"title":"Numeri primoriali e compositoriali","author":".mau.","date":"2026-03-11","format":false,"excerpt":"Perch\u00e9 i fattoriali sono troppo mainstream","rel":"","context":"In &quot;mate-light 2026&quot;","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":33311,"url":"https:\/\/xmau.com\/notiziole\/2025\/09\/26\/quanto-sono-migliorati-i-computer\/","url_meta":{"origin":34230,"position":3},"title":"Quanto sono migliorati i computer!","author":".mau.","date":"2025-09-26","format":false,"excerpt":"ma forse anche i programmi di fattorizzazione","rel":"","context":"In &quot;curiosita'&quot;","block_context":{"text":"curiosita'","link":"https:\/\/xmau.com\/notiziole\/category\/curiosita\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":3323,"url":"https:\/\/xmau.com\/notiziole\/2005\/01\/28\/nuove_frontiere\/","url_meta":{"origin":34230,"position":4},"title":"Nuove frontiere","author":".mau.","date":"2005-01-28","format":false,"excerpt":"Abbiamo i numeri primi prodotto di altri numeri primi. [...]","rel":"","context":"In &quot;povera_matematica&quot;","block_context":{"text":"povera_matematica","link":"https:\/\/xmau.com\/notiziole\/category\/povera_matematica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":34334,"url":"https:\/\/xmau.com\/notiziole\/2025\/11\/12\/un-paio-di-dimostrazioni-non-standard\/","url_meta":{"origin":34230,"position":5},"title":"Un paio di dimostrazioni non standard","author":".mau.","date":"2025-11-12","format":false,"excerpt":"A volte ci si ingegna a trovare dimostrazioni matematiche \"inutili\", perch\u00e9 pi\u00f9 complicate, ma con un loro interesse.","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/34230","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=34230"}],"version-history":[{"count":2,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/34230\/revisions"}],"predecessor-version":[{"id":34246,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/34230\/revisions\/34246"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=34230"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=34230"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=34230"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}