O metodă nouă pentru a ascunde datele folosind numere prime?

A fost propusă sau studiată următoarea metodă de ascundere a datelor? Care este eficiența sau securitatea acestei metode? Ce aplicații ar putea folosi această metodă?

Datele trebuie ascunse într-un număr care este produsul a două numere prime. Un număr prim conține datele ascunse și un număr mai mare numărul prim indică lungimea datelor, construite folosind concatenarea după cum urmează.

$p = p_0 \ || \ date \ || \ p_{end}\ \ $ și $ \ \ q = q_0 \ || \ marker \ || \ q_{end}$

Unde $p_0$ și $q_0$ sunt aleatorii $singure$ cifre diferite de zero cu $p_0 < q_0$, $date$ este un număr cu $k$ cifre (zecimale), $marcator$ este un număr aleatoriu cu $k-1$ cifre diferite de zero urmate de $0$, și $p_{end}$ și $q_{end}$ sunt numere aleatorii cu $n-k-1$ cifre.

Datele codificate sunt $N = P \time Q$ Unde $P$ și $Q$ sunt numerele prime următoare după $p$ și $q$. $n$ este ales suficient de mare pentru ca factorizarea lui a 2n$-numărul cifrelor nu este fezabil şi astfel încât, împreună cu alegerile de $p_{end}$ și $q_{end}$, construcția de $P$ și $Q$ nu provoacă $date$ sau $marcator$ a schimba.

Câteva comentarii: (1) Deși unele constrângeri asupra $P$ și $Q$ sunt cunoscute, nu este suficient să se folosească „factorizarea cu informații parțiale/biți cunoscuți”. (2) Cunoașterea $P$ și $Q$, în orice ordine, permite ca datele ascunse să fie găsite în mod unic. (3) Metoda este ușor de adaptat la binar.

Exemplu: $date$ este 271828 cu $k$ = 6. Pentru simplitate folosire $n$ = 12:

$p = \mathtt {1 \underline {271828} 67213}$, $P = \mathtt {1 \underline {271828} 67221} \ \ $ și $ \ \ q=\mathtt {6 \underline{97811} \underline {\underline {0}}97478}$, $Q = \mathtt {6 \underline{97811} \underline {\underline {0}}97499}$

$N = P \times Q = \mathtt {88749616158555602180279}$.

EDITARE: Datele pot fi orice număr întreg (zero sau mai mare). Pentru a sublinia faptul că nu trebuie să fie prim, am schimbat datele exemplu de la 314159 (care este prim) la 271828 (un compus).

EDITARE (30 martie): S-a adăugat „singur” la descrierile $p_0$ și $q_0$ pentru a sublinia că fiecare dintre $p_0$ și $q_0$ este o singură cifră diferită de zero. Rețineți că dimensiunea datelor ($k$) nu este cunoscută în prealabil, dar este indicată prin $marcator$. De asemenea, cel mai cunoscut rezultat, datorat lui Coppersmith, este că factorizarea este ușoară dacă se cunosc jumătate din biții unui factor.

Voi examina acest lucru ca o potențială schemă de angajament (deoarece nu mă pot gândi la cum ați utiliza altfel).

După cum știi, Bob, o schemă de angajament este una în care Alice are un secret; ea publică un angajament față de secret („se angajează în secret”), apoi, mai târziu, „deschide” angajamentul, dezvăluind secretul.

Există două proprietăți de securitate de interes într-o schemă de angajament:

• Ascundere; Bob care vede angajamentul nu poate spune care este secretul (chiar dacă are o ghicire)
• Legare; atunci când Alice deschide angajamentul, trebuie să-l deschidă la valoarea pe care a avut-o în minte când a generat angajamentul (adică nu-l poate deschide la nici una dintre cele două valori diferite la momentul deschiderii).

De fapt, o schemă de angajament poate fi fie perfect ascunsă (adică este imposibil pentru Bob să obțină orice informație, chiar dacă avea o putere de calcul infinită la dispoziție), fie perfect obligatorie (adică este imposibil ca Alice să deschidă angajament în două moduri diferite); este imposibil ca o schemă să fie ambele.

