📒
Book of VanLuong
  • 👨‍💻About the Author
  • Cryptanalysis
    • RSA & RSA ATTACK
    • DES (Data Encryption Standard)
    • AES (Advanced Encryption Standard)
    • ECC ( Elliptic Curve of Cryptography)
    • Group-based Cryptography
    • Lattice-based Cryptography
    • ChaCha20-Poly1305
    • Hash Function
    • Wargame CTF
  • Windows
    • 70 Vital Windows Commands
  • Guide to Installing Kali Linux, DVWA, and bWAPP
    • Phần 1. CÀI ĐẶT HỆ ĐIỀU HÀNH KALI LINUX
    • Phần 2. CÀI ĐẶT DVWA
    • Phần 3. CÀI ĐẶT BWAPP
  • Cybersecurity Lab & Threat Intelligence
    • Build ELK Lab
      • Configure Elasticsearch and Kibana setup in ubuntu
      • Fluent Bit – Sending Logs to ELK with Fluent Bit
      • Winlogbeat – Collecting and Forwarding Windows Event Logs.
      • Filebeat – Collecting and Forwarding Windows Event Logs.
      • Send Logs from Winlogbeat through Logstash to ELK
      • Audit policy & Winlogbeat
    • Watch full series
  • CyberDefender Labs
Powered by GitBook
On this page
  • Định nghĩa
  • Tính chất
  • Tính đóng
  • Tính kết hợp
  • Phần tử đơn vị
  • Phần tử nghịch đảo
  • Tính giao hoán
  • Order của một nhóm
  • Định ý Lagrange
  • Định lý Cauchy
  • Vành (Ring)
  • Trường (Field)
  • Diffie-Hellman
  • Reference

Was this helpful?

  1. Cryptanalysis

Group-based Cryptography

PreviousECC ( Elliptic Curve of Cryptography)NextLattice-based Cryptography

Last updated 7 months ago

Was this helpful?

Định nghĩa

Trong toán học, một nhóm (group) là một tập hợp các phần tử được trang bị một phép toán hai ngôi kết hợp hai phần tử bất kỳ của tập hợp thành một phần tử thứ ba thỏa mãn bốn điều kiện gọi là tiên đề nhóm, lần lượt là tính đóng, tính kết hợp, sự tồn tại của phần tử đơn vị và tính khả nghịch. Một trong những ví dụ quen thuộc nhất về nhóm đó là tập hợp các số nguyên cùng với phép cộng; khi thực hiện cộng hai số nguyên bất kỳ luôn thu được một số nguyên khác. Hình thức trình bày trừu tượng dựa trên tiên đề nhóm, tách biệt nó khỏi bản chất cụ thể của bất kỳ nhóm đặc biệt nào và phép toán trên nhóm, cho phép nhóm bao trùm lên nhiều thực thể với nguồn gốc toán học rất khác nhau trong đại số trừu tượng và rộng hơn, và có thể giải quyết một cách linh hoạt, trong khi vẫn giữ lại khía cạnh cấu trúc căn bản của những thực thể ấy. Sự có mặt khắp nơi của nhóm trong nhiều lĩnh vực bên trong và ngoài toán học khiến chúng trở thành nguyên lý tổ chức trung tâm của toán học đương đại

Nhóm là một tập hợp, G, cùng với phép toán hai ngôi * (còn gọi là luật nhóm của G) kết hợp hai phần tử a và b bất kỳ để tạo ra một phần tử khác, viết là a * b hoặc ab.

Tính chất

Tính đóng

∀a, b∈G, (a∗b)∈G\forall a, \ b \in G, \ (a * b) \in G∀a, b∈G, (a∗b)∈G

Tính kết hợp

∀a ,b , c∈G, (a ∗ b) ∗ c = a ∗ (b ∗ c)\forall a \ ,b \ , \ c \in G, \ (a \ * \ b) \ * \ c \ = \ a \ * \ (b \ * \ c)∀a ,b , c∈G, (a ∗ b) ∗ c = a ∗ (b ∗ c)

Phần tử đơn vị

Tồn tại một phần tử e trong nhóm G sao cho

Phần tử nghịch đảo

tồn tại một phần tử a^{-1} (phần tử nghịch đảo của a) trong nhóm G sao cho

Tính giao hoán

Nếu * có tính giao hoán

thì nhóm G sẽ được gọi là nhóm giao hoán hay nhóm Abel

Order của một nhóm

Nhóm hữu hạn là một nhóm có số phần tử hữu hạn

Xét một nhóm hữu hạn G

  1. Bậc của nhóm là số phần tử của nhóm đó, kí hiệu

  1. Bậc của một phần tử a \in G là số nguyên dương m nhỏ nhất sao cho a^m = e với e là phần tử đơn vị của nhóm, kí hiệu

