Programma di criptazione/decriptazione

Pubblicità
Stato
Discussione chiusa ad ulteriori risposte.

piergiac-1

Nuovo Utente
Messaggi
38
Reazioni
3
Punteggio
4
Questo programma di cassaforte è open source e utilizza due sistemi di criptazione, fernet e GC57. Fernet immagino lo conosciate un po’ tutti, mentre il GC57 no. Il GC57, più che un sistema di criptazione, è un nuovissimo algoritmo di fattorizzazione con capacità straordinarie che riesce a fattorizzare semiprimi in meno di un secondo indipendentemente dalla sua grandezza. Il programma che sto per presentare, per esempio, utilizza per quanto riguarda la codifica eseguita nella parte GC57, dei semiprimi a 5000bit. Se volete sapere di più su questa formidabile capacità del GC57, troverete tutte le informazioni sul sito www.gc57crypto.net dove viene presentata la sua scoperta con tanto di esempi e documentazione.

Ma torniamo al programma. Sicuramente non riuscirò a spiegare tutto e perciò mi auguro che chi è interessato ad usarlo ponga le sua domande e sarò ben lieto di rispondere.

Il programma, come dicevo, è open source, perciò libero di essere modificato o usato per i propri scopi personali. E’ scritto in Python e quello che io fornirò sarà lo script in chiaro così oltre che a usarlo lo potrete anche studiare, se siete interessati al suo funzionamento. Per farlo funzionare bisogna avere installato Python, che sia su windows o linux, o mac, non ha importanza, l’importante è l’installazione delle librerie richieste che vengono richiamate all’interno del programma. Poi può anche essere compilato in eseguibile, se uno vuole, e usato su più computer senza dover installare Python su ogni computer. Io personalmente lo uso compilato, anche per nascondere la password d’entrata, e lo uso con delle cartelle nel cloud così da avere tutti i dati, documenti, file, foto, o quant’altro, a mia disposizione su qualsiasi computer e in qualsiasi località mi trovo.

All’inizio il programma crea un piccolo file .cfg dove chiede di mostrargli dove prendere i file da criptare e dove li deve depositare. Dentro la cartella che noi abbiamo indicato al programma di dove prendere i file o i dati da criptare, andiamo a inserire a mano tutti i file o documenti che intendiamo proteggere. Sono due cartelle create a priori che nel mio caso sono sul cloud sincronizzate con tutti i miei pc, nel vostro caso dove volete, e potrebbe essere anche su una USB. Questo viene fatto solo una volta, a meno che il file .cfg non venga cancellato. Nell’avvio normale, viene chiesta la password, che si trova ovviamente in chiaro dentro il programma, e viene chiesto di inserire una USB, impostata per default ma che può essere cambiata anche con il programma compilato. Di questa USB ne parliamo dopo ma sappiate che senza quella il programma non funziona.

Nella cartella dove il programma prende i file o dati da criptare, andiamo a mettere tutti quelli che noi vogliamo proteggere, qualsiasi sia il dato da proteggere.

Sempre alla prima esecuzione il programma avvisa che non è stato trovato nessun database nella cartella che gli abbiamo indicato e ci chiederà di proseguire senza per crearne uno nuovo.

A questo punto clicchiamo su apri file nella parte cripta file e selezioniamo uno ad uno i file che vogliamo criptare. Il file verrà criptato con il sistema fernet il quale creerà una chiave simile: “HhdPOWgPzUsT7urPK_5iGb8yEDpQKE7kuK-63DOYUmE=” che verrà poi memorizzata in un database abbinata al file criptato. Questo file con l’estensione finale .crp verrà creato e depositato nella cartella da noi impostata e il file originale verrà cancellato in modo definitivo per non lasciare la possibilità di recuperarlo eventualmente da un cestino. Ogni volta che verrà processato, criptato un file, il database si aggiornerà e verranno tenuti catalogati tutti i file per data, estensione, e nome con cui sono stati memorizza, oltre che naturalmente alla chiave fernet sempre diversa e abbinata solo a quel file.

Siamo a metà dell’opera. I file sono al sicuro dentro una cartella e ora non ci rimane che chiudere il programma con la X in alto a destra che questo procederà a criptare il database con dentro tutte le chiavi e i riferimenti ai file.

Naturalmente da ora in avanti possiamo, tramite il programma, visualizzare i file criptati, aggiungerne dei nuovi o cancellare quelli che non ci servono più, e ogni volta che verrà modifica il database verrà di nuovo criptato con un codice sempre diverso.

Dicevo all’inizio che il programma ha bisogno di leggere su USB un file che contiene la chiave per il GC57. Se questo file non viene trovato il programma non parte. Il contenuto del file è di tipo questo.

762835762534762537654726542789988973
21
19
23
10000
225
5006
389
482
429
260
427

Lo potete usare come prova se volete sperimentare il programma. Nel caso vi piaccia vi dirò come creare da soli il vostro codice chiave in modo da averlo solo voi. Naturalmente anche in questo caso la cosa è totalmente gratuita e open source.

Il file si deve chiamare, sempre nel caso lo voleste provare, dati_cassaforte_crp.txt, e deve essere creato su una USB. Create il file e copiateci dentro quei dati.

Non starò a spiegarvi come funziona il GC57, per il motivo descritto sopra, ma posso dire che le chiavi per la criptazione/decriptazione del database le prende dai semiprimi a 5000bit che devono essere fattorizzati in due numeri primi di circa 2500bit, cosa assai complicata. Se vi state chiedendo quanto vale un bit, sappiate che un numero intero del peso di 2500bit è composto da 753 cifre.

Spero di non essere stato noioso in questo post, e cercherò di rispondere a qualsiasi domanda o dubbio abbiate

Python:
# Cassaforte criptata ultima modifica Maggio 2024
import tkinter as tk
from tkinter import filedialog
from cryptography.fernet import Fernet
import os
from tkinter import messagebox
import customtkinter as tkc
from tkinter import messagebox
import time
import locale
from tkinter import simpledialog
from math import gcd
from sympy import nextprime
import hashlib
from random import randint, seed

T = int(time.time())
seed(T)

locale.setlocale(locale.LC_TIME, "it_IT")

# ****************************************************
# **            Password
# ****************************************************
def hash_password(password):
    salt = os.urandom(32)
    hashed_password = hashlib.pbkdf2_hmac(
        "sha256", password.encode("utf-8"), salt, 100000
    )
    hashed_password_hex = salt.hex() + hashed_password.hex()
    return hashed_password_hex

def verify_password(input_password, stored_password):
    salt = bytes.fromhex(stored_password[:64])
    hashed_input_password = hashlib.pbkdf2_hmac(
        "sha256", input_password.encode("utf-8"), salt, 100000
    )
    return stored_password[64:] == hashed_input_password.hex()

def get_password_from_user():
    def toggle_password():
        if show_password_var.get():
            entry.config(show="")
        else:
            entry.config(show="*")

    def submit():
        nonlocal password
        password = entry.get()
        #password_dialog.destroy()
        dialog.destroy()
    password = None
    dialog = tk.Tk()
    dialog.withdraw()

    password_dialog = tk.Toplevel(dialog)
    password_dialog.title("Password")

    screen_width = password_dialog.winfo_screenwidth()
    screen_height = password_dialog.winfo_screenheight()

    x = (screen_width - 200) // 2
    y = (screen_height - 130) // 2

    password_dialog.configure(bg="#2F4F4F")
    password_dialog.geometry(f"200x130+{x}+{y}")

    tk.Label(password_dialog, text="Inserisci la password:", bg="#2F4F4F").pack(pady=5)

    entry = tk.Entry(password_dialog, show="*", width=30)
    entry.pack(pady=5)

    show_password_var = tk.BooleanVar()
    show_password_checkbox = tk.Checkbutton(
        password_dialog,
        text="Mostra password",
        variable=show_password_var,
        bg="#2F4F4F",
        command=toggle_password,
    )
    show_password_checkbox.pack()

    submit_button = tk.Button(password_dialog, text="OK", bg="#228B22", command=submit)
    submit_button.pack(pady=5)

    # Registra la funzione exit_handler per essere eseguita quando la finestra viene chiusa
    password_dialog.protocol("WM_DELETE_WINDOW", exit_handler)

    dialog.mainloop()

    return password

def exit_handler():
    quit()

password = "12345"
hashed_password = hash_password(password)

input_password = get_password_from_user()

