Teoria Numerelor, Algebra Abstracta, Statistica si Teoria Informatiei
Def: Daca a, b intregi, spunem ca
a este congruent cu b modulo n,scris
a ≡
b (mod n) daca n divide (a-b)
Proprietati:
- i)(reflexivitate) a ≡ a (mod n);
- ii)(simetrie) daca a ≡ b (mod n) atunci b ≡ a (mod n);
- iii)(tranzitivitate) daca a ≡ b (mod n) si b ≡ c (mod n), atunci a ≡ c (mod n);
- iv)
Proprietati ale aritmeticii modulare(I): daca a = b mod n si c = d mod n, atunci:
- a+c = b+d mod n
- a-c = b-d mod n
- a*c = b*d mod n
-
- k*a = k*b mod n
- a/k = b/k mod n/k , daca k divide a,b,n
Proprietati ale aritmeticii modulare(II) fie numerele intregi x, y, n ≠ 0 cu c.m.m.d.c(y, n) = 1
atunci:
- i) (x + y) mod n = [(x mod n) + (y mod n)] mod n
- ii) (-x) mod n = (n - x) mod n = n - (x mod n)
- iii) xy mod n = [(x mod n)(y mod n)] mod n
- iv) inversul lui y fata de operatia de multiplicare, notat
Teorema chineza a resturilor (CRT): daca intregii
are solutie x unica calculata modulo n=
NOTA: determinarea solutiei unice se efectueaza cu ajutorul algoritmului lui Gauss.
Def:se numeste
grup multiplicativ peste
Def: pentru n ∈ N si n ≥ 1,
functia Euler, notata φ(n), reprezinta numarul de
intregi k cu 0 ≤ k < n si c.m.m.d.c(k, n) = 1.
Daca φ(n) este functia Euler, atunci:
i) φ(1) = 1;
ii) daca c.m.m.d.c (m, n) = 1, atunci φ(m*n) = φ(m)*φ(n); (φ - omomorfica)
iii) daca n =
este descompunerea in factori primi a lui n, atunci φ(n) = n
Def: Daca exista un element α ∈ G-grup ciclic, astfel incat ∀ b ∈ G, ∃ i ∈ Z
astfel incat b =
mod p atunci α se mai numeste
generator (radacina primitiva) al grupului.
Def: ordinul unui grup este definit de numarul de elemente ale grupului.
Def: ordinul unui element a ∈ G-grup, este definit de cel mai mic intreg, pozitiv t
astfel incat
Teorema lui Fermat daca p - prim, atunci
NOTA: se mai numeste mica teorema a lui Fermat
Teorema lui Euler daca a ∈
Omomorfism de grup
Fie doua grupuri (G, +) si (H, #). O functie f(.) : G → H este omomorfica daca:
∀ a,b ∈ G, f(a+b) = f(a)#f(b)
Daca exista o functie omomorfica, atunci G si H au aceasi structura.
Izomorfism de grup
Daca functia f(.) este omomorfica si bijectiva atunci este izomorfica.
Daca exista o functie izomorfica, atunci G si H sunt echivalente (nu egale).
Paradoxul "Birthday"
Fie o functie surjectiva oarecare f : X → Y, unde |Y| = n elemente si o constanta 0 < ε < 1,
se cere sa se determine un numar k, astfel incat daca sunt selectate k valori distincte
∈ X, Prob[f(
) = f(
)] ≥ ε, cu i ≠ j. S-a constatat (si demonstrat) chiar in cazul in care ε
este mare (foarte aproape de 1), k ramane proportional cu
.
In general, pentru a determina o coliziune cu probabilitatea de aprox 0.5 sunt necesare
incercari.
De exemplu, intr-o clasa cu 23 de studenti, probabilitatea ca doi dintre ei sa aiba aceasi zi de nastere
(din cele 365 ale unui an) este aproximativ 0.5. Daca sunt 30 de studenti probabilitatea creste la
aproximativ 0.7 (de unde si denumirea).
Aplicatii ale paradoxului Birthday: atacul Birthday (tot din categoria FB) pentru determinarea
coliziunilor unei functii hash, evaluarea proprietatii de difuzie a unei functii hash (o fct.
hash ideala asociaza in mod echiprobabil oricare dintre valorile posibile de iesire atunci cand
valorile de intrare sunt alese dupa o distributie
uniform aleatoare);
Legea numerelor mari
Fie
o secventa de variabile aleatoare i.i.d cu valoarea asteptata
Media aritmetica a unui esantion (en. sample) dintre variabile converge catre μ atunci cand
dimensiunea esantionului n → ∞
Problema celor 2 maestri sahisti:
Un sahist amator angajat simultan in doua jocuri cu
2 maestri diferiti, ce joaca cu negru intr-un joc, respectiv cu alb in celalalt si copiaza miscarile
maestrilor in celalalt joc, va avea urmatoarele rezultate: fie remiza in ambele jocuri, fie un
castig si o pierdere in cele doua jocuri.
picoManual de Scapy (cheatsheet)
- Scapy este o extensie a limbajului python care faciliteaza(prin abstractizare) interactiunea cu
subsistemul local de comunicatie Internet;
- biblioteca Scapy include atat functii pentru generarea si interceptarea cu suport pentru filtrarea
(BPF)de trafic cat si functii orientate pe tranzactie (asociaza mesajele cere-raspuns), functii
specializate pentru diagnoza retelei;
- dezvoltarea programelor cu biblioteca de functii Scapy se poate face in doua moduri:
interactiv sub
interpretorul cu acelasi nume sau
script prin importarea bibliotecii in programul python (ex.
from scapy.all
import *);
- in modul script, specificarea interpretorului python se face adaugand in prima linie:
#!/usr/bin/env python . Lansarea
in executie a scriptului din shell se poate face invocand
python <scriptname.py> [args] sau
atribuind
permisiuni de executie fisierului
<scriptname>.py apoi
^CR
- in continuare, pentru prezentare a fost folosit interpretorul Scapy;
Util de memorat
Atunci cand este necesara clarificarea unor detalii urmatoarele comenzi pot fi de un real folos:
ptr. listarea tuturor protocoalelor suportate de Scapy:
>>>ls()
ptr. identificarea membrilor unei clase si sintaxa:
>>>ls(nume_proto)
ptr. identificarea comenzilor disponibile:
>>>lsc()
ptr. sintaxa unei comenzi:
>>>help(nume_cmd)
Obiecte Scapy
N.b. pentru fiecare antet TCP/IP a fost definita o clasa;de ex. Ether(), ARP(), IP(),
ICMP(), UDP(), TCP(), s.a.;
Pentru a lista toti membrii unei clase impreuna cu valorile lor implicite, se va folosi metoda
supraincarcata "show()":
>>>IP.show()
sau echivalent
>>>proto = IP()
>>>proto.show()
N.b. cu operatorul "/" putem construi o "ruta" in stiva TCP/IP;
>>>ip = IP(dst="141.85.43.*")
>>>tcp = TCP(sport=RandShort(), dport=(1024, 1500), flags="SRAFPU")/"Hello World!"
>>>(Dot1Q(vlan=1)/Dot1Q(vlan=2)/ip/tcp).show()
Functii de transmisie/receptionare
ptr. transmisia pachetelor pe socket RAW de nivel 3, respectiv de nivel 2:
>>>send(IP(dst="141.85.43.1-100")/tcp [, verbose])
>>>sendp(Ether(dst="00:19:90:ae:b5:c1", ...)/ip/TCP(dport=[80,21])/DNS(rd=1, DNSQR(qtype="NS", qname="k.ro")) )
functii orientate pe tranzactie pe socket RAW de nivel 3, respectiv de
nivel 2, si variantele lor iterative:
>>>[answered, unanswered =] sr(ip/tcp [, retry=..., timeout=..., inter=RandNum(20,80)])
>>>[answered, unanswered =] srloop(ip/tcp [, count=...])
>>>[answered, unanswered =] srp(Ether(...)/ip/tcp)
>>>[answered, unanswered =] srploop(Ether(...)/ip/tcp)
#get last in the list:
>>>answered, unanswered=_
Functia pt. captura de trafic
>>>pkt = sniffer([iface=eth0, filter="tcp", count=0, ..., prn=callback])
>>>print len(pkt) #no. of captured packets
>>>pkt[5:20].summary()
>>>pkt[6].dst
>>>pkt[6][Ether]
>>>pkt[7][TCP].sprintf("%flags%")
>>>pkt[7].sprintf("%TCP.dport%\t%TCP.flags%")
Suport pentru implementarea automatelor
documentatia cu exemplu
Alte functii
verifica daca este pachet ICMP cu functia:
pkt.haslayer(ICMP)
pentru a procesa payload-ul unui pachet de la nivelul TCP:
pkt[TCP].payload()
conversia adr.IP->adr.MAC:
getmacbyIP(...)
generarea de pachete UDP cu campuri aleatoare:
fuzz(UDP())
(non-scapy)conversia adr.IP->nume de domeniu:
gethostbyaddr(...)
(non-scapy)conversia din format intreg -> format ASCII si concatenare siruri:
str(response[TCP].seq) + ":\tseq number"
(non-scapy)generarea unui numar aleator intr-un interval dat:
randint(1, 65535)
(non-scapy)generarea unui MAC aleator:
randMAC()
(non-scapy)generarea unei adrese IP aleatoare:
randIP()
... si parasirea interpretorului scapy cu comanda
>>>quit()