CTF Wiki
  • 简介
  • 如何使用 CTF Wiki
  • introduction
    • CTF 历史
    • CTF 竞赛模式简介
    • CTF 竞赛内容
    • 线下攻防经验小结
    • CGC 超级挑战赛
    • 学习资源
  • misc
    • 杂项简介
    • 取证隐写前置技术
    • 信息搜集技术
    • encode
      • 通信领域常用编码
      • 计算机相关的编码
      • 现实世界中常用的编码
    • picture
      • 图片分析简介
      • JPG
      • PNG
      • GIF
    • audio
      • 音频隐写
    • archive
      • RAR 格式
      • ZIP 格式
    • traffic
      • 流量包分析简介
      • 协议分析概述
        • Wireshark
        • DNS
        • HTTP
        • HTTPS
        • FTP
        • USB
        • WIFI
      • 数据提取
      • PCAP 文件修复
    • disk-memory
      • 磁盘内存分析
      • 题目
    • shellcode
    • other
      • pyc
  • web
    • Web 简介
    • XSS
    • php
      • PHP 代码审计
    • SQL 注入
      • sqlmap绕过脚本
      • 各版本数据库语句备忘
    • CSRF
    • SSRF
  • reverse
    • 软件逆向工程简介
    • identify-encode-encryption
      • 常见加密算法和编码识别
    • language
      • 简介
      • go
        • Golang 逆向入门
      • python
        • Python 逆向入门
      • rust
        • Rust 逆向入门
    • maze
      • 迷宫问题
    • obfuscate
      • 控制流平坦化
      • 花指令
      • movofuscator
      • Self-Modified Code
    • vm
      • 虚拟机分析
    • platform
      • linux
        • Detecting Breakpoints
        • Detecting debugging
        • False Disassembly
        • LD_PRELOAD
      • windows
        • anti-debug
          • CheckRemoteDebuggerPresent
          • 反调试技术例题
          • Heap Flags
          • Interrupt 3
          • IsDebuggerPresent
          • 花指令
          • NtGlobalFlag
          • NtQueryInformationProcess
          • The Heap
          • Thread Local Storage(TLS)
          • ZwSetInformationThread
        • unpack
          • 一步到达 OEP 法
          • ESP 定律法
          • DUMP 及 IAT 重建
          • 最后一次异常法
          • 手动查找 IAT 并使用 ImportREC 重建
          • 内存镜像法
          • 保护壳简介
          • SFX 法
          • 单步跟踪法
          • DLL 文件脱壳
    • tools
      • constraint
        • z3
      • debug
        • gdb
        • ollydbg
        • windbg
        • x64dbg/x32dbg
      • simulate-execution
        • angr
        • Unicorn Engine
      • static-analyze
        • dnspy
        • Ghidra
        • IDA Pro
        • jadx
  • crypto
    • 密码学简介
    • asymmetric
      • 介绍
      • discrete-log
        • 离散对数
        • ECC
        • ElGamal
      • knapsack
        • 背包加密
      • lattice
        • CVP
        • 基本介绍
        • 格基规约算法
        • 格概述
      • rsa
        • RSA 选择明密文攻击
        • RSA 复杂题目
        • Coppersmith 相关攻击
        • 公钥指数相关攻击
        • 模数相关攻击
        • Bleichenbacher's attack
        • RSA 侧信道攻击
        • RSA 介绍
        • d_attacks
          • 私钥 d 相关攻击
          • 扩展维纳攻击
    • attack-summary
      • 简介
      • 比特攻击
      • 中间相遇攻击 - MITM
    • basic
      • 基础数学知识
    • blockcipher
      • AES
      • ARX: Add-Rotate-Xor
      • DES
      • IDEA
      • 块加密
      • Simon and Speck Block Ciphers
      • mode
        • CBC
        • CFB
        • CTR
        • ECB
        • 分组模式
        • OFB
        • Padding Oracle Attack
        • 填充方式
        • PCBC
    • certificate
      • 证书格式
    • classical
      • 古典密码简介
      • 单表代换加密
      • 其它类型加密
      • 多表代换加密
      • 总结
    • hash
      • Hash Attack
      • 综合题目
      • Fowler–Noll–Vo hash function
      • 哈希函数
      • MD5
      • SHA1
    • signature
      • DSA
      • ElGamal
      • 数字签名
      • RSA 数字签名
    • streamcipher
      • 流密码
      • fsr
        • 反馈移位寄存器
        • 线性反馈移位寄存器 - LFSR
        • 非线性反馈移位寄存器
      • lcg
        • 题目
        • 线性同余生成器
      • prng
        • 密码安全伪随机数生成器
        • 伪随机数生成器介绍
        • 题目
      • special
        • RC4
  • pwn
    • MacOS
    • misc-os
    • 概述
      • stackoverflow
        • 执行 Shellcode
        • 栈介绍
        • 栈溢出原理
    • browser
      • Chrome
      • Firefox
      • Safari
    • hardware
      • 简介
        • side-channel
          • prefetch side-channel attack
      • trusted-computing
        • 可信执行环境
    • linux
      • kernel-mode
        • 基础知识
        • Introduction
          • DoS
          • Information Disclosure
          • Introduction
            • Change Others
            • Change Self
        • Introduction
          • Introduction
            • 信息泄漏
            • Misc
          • Introduction
            • Kernel Stack Canary
          • Introduction
            • inner-kernel
              • 内部隔离
            • Introduction
              • KPTI - Kernel Page Table Isolation
              • 用户代码不可执行
              • 用户数据不可访问
          • Introduction
            • FGKASLR
            • KASLR
        • Introduction
          • 编译内核驱动
          • 内核下载与编译
          • Qemu 模拟环境
          • Real Device
        • exploitation
          • heap
            • 内核堆概述
            • buddy
              • Cross-Cache Overflow & Page-level Heap Fengshui
              • Page-level UAF
            • slub
              • freelist 劫持
              • Heap Spray
              • kernel UAF
          • race
            • Double Fetch
            • userfaultfd 的使用
          • rop
            • bypass-smep
            • ret2dir
            • 利用 pt_regs 构造通用内核 ROP
            • ret2usr(已过时)
            • Kernel ROP
          • tricks
            • 在内存中直接搜索 flag
      • user-mode
        • environment
        • fmtstr
          • 检测
          • 例子
          • 利用
          • 原理介绍
        • integeroverflow
          • 整数溢出
        • io-file
          • glibc 2.24下 IO_FILE 的利用
          • 伪造vtable劫持程序流程
          • FSOP
          • FILE结构
        • mitigation
          • Canary
        • race-condition
          • introduction
          • 题目
        • summary
          • 获取地址
          • shell 获取小结
          • 控制程序执行流
        • Type Confusion
        • Uninitialized Memory
        • heap
          • mallocng
          • ptmalloc2
            • Chunk Extend and Overlapping
            • Fastbin Attack
            • 堆概述
            • 堆相关数据结构
            • 堆溢出
            • House Of Einherjar
            • House Of Force
            • House of Lore
            • House of Orange
            • House of Pig
            • House of Rabbit
            • House of Roman
            • 堆利用
            • Large Bin Attack
            • 通过堆进行信息泄漏
            • 堆中的 Off-By-One
            • 堆中的检查
            • tcache makes heap exploitation easy again
            • Unlink
            • Unsorted Bin Attack
            • Use After Free
            • implementation
              • 基础操作
              • 释放内存块
              • 堆初始化
              • malloc_state 相关函数
              • 申请内存块
              • 测试支持
              • 深入理解堆的实现
              • tcache
        • stackoverflow
          • arm
            • 环境搭建
            • Arm ROP
          • mips
            • mips - ROP
          • RISC-V
          • x86
            • 基本 ROP
            • 花式栈溢出技巧
            • 中级ROP
            • 栈介绍
            • 栈溢出原理
            • advanced-rop
              • 高级 ROP
              • ret2dlresolve
              • ret2VDSO
              • SROP
    • sandbox
      • Chroot
      • Docker
      • Namespace
      • python
        • Python 沙盒
      • seccomp
        • C 沙盒逃逸
      • Shell Sandbox
    • virtualization
      • basic-knowledge
        • 虚拟化技术简介
        • CPU 虚拟化
        • IO 虚拟化
        • 内存虚拟化
      • parallels
        • Parallels
      • VirtualBox
      • VMWare
      • qemu
        • basic-knowledge
          • QEMU 设备模拟
          • QEMU 内存管理
        • environment
          • 编写 QEMU 模拟设备
          • QEMU 下载与编译
        • exploitation
          • QEMU 逃逸入门
          • 越界读写
  • Android 安全
    • basic_develop
      • Android 开发基础
    • Android 应用运行机制简述
      • Android 中 Java 层的运行机制
        • dex
          • DEX文件
          • ODEX文件
        • smali
          • Smali
      • native_layer
        • so 介绍
    • basic_reverse
      • Android 关键代码定位
      • Android 逆向基本介绍
      • dynamic
        • Android 动态调试
        • IDA 动态调试原生层程序
        • IDA 动态调试 smali 代码
      • static
        • 静态分析综合题目
        • 静态分析 java 层例子
        • 静态分析原生层程序
  • blockchain
    • Blockchain Security Challenges
    • Blockchain Security Overview
    • ethereum
      • Ethereum Basics
      • Ethereum Overview
      • Ethereum Opcodes
      • 学习资源
      • Smart Contract Reverse
      • Function Selector and Argument Encoding
      • Ethereum Storage
      • attacks
        • Airdrop Hunting
        • Arbitrary Writing
        • CREATE2
        • Delegatecall
        • Introduction
        • Jump Oriented Programming
        • Integer Overflow and Underflow
        • Randomness
        • Re-Entrancy
        • Short Address Attack
        • Uninitialized Storage Pointer
    • publicblockchain
      • Public Blockchain Security Overview
      • Blockchain Weaknesses
  • assembly
    • ARM
    • MIPS
    • x86_x64
  • executable
    • elf
      • 程序加载
      • 程序执行流程
      • linking
        • 程序链接
        • Symbol Reslove
      • structure
        • ELF 文件
        • Code Section
        • Data Related Sections
        • Dynamic Sections
        • Misc Sections
        • Sections
        • String Sections
        • .symtab: Symbol Table
    • pe
      • PE 文件格式
      • 导出表
      • 导入表
      • 基址重定位表
  • ics
    • ICS_CTF 竞赛
    • ICS_CTF 发现
    • ICS_CTF 利用
    • ICS_CTF 学习资源
  • contribute
    • 贡献之前
    • 基本贡献方式
    • 贡献文档要求
    • 翻译
  • write up
    • 浙江工业大学CTF赛事
      • 2023第四届“安恒杯”CTF新生赛题解