if verify_password(input_password, hashed_password):
    pass
else:
    messagebox.showerror("Errore", "La password inserita è errata.")
    quit()

# *******************************************************
# * controllo file CFG
# *******************************************************

filecfg = "CsCfg"
if os.path.exists(filecfg):
    pass
else:

    def esci_pr():
        risposta=messagebox.askquestion("Attenzione","Il programma sta per essere\nchiuso per mancanza dei dati richiesti\nsi vuole continuare?")
        if risposta=="yes":
            rootcfg.destroy()
            quit()
        else:
            return              
           
    def salva_esci():

        controllo1 = e2_cfg.get()
        if controllo1 == "":
            messagebox.showerror("Attenzione:", "Tutti i campi devono essere compilati")
            return
        elif os.path.exists(f"{controllo1}"):
            pass
        else:
            messagebox.showerror("Attenzione:", "La cartella INVIO non esiste")
            return

        controllo2 = e3_cfg.get()
        if controllo2 == "":
            messagebox.showerror("Attenzione:", "Tutti i campi devono essere compilati")
            return
        elif os.path.exists(f"{controllo2}"):
            pass
        else:
            messagebox.showerror("Attenzione:", "La cartella RICEVE non esiste")
            return

        scrivi = open("CsCfg", "w")
        scrivi.write(controllo1 + "\n")
        scrivi.write(controllo2 + "\n")
        scrivi.close()
        messagebox.showinfo("Salvataggi CFG:", "Configurazione Salvata")
        rootcfg.destroy()

    rootcfg = tk.Tk()

    # Imposta le dimensioni della finestra
    window_width = 415
    window_height = 330

    # Ottieni le dimensioni dello schermo
    screen_width = rootcfg.winfo_screenwidth()
    screen_height = rootcfg.winfo_screenheight()

    # Calcola la posizione x e y per centrare la finestra
    x = (screen_width - window_width) // 2
    y = (screen_height - window_height) // 2

    # Imposta la posizione e le dimensioni della finestra
    rootcfg.geometry(f"{window_width}x{window_height}+{x}+{y}")
    rootcfg.title("Configurazione Cartelle GC57")
    rootcfg.configure(bg="#458B74")
    colore_testo_entry = "#104E8B"
    testo = (
        "Se appare questa finestra è perchè il programma viene eseguito per la prima volta in questa posizione, \
oppure il file 'CsCfg' è stato cancellato\n\
Copiare e incollare con CTR-V la posizione delle cartelle:",
    )

    l1_cfg = tk.Label(
        rootcfg, text=testo, justify=tk.LEFT, font="arial 12 bold", wraplength=400
    )
    l1_cfg.place(x=10, y=20)

    px = 10
    py = 150
    l2_cfg = tk.Label(
        rootcfg,
        text="Incollare Indirizzo Cartella Cassaforte",
        bg="#458B74",
        font="arial 12 bold",
    )
    l2_cfg.place(x=px, y=py)
    py = py + 20
    e2_cfg = tk.Entry(rootcfg, width=40, fg=colore_testo_entry, font="arial 12")
    e2_cfg.place(x=px, y=py)

    py = py + 30
    l3_cfg = tk.Label(
        rootcfg,
        text="Incollare Indirizzo Cartella DCP",
        bg="#458B74",
        font="arial 12 bold",
    )
    l3_cfg.place(x=px, y=py)
    py = py + 20
    e3_cfg = tk.Entry(rootcfg, width=40, fg=colore_testo_entry, font="arial 12")
    e3_cfg.place(x=px, y=py)

    px = px + 150
    py = py + 50
    b1 = tk.Button(
        rootcfg,
        text="Salva ed Esci",
        font="arial 12 bold",
        cursor="hand1",
        bg="green",
        command=salva_esci,
    )
    b1.place(x=px, y=py)
    rootcfg.protocol("WM_DELETE_WINDOW", esci_pr)

    rootcfg.mainloop()

# *******************************************************
# * Carica CFG
# *******************************************************
filename = ""
apricfg = open("CsCfg", "r")
cartella2 = apricfg.readline().strip()
cartella1 = apricfg.readline().strip()
apricfg.close()


# *******************************************************
# * Controllo porta USB
# *******************************************************
apri_dati = simpledialog.askstring("USB", "Inserisci la porta USB se diversa da D")
if apri_dati == None:
    quit()

if not apri_dati:
    apri_dati = "d"
usb_path = apri_dati + ":\\"

if os.path.exists(usb_path):
    try:
        storage_devices = os.listdir(usb_path)
    except FileNotFoundError:
        pass
else:
    messagebox.showwarning(
        "Attenzione", "Chiavetta USB non trovata nella lettera di unità " + apri_dati
    )
    quit()

# ****************************************************
# **  Cerca nella USB i dati di criptazione GC57
# ****************************************************

file_path = os.path.join(apri_dati + ":", "dati_cassaforte_crp.txt")

try:
    with open(file_path, "r") as leggif:
        leggi1 = leggif.readline().strip()
        leggi2 = leggif.readline().strip()
        leggi3 = leggif.readline().strip()
        leggi4 = leggif.readline().strip()
        leggi5 = leggif.readline().strip()
        leggi6 = leggif.readline().strip()
        leggi7 = leggif.readline().strip()
        m1 = int(leggif.readline())
        m2 = int(leggif.readline())
        m3 = int(leggif.readline())
        m4 = int(leggif.readline())
        m5 = int(leggif.readline())
except FileNotFoundError:
    messagebox.showerror("Errore", "Dati su USB non trovati")
    quit()

# ****************************************************
# ** Vede se c'è il file criptato delle chiavi per decriptarlo
# ****************************************************

path = cartella2 + "/database_chiavi.cr"
if os.path.exists(path):
    leggi = open(path, "r")
    n_semiprimo = leggi.readline()
    testo_criptato = leggi.readline()
    leggi.close()
    n_semiprimo = n_semiprimo.strip()

    testo_criptato = testo_criptato.strip()
    chiave = int(leggi1) ** int(leggi2)
    n_semiprimo = int(n_semiprimo)
    a = n_semiprimo % chiave
    b = n_semiprimo - a
    for i in range(10):
        r = gcd(b, a)
        if r != 1:
            break
        a = a + chiave
        b = b - chiave
    if r == 1:
        messagebox.showerror("Attenzione", "Chiave GC57 errata")
        quit()
    start1 = str(r)
    start2 = len(start1)
    start = int(start1[start2 - 5] + start1[start2 - 4])
    ln = list(str(r))
    if len(ln) % 2 == 0:
        pass
    else:
        ln.append("0")

    divln = []
    for i in range(0, len(ln), 2):
        c1 = int(ln[i])
        c2 = int(ln[i + 1])
        c3 = c1 * 10 + c2
        divln.append(c3)

    te = []
    d0 = list(testo_criptato)
    for i in range(0, len(d0), 3):
        d1 = d0[i]
        d2 = d0[i + 1]
        d3 = d0[i + 2]
        te.append(d1 + d2 + d3)
    cont = start
    tdecript = ""
    for i in range(len(te)):
        if cont >= len(divln):
            cont = 0
        x = int(divln[cont])
        if x >= 0 and x < 25:
            y = int(te[i])
            tdecript = tdecript + (chr(y - x - m1))
        if x >= 25 and x < 40:
            y = int(te[i])
            tdecript = tdecript + (chr(y - x - m2))
        if x >= 40 and x < 50:
            y = int(te[i])
            tdecript = tdecript + (chr(y - x - m3))
        if x >= 50 and x < 75:
            y = int(te[i])
            tdecript = tdecript + (chr(y - x - m4))
        if x >= 75 and x < 100:
            y = int(te[i])
            tdecript = tdecript + (chr(y - x - m5))
        cont = cont + 1
    path = cartella1 + "/database_chiavi.txt"
    scrivi = open(path, "w")
    scrivi.write(str(tdecript) + "\n")
    scrivi.close()
else:
    risposta = messagebox.askquestion(
        "Attenzione",
        "Il database_chiavi è stato rimosso\no non ancora creato\nsi vuole proseguire",
    )
    if risposta == "yes":
        pass
    else:
        quit()

# ****************************************************
# ** Esce dal programma e cripta il database delle chiavi fernet
# ****************************************************

