Puncte:0

Funcție text unidirecțională... text

drapel jp

Am nevoie de o modalitate de a mapa un text imprimabil cu un alt text imprimabil. De exemplu.:

Ian Boyd â Kcp Zbas

Observați câteva dintre cerințele importante:

  • majuscule este majuscule în ieșire
  • litere mici în intrare sunt litere mici în intrare
  • spațiile (și orice altceva în afara A-Z0-9) sunt lăsate singure

Cerința suplimentară este să fie determinat, aceeași intrare dă întotdeauna aceeași ieșire:

  • Ian Boyd â Kcp Xbas
  • Ian Boyd â Kcp Xbas
  • Ian Boyd â Kcp Xbas

Cealaltă cerință se extinde asupra determinismului și nu știu cum să o numesc, cu excepția faptului că cuvintele cu prefixe comune trebuie să aibă aceeași ieșire pentru același prefix comun:

  • eu â K
  • In absenta â Kc
  • Ian â Kcp
  • Ian â Kcp
  • Ian B â Kcp X
  • Ian Bo â Kcp Xb
  • Ian Boy â Kcp Xba
  • Ian Boyd â Kcp Xbap

Soluția mea

Am creat o soluție la aceste cerințe tehnice în urmă cu 15 ani; dar încerc să revăd ceva "mai bine".

Soluția mea a fost a „un cifru Caesar în flux cu înlănțuire”.

Creați o substituție caesar simplă:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
F H U D I R Y E K C Z N S A B G J P V O W T L M Q X

Dar mai degrabă decât o simplă înlocuire:

  • Ian Boyd â Fks Hbqd

în schimb am folosit înlănțuirea:

Previous State Current Character Sum (mod) Următorul caracter de ieșire
-------------- ----------------- ---------- --------- ----- --------------------
0 I (9) 9 K K
9 a (1) 10 c Kc
10 n (14) 24 p Kcp

24 B (2) 26 X Kcp X
26 o (15) 15 b Kcp Xb
15 y (25) 14 a Kcp Xba
14 d (4) 18 m Kcp Xbap

Soluție mai bună cu hashing?

Aceste valori nu sunt ceva de care am nevoie (sau vreau). "decripta", iar utilizarea unui cifru caesar implică capacitatea de a decripta (care știm cu toții că nu este atât de greu).

Deci conceptual îmi doresc foarte mult un "funcție unidirecțională": ceva care:

  • convertește intrarea
  • la o ieșire imprevizibilă
  • în mod determinist