Powered by GitBook
On this page
  • 代数系统和近世代数
  • 群
  • 半群和幺半群
  • 交换群
  • 环和域
  • 阶
  • 同态
  • References
  1. crypto
  2. basic

基础数学知识

本部分会介绍“基础数学知识”,这里加了引号,所以并不见得真的很基础。。

代数系统和近世代数

在一个集合中,如若有一种或多种代数运算(Algebraic Operation),我们往往会笼统地称它为代数系统(Algebraic System),也称代数结构(Algebraic Structure)。

作为一个不断进步完善的数学分支,代数学的研究范围也逐渐扩大,其关注的集合亦从古典的整数、有理数、实数与复数等常见数集,扩展到矢量、矩阵、线性算子等对象,并着眼于定义在它们之上的代数运算。这类课题共同组成了如今的近世代数(Modern Algebra)学科,或言抽象代数(Abstract Algebra)。

上文提到的代数运算,是定义在集合中的元素之间的法则,亦与集合是否能作成代数系统有着密切关联,它们扩展自常见的加减乘除这样的运算。经过定义合适的代数运算,集合可以作成群、环、域、格等代数系统,这也是笔者行将介绍的。

群

给定一个集合 $G\neq\varnothing$ 以及其上的二元代数运算「 $\circ$ 」,如若它们满足如下性质:

  1. 封闭性(Closure): $\forall v, u \in G, \quad v \circ u \in G;$

  2. 结合律(Associativity): $\forall v, u, w \in G, \quad (v \circ u) \circ w = v \circ (u \circ w);$

  3. 单位元(Identity): $\exists e \in G, \forall v \in G, \quad e \circ v = v;$

  4. 逆元(Inverse,亦称反元): $\forall v \in G, \exists v^{-1} \in G, \quad v^{-1} \circ v = e;$