def esci():
    if lmodifica.cget("text") == "O":
        scegli = messagebox.askquestion(
            "Uscita Programma",
            "Il database chiavi non è stato modificato\nVuoi Cancellare tutti i file decriptati?",
        )
        if scegli == "yes":
            cartella = cartella1
            for elemento in os.listdir(cartella):
                percorso_elemento = os.path.join(cartella, elemento)

                if os.path.isfile(percorso_elemento):
                    os.remove(percorso_elemento)
            window.destroy()
            quit()
        else:
            cancella = cartella1 + "/database_chiavi.txt"
            if os.path.exists(cancella):
                os.remove(cancella)
            window.destroy()
            quit()

    messagebox.showinfo(
        "Uscita Programma",
        "Lasciare che il programma esegua la criptazione delle chiavi",
    )
    path = cartella1 + "/database_chiavi.txt"
    testo = ""
    apri = open(path, "r")
    for i in range(10000):
        te = apri.readline()
        if te == "\n" or te == "":
            apri.close()
            break
        testo = testo + te
    testo = testo.strip()
    p = int(leggi1) ** int(leggi3)
    q = int(leggi1) ** int(leggi4)
    nd = nextprime(p + randint(1, int(leggi5) * 2 ** int(leggi6)))
    nd2 = nextprime(q + randint(1, int(leggi5) * 2 ** int(leggi6)))
    n = nd * nd2
    # ******************* controllo di fattorizzazione
    chiave = int(leggi1) ** int(leggi2)
    a = n % chiave
    b = n - a
    for i in range(10):
        r = gcd(a, b)
        if r != 1:
            break
        else:
            a = a + chiave
            b = b - chiave
    if r == 1:
        messagebox.showerror("Attenzione", "Test non superato: Riprovare")
        return
    # ******************* fine controllo
    start1 = str(nd)
    start2 = len(start1)
    start = int(start1[start2 - 5] + start1[start2 - 4])
    ln = list(str(nd))
    if len(ln) % 2 == 0:
        pass
    else:
        ln.append("0")
    divln = []
    for i in range(0, len(ln), 2):
        c1 = int(ln[i])
        c2 = int(ln[i + 1])
        c3 = c1 * 10 + c2
        divln.append(c3)

    text = testo
    te = list(text)
    cont = start
    tcript = ""

    for i in range(len(text)):
        if cont >= len(divln):
            cont = 0
        if ord(te[i]) > 700:
            pass
        else:
            x = int(divln[cont])
            if x >= 0 and x < 25:
                x = x + m1 + ord(te[i])
            if x >= 25 and x < 40:
                x = x + m2 + ord(te[i])
            if x >= 40 and x < 50:
                x = x + m3 + ord(te[i])
            if x >= 50 and x < 75:
                x = x + m4 + ord(te[i])
            if x >= 75 and x < 100:
                x = x + m5 + ord(te[i])
            tcript = tcript + str(x)
            cont = cont + 1

    path = cartella2 + "/database_chiavi.cr"
    scrivi = open(path, "w")
    scrivi.write(str(n) + "\n")
    scrivi.write(tcript + "\n")
    scrivi.close()
    messagebox.showinfo("OK", "Database memorizzato con GC57 correttamente")
    path = cartella2 + "/database_chiavi.cr"
    cancella = cartella1 + "/database_chiavi.txt"
    if os.path.exists(path):
        os.remove(cancella)
    else:
        pass

    cartella = cartella1

    elementi_cartella = os.listdir(cartella)

    file_nella_cartella = any(
        os.path.isfile(os.path.join(cartella, elemento))
        for elemento in elementi_cartella
    )

    if file_nella_cartella:
        risposta = messagebox.askquestion(
            "Cartella DCP", "Ci sono dei dati decodificati\nVuoi Eliminarli?"
        )
        if risposta == "yes":
            for elemento in os.listdir(cartella):
                percorso_elemento = os.path.join(cartella, elemento)
                if os.path.isfile(percorso_elemento):
                    os.remove(percorso_elemento)

    window.destroy()

# ****************************************************
# **        Cancella file criptati
# ****************************************************
def cancella_cr():
    initial_dir = cartella2
    filename = filedialog.askopenfilename(
        initialdir=initial_dir,
        filetypes=(("File Criptato", "*.crp"), ("File Criptato", "*.crp")),
    )
    nome_file = os.path.split(filename)
    risposta = messagebox.askquestion("Vuoi cancellare questo file??", nome_file)
    if risposta == "yes":
        pass
    else:
        return
    nome_database = nome_file[1].replace(".crp", "")
    database = []
    trovato = 0
    apri = open(cartella1 + "/database_chiavi.txt", "r")
    for i in range(10000):
        leggi_database = apri.readline()
        if leggi_database == "\n" or leggi_database == "":
            apri.close()
            break
        if nome_database in leggi_database:
            trovato = 1
            pass
        else:
            leggi_database = leggi_database.strip()
            database.append(leggi_database)
    database.append("fine")
    if trovato == 0:
        messagebox.showerror("Cancella file criptato", "Nessun dato trovato")
        return
    lmodifica.configure(text="M")

    apri = open(cartella1 + "/database_chiavi.txt", "w")
    for i in range(10000):
        if database[i] == "fine":
            apri.close()
            break
        apri.write(database[i] + "\n")
    cancella = cartella2 + "/" + nome_file[1]
    os.remove(cancella)
    messagebox.showinfo("Cancella file criptao:", "File cancellato con successo")

# ****************************************************
# **             Generazione codice fernet
# ****************************************************
def generate_key_if_not_exists(key_filename):
    if not os.path.exists(key_filename):
        key = generate_key()
        save_key(key, key_filename)
    else:
        key = load_key(key_filename)
    return key

def generate_key():
    return Fernet.generate_key()

def save_key(key, filename):
    with open(filename, "wb") as key_file:
        key_file.write(key)

def load_key(filename):
    return open(filename, "rb").read()

def encrypt_file(key, input_file, output_file):
    cipher = Fernet(key)

    with open(input_file, "rb") as file:
        data = file.read()

    encrypted_data = cipher.encrypt(data)

    with open(output_file, "wb") as file:
        file.write(encrypted_data)

def decrypt_file(key, input_file, output_file):
    cipher = Fernet(key)

    with open(input_file, "rb") as file:
        encrypted_data = file.read()

    decrypted_data = cipher.decrypt(encrypted_data)

    with open(output_file, "wb") as file:
        file.write(decrypted_data)

def choose_file(entry_widget):
    initial_dir = cartella1
    filename = filedialog.askopenfilename(
        initialdir=initial_dir,
        filetypes=(
            ("Tutti i File", "*.*"),
            ("File di testo", "*.txt"),
            ("File eseguibile", "*.exe"),
            ("File Video", "*.mpeg *.mpg *.mkw *.mp4"),
            ("File Audio", "*.mp3 *.wav *.flac "),
            ("File Immagini", "*.jpg *.jpeg *.jpe *.webp *.ico *.png *.xcf *.bmp"),
            ("File Libreoffice", "*.odt *.ods *.odg *.odf"),
        ),
    )
    nome_file = os.path.split(filename)
    entry_widget.delete(0, tk.END)
    entry_widget.insert(0, nome_file[1])

def choose_file2(entry_widget):
    initial_dir = cartella2
    filename = filedialog.askopenfilename(
        initialdir=initial_dir,
        filetypes=(("File Criptato", "*.crp"), ("File Criptato", "*.crp")),
    )
    nome_file = os.path.split(filename)
    entry_widget.delete(0, tk.END)
    entry_widget.insert(0, nome_file[1])

# ****************************************************
# **  crea i dati per criptare il file
# ****************************************************

def on_encrypt():
    file_to_encrypt = e1.get()
    if file_to_encrypt == "":
        messagebox.showerror("Errore:", "Nessun file selezionato")
        return
    if file_to_encrypt == "database_chiavi.txt":
        messagebox.showinfo("File criptato come: ", "questo file non si può criptare")
        e1.delete(0, "end")
        return
    output_filename = cartella2 + "/" + file_to_encrypt + ".crp"

    if os.path.exists(output_filename):
        messagebox.showerror(
            "Cripta File:",
            "questo file esiste già e non può essere sostituito\ncancellare prima il file se lo si vuole sostituire",
        )
        return
    lmodifica.configure(text="M")

    nome_file = file_to_encrypt
    file_to_encrypt = cartella1 + "/" + file_to_encrypt
    key = generate_key()

    encrypt_file(key, file_to_encrypt, output_filename)
    # os.remove(file_to_encrypt)
    data = time.strftime("%A:%B:%Y")
    memorizza_key = key.decode("utf-8") + "," + nome_file + "," + str(data)
    apri_file_key = open(cartella1 + "/database_chiavi.txt", "a")
    apri_file_key.write(memorizza_key + "\n")
    apri_file_key.close()
    messagebox.showinfo("File criptato come: ", output_filename)
    e1.delete(0, "end")
    path = output_filename
    cancella = file_to_encrypt
    if os.path.exists(path):
        os.remove(cancella)
    else:
        pass

