Grobner Basis là một công cụ thường được sử dụng trong Algebraic Cryptanalysis. Trong bài viết dưới đây, mình sẽ trình bày vắn tắt các khái niệm, thuật toán cũng như cơ sở toán học xoay quanh Grobner Basis. Cấu trúc đại số Vành đa thức Trước tiên ta cần nhắc lại định nghĩa về vành Vành Vành là một tập hợp $\displaystyle R$ khác rỗng, được trang bị hai phép toán cộng $\displaystyle +:( a,b)\rightarrow a+b$ và nhân $\displaystyle \times :( a,b)\rightarrow a\times b$ thỏa mãn đồng thời các điều kiện sau: $\displaystyle ( R,+)$ là một nhóm giao hoán

Trước khi có sự ra đời của Groebner Basis thì Polynomial Resultant là một công cụ khá mạnh được sử dụng thường xuyên trong các bài toán giải hệ phương trình đa thức. Ngoài ra trong một số trường hợp đặc biệt thì Polynomial Resultant chạy hiệu quả hơn Groebner Basis. Trong bài viết này mình sẽ giới thiệu qua công cụ trên cũng như cơ sở lý thuyết của nó. Đầu tiên mọi người có thể xem qua bài viết trước đó của mình về Groebner Basis. Trong bài mình có định nghĩa cụ thể các khái niệm về đa thức trên các vành giao hoán cũng như cách định nghĩa các đa thức nhiều biến. (vì không biết dịch resultant như thế nào cho hợp lý nên mình sẽ để nguyên như vậy trong bài luôn) Trường hợp đơn biến Resultant của hai đa thức $\displaystyle f( x)$ và $\displaystyle g( x)$ là một giá trị mà nó sẽ triệt tiêu, tức là bằng 0 nếu như $\displaystyle f,g$ có nghiệm chung trong trường đóng đại số của trường mà ta đang nói tới. Để tính resultant của hai đa thức $\displaystyle f$ có bậc $\displaystyle d_{1}$ và $\displaystyle g$ có bậc $\displaystyle d_{2}$ thì ta sẽ viết các hệ số của hai đa thức dưới dạng ma trận Slyvester. https://en.wikipedia.org/wiki/Sylvester_matrix Cụ thể như sau:

Z3 Solver là một SMT solver (Satisfiability Modulo Theories solver hay còn được gọi là trình chứng minh định lí) và được phát triển bởi Microsoft Research. Nhiệm vụ của Z3 là giải các bài toán logic có ràng buộc theo nhiều lí thuyết khác nhau chẳng hạn như số nguyên, bit-vector, mảng hay logic boolean. Mới đầu xài Z3 thì mình thấy nó khả ảo diệu và "magic", ném một đống biểu thức vào z3 và nó tự recover cho mình =)). Sau 1 thời gian dùng thì mình thấy nó vẫn ảo diệu Syntax và ví dụ Mọi người có thể tham khảo syntax và doc của nó tại đây: [1] https://github.com/Z3Prover/doc/tree/master/programmingz3/code [2] https://z3prover.github.io/api/html/z3.z3.html

Các kí hiệu: Các vector với các phần tử trong $\displaystyle \mathbb{R}$ được xem như là vector cột và được biểu thị bằng các chữ in thường đậm, ví dụ $\displaystyle \mathbf{x} ,\mathbf{y} ,\mathbf{z}$. Các ma trận được biểu thị bằng các chữ cái in hoa đậm, ví dụ $\displaystyle \mathbf{A} ,\mathbf{S} ,\mathbf{B} ,...$ Chuyển vị của một vector hoặc ma trận được biểu thị bằng $\displaystyle \mathbf{v}^{T}$ hoặc $\displaystyle \mathbf{V}^{T}$ tương ứng. Ngoài ra, chúng ta biểu thị tích trong của hai vector cột $\displaystyle \mathbf{v} ,\mathbf{w} \in \mathbb{R}^{n}$ theo $\displaystyle \langle \mathbf{v} ,\mathbf{w} \rangle =\mathbf{v}^{T}\mathbf{w}$. Một số kí hiệu khác: $\displaystyle \mathbb{R}^{n\times m}$: không gian của ma trận $\displaystyle n\times m$ với các mục số thực $\displaystyle | \cdotp | ,\ | \cdotp | _{\infty }$: Chuẩn Euclid và chuẩn tối đa $\displaystyle \mathcal{L}$: Một lưới $\displaystyle \mathcal{L}(\mathbf{B})$: lưới với các cột của ma trận $\displaystyle \mathbf{B}$ làm cơ sở.