则称集合 $G$ 对该代数运算作成一个群(Group),记作 $(G,\circ)$.

一个很常见的例子便是所谓的整数加法群 $(\mathbb{Z},+)$,不难验证其不仅对加法封闭,满足结合律,且存在整数 $0$ 作为单位元,并对于每个整数 $m$ 皆有其相反数 $-m$ 作为其逆元。类似地,可以验证正有理数集 $(\mathbb{Q}_+,\times)$ 对乘法亦作成群(单位元为 $1$ ,对于每个元素 $a$ 其逆元为 $\frac{1}a$);实数域 $\mathbb{R}$ 上的全体 $m$ 阶可逆矩阵对于矩阵乘法作成群(单位元为 $m$ 阶单位矩阵 $E_m$,对于每个元素 $A$ 其逆元为它的逆矩阵 $A^{-1}$),这在近世代数中被称为 $m$ 阶一般线性群 $GL_m(\mathbb{R})$.

此外笔者举出一个更简单的例子,即是定义在集合 ${-1,1}$ 上的乘法群 $({-1,1},\times)$,这亦不难验证其作成一个群。

在近世代数中,研究群的分支被称为群论(Group Theory)。

半群和幺半群

在近世代数中,有些代数系统具有环的部分性质,虽不在我们的主要讨论范围内,但它们也具有广泛的应用场景与不可忽视的研究价值:

对于其上二元代数运算封闭的非空集合,

  • 如若仅满足结合律,那么可以称该集合对该代数运算作成半群(Semigroup);

  • 如若集合对于代数运算除封闭外,满足结合律,且具有单位元,则可以称其对该运算作成幺半群(Monoid)。

由此,我们可以认为:

  • 幺半群是含有单位元的半群;

  • 群是每个元素皆有逆元的幺半群。

举例来说,正整数对于整数加法作成半群,而非负整数对于整数加法作成幺半群,由于零可以视为整数加法的单位元。

交换群

给定一个群 $(G,\circ)$,如若其满足交换律(Commutativity)i.e. $\forall v, u \in G,$

v∘u=u∘v,v \circ u = u \circ v,v∘u=u∘v,

则称这个群是一个交换群或 Abel(阿贝尔)群(Abelian Group)。

易见,上文提到的举例中,整数加法群 $(\mathbb{Z},+)$ 是交换群,但 $m$ 阶一般线性群 $GL_m(\mathbb{R})$ 不是交换群。

环和域

给定一个集合 $R\neq\varnothing$ 以及其上的两个二元代数运算「 $+$ 」和「 $\circ$ 」,如若它们满足如下性质:

  1. $(R,+)$ 作成交换群;

  2. $R$ 对运算「 $\circ$ 」满足结合律: $\forall v, u, w \in R,$ 皆有 $(v \circ w) \circ u = v \circ (w \circ u);$

  3. 分配律(Distributivity): $\forall v, u, w \in R,$ 皆有 $w \circ (v + u) = w \circ v + w \circ u$ 与 $(v + u) \circ w = v \circ w + u \circ w$ 成立;

则称集合 $R$ 对此二代数运算作成一个环(Ring),记作 $(R,+,\circ)$,并常分别称运算「$+$」和「$\circ$」为加法和乘法。

  • 如若环 $R$ 上的乘法存在单位元 i.e. $\exists e \in G, \forall v \in G,$ 皆有 $e \circ v = v,$ 则称环 $R$ 为幺环(Ring with identity);

  • 如若环 $R$ 上的乘法满足交换律,则称其为交换环(Commutative Ring);

  • 如若环 $R$ 中对除加法单位元外任意元素 $a \neq 0$ 皆存在乘法逆元 $a^{-1}$,则称 $R$ 为除环(Division Ring);

  • 如若环 $R$ 既是交换环又是除环,那么环 $R$ 是一个域(Field)。

在部分书籍中,默认环含有乘法单位元,并称不含有乘法单位元的环为伪环(Pseudo Ring)。

在近世代数中,研究环和域的分支被分别称为环论(Ring Theory)和域论(Field Theory)。

在部分繁体中文语境下,域和域论常被称为体和体论(繁体中文分别写作「體」和「體論」)。

阶

指数:仿照数的指数,我们定义群中元素的指数,对于 $v \in G, m$ 为正整数,

  • $v^0 = e;$

  • $v^m = v \circ v \circ \cdots \circ v,$ 其中共有 $m$ 个 $v$ 参与代数运算;

  • $v^{-m} = \left(v^{-1}\right)^m;$

元素的阶:对于任意给定的元素 $v \in G,$ 如若正整数 $m$ 满足 $v^m = e,$ 则称元素 $v$ 的阶数为 $m$. 如若这样的正整数不存在,则称该元素的阶为无限。

举例而言,在群 $\left({1,-1,+\mathrm{j},-\mathrm{j}},\times\right)$ 中,各元素的阶如下:

元素
阶

1

1

-1

2

$+\mathrm{j}$

4

$-\mathrm{j}$

4

同态

代数系统间的同态(Homomorphism)指在不同代数系统间能够保持代数运算的映射。

具体来讲,对于群 $(G,\circ)$ 和 $(H,\ast)$ 而言,如若一个映射 $\psi: G \to H$ 满足 $\forall v, u \in G,$

ψ(v∘u)=ψ(v)∗ψ(u),\psi(v \circ u) = \psi(v) \ast \psi(u),ψ(v∘u)=ψ(v)∗ψ(u),

那么映射 $\psi$ 便可以称为从 $G$ 到 $H$ 的一个群同态。

References

  • 杨子胥,《近世代数》(第四版),高等教育出版社

PreviousbasicNextblockcipher

Last updated 1 year ago

群论简介 - OI-Wiki