# ****************************************************
# **  crea i dati per decriptare il file
# ****************************************************

def on_decrypt():
    file_to_decrypt = e2.get()
    if file_to_decrypt == "":
        messagebox.showerror("Errore:", "Nessun file selezionato")
        return
    nome_originale = e2.get().replace(".crp", "")
    apri = open(cartella1 + "/database_chiavi.txt", "r")
    for i in range(1000):
        stringa = apri.readline()
        stringa = stringa.strip()
        if stringa == "\n" or stringa == "":
            messagebox.showinfo("Ricerca Codice:", "Nessun codice Trovato")
            apri.close()
            return
        trovata = nome_originale in stringa
        if trovata == True:
            sp = stringa.split(",")
            chiave = sp[0].encode("utf-8")
            apri.close()
            break

    original_filename = cartella1 + "/" + file_to_decrypt.replace(".crp", "")
    file_to_decrypt = cartella2 + "/" + file_to_decrypt

    decrypt_file(chiave, file_to_decrypt, original_filename)
    e2.delete(0, "end")
    messagebox.showinfo("File decriptato come:", original_filename)

# ****************************************************
# **  Interfaccia principale customtkinter
# ****************************************************

# Modes: system (default), light, dark
tkc.set_appearance_mode("dark")
# Themes: blue (default), dark-blue, green
tkc.set_default_color_theme("blue")
window = tkc.CTk()  # create CTk window like you do with the Tk window
window.geometry("460x250")
window.title("Cripta/Decripta Metodo Fermat 128bit/GC57")
# Creazione degli elementi nella finestra
px = 50
e1 = tkc.CTkEntry(window, width=300, font=("Helvetica", 12), justify=tkc.CENTER)
e1.place(x=px, y=10)
b1 = tkc.CTkButton(
    master=window,
    width=50,
    text="Apri file",
    fg_color="blue",
    hover_color="green",
    command=lambda: choose_file(e1),
)
b1.place(x=px + 320, y=10)
b2 = tkc.CTkButton(
    master=window,
    width=300,
    text="Cripta File",
    fg_color="blue",
    hover_color="green",
    command=on_encrypt,
)
b2.place(x=px, y=40)

py = 100
e2 = tkc.CTkEntry(window, width=300, font=("Helvetica", 12), justify=tkc.CENTER)
e2.place(x=px, y=py)
b3 = tkc.CTkButton(
    master=window,
    width=300,
    text="Decripta file",
    fg_color="blue",
    hover_color="green",
    command=on_decrypt,
)
b3.place(x=px, y=py + 30)
b4 = tkc.CTkButton(
    master=window,
    width=50,
    text="Apri file",
    fg_color="blue",
    hover_color="green",
    command=lambda: choose_file2(e2),
)
b4.place(x=px + 320, y=py)
lmodifica = tkc.CTkLabel(
    master=window, text="O", fg_color="transparent", font=("arial", 12, "bold")
)
lmodifica.place(x=10, y=py + 70)
b5 = tkc.CTkButton(
    master=window,
    width=300,
    text="Elimina un file criptato e aggiorna il Database",
    fg_color="blue",
    hover_color="red",
    command=cancella_cr,
)
b5.place(x=px, y=py + 100)

window.protocol("WM_DELETE_WINDOW", esci)

window.mainloop()
 
Ultima modifica da un moderatore:
semplice spam, penso sia il solito bot senziente che prende roba e ci inserisce il link per il redirect
 
Ma tutta sta pappardella per dire cosa?

Io ho trovato una repo github https://github.com/Claugo/GC57_cassaforte/blob/main/CassaCriptata2.py

E il codice sorgente mi sembra lo stesso che tu hai postato.

Non capisco questo thread.
Mi dai delucidazioni?
mi fa piacere che tu abbia trovato il programma su Github perchè è sempre mio. Immagino tu abbia visto anche gli altri programmi come GC57eAL. Questo post non è spam come dice mr_loco ma è un modo per mostrare questo algoritmo a molti che lo ignorano. Mi chiedi perchè lo faccio? Non certo per guadagnarci, lo faccio perchè credo che l'algoritmo abbia delle caratteristiche uniche e meriti essere conosciuto. Se mi sbaglio mi farebbe piacere sentirmi dire da persone competenti che non vale niente
 
Se mi sbaglio mi farebbe piacere sentirmi dire da persone competenti che non vale niente
apprezzo il fatto di dedicare il proprio tempo a simili ragionamenti, è un ottimo allenamento per la mente e un bell'esercizio di programmazione.

Tuttavia sono andato a qguardare le speigazioni che dai in "Gli step della ricerca" beh... abbi pazienza ma dal punto di vista matematico fanno acqua da tutte le parti, non hanno generalità né rigore matematico: dove sono le dimostrazioni?

Poi parli di complessità non mi pare che tu abbia le idee chiarissime: addirittura parli di O(1).... siamo seri su!
O(1) significa tempo costante indipendentemente dalla grandezza dell'input, il che è banalmente falso, anzi assurdo;

D'altra parte basta guardare anche superficialmente i passi dell'algoritmo: moltiplichi numeri interi ma la moltiplicazione non è affatto un'operazione O(1): moltiplicare 2 interi da n cifre ha complessità nel migliore dei casi (è un limite inferiore) di n*log(n) (il logaritmo è in base 2), dimostrato da Harvey e Van Den Hoeven nel 2019; con un po' di fortuna si può limare il tempo, ma tant'è;
altra cosa che fai è che poi estrai la radice quadrata e nemmeno quella è gratis o O(1)
così ad occhio stai confondendo la singola istruzione in Python come se il suo costo computazionale fosse O(1)...

NOTA BENE: io non ti sto dicendo che il tuo algoritmo non funzioni, ti sto dicendo che manca di generalità e soprattutto che la complessità computazionale non è affatto quella che credi

Al momento e a memoria, il miglior algoritmo per fattorizzare un intero è l'lagoritmo di Shor (non so se ce ne siano altri): si tratta di un algoritmo quantistico di complessità polinomiale ossia è di complessità polinomiale se viene eseguito su un computer quantistico...;
la ricerca va verso algoritmi post-quantum cryptography, poiché i computer quantistici possono TEORICAMENTE essere equiparati a macchine non deterministiche, ossia macchine che possono risolvere in tempo polinomiale, problemi che attualmente richiedono tempo super-polinomiale su computer tradizionali
 
Grazie Bat per la risposta
Tuttavia sono andato a qguardare le speigazioni che dai in "Gli step della ricerca" beh... abbi pazienza ma dal punto di vista matematico fanno acqua da tutte le parti, non hanno generalità né rigore matematico: dove sono le dimostrazioni?
Nella pagina esempi numerici ho messo alcuni esempi pratici su numeri semiprimi molto grandi e ho invitato a provarli sul proprio computer utilizzando la chiave assegnata. Il fatto che non abbiano un rigore matematico è certamente vero in quanto io non sono un matematico. La sostanza sta nella capacità di risolvere in concreto un'operazione complessa come può essere la fattorizzazione sui grandi semiprimi

poi parli di complessità non mi pare che tu abbia le idee chiarissime: addirittura parli di O(1).... siamo seri su!
O(1) significa tempo costante indipendentemente dalla grandezza dell'input, il che è banalmente falso, anzi assurdo