Acum, există două scheme standard de angajament:

• Angajamente bazate pe hash, unde Alice preia secretul $S$ și o valoare aleatorie $R$ și publică angajamentul $\text{Hash}( S || R )$, pentru o funcție hash rezistentă la coliziuni $\text{Hash}$; pentru a-l deschide, ea publică $S$ și $R$. Acest lucru se dovedește a fi obligatoriu din punct de vedere computațional (pe baza rezistenței la ciocnire a hashului și presupunând că lungimea fie a lui S, fie a lui R este bine cunoscută) și se ascunde statistic (presupunând că $R$ este suficient de lungă și o presupunere nestandard, dar intuitivă privind funcția hash).

• Angajamente Pedersen, unde avem două generatoare diferite $g$ și $h$ (cu relație necunoscută) a unui grup în care problema logului discret este grea; a se angaja la o valoare $S$, ea alege o valoare aleatorie $R$ și publică $g^Sh^R$; pentru a-l deschide, ea publică $S$ și $R$. Acest lucru se dovedește a fi ascunderea perfecționării și legarea computațională (reductibil la problema DLog).

Angajamentele bazate pe hash au avantajul practic că sunt eficiente. Angajamentele Pedersen au avantajul că au proprietăți demonstrabile mai frumoase și sunt, de asemenea, prietenoase cu dovezile zero-cunoștințe; de exemplu, dacă Alice generează două angajamente, ea poate genera o scurtă dovadă de zero cunoștințe că acele două angajamente au aceeași valoare (presupunând, desigur, că acestea sunt).

Acum, trec la schema ta:

• În ceea ce privește proprietatea de legare, sunteți perfect obligatoriu; Alice are un singur mod în care poate deschide secretul (presupunând că Bob verifică factorii revelați pentru primalitate).

• În ceea ce privește proprietatea de ascundere, ar putea părea la prima vedere reductibilă la problema factorizării. Cu toate acestea, nu este chiar atât de simplu; atacatorul știe a priori ceva despre factori (de exemplu, dacă are o ghicire a secretului și, de asemenea, ghicește unde în $P$ care apare (nu atat de multe posibilitati), atunci are ambele cifre ale $P$ și știe unde sunt cifre diferite de zero $Q$ apar (precum și o cifră zero)). Deși nu este clar cum poate fi folosit pentru a face factorizarea mai ușoară, aceasta ar fi o presupunere nestandard.

Evaluând această schemă, nu este oribilă (atâta timp cât secretul este scurt, informațiile suplimentare disponibile atacatorului nu sunt susceptibile de a fi exploatabile); pe de altă parte, este, de asemenea, ineficient (generarea primelor este costisitoare; validarea celor revelate $P$ și $Q$ valori (asigurându-vă că sunt prime), deși nu sunt la fel de scumpe, nu este totuși excesiv de ieftin). Și, nu ar fi evident cum ați crea o dovadă eficientă de zero cunoștințe despre o declarație despre valorile angajate.

O să subliniez câteva probleme pe care le văd cu asta, acestea pot fi greșite, dar tot mi s-a părut intrigant.

• Setarea datelor dvs. la egalitate (sau reprezentată) printr-un număr prim nu este întotdeauna atât de ușoară. Având în vedere un anumit mesaj care criptează la primul 1, ceea ce oprește un alt mesaj de lungime egală de la criptare la același prim. (Poate spațiu mic pentru mesaje?)

• Cum ar funcționa decriptarea aici...

• Nu văd aici dovada de securitate. Atacurile asupra RSA au arătat că puteți recupera numerele prime având o anumită cantitate de biți în el. Atunci puteți aborda un atac cu forță brută pe lungimea mesajului pot fi utilizați un fel de atac de expunere parțială a cheii

Sunt nou în criptografie, așa că este foarte probabil că am greșit una dintre aceste presupuneri, nu ezitați să mă sunați și totuși felicitări pentru ideile interesante!