Kí hiệu

là nhóm con sinh bởi

Ta có tính chất

( Bậc của nhóm con sinh bởi a bằng bậc của a)

Định ý Lagrange

Nếu H là nhóm con của G thì

là ước của

Hệ quả:

với p nguyên tố và a \ne 0. Xét nhóm nhân

ta có

Mặt khác

Định lý Cauchy

Cho nhóm G hữu hạn. Nếu cấp của G chia hết cho p, và p là số nguyên tố, thì tồn tại ít nhất một phần tử a thuộc G có cấp bằng p.

Vành (Ring)

Xét tập hợp R với 2 phép toán + và *, R được gọi là một vành nếu ta có các tính chất sau:

  1. Cộng và nhân có tính đóng

  2. Cộng và nhân có tính kết hợp:

  1. Tồn tại phần tử đơn vị cho phép cộng và nhân, ta kí hiệu 0 và 1 lần lượt là phần tử đơn vị của phép cộng và nhân:

  1. Phép cộng có tính giao hoán

  1. Tồn tại phần tử nghịch đảo cho phép cộng

  1. Tính phân phối của phép nhân đối với phép cộng:

Ví dụ: Tập hợp các ma trận vuông 2x2 trên tập số thực là một vành. Nếu R là một vành thì tập hợp các ma trận nxn với mỗi phần tử ma trận \in R , kí hiệu M_n(R) , cũng là một vành

Trường (Field)

Xét tập hợp F với 2 phép toán + và *. F được gọi là một trường nếu nó thỏa các tính chất sau:

  1. Cộng và nhân có tính đóng

  2. Cộng và nhân có tính giao hoán

  3. Tồn tại phần tử đơn vị cho cộng và nhân, kí hiệu lần lượt là 0 và 1.

  4. Tồn tại phần tử nghịch đảo

  1. Tính phân phối của phép nhân đối với phép cộng:

Trường hữu hạn là một trường có số phần tử là hữu hạn. Một trường hữu hạn thường gặp là $Z_p$ với p là số nguyên tố

Diffie-Hellman

Để giải quyết các bài trong phần này, mình sẽ giải thích tóm tắt về trao đổi khóa Diffie-Hellman.

Alice và Bob thỏa thuận sử dụng chung một nhóm cyclic hữu hạn G và một phần tử sinh g của G. Phần tử sinh g công khai với tất cả mọi người, kể cả kẻ tấn công. Giả sử nhóm G là nhóm nhân.

  1. Đầu tiên Alice chọn ngẫu nhiên một số tự nhiên a và gửi g^a \ mod \ p cho Bob

  2. Tiếp đó Bob chọn ngẫu nhiên một số tự nhiên b và gửi g^b \ mod \ p cho Alice

  3. Trên cơ sở đó Alice tính (g^a)^b \ mod \ p = g^{ab} \ mod \ p

  4. Trên cơ sở đó Alice tính (g^a)^b \ mod \ p = g^{ab} \ mod \ p

  5. Khi đó (g^b)^a = (g^a)^b vì nhóm G có tính kết hợp, Alice và Bob tính được giá trị g^{ab} và sử dụng nó cho khóa bí mật chung.

  6. Các giá trị a, b, g^{ab} = g^{ba} \ mod \ p được giữ bí mật, các giá trị p, \ g, \ g^a \ mod \ p , \ g^b \ mod \ p được truyền công khai.

  7. Alice và Bob tính được bí mật chung, cả hai có thể sử dụng nó làm khóa mã hóa chung chỉ có hai người biết để gửi dữ liệu trên kênh truyền thông mở.

Reference