So benissimo cosa significa O(1) e non mi sono sbagliato a scriverlo. Ti faccio un piccolo esempio: Parliamo solo di fattorizzazione naturalmente.
Prendi due numeri primi e li moltiplichi creando il semiprimo S=pq
I due numeri primi sono presi in questa forma p=n^1200+RND(1,2^1000), q=n1^1206+RND(2^1000), dove n e n1 sono due numeri diversi e RND è un numero casuale che va da 1 a 2^1000.
Dal numero semiprimo ottenuto l'algoritmo GC57 otterrà tramite la chiave i due numeri primi che lo compongono con velocità O(1) meno di un secondo. Puoi ripetere l'operazione tutte le volte che vuoi e con RND avrai sempre dei semiprimi diversi ma il tempo di fattorizzazione sarà sempre uguale, meno di un secondo.
Ora vediamo perchè allora O(1) vale per qualsiasi grandezza: cambiamo i parametri dei numeri primi p=n^1500+RND(1,2^1000), q=n1^1508+RND(2^1000). Ripeti più volte lo stesso processo con RND e avrai lo stesso risultato. La velocità di fattorizzazione con la chiave GC57 rimarrà sempra a velocita O(1) meno di un secondo.
Ora mi dovresti dire perchè è banalmente falso. Solo una cosa vorrei che tu tenessi in considerazione e cioè che quello che io affermo avete la possibilità di sperimentarlo voi stessi sul vostro computer, anche fosse un celeron.

Al momento e a memoria, il miglior algoritmo per fattorizzare un intero è l'lagoritmo di Shor (non so se ce ne siano altri): si tratta di un algoritmo quantistico di complessità polinomiale ossia è di complessità polinomiale se viene eseguito su un computer quantistico...;

Al momento l'algoritmo più potente riconosciuto dalla comunità scentfico matematica è GNFS General Number Field Sieve. Quello di Shor è inutilizzabile con i computer attuali.. Ma il mio algoritmo ha qualcosa che gli altri non hanno, non voglio essere certamente presuntuoso e mi limito solo ai fatti e non a teorie strampalate, e cioè può fattorizzare miliardi di miliardi di semiprimi con delle grandezze mai raggiunte prima mantenendo sempre la velocità costante O(1) meno di un secondo. Questo lo posso dimostrare come e quando vuoi
 
Ultima modifica:
Ciao, lasciando perdere la criptazione dei file, vorrei soffermarmi sulla parte prettamente logico-matematica della questione. Premesso che non so nulla di questi argomenti, mi sembra di capire che un "semiprimo" sia il prodotto di due numero primi, e da wikipedia leggo:
I semiprimi sono molto utili nell'area della crittografia e la teoria dei numeri, [...] Questi metodi contano sul fatto che trovare due numeri primi grandi e moltiplicarli è computabilmente facile, mentre trovare i fattori originali è computazionalmente proibitivo con i mezzi di calcolo odierni e prevedibilmente disponibili in un futuro prossimo.
In particolare mi ha colpito l'affermazione che trovare numeri primi grandi sia "computabilmente facile", in quanto si tratta di una questione su cui non mi è mai capitato di soffermarmi prima d'ora.
In ogni caso da una lettura veloce dei tuoi post mi sembra di capire che il tuo algoritmo di fattorizzazione non sia pensato per input generici, ma per semiprimi derivanti dal prodotto di numeri primi di un certo tipo, giusto? E in tal caso qual è la formula generale che utilizzi per il calcolo dei due primi?
 
Ciao, lasciando perdere la criptazione dei file, vorrei soffermarmi sulla parte prettamente logico-matematica della questione. Premesso che non so nulla di questi argomenti, mi sembra di capire che un "semiprimo" sia il prodotto di due numero primi, e da wikipedia leggo:

In particolare mi ha colpito l'affermazione che trovare numeri primi grandi sia "computabilmente facile", in quanto si tratta di una questione su cui non mi è mai capitato di soffermarmi prima d'ora.
In ogni caso da una lettura veloce dei tuoi post mi sembra di capire che il tuo algoritmo di fattorizzazione non sia pensato per input generici, ma per semiprimi derivanti dal prodotto di numeri primi di un certo tipo, giusto? E in tal caso qual è la formula generale che utilizzi per il calcolo dei due primi?
Ciao, si i semiprimi sono il prodotto di due numeri primi. Per capirci meglio il numero primo è quel numero naturale che non ha altri divisori se non se stesso e 1. (2-3-5-7-11-13...) Il semiprimo è il prodotto di due numeri primi 3*7=21 7*11=77 2*13=26.
La complessita di risolvere una fattorizzazione sui semiprimi grandi, o molto grandi, sta proprio nel fatto che esistono solo due numeri non banali che lo posso fare. La mia scoperta sulla fattorizzazione elimina questo problema inserendo un nuovo elemento, una chiave. Questa chiave porta in modo molto efficente e veloce a identificare uno dei due numeri primi.

In particolare mi ha colpito l'affermazione che trovare numeri primi grandi sia "computabilmente facile", in quanto si tratta di una questione su cui non mi è mai capitato di soffermarmi prima d'ora.
Si è computazionalmente facile, grazie agli algoritmi probabilistici come quello di Rabin-Miller.
Questi calcoli hanno una probabilità di errore molto bassa e vengono usati per identificare numeri primi anche molto grandi. Gli stessi numeri RSA vengono affidati a questo metodo. Ci sono programmi come Pari/Gp o librerie come Sympy in Python, che eseguono questi calcoli. Ammettiamo che in Python vuoi trovare un numero primo. Dopo aver caricato la libreria esegui questo comando nextprime(n), dove n è un numero intero qualsiasi, anche digitato a mano libera, e ti restituirà il numero primo, su base probabilistica, che troverà subito dopo n.
Questo calcolo è più o meno lungo e va in base alla grandezza del numero, che può essere di neanche un secondo per numeri a 100/200 cifre, a oltre qualche minuto per numeri più grandi. Per esempio un numero primo di 800 cifre viene identificato in 5 o10 minuti. Perchè questa differenza? La differenza non sta tanto nel numero grande, anche se quello sicuramente incide, ma è il fatto che con l'aumentare dei numeri naturali i numeri primi diventano sempre meno, e per questo motivo, sui numeri molto grandi bisogna testarne molti di più per trovarne uno.

In ogni caso da una lettura veloce dei tuoi post mi sembra di capire che il tuo algoritmo di fattorizzazione non sia pensato per input generici, ma per semiprimi derivanti dal prodotto di numeri primi di un certo tipo, giusto? E in tal caso qual è la formula generale che utilizzi per il calcolo dei due primi?

Non è del tutto esatto. Si possono inserire anche numeri digitati a mano in modo casuale e trasformati in numeri primi come descritto sopra.
Questo sistema è completamente nuovo e offre degli spunti di ricerca interessantissimi. Nel sito che ho creato per spiegare come funziona e quali potrebbero essere le sue potenzialità, ho aggiunto una sezione che parla di eventuali sviluppi. E' proprio di qualche settimana fa l'ultimo sviluppo inaspettato della scoperta di una nuova famiglia molto ampia. Questo tipo di famiglia mette in evidenza la scoperta di due genitori differenti tra loro e che il campo in cui operano è il doppio di quello trovato fino ad ora, e cioè di 2^500, portandolo a 2^1000
 
Ultima modifica:
Non è del tutto esatto. Si possono inserire anche numeri digitati a mano in modo casuale e trasformati in numeri primi come descritto sopra.
Ti riferisci alla funzione nextprime(n) ?
Giusto per capire, nextprime(n) ritorna il numero primo immediatamente successivo al parametro n fornito alla funzione, è corretto?
In tal caso stai dicendo che il tuo algoritmo di fattorizzazione dovrebbe funzionare anche con i numeri RSA, in quanto, per quanto improbabile, è possibile che con due chiamate a nextprime(n) vada a pescare proprio due primi il cui prodotto sia uguale ad un semiprimo RSA. Sbaglio?
 
Al momento l'algoritmo più potente riconosciuto dalla comunità scentfico matematica è GNFS General Number Field Sieve
che non è un algoritmo quantistico, infatti ha complessità esponenziale/superpolinomiale
l'lagoritmo di Shor è polinomiale (con la "lieve" limitazione che serve un computer quantistico)
ma non è questo il punto
So benissimo cosa significa O(1) e non mi sono sbagliato a scriverlo.
no,mi spiace ma non lo sai: confondi O(1) con il "tempo costante di meno di un secondo"
p=n^1200+RND(1,2^1000) non è O(1) perché RND non lo è 😟
nextprime() non è O(1)
radice quadrata non è O(1)
massimo comun divisore e minimo comune multiplo non sono O(1)
dal cui deduco che non hai nessuna familiarità col concetto di complessità computazionale
Ora mi dovresti dire perchè è banalmente falso
perché, è basato su premesse false:
O(1) non è il tempo di esecuzione misurato in (nano)secondi
O(1)
è la misura di complessità computazionale di una operazione elementare di programmazione e, supponendo (ottimisticamente) di rendere "omogenee" le operazioni aritmetiche, sono di complessità O(1) le seguenti istruzioni:
  • operazioni aritmetiche tra numeri (+ - * /), tuttavia anche qui ci sarebbe da discutere...
  • dichiarazione/assegnazione di una valore ad una variabile
  • stampa di una stringa o lettura di un input
