{"id":38504,"date":"2026-10-21T04:51:41","date_gmt":"2026-10-21T02:51:41","guid":{"rendered":"https:\/\/xmau.com\/notiziole\/?p=38504"},"modified":"2026-10-20T19:22:48","modified_gmt":"2026-10-20T17:22:48","slug":"come-si-fattorizzano-i-numeri-rsa","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2026\/10\/21\/come-si-fattorizzano-i-numeri-rsa\/","title":{"rendered":"Come si fattorizzano i numeri RSA"},"content":{"rendered":"

Uno dei metodi pi\u00f9 noti di crittografia a chiave pubblica, RSA, si basa sul fatto che \u00e8 difficile trovare i due fattori primi di un numero molto grande. Per dimostrare che in effetti i loro algoritmi sono robusti, nel 1991 gli RSA Laboratories hanno indetto una gara<\/a> nella quale bisognava\u00a0 trovare quali erano i due numeri primi che moltiplicati tra loro davano i numeri da loro presentati. La gara \u00e8 stata ufficialmente chiusa nel 2007, ma comunque gli appassionati hanno continuato a lavorarci su. Era dal 2020 (subito prima del lockdown, nel caso qualcuno volesse fare delle battutine) che non c’erano nuove fattorizzazioni, ma a settembre 2026 ne sono state pubblicate due di nuove: RSA-260, un numero di 260 cifre, e RSA-896, un numero di 896 bit cio\u00e8 270 cifre. Come \u00e8 stato possibile?<\/p>\n

Per il caso di RSA-260 Alan Woodward ha scritto una spiegazione<\/a> (relativamente) semplice della matematica che sta dietro la fattorizzazione di un numero N cos\u00ec grande. Usare il metodo banale (dividere N per tutti i numeri primi fino alla radice quadrata di N, e fermarsi quando il resto \u00e8 zero) \u00e8 impraticabile. L’idea che al momento funziona meglio \u00e8 un’altra: cercare due numeri X e Y tali che X\u00b2\u2212Y\u00b2 sia un multiplo di N. Prendiamo per esempio N=91, un numero che tutti sanno non essere primo. Se X=20 e Y=6, abbiamo X\u00b2\u2212Y\u00b2 = 400\u221236 = 364 = 4\u00b791. Ora, sappiamo che X\u00b2\u2212Y\u00b2 = (X+Y)(X\u2212Y). Se non siamo cos\u00ec sfortunati per cui uno dei due fattori \u00e8 un multiplo di N, sappiamo che i suoi due fattori primi sono uno da una parte e uno dall’altra; ci basta quindi trovare il massimo comun divisore tra X\u2212Y e N. Nel nostro caso abbiamo 14 e 91; l’MCD \u00e8 7, che \u00e8 uno dei fattori di 91. Ovviamente avremmo potuto fare la stessa cosa con X+Y, nel qual caso avremmo trovato 13. Questa \u00e8 la prima idea alla base del General Number Field Sieve, GNFS per gli amici.<\/p>\n

Tutto bellissimo, ma come troviamo X e Y? Qui arriva la seconda idea. Un numero si dice essere “facile” se \u00e8 il prodotto di numeri primi piccoli. Per esempio 300 \u00e8 2\u00b72\u00b73\u00b75\u00b75, e 2, 3, 5 sono primi piccoli. Invece 1372081 \u00e8 un numero primo, e quindi di primi piccoli nella sua fattorizzazione non ce ne sono. Il GNFS setaccia i numeri dell’ordine di N per trovare quelli che sono prodotti di primi piccoli e si salva la loro fattorizzazione; un crivello (sieve) che non \u00e8 quello di Eratostene ma \u00e8 pur sempre un crivello. Una volta che abbiamo tante fattorizzazioni, \u00e8 relativamente semplice costruire dei quadrati perfetti: basta provare a moltiplicare coppie di candidati per avere un risultato dove tutti i primi appaiono un numero pari di volte. Lavorare con primi piccoli rende pi\u00f9 semplice fare questi accoppiamenti, tutto qua. Tutto qua si fa per dire, perch\u00e9 comunque anche questo accoppiamento equivale a una moltiplicazione di matrici sparse di elementi 0 e 1. (“sparse” perch\u00e9 di 1 ce ne sono pochi.) Proprio il tipo di operazioni che fanno gli LLM, tra l’altro. In realt\u00e0 non si usano gli interi ma gli anelli Z<\/em>[r<\/em>], dove\u00a0r<\/em> \u00e8 la radice di un polinomio irriducibile, che cio\u00e8 non ha radici intere; in questo modo si riducono molto i candidati possibili e quindi si velocizza la computazione.<\/p>\n

Naturalmente “velocizzare” \u00e8 sempre relativo: Eric Lu, che ha fattorizzato RSA-260 con la sua startup Cognition, ha detto che l’operazione \u00e8 costata 13,5 anni di GPU, per un costo teorico di 400000 dollari. In realt\u00e0 ha usato tempo morto dei computer di Cognition, quindi il costo \u00e8 teorico. Inolte ha usato un assistente software IA, Devin<\/a>, per accelerare le operazioni. La stima di Lu \u00e8 che si potrebbe dimezzare il costo senza grandi modifiche, e il costo per craccare RSA-1024 sarebbe intorno ai 30 milioni di dollari. Considerando che le chiavi a 1024 bit sono state deprecate nel 2013; la lunghezza minima di chiave suggerita \u00e8 2048 bit, e anche il GNFS non pu\u00f2 fare molto. Si potranno fare miglioramenti? Non si sa, ma cos\u00ec ad occhio non credo che l’IA possa aiutare in questo campo, se non appunto a migliorare il software attuale.<\/p>\n

 

Una spiegazione di base della fattorizzazione di numeri molto grandi. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","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":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","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_feature_clip_id":0,"_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_post_was_ever_published":false},"categories":[1033,214],"tags":[1104,1103],"class_list":["post-38504","post","type-post","status-publish","format-standard","hentry","category-matelight-2026","category-matematica_light","tag-fattorizzazione","tag-gnfs"],"modified_by":".mau.","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-a12","jetpack_likes_enabled":true,"jetpack-related-posts":[{"id":33311,"url":"https:\/\/xmau.com\/notiziole\/2025\/09\/26\/quanto-sono-migliorati-i-computer\/","url_meta":{"origin":38504,"position":0},"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 "curiosita'"","block_context":{"text":"curiosita'","link":"https:\/\/xmau.com\/notiziole\/category\/curiosita\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":34160,"url":"https:\/\/xmau.com\/notiziole\/2025\/10\/29\/rsa-non-e-piu-quello-di-una-volta-i\/","url_meta":{"origin":38504,"position":1},"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 "mate-light-2025"","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":34230,"url":"https:\/\/xmau.com\/notiziole\/2025\/11\/05\/rsa-non-e-piu-quello-di-una-volta-ii\/","url_meta":{"origin":38504,"position":2},"title":"RSA non \u00e8 pi\u00f9 quello di una volta (II)","author":".mau.","date":"2025-11-05","format":false,"excerpt":"La phi di Eulero non \u00e8 davvero necessaria, anche se cambia in realt\u00e0 poco.","rel":"","context":"In "mate-light-2025"","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":3323,"url":"https:\/\/xmau.com\/notiziole\/2005\/01\/28\/nuove_frontiere\/","url_meta":{"origin":38504,"position":3},"title":"Nuove frontiere","author":".mau.","date":"2005-01-28","format":false,"excerpt":"Abbiamo i numeri primi prodotto di altri numeri primi. [...]","rel":"","context":"In "povera_matematica"","block_context":{"text":"povera_matematica","link":"https:\/\/xmau.com\/notiziole\/category\/povera_matematica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":3681,"url":"https:\/\/xmau.com\/notiziole\/2005\/09\/05\/quando_si_dice_basta\/","url_meta":{"origin":38504,"position":4},"title":"quando si dice "basta"…","author":".mau.","date":"2005-09-05","format":false,"excerpt":"Il generatore casuale non genera pi\u00f9: ha fatto il suo tempo.","rel":"","context":"In "IA e informatica"","block_context":{"text":"IA e informatica","link":"https:\/\/xmau.com\/notiziole\/category\/ia\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":33613,"url":"https:\/\/xmau.com\/notiziole\/2025\/09\/08\/adda-veni-la-fattorizzazione-quantistica\/","url_meta":{"origin":38504,"position":5},"title":"Adda ven\u00ec la fattorizzazione quantistica!","author":".mau.","date":"2025-09-08","format":false,"excerpt":"Gi\u00e0 fattorizzare 21 \u00e8 troppo complicato.","rel":"","context":"In "IA e informatica"","block_context":{"text":"IA e informatica","link":"https:\/\/xmau.com\/notiziole\/category\/ia\/"},"img":{"alt_text":"circuito logico quantistico per fattorizzare 15","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/09\/factor15.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/09\/factor15.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/09\/factor15.png?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/09\/factor15.png?resize=700%2C400&ssl=1 2x"},"classes":[]}],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/38504","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=38504"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/38504\/revisions"}],"predecessor-version":[{"id":38510,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/38504\/revisions\/38510"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=38504"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=38504"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=38504"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}