Cho $\displaystyle A$ là một vành giao hoán có đơn vị 1. Với một kí hiệu $\displaystyle x$, ta gọi $A[x]$ là tập các biểu thức có dạng $\displaystyle f=a_{0} +a_{1} x+...+a_{n} x^{n}$, trong đó $\displaystyle a_{i} \in A$ với mọi $\displaystyle 0\leqslant i\leqslant n,n\in \mathbb{N}$. Giả sử ta có \begin{equation*} f=a_{0} +a_{1} x+...+a_{n} x^{n} ,g=b_{0} +b_{1} x+...+b_{m} x^{m} \in A[ x] \end{equation*} Không mất tính tổng quát có thể giả sử $\displaystyle m\geqslant n$ và $\displaystyle m=n+s$. Khi đó \begin{equation*} g=b_{0} +b_{1} x+...+b_{n} x^{n} +b_{n+1} x^{n+1} +....+b_{n+s} x^{n+s} \in A[ x]

Source code của bài: from Crypto.Random.random import randint, choice import os # In a realm where curiosity roams free, our fearless cat sets out on an epic journey. # Even the cleverest feline must respect the boundaries of its world—this magical limit holds all wonders within. limit = 0xe5db6a6d765b1ba6e727aa7a87a792c49bb9ddeb2bad999f5ea04f047255d5a72e193a7d58aa8ef619b0262de6d25651085842fd9c385fa4f1032c305f44b8a4f92b16c8115d0595cebfccc1c655ca20db597ff1f01e0db70b9073fbaa1ae5e489484c7a45c215ea02db3c77f1865e1e8597cb0b0af3241cd8214bd5b5c1491f # Through cryptic patterns, our cat deciphers its next move.

Về lý thuyết nhóm em/mình có tóm tắt tại đây DHKE là giao thức trao đổi khóa bí mật trên kênh công khai. Lược đồ của thuật toán như sau: image DHKE được thiết kế dựa trên bài toán DLP là bài toán khó. Cụ thể, hai bên $\displaystyle A$ và $\displaystyle B$ muốn trao đổi với nhau một khóa công khai (khóa này có thể được dùng cho nhiều mục đích, chẳng hạn là key cho thuật mã hóa AES).

How AES Work Để xử lí các bài tập trong set đầu tiên này thì cần trang bị một chút kiến thức về AES tại đây: https://www.youtube.com/watch?v=O4xNJsjtN6E&t=102s Keyed Permutations image one-to-one là chỉ ánh xạ song ánh. crypto{bijection} Resisting Bruteforce image

Tài liệu tham khảo về ECC: An Introduction to the Theory of Elliptic Curves An Introduction to Mathematical Cryptography, Jeffrey Hoffstein Các hàm EC trên Sagemath Elliptic Curves, Number theory and Cryptography Về lý thuyết cụ thể cho từng phần mình sẽ lồng trong từng challenge để mọi người tiện theo dõi. CryptoHack

Khái niệm không gian vector là một trong những trụ cột quan trọng của bộ môn đại số tuyến tính. Việc hiểu rõ bản chất của không gian vector giúp ta xây dựng một nền tảng vững chắc phục vụ cho việc tiếp cận các khái niệm cao cấp hơn sau này. Trong bài viết này tác giả sẽ trình bày vắn tắt lại một số kết quả quan trọng liên quan đến không gian vector. Khái niệm Ta sẽ quy ước $\displaystyle \text{K}$ là một trường. Định nghĩa 1. Không gian vector Tập hợp $\displaystyle V$ được gọi là một không gian vector trên $\displaystyle \text{K}$ nếu nó được trang bị hai phép toán, phép toán đầu tiên là phép cộng hai vector, kí hiệu là $\displaystyle +$, phép toán thứ hai là phép nhân một vector với vô hướng $\displaystyle a$, kí hiệu là $\displaystyle \times$. Cụ thể, như sau Phép cộng hai vector : là một ánh xạ $\displaystyle +:V\times V\rightarrow V$ , ví dụ $\displaystyle ( \alpha ,\beta )\rightarrow \alpha +\beta$ Phép nhân hai vector: là một ánh xạ $\displaystyle \times :\text{K} \times V\rightarrow V$ , ví dụ : $\displaystyle ( a,\alpha )\rightarrow a\alpha$ với $\displaystyle a\in \text{K} ,\alpha \in V$

Tiếp tục các bài tập RSA phần trước và note thêm một số bài RSA sưu tầm được. Signing Server Server của bài: socket.cryptohack.org 13374 Source code của bài: #!/usr/bin/env python3 from Crypto.Util.number import bytes_to_long, long_to_bytes from utils import listener