usare qualunque altra funzione (come i generatori random) rende automaticamente qualunque algoritmo di complessità superiore
usare una funzione di generazione pseudocasuale non è O(1)
i cicli non sono O(1), un ciclo ripetuto n voltè è O(n) a patto che sia composto solo da singole istruzioni elementari che siano ciascuna O(1);

nel codice usi sia generatori random che cicli, quindi non può essere O(1), non c'è nulla di cui discutere
"tempo fisico (più o meno) costante" e O(1) sono 2 cose concettualmente diverse:
  • la complessità computazionale calcola il tempo di esecuzione di un algoritmo in termini di numero di operazioni elementari eseguite, perché è un cirterio oggettivo
  • il tempo fisico (quello che gli esseri umani misurano in secondi e/o loro multipli o sottomultipli) invece non è una misura oggettiva perché dipende dalla velocità della macchina che lo esegue
Codice di programmazione a parte, un algoritmo va descritto in modo formale (non a chiacchiere) e si deve dimostranerne correttezza e completezza;
  • correttezza in parole povere significa che l'algoritmo restituisce risultati corretti
  • completezza significa che funziona in tutti i casi possibili
  • le 2 cose richiedono una DIMOSTRAZIONE MATEMATICA formale, le chiacchiere non servono
ammesso e non concesso che il tuo algoritmo sia corretto, non è completo, quindi di fatto non vale nulla dal punto di vista teorico e ancor meno che a fini pratici: "fattorizzi" numeri che hanno una struttura che ti fa comodo, ma la sicurezza della crittografia sa nel fatto che sia "impossibile a livello pratico" eseguire una fattorizzazione in tempi ragionevoli.
il campo in cui operano è il doppio di quello trovato fino ad ora, e cioè di 2^500, portandolo a 2^1000
la matematica non è un'opinine: il doppio di 2^500 è 2^501 😉 pensaci su
 
Ti riferisci alla funzione nextprime(n) ?
Giusto per capire, nextprime(n) ritorna il numero primo immediatamente successivo al parametro n fornito alla funzione, è corretto?
In tal caso stai dicendo che il tuo algoritmo di fattorizzazione dovrebbe funzionare anche con i numeri RSA, in quanto, per quanto improbabile, è possibile che con due chiamate a nextprime(n) vada a pescare proprio due primi il cui prodotto sia uguale ad un semiprimo RSA. Sbaglio?

Si, esatto. nextprime intercetta il numero primo subito dopo n.
L'agoritmo GC57 funziona si con numeri RSA ed è quanto ho riportato nella pagina "nuovi svilutppi" che si trova nella sezione "telecomando".
In quella pagina descrivo come due numeri primi RSA creano una nuova famiglia più capiente di quelle scoperte in precedenza.

Per quanto riguarda i numeri primi, devi considerare che non tutti hanno la stessa complessità e non tutti sono adatti a creare dei numeri semiprimi inattaccabili. Il numero primo RSA è noto per una difficoltà di essere rilevato e si trova in posizioni speciali, per esempio lontano dai numeri primi vicini. Se tu per esempio moltiplichi questi due numeri primi 657276569*657276577, sono facilmente rintracciabili perchè sono molto vicini. Ci sono librerie in Python che creano un semiprimo selezionando due numeri primi RSA, e lo fanno sulla base di alcune caratteristiche che devono avere questi numeri

Per capire, i numeri RSA non vengono selezionati utilizzando la funzione nextprime. Questa funzione la uso io ma sulla base di un altro sistema che crea si numeri primi molto complessi ma che non hanno a che fare con gli RSA. Di fatti il mio algoritmo non riuscirebbe a fattorizzare un semiprimo creato con dei numeri primi RSA. Gli RSA che io utilizzo non hanno la stessa funzione di come li utilizza RSA stessa, perchè i miei vengono elevati a potenza e perdono la loro primalità e per tanto bisogna dargliene un'altra che io faccio con nextprime.
Supponi che questo sia un numero primo RSA 765275623. Se io questo numero lo trasformo in 765275623^10 cessa di essere un numero primo e diventa un multiplo di se stesso. La complessità di questo multiplo è comunque notevole anche se non è un numero primo. A quel punto chiedo al programma di trovarmi un numero primo che si trovi entro un campo predefinito oltre a questo multiplo che essendo già complesso di suo aumenterà la complessità facendolo di nuovo diventare numero primo

che non è un algoritmo quantistico, infatti ha complessità esponenziale/superpolinomiale
l'lagoritmo di Shor è polinomiale (con la "lieve" limitazione che serve un computer quantistico)
ma non è questo il punto

no,mi spiace ma non lo sai: confondi O(1) con il "tempo costante di meno di un secondo"
p=n^1200+RND(1,2^1000) non è O(1) perché RND non lo è 😟
nextprime() non è O(1)
radice quadrata non è O(1)
massimo comun divisore e minimo comune multiplo non sono O(1)
dal cui deduco che non hai nessuna familiarità col concetto di complessità computazionale

perché, è basato su premesse false:
O(1) non è il tempo di esecuzione misurato in (nano)secondi
O(1)
è la misura di complessità computazionale di una operazione elementare di programmazione e, supponendo (ottimisticamente) di rendere "omogenee" le operazioni aritmetiche, sono di complessità O(1) le seguenti istruzioni:
  • operazioni aritmetiche tra numeri (+ - * /), tuttavia anche qui ci sarebbe da discutere...
  • dichiarazione/assegnazione di una valore ad una variabile
  • stampa di una stringa o lettura di un input
usare qualunque altra funzione (come i generatori random) rende automaticamente qualunque algoritmo di complessità superiore
usare una funzione di generazione pseudocasuale non è O(1)
i cicli non sono O(1), un ciclo ripetuto n voltè è O(n) a patto che sia composto solo da singole istruzioni elementari che siano ciascuna O(1);

nel codice usi sia generatori random che cicli, quindi non può essere O(1), non c'è nulla di cui discutere
"tempo fisico (più o meno) costante" e O(1) sono 2 cose concettualmente diverse:
  • la complessità computazionale calcola il tempo di esecuzione di un algoritmo in termini di numero di operazioni elementari eseguite, perché è un cirterio oggettivo
  • il tempo fisico (quello che gli esseri umani misurano in secondi e/o loro multipli o sottomultipli) invece non è una misura oggettiva perché dipende dalla velocità della macchina che lo esegue
Codice di programmazione a parte, un algoritmo va descritto in modo formale (non a chiacchiere) e si deve dimostranerne correttezza e completezza;
  • correttezza in parole povere significa che l'algoritmo restituisce risultati corretti
  • completezza significa che funziona in tutti i casi possibili
  • le 2 cose richiedono una DIMOSTRAZIONE MATEMATICA formale, le chiacchiere non servono
ammesso e non concesso che il tuo algoritmo sia corretto, non è completo, quindi di fatto non vale nulla dal punto di vista teorico e ancor meno che a fini pratici: "fattorizzi" numeri che hanno una struttura che ti fa comodo, ma la sicurezza della crittografia sa nel fatto che sia "impossibile a livello pratico" eseguire una fattorizzazione in tempi ragionevoli.

la matematica non è un'opinine: il doppio di 2^500 è 2^501 😉 pensaci su
Prima di rsiposnderti adeguatamente vorrei farti leggere una cosa sugli algoritmi: Questo spezzone è tratto da quanto ho scrtto nella "gli step della ricerca" e che evidentemente non hai letto

Capitolo 3


Analizziamo per un attimo questo metodo e lo confrontiamo con gli algoritmi conosciuti per vedere eventuali similitudini nei vari sistemi. Riporto qui, presi dall’intelligenza artificiale, le caratteristiche dei due principali algoritmi ECM e GNFS.

ECM (Elliptic Curve Method):

L'ECM è un algoritmo di fattorizzazione di numeri interi sviluppato da H.W. Lenstra Jr. nel 1985. Si basa sulle proprietà delle curve ellittiche e risulta particolarmente efficace per trovare fattori primi relativamente piccoli di numeri molto grandi.