M-am gândit: ce se întâmplă dacă aș folosi un algoritm hash, adăugând litere câte una și obținând curentul "stat"și convertiți acel rezumat parțial într-un caracter (majuscule/minuscule/cifră, după caz, pentru a se potrivi cu intrarea):

   String FrobTheGrobber (Intrare șir)
   {
      //dovada de concept pseudocod care se ocupă doar de majuscule
      HashAlgorithm hash = nou SHA256();
      hash.AddBytes(SECRET_KEY);

      String res = "";

      pentru Char ch în intrare
      {
         hash.Add(ch);
         int charCode = (hash.Hash[0] % 26) + 1; //folosește primul octet, mod 26 pentru a obține o valoare de la 0..25
         res += Char(Ord('A') + charCode;
      }            
   }

Știu; îl urăști pe cerințe.

Poate cineva să facă ceva mai bun?

DannyNiu avatar
drapel vu
Tastați cifrul Caesar și îl faceți să funcționeze ca o funcție de compresie Davies-Meyer?
DannyNiu avatar
drapel vu
Proprietatea prefix-idempotență face dificilă *nu* să inverseze maparea.
fgrieu avatar
drapel ng
Proprietatea prefixului implică faptul că, dacă `I` â `K`, atunci `i` â `k`, sau ar putea fi acel `i` â `z`? Asta dacă `Ian â Kcp ` atunci `Ian Ian` â `Kcp Kcp`, sau ar putea fi acel `Ian Ian` â `Kcp Zar`?
drapel jp
@fgrieu Pentru simplitate, a fost *"insensitive"*, adică `i` și `I` ambele mapează la `k` și `K`. Soluția completă include și `0`-`9` în cifrul Caesar. În acest fel, lucruri precum numerele de telefon sunt asociate cu ceva care arată și ca un număr de telefon ( `905-867-5309` → `619-112-8408`). Și aș putea mapa, de asemenea, litere mici separat de litere mari. Oricum: nu contează. Dacă cineva poate veni cu o soluție pentru `A`-`Z`, o pot extinde la orice alte personaje.
SAI Peregrinus avatar
drapel si
Cum te-ai descurca pe i și ι care ambele se mapează la I? Doar ignori Turcia? Lipsa minusculelor este aproape întotdeauna o idee TERRIBILĂ, este întotdeauna cu pierderi.
drapel jp
@SAIPeregrinus Întrebarea nu are nevoie de aceste detalii. În scopul acestei întrebări, trebuie doar să rezolvați manipularea „A-Z”. Răspunde, iar eu mă ocup de restul. Restul este banal de gestionat și complet irelevant pentru întrebarea mea. Dacă te ajută: pretinde că sistemul sursă folosește o pagină de cod pe 5 biți, care definește doar caracterele `A`-`Z`. Acestea fiind spuse, știți **exact** cum m-aș descurca cu testul pentru curcan - dar nu face parte din întrebarea mea, deoarece nu este importantă pentru întrebare și nici nu este întrebarea pe care o pun.
jjj avatar
drapel cn
jjj
Cu cerința de prefix nu poate fi unidirecțională, deoarece se poate reconstrui cu ușurință caracter pentru caracter.
Ievgeni avatar
drapel cn
Nu înțeleg care sunt cerințele de securitate?
Puncte:1
drapel ng

Problema cu soluția originală a întrebării este că tabelul de substituție este același la fiecare index și cea mai bună parte a cheii. Se poate determina astfel din exemple. Problema cu soluția „mai bună” este că cunoașterea unei inițiale eu criptează la K, știm o inițială A criptează la C, o inițială B criptează la D, etc..

Propun următoarele, cu un hash de cel puțin 256 de biți $H$ cum ar fi SHA-256 și cheia $K$:

  • a stabilit $y=\mathtt{\text{â0â}}$
  • pentru fiecare personaj $x$ a cifra sau a descifra
    • lăsa $b=0$
    • dacă $x$ este o cifră, deci $b=10$ si lasa $c=\mathtt{\text{â0â}}$
    • dacă $x$ este o literă mare, let $b=26$ si lasa $c=\mathtt{\text{âAâ}}$
    • dacă $x$ este o literă mică, let $b=26$ si lasa $c=\mathtt{\text{âaâ}}$
    • dacă $b\ne0$
      • a stabilit $K=H(K\mathbin\|\operatorname{majuscule}(y)\mathbin\|b)$
      • pregăti o permutare $p$ de $b$ elemente tastate de valoarea curentă a $K$; si spre asta:
        • set întreg $r=K$ (după cum spune convenția big-endian)
        • pentru $i=0$ la $b-1$
          • a stabilit $j=r\bmod(i+1)$, atunci $r=\lfloor r/(i+1)\rfloor$
          • a stabilit $p[i]=i$
          • a stabilit $p[i]=p[j]$
          • a stabilit $p[j]=i$
      • dacă se criptează
        • a stabilit $y=x$
        • a stabilit $x=p[x-c]+c$
      • in caz contrar
        • a stabilit $x=p^{-1}[x-c]+c$
        • a stabilit $y=x$
    • ieșire $x$

Și asta dă rezultatele:

Introdu textul Amestecate
eu B
In absenta Bf
Ian Bfd
Ian Bfd
Ian B Bfd K
Ian Bo Bfd Kf
Ian Boy Bfd Kft
Ian Boyd Bfd Kftv
Ian Boyd Bfd Kftv
Ian Boyd 2 Bfd Kftv 2
Ian Boyd 20 Bfd Kftv 25
Ian Boyd 201 Bfd Kftv 257
Ian Boyd 2017 Bfd Kftv 2571

Încearcă online! în Python.

The $K=H(K\mathbin\|\operatorname{majuscule}(y)\mathbin\|b)$ pasul pregătește o cheie nouă care depinde de cea anterioară, de caracterul anterior (normalizat la majuscule, pentru că nu este clar dacă majusculele pot avea vreo influență pentru caracterele următoare) și de dacă caracterul curent este o cifră sau nu (deoarece regulile permitem și vrem să depindem de atât cât ne permit ei). La fiecare pas, 256 USD-\log_2(26!)>167,6 USD parte din stat rămâne necunoscută pentru atacator chiar și într-un atac în text clar. Am construit o permutare de dimensiunea potrivită în funcție de caracterul curent, în direcția potrivită pentru criptare sau decriptare.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.