∀a∈G, a ∗ e = e ∗ a = a\forall a \in G, \ a \ * \ e \ = \ e \ * \ a \ = \ a∀a∈G, a ∗ e = e ∗ a = a
∀a∈G\forall a \in G∀a∈G
a∗a−1=a−1∗a=ea*a^{-1}=a^{-1}*a =ea∗a−1=a−1∗a=e
∀a∈G, a∗b=b∗a\forall a \in G, \ a * b = b * a ∀a∈G, a∗b=b∗a
∣G∣\vert G \vert∣G∣
∣a∣ \vert a \vert∣a∣
⟨a⟩\langle a \rangle⟨a⟩
a∈G,⟨a⟩=ak∣k∈Za \in G, \langle a \rangle = {a^k \vert k \in \mathbb{Z}}a∈G,⟨a⟩=ak∣k∈Z
∣⟨a⟩∣=∣a∣\lvert \langle a \rangle \rvert = \lvert a \rvert∣⟨a⟩∣=∣a∣
∣H∣\vert H \vert∣H∣
∣G∣\vert G \vert∣G∣
∣ G ∣ ⋮ ∣ a ∣, ∀ a ∈ G\vert \ G \ \vert \ \vdots \ \vert \ a \ \vert, \ \forall \ a \ \in \ G∣ G ∣ ⋮ ∣ a ∣, ∀ a ∈ G
ap−1=1(modp)a^{p-1} = 1 \pmod pap−1=1(modp)
Zp∗=1ˉ,2ˉ,…,p−1‾\mathbb{Z}_p^* = {\bar{1}, \bar{2}, \dots, \overline{p-1}}Zp∗​=1ˉ,2ˉ,…,p−1​
∣Zp∗∣=p−1\vert \mathbb{Z}_p^* \vert = p - 1∣Zp∗​∣=p−1
 ∣ Zp∗ ∣ ⋮ ∣ a ∣ ne^n ap−1 = ak∣ a ∣ = 1 (mod )p(do a∣ a ∣ = 1 (mod )p) \ \vert \ \mathbb{Z}_p^* \ \vert \ \vdots \ \vert \ a \ \vert \ nên \ a^{p-1} \ = \ a^{k\vert \ a \ \vert} \ = \ 1 \ \pmod \ p(do \ a^{\vert \ a \ \vert} \ = \ 1 \ \pmod \ p) ∣ Zp∗​ ∣ ⋮ ∣ a ∣ ne^n ap−1 = ak∣ a ∣ = 1 (mod )p(do a∣ a ∣ = 1 (mod )p)
∀a,b,c∈R,(a+b)+c=a+(b+c),(a∗b)∗c=a∗(b∗c)\forall a, b, c \in R, (a + b) + c = a + (b + c), (a * b) * c = a * (b * c)∀a,b,c∈R,(a+b)+c=a+(b+c),(a∗b)∗c=a∗(b∗c)
∀a∈R,a+0=0+a=a,a∗1=1∗a=a\forall a \in R, a + 0 = 0 + a = a, a * 1 = 1 * a = a∀a∈R,a+0=0+a=a,a∗1=1∗a=a
a+b=b+a,∀a,b∈Ra + b = b + a, \forall a, b \in Ra+b=b+a,∀a,b∈R
∀a∈R,∃b∈R,a+b=0\forall a \in R , \exists b \in R, a + b = 0∀a∈R,∃b∈R,a+b=0
a ∗ (b + c) = (a ∗ b) + (a ∗ b), (b + c) ∗ a = (b ∗ a) + (c ∗ a)a \ * \ (b \ + \ c) \ = \ (a \ * \ b) \ + \ (a \ * \ b), \ (b \ + \ c) \ * \ a \ = \ (b \ * \ a) \ + \ (c \ * \ a)a ∗ (b + c) = (a ∗ b) + (a ∗ b), (b + c) ∗ a = (b ∗ a) + (c ∗ a)
−a, ∀ a ∈ F thỏa a +(−a)=0-a, \ \forall \ a \ \in \ F \ thỏa \ a \ +(-a)=0−a, ∀ a ∈ F thỏa a +(−a)=0
∀ a ≠ 0, ∃ a−1 thỏa ma~n a∗a−1 = 1\forall \ a \ \ne \ 0, \ \exists \ a^{-1} \ thỏa \ mãn \ a*a^{-1} \ = \ 1∀ a = 0, ∃ a−1 thỏa ma~n a∗a−1 = 1
a∗(b+c)=(a∗b)+(a∗c)a * (b+c)=(a * b)+(a * c)a∗(b+c)=(a∗b)+(a∗c)

Các bạn có thể đọc hoặc xem để hiểu rõ và lấy cảm hứng để giải những challenges trong phần này.

[1]

[2]

[3]

[4]

[5]

[6]

Diffie-Hellman
ATTT-Diffie-Hellman
https://vi.wikipedia.org/wiki/L%C3%BD_thuy%E1%BA%BFt_nh%C3%B3m
https://websitehcm.com/ly-thuyet-so-nhom-vanh-truong/
https://vi.wikipedia.org/wiki/Tr%C6%B0%E1%BB%9Dng_(%C4%91%E1%BA%A1i_s%E1%BB%91)
https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchangehttps://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
https://www.amazon.com/Introduction-Mathematical-Cryptography-Undergraduate-Mathematics/dp/1441926747
https://vi.wikipedia.org/wiki/Tr%C6%B0%E1%BB%9Dng_h%E1%BB%AFu_h%E1%BA%A1n