Funzionamento principale:​
  1. Sceglie casualmente una curva ellittica E e un punto P su di essa​
  2. Esegue operazioni aritmetiche su E modulando il numero n da fattorizzare​
  3. Se durante i calcoli si trova un divisore non banale di n, l'algoritmo termina con successo​
L'ECM è considerato un algoritmo probabilistico e la sua complessità dipende dalla dimensione del fattore più piccolo di n.




GNFS (General Number Field Sieve):

Il GNFS è attualmente l'algoritmo più efficiente conosciuto per fattorizzare numeri interi di grandi dimensioni (oltre 100 cifre). È un'evoluzione del Number Field Sieve sviluppata negli anni '90.

Funzionamento principale:​

  1. Seleziona un polinomio adatto e costruisce dei campi di numeri​
  2. Genera relazioni tra elementi in questi campi​
  3. Utilizza l'algebra lineare per trovare combinazioni di queste relazioni​
  4. Estrae i fattori del numero originale da queste combinazioni​
Il GNFS ha una complessità subexponenziale, rendendolo molto più veloce degli algoritmi con complessità esponenziale per numeri molto grandi.



Difficile trovare delle similitudini tra il GC57 e questi due potentissimi algoritmi di fattorizzazione. Questi due sistemi usano calcoli complessi mentre il GC57 usa un sistema molto semplice e diretto.

L'unica somiglianza rilevante, a mio avviso, è che tutti questi algoritmi operano all'interno di determinati "campi" o intervalli, dove cercano i fattori primi. Questo significa che se il semiprimo non rientra nel campo o intervallo specifico dell'algoritmo, anche se non è un numero estremamente grande, potrebbe non essere individuato utilizzando solo quell'algoritmo. Ogni algoritmo ha quindi delle zone di efficacia specifiche.


che non è un algoritmo quantistico, infatti ha complessità esponenziale/superpolinomiale
l'lagoritmo di Shor è polinomiale (con la "lieve" limitazione che serve un computer quantistico)
ma non è questo il punto

no,mi spiace ma non lo sai: confondi O(1) con il "tempo costante di meno di un secondo"
p=n^1200+RND(1,2^1000) non è O(1) perché RND non lo è 😟
nextprime() non è O(1)
radice quadrata non è O(1)
massimo comun divisore e minimo comune multiplo non sono O(1)
dal cui deduco che non hai nessuna familiarità col concetto di complessità computazionale

perché, è basato su premesse false:
O(1) non è il tempo di esecuzione misurato in (nano)secondi
O(1)
è la misura di complessità computazionale di una operazione elementare di programmazione e, supponendo (ottimisticamente) di rendere "omogenee" le operazioni aritmetiche, sono di complessità O(1) le seguenti istruzioni:
  • operazioni aritmetiche tra numeri (+ - * /), tuttavia anche qui ci sarebbe da discutere...
  • dichiarazione/assegnazione di una valore ad una variabile
  • stampa di una stringa o lettura di un input
usare qualunque altra funzione (come i generatori random) rende automaticamente qualunque algoritmo di complessità superiore
usare una funzione di generazione pseudocasuale non è O(1)
i cicli non sono O(1), un ciclo ripetuto n voltè è O(n) a patto che sia composto solo da singole istruzioni elementari che siano ciascuna O(1);

nel codice usi sia generatori random che cicli, quindi non può essere O(1), non c'è nulla di cui discutere
"tempo fisico (più o meno) costante" e O(1) sono 2 cose concettualmente diverse:
  • la complessità computazionale calcola il tempo di esecuzione di un algoritmo in termini di numero di operazioni elementari eseguite, perché è un cirterio oggettivo
  • il tempo fisico (quello che gli esseri umani misurano in secondi e/o loro multipli o sottomultipli) invece non è una misura oggettiva perché dipende dalla velocità della macchina che lo esegue
Codice di programmazione a parte, un algoritmo va descritto in modo formale (non a chiacchiere) e si deve dimostranerne correttezza e completezza;
  • correttezza in parole povere significa che l'algoritmo restituisce risultati corretti
  • completezza significa che funziona in tutti i casi possibili
  • le 2 cose richiedono una DIMOSTRAZIONE MATEMATICA formale, le chiacchiere non servono
ammesso e non concesso che il tuo algoritmo sia corretto, non è completo, quindi di fatto non vale nulla dal punto di vista teorico e ancor meno che a fini pratici: "fattorizzi" numeri che hanno una struttura che ti fa comodo, ma la sicurezza della crittografia sa nel fatto che sia "impossibile a livello pratico" eseguire una fattorizzazione in tempi ragionevoli.

la matematica non è un'opinine: il doppio di 2^500 è 2^501 😉 pensaci su
Un altra cosa che ti prego di non confondere è questa:
no,mi spiace ma non lo sai: confondi O(1) con il "tempo costante di meno di un secondo"
p=n^1200+RND(1,2^1000) non è O(1) perché RND non lo è 😟
nextprime() non è O(1)
massimo comun divisore e minimo comune multiplo non sono O(1)
dal cui deduco che non hai nessuna familiarità col concetto di complessità computazionale

Quando si parla di fattorizzazione non ci si riferisce alla creazione del semiprimo perchè quello non lo devi creare, già ce l'hai.
Per questo motivo non capisco perchè ti ostini a mettere nel tempo O(1) il fatto di creare un semiprimo. O(1) riguarda la fattorizzazione del semiprimo e si svolge in questo modo in meno di un secondo a prescindere dalla potenza del calcolatore che usi, a meno che non usi una calcolatrice manuale😅

A=S Mod(chiave)
B=S-A
MCD(A,B)=p

indipendentemente dalla grandezza di S

A meno che tu non asserisca che sia MOD che MCD influenzano la velocità. Ma vorrei che tu notassi che nella sequenza riportata non c'è nessuno incremento e nessuna ricerca per arrivare alla soluzione e per tanto si può definire la sequenza O(1)
 
Ultima modifica:
Per capire, i numeri RSA non vengono selezionati utilizzando la funzione nextprime.
Ovviamente, in quanto i numeri RSA non sono primi, ma semiprimi.

Quello che vorrei capire meglio è l'ambito di applicabilità del tuo algoritmo di fattorizzazione. Da quello che ho capito non funziona con input generici, ma solo con semiprimi ottenuti in un determinato modo. A ciò mi hai risposto dicendo:
Non è del tutto esatto. Si possono inserire anche numeri digitati a mano in modo casuale e trasformati in numeri primi come descritto sopra.
A tal proposito, quale sarebbe di preciso questo metodo "descritto sopra" di cui parli?
 
  • Mi piace
Reazioni: BAT
O(1) riguarda la fattorizzazione del semiprimo e si svolge in questo modo in meno di un secondo a prescindere dalla potenza del calcolatore che usi
lo vedi che non hai capito?
O(1) in complessità si riferisce ad un numero di operazioni ELEMENTARI costanti non riguarda il tempo di calcolo misurato in (nano/micro/milli)secondi

MCD non è O(1) lo capisci o no questo? è una funzione che ha comlessità O(n^2) dove n è il numero di cifre degli input
la rafice quadrata non è O(1), ha complessita O(log(n)) nel caso migliore

continui a confondere la singola istruzione in linguaggio di programmazione con tempo costante

tra l'altro pensi di aver fatto una "scoperta" che chiami "chiave" e che calcoli con una radice quadrata...
ma non è una scoperta: è noto da circa 2300 anni che i fattori di un numero intero si dispongono a coppie intorno alla radice quadrata del numero, per cui è banalmente ovvio che un semiprimo ha un fattore minore della sua radice, e l'altro maggiore

il GC57 usa un sistema molto semplice e diretto.
gli altri algoritmi funzioano sempre, indipendentemente dal numero, il tuo "funziona" con semiprimi che decidi tu perchè i test li fai generandoli con le funzioni che hai descritto.

E torno a chiedere per la terza volta: dove sono le dimostrazioni di correttezza e completezza? senza l'algoritmo non vale nulla

P.S.
Fai una cosa:
metti un codice semplice in Python visto che è quello che usi, una semplice finestra di testo dove si possa inserire un input (il numero da fattorizzare) e che restituisco i 2 fattori nel caso dei semiprimi, senza bisogno di USB, file di configurazione e robaccia che non serve a nulla per testare se funziona o no
 
Le basi degli algoritmi.
Ti consiglierei di rivedere Algoritmi e Strutture dati ed i relativi calcoli alla complessità nello spazio e nel tempo.
 
  • Mi piace