Lý thuyết nhóm Nhóm Đầu tiên ta có khái niệm về phỏng nhóm. Phỏng nhóm là một tập hợp mà trên đó được trang bị một phép toán. Nửa nhóm là một phỏng nhóm sao cho phép toán trên đó có tính chất kết hợp. Tính chất kết hợp của một phép toán hai ngôi $\displaystyle \cdot :X\times X\rightarrow X$ được hiểu là với các phần tử $\displaystyle a,b,c\in X$ thì ta có \begin{equation*} ( a\cdot b) \cdot c=a\cdot ( b\cdot c) \end{equation*} Tiếp theo ta có vị nhóm là một nửa nhóm nhưng có thêm phần tử trung hòa. Phần tử trung hòa $\displaystyle e\in X$ là phần tử sao cho với mỗi $\displaystyle x\in X$ thì ta có hoặc $\displaystyle e\cdot x=x$ hoặc $\displaystyle x\cdot e=x$, tương ứng với vị trí của $\displaystyle e$ so với $\displaystyle x$ trong phép toán ta gọi $\displaystyle e$ là phần tử trung hòa trái hoặc phần tử trung hòa phải. Nếu như $\displaystyle e\cdot x=x\cdot e=x$ thì ta gọi $\displaystyle e$ là phần tử trung hòa hoặc phần tử đơn vị của tập $\displaystyle X$.

Thuật toán image RSA là thuật toán mã hóa công khai cho nên sẽ gồm có 2 cặp khóa công khai và khóa bí mật. Các khóa công khai có dạng $\displaystyle ( n,e)$ được khởi tạo như sau: Ta chọn $\displaystyle n=pq$ là tích của hai số nguyên tố lớn $\displaystyle p$ và $\displaystyle q$ Số mũ lập mã của ta sẽ là số nguyên dương $\displaystyle e$ thỏa mãn $\displaystyle \gcd( e,( p-1)( q-1)) =1$. Tiếp theo là cặp khóa bí mật $\displaystyle ( n,d)$:

Các chall mix một chút kiến thức giữa Web và Crypto :D. Để tiện thì mọi người lên web chính của cryptohack để xem các chall nhé nên mình sẽ không chèn ảnh ở đây Token Appreciation Phần này nói về JWTs - Json Web Tokens. Tóm tắt như sau: Đầu tiên là về JSON. JSON là viết tắt của JavaScript Object Notation, là một loại định dạng dữ liệu dựa trên văn bản để trao đổi dữ liệu giữa các ứng dụng. Ngoài ra nó còn được dùng để truyền dữ liệu giữa máy chủ và ứng dụng web. Định dạng của JSON chỉ đơn giản bao gồm các cặp key-value { "username" : "kimoanh", "email" : "kimoan@gmail.com", "website" : "json.org",

Máy tính lượng tử là một thiết bị sử dụng các định luật vật lí lượng tử để giải các bài toán. Một số máy tính lượng tử đã được triển khai thành công ở quy mô nhỏ và dự kiến sẽ tiếp tục phát triển trong tương lai. Trong bài viết này mình sẽ tóm tắt các khái niệm liên quan đến tính toán lượng tử và thuật toán Shor. Biểu diễn bit và qubit Đầu tiên ta nói về cách thông tin được lưu trữ trong các máy tính cổ điển. Ta đã biết, thông tin trong các máy tính được lưu dưới dạng "bit". Mỗi bit được biểu diễn trong máy tính bởi một đối tượng tồn tại ở một trong hai trạng thái, được kí hiệu là 0 và 1. Chúng ta thao tác, điều chỉnh trạng thái của các bit thông qua các phép toán logic cơ bản bao gồm OR,AND và NOT. Ngoài ra ta còn có thể biểu diễn "bit" dưới dạng vector cột như sau: \begin{equation*} |0\rangle =\begin{pmatrix} 1\ 0 \end{pmatrix} ,\ |1\rangle =\begin{pmatrix} 0\

(Sưu tầm) Trong bài viết dưới đây mình sẽ trình bày lại một bổ đề liên quan đến nâng bậc đồng dư của đa thức theo modulo $p$. Bài toán: Với mỗi đa thức $\displaystyle P( x)$ hệ số nguyên, chứng minh rằng tồn tại số nguyên dương $\displaystyle M$ đủ lớn sao cho tồn tại vô hạn số nguyên dương $\displaystyle n\in \mathbb{N}$ để thỏa mãn $\displaystyle v_{p}( P( n)) \leqslant M,\forall p\in \mathbb{P}$. Lời giải. Bài toán là một hệ quả rất hay của bổ đề Hensel. Cụ thể bài toán yêu cầu ta chứng minh rằng, tồn tại một hằng số $\displaystyle M$ để có vô số số $\displaystyle n$ thỏa mãn trong phân tích tiêu chuẩn của $\displaystyle P( n)$, tất cả các số mũ nguyên tố đều bé hơn $\displaystyle M$.

Tuần vừa rồi lớp CTF NMLT, thầy mình có tổ chức kiểm tra cuối kì bằng các bài tập CTF. Sau đây là WU của mình cho các câu giải được trong quá trình thi. substitution image Chall cho mình một file python như sau KEY = { 'A': 'Q', 'B': 'W', 'C': 'E', 'D': 'R', 'E': 'T', 'F': 'Y', 'G': 'U', 'H': 'I', 'I': 'O', 'J': 'P', 'K': 'A', 'L': 'S', 'M': 'D', 'N': 'F', 'O': 'G', 'P': 'H', 'Q': 'J', 'R': 'K',

Thuật BSGS sử dụng ý tưởng time/memory tradeoff và đúng như cái tên của nó, thuật này giúp giảm thời gian chạy bằng cách tăng chi phí lưu trữ lên, cụ thể ở đây là $\displaystyle O\left(\sqrt{p}\right)$ với $\displaystyle p$ là cấp của nhóm hữu hạn đang xét. Ý tưởng của thuật là như sau: Cho $\displaystyle G$ là một nhóm với $\displaystyle g\in G$ có cấp là $\displaystyle N\geqslant 2$. Để giải bài toán tìm $\displaystyle x$ thỏa $\displaystyle g^{x} =h$ ta làm như sau: Đặt $\displaystyle n=1+\left\lfloor \sqrt{N}\right\rfloor$ thì khi đó $\displaystyle n >\sqrt{N}$. Tạo hai danh sách để lưu các số sau \begin{gather*} \text{Danh sách 1:} \ e,g,g^{2} ,...,g^{n}\ \text{Danh sách 2:} \ h,hg^{-n} ,hg^{-2n} ,..,hg{^{-n}}^{2} \end{gather*}

RSA là một trong những hệ mã khóa công khai đầu tiên và phổ biến nhất. Trải qua lịch sử phát triển và nghiên cứu lâu dài, nhiều thuật toán bẻ khóa RSA đã được chứng minh và đưa vào sử dụng. Trong bài viết dưới đây ta sẽ đi vào tìm hiểu một kĩ thuật tấn công mã khóa RSA dựa vào tính chất của biểu diễn liên phân số của một số. Trước khi bắt đầu ta nhắc qua lại về hệ mã khóa RSA. Hệ mật mã RSA Trước khi tìm hiểu về thuật toán tấn công Wiener, ta nhắc lại lý thuyết về hệ mật mã RSA: Cho $\displaystyle N=pq$ là một số nguyên dương và $\displaystyle p,q$ là hai số nguyên tố có cùng độ lớn bit với nhau. Ta thường chọn $\displaystyle N$ có độ dài 1024 bit tương đương với 309 chữ số thập phân. Như vậy mỗi số nguyên tố $\displaystyle p,q$ có độ dài 512 bit mỗi số. Sau khi chọn được $\displaystyle N$ ta sẽ thực hiện tính toán $\displaystyle \varphi ( N) =( p-1)( q-1)$ và sau đó chọn một số $\displaystyle e$ sao cho $\displaystyle 1< e< \varphi ( N)$ đồng thời $\displaystyle ( e,\varphi ( N))$. Lúc này $\displaystyle e$ được gọi là khóa công khai của hệ mật mã RSA còn $\displaystyle N$ được gọi là modulo của hệ mật mã RSA. Để hoàn thiện sơ đồ mã hóa thì ta cần chọn thêm một số $\displaystyle d$ thỏa mãn \begin{equation*} ed\equiv 1\bmod( \varphi ( n))

Tuần vừa rồi team bọn mình - UIT.0r2 có tham gia giải 1337UP LIVE CTF 2024. Các thành viên trong team gồm có 5 bạn lớp ATTN2024: Lê Trí Đức (dvck13) Đặng Minh Tú (l1ttl3) Phạm Nguyễn Thành Long (tatsuya_akira) Nguyễn Tuấn Hùng (hn1106) Vũ Hoàng Long (logn) Sau đây là writeup của bọn mình cho các chall trong giải.