Reazioni: BAT
Ovviamente, in quanto i numeri RSA non sono primi, ma semiprimi.

Quello che vorrei capire meglio è l'ambito di applicabilità del tuo algoritmo di fattorizzazione. Da quello che ho capito non funziona con input generici, ma solo con semiprimi ottenuti in un determinato modo. A ciò mi hai risposto dicendo:

A tal proposito, quale sarebbe di preciso questo metodo "descritto sopra" di cui parli?
Ti rispondo con questo e che è parte della sicurezza del mio algoritmo. Quando noi eleviamo a potenza un numero creiamo una certa sequenza di cifre che possono esser più o meno complicate. prendiamo per esempio il numero 2 e il numero 13 che vengono elevate a potenza tenendo conto che il risultato produrrà le stesse cifre: Ti riporto un confronto che ho chiesto di eseguire all'intelligenza artificiale ChatGPT.
Io utilizzo questo tipo di complessità per creare i numeri primi che poi vado a utilizzare nel mio algoritmo. Questa prova l'ho testata molte volte su programmi come ECM o GFNS utilizzando semiprimi non molto grandi per agevolare il test. I numeri semiprimi creati da basi esponenzaili di 2^n+RND(1,x) venivano nella maggior parte risolti. Cambiando la base 13^n+RND(1,x) non venivano mai risolti

Confrontiamo numeri come \( 2^n \) e \( 13^n \), anche se possono avere lo **stesso ordine di grandezza** (cioè un numero simile di cifre), la **struttura interna** dei due numeri è molto diversa in termini di **complessità aritmetica** e **composizione**.

Ecco alcune differenze chiave:

### 1. **Distribuzione delle cifre**
- I numeri generati da \( 2^n \) tendono a essere più **regolari** e **prevedibili** nella loro struttura. Questo è dovuto al fatto che la base 2 è una potenza di un numero piccolo, e quindi i numeri generati da \( 2^n \) hanno meno variabilità nelle loro cifre.
- I numeri generati da \( 13^n \) hanno una **distribuzione più complessa delle cifre**. Man mano che calcoli \( 13^n \), le cifre sono più "caotiche" rispetto a quelle generate da \( 2^n \), e la struttura del numero diventa più intricata e meno prevedibile.

### 2. **Divisibilità e fattorizzazione**
- I numeri come \( 2^n \) sono facilmente **divisibili per 2**. Questo significa che hanno una struttura molto semplice dal punto di vista della divisibilità: saranno sempre divisibili per 2, per 4, per 8, ecc.
- Invece, i numeri come \( 13^n \) sono molto più **difficili da scomporre** e hanno una struttura aritmetica più complicata. Ad esempio, \( 13^n \) non è divisibile per molti numeri (a parte 13), e questo li rende più "irregolari" nella fattorizzazione.

### 3. **Complessità algoritmica**
- Quando si tratta di **algoritmi di calcolo** o di operazioni con numeri grandi, come la moltiplicazione, i numeri derivati da \( 13^n \) sono più **complessi da manipolare** rispetto a \( 2^n \). Questo perché le operazioni con numeri più grandi richiedono più risorse computazionali, e un numero come \( 13^n \) tende ad avere una rappresentazione binaria più lunga e complessa.
- Anche per operazioni come la **crittografia** o la **compressione dei dati**, i numeri con basi più grandi (come \( 13^n \)) presentano sfide più complesse rispetto ai numeri con basi piccole come \( 2^n \).

### 4. **Rappresentazione in base 10**
- Un numero come \( 2^n \), anche se può avere molte cifre, tende a produrre una **distribuzione delle cifre** meno variabile rispetto a \( 13^n \). Per esempio, \( 2^n \) ha una crescita più lineare nel numero delle cifre, mentre \( 13^n \) produce numeri in cui le cifre sono più disperse e difficili da prevedere.
- \( 13^n \), d'altra parte, ha una struttura più complessa in base 10. Se prendi \( 13^5 = 371293 \), vedi che la disposizione delle cifre è molto più complessa rispetto a \( 2^5 = 32 \), anche se si può pensare che abbiano entrambi "molte cifre" in una scala più grande.

### 5. **Complessità cognitiva**
- La percezione della **complessità cognitiva** di un numero come \( 13^n \) è più alta. Anche se il numero può avere la stessa quantità di cifre di \( 2^n \), \( 13^n \) sembra più "caotico" o difficile da comprendere a livello intuitivo, perché la struttura del numero è meno regolare e più difficile da interpretare senza un calcolo diretto.

In sintesi, anche se numeri come \( 2^n \) e \( 13^n \) possono avere lo stesso ordine di grandezza (lo stesso numero di cifre), la **struttura interna** del numero è molto più **complessa** nel caso di \( 13^n \). Questa complessità si riflette nella **distribuzione delle cifre**, nella **fattorizzazione** e nelle **operazioni aritmetiche**, rendendo \( 13^n \) un numero più difficile da gestire sia dal punto di vista computazionale che teorico.

Risposta a Bat


Adesso ti rispondo punto per punto cominciando dai più banali:
la matematica non è un'opinine: il doppio di 2^500 è 2^501
😉
pensaci su

Tu stai parlando di una base 2 ed è corretto dire che 2^11 è il doppio di 2^10, ma io mi riferisco a un campo e questo campo è rapprentato da da una potenza 2^500. La potenza diventa il doppio e cioè 2^1000. Il numero rappresentato da 2^1000 non è il doppio del numero rappresentato di 2^500 rappresentato questo è ovvio

  • correttezza in parole povere significa che l'algoritmo restituisce risultati corretti
  • completezza significa che funziona in tutti i casi possibili
  • le 2 cose richiedono una DIMOSTRAZIONE MATEMATICA formale, le chiacchiere non servono

non mi sembra di aver mostrato probemi in questo. Correttezza: il risultato è uno dei due fattori primi che compongono il semiprimo. Completezza: ogni semiprimo creato con numeri primi all'interno dal campo di 2^1000 viene risolto nella fattorizzazione sempre con la stessa chiave e la stessa velocità. Qui di chiacchere ne vedo molto poche e ti invito a sperimentarlo personalmente perchè hai tutti gli elementi per poterlo fare. E a questo proposito ti invito a leggere tutto quello che ho scritto sul sito gc57crypto.net compreso i capitoli che parlano del sistema GC57eAL di come questo utilizza l'algoritmo per criptare dati e allegati.

Per quanto riguarda la velocita O(1) mi sembra di averti già risposto e comunque è inutile, almeno fino a quando inserisci dentro questo tempo la costruzione del semiprimo

ammesso e non concesso che il tuo algoritmo sia corretto, non è completo, quindi di fatto non vale nulla dal punto di vista teorico e ancor meno che a fini pratici: "fattorizzi" numeri che hanno una struttura che ti fa comodo, ma la sicurezza della crittografia sa nel fatto che sia "impossibile a livello pratico" eseguire una fattorizzazione in tempi ragionevoli.
Fattorizzo numeri complessi che nessun algoritmo conosciuto riesce a fattorizzare, sia che si parli di tempo o di grandezza. Il fatto di usare numeri primi creati in un certo modo, se critichi me dovresti criticare anche RSA. Il fatto di riuscire a riportare il semiprimo creato ai suoi due numeri primi, senza usare uno dei due numeri primi per risolvere la fattorizzazione è un cosa senza precedenti.

E torno a chiedere per la terza volta: dove sono le dimostrazioni di correttezza e completezza? senza l'algoritmo non vale nulla

Dimmi a cosa ti riferisci più nel contesto e forse riuscirò a risponderti. Comunque sappi che io non voglio convincere nessuno sulla validità di questo algoritmo, men che meno te. Non per mancarti di rispetto. Mi sta bene che tu dica la tua ma alla conta dei fatti non ti devo convincere di niente. Se lo vuoi sperimentare sono a tua disposizione tutte le informazione, se lo ritiene inutile, come hai scritto, me ne farò una ragione😉

Le basi degli algoritmi.
Ti consiglierei di rivedere Algoritmi e Strutture dati ed i relativi calcoli alla complessità nello spazio e nel tempo.
Mi fa un po' sorridere la tua affermazione di spaio e tempo, mi viene in mente subito Einstein. Comunque grazie apprezzo ogni consiglio
 
Stato
Discussione chiusa ad ulteriori risposte.
Pubblicità
Pubblicità
Indietro
Top