【命题1】控制流图G中若a dom n，且b dom n，则a dom b 或b dom a
【证明】设G入口为s，假设结论不成立，即a 不dom b且b 不dom a，或a dom b且b dom a。根据支配结点定义，如果是前者，则从s有全部路径经a（或b）到n但不经过b（或a），这与题设b（或a）dom n矛盾；如果是后者，则从s有全部路径经a，然后经b，再经a，构成了无限循环a->b->a->•••，永远到不了n，这也与题设矛盾。故结论成立
【命题2】控制流图G中若m idom n，则m是唯一的，若d ≠ n 且d dom n ，则d dom m
【证明】设G入口为s，假设不唯一，G中有另一个结点m'且m' idom n，根据支配结点定义，从s经m到n的路径上必有m' dom m，从s经m'到n的路径上必有m dom m'，根据支配关系的反对称性，有m'=m，故唯一。假设d 不dom m，则从s到m的路径上不必然经过d，又m是n的唯一直接支配结点，则从s到n的路径上不必然经过d，即d 不dom n，这与题设矛盾，故d dom m。可以看到用反证法证明后一个结论时，直接支配结点的唯一性很关键
posted @
2023-09-06 22:57 春秋十二月 阅读(355) |
评论 (0) |
编辑 收藏1. 迭代算法在什么情况下是正确的
数据流值满足半格的定义，以及数据流方程中的传递函数满足单调性
2. 迭代算法在什么情况下必定收敛
在满足正确性的前提下，当数据流值对应的半格高度有限时，必定收敛。以最小元为初值的迭代收敛于最小不动点，以最大元为初值的迭代收敛于最大不动点
3. IDEAL、MOP、MFP三种解的意义与关系
IDEAL是理想解即最精确的解，它将程序入口entry到某点p所有可达路径（可执行路径）的尾端的数据流值做聚合操作，区分来自不同路径的数据流值，若聚合操作是交运算，则最大下界为其值，任何大于IDEAL的解都是错误的，而小于IDEAL的解是保守的；若聚合操作是并运算，则最小上界为其值，任何小于IDEAL的解都是错误的，而大于IDEAL的解是保守的。MOP是全路径聚合解，它将entry到p所有流图路径（不一定可执行）的尾端的数据流值做聚合操作，区分来自不同路径的数据流值，若包含了不可执行路径，则会丢失精确性，否则等于IDEAL；MFP是基于数据流方程与迭代算法求得的最大或最小不动点解，它在每个控制流图的汇合节点做聚合操作而非路径尾端，不区分来自不同路径的数据流值，若传递函数不满足分配律，则会丢失精确性，否则等于MOP。故精确性关系为MFP<=MOP<=IDEAL，可知MFP解是安全的，基于MFP作的优化是正确的
4. 为什么不采用IDEAL和MOP解
因为一般程序路径数可能无限，所以没有求MOP的有效算法，且不可达路径是一个不可判定问题，所以没有求IDEAL的有效算法
posted @
2023-09-06 22:53 春秋十二月 阅读(23) |
评论 (0) |
编辑 收藏为什么要加宽算子？
因为当格的偏序集合L不满足升链条件，从最小元迭代计算最小不动点的过程是不收敛的，即迭代序列(fⁿ(⊥))ₙ不保证最终稳定，且其最小上界不保证等于最小不动点，因此需要一种近似lfp(f)的方法。引入加宽算子fw:L×L—>L, fw(x)=x▽f(x)，可以将L上的一个序列转为收敛的升链，从L的最小元开始迭代不断上升，直至lfp(f)的一个上近似即fw的最小不动点lfp(fw)，关系式为lfp(f)<=f(lfp(fw))<=fw(lfp(fw))=lfp(fw)。对上式反复应用f单调得到：lfp(f)<=fⁿ⁺¹(lfp(fw))<=fⁿ(lfp(fw))<=…<=f(lfp(fw))<=lfp(fw)，这表明对lfp(fw)使用f迭代可获得更精确的上近似，其过程可看成沿一个递降链进一步逼近lfp(f)，但L不一定满足降链条件而导致上述过程不收敛，故需要引入变窄算子fn:L×L—>L, fn(x)=x△f(x)，将L的一个序列转为收敛的降链，从lfp(fw)开始迭代，不断下降直至fn的一个不动点fp(fn)，则有关系式：lfp(f)<=fp(fn)<=lfp(fw)。注意，这里根据加宽算子的定义可知fw是单调的，但根据变窄算子的定义不确定fn是否单调，故从lfp(fw)迭代求得的fp(fn)，不确定是最小还是最大不动点，只能说是一个不动点，这也反映了变窄算子不需要满足单调性，就可以更加逼近lfp(f)
posted @
2023-09-06 22:45 春秋十二月 阅读(39) |
评论 (0) |
编辑 收藏【性质】
1. 判定两个完全格L和M能否构成伽罗瓦连接，即抽象化函数α: L—>M是否完全加性的，或具体化函数γ: M—>L是否完全乘性的
2. 构造抽象化函数和具体化函数，即对于一个Galois连接（L, α, γ, M），给定α可通过γ(m) = ⊔{l | α(l) ⊑ m}确定γ，这对于所有m成立，且由于α是确定的，因此γ是唯一确定的。取最小上界是为了保证m描述的L中元素对于所有安全地描述了M中α(l)的l是安全的；给定γ可通过 α(l) = ⊓ {m | l ⊑ γ(m) } 确定α，其唯一性和取最大下界的原因类似前面
3. 帮助定义分析具体格源值到抽象格属性的正确性关系与表示函数。设有Galois连接（L, α, γ, M），R: V×L —>{true, false}为正确性关系，由表示函数β:V—>L生成，定义S: V×M —>{true, false}，则有v S m ⇔ v R (γ(m)) ⇔ β(v ) ⊑ γ(m) ⇔ (α◦β)(v) ⊑ m，即S为正确性关系，由表示函数α◦β: V—>M生成
4. 抽象化上迭代多次具体化+抽象化，结果等于一次抽象化，即α◦γ◦α = α；具体化上迭代多次抽象化+具体化，结果等于一次具体化，即γ◦α◦ γ = γ。这个性质被用于基于约化算子构造的伽罗瓦插入（特殊的伽罗瓦连接：具体化为单射，抽象化为满射）的证明
【组合】
分三大类，即顺序组合、并行组合和函数空间。为简化描述，下文简称Galois为G
1. 顺序组合：取第一个G连接的具体格，最后一个G连接的抽象格，从第一个G连接到最后一个G连接组合各抽象化函数，从最后一个G连接到第一个G连接组合各具体化函数。例如，设（L₀, α₁, γ₁, L₁）和（L₁, α₂, γ₂, L₂）都是G连接，则（L₀, α₂◦α₁, γ₂◦γ₁, L₂）也是一个G连接
2. 并行组合：有六种方法，即独立特征、相关性、直积、直张量积、约化积、约化张量积，前两种用于组合分别针对不同结构多个分析的多个G连接为一个G连接。中间两种组合针对同一结构多个分析的多个G连接为一个G连接，后两种组合针对同一结构多个分析的多个G连接为一个G插入。独立特征、直积、约化积与其它方法的区别是两对抽象化函数与具体化函数之间没有相互作用，会损失分析结果精度，本质就是P(A)×P(B)和P(A×B)的差别（P为幂集，A、B为集合）；独立特征与直积、约化积的区别是具体化函数定义不同（抽象化函数相同），前者是两个具体化函数的二元组即γ(m₁, m₂)=(γ₁(m₁), γ₂(m₂))，后者则是最大下界即γ(m)=γ₁(m₁)∧γ₂(m₂)
3. 函数空间：分为总函数空间和单调函数空间。对于前者，设（L, α, γ, M）为一个G连接，S为一个集合，f为S到L的函数，g为S到M的函数，因L和M为完全格，故由f或g构成的函数集合为总函数空间，则得到一个G连接（S—>L, α', γ', S—>M），其中α'(f)=α◦f, γ'(g)=γ◦g。对于后者，设（L₁, α₁, γ₁, M₁）和（L₂, α₂, γ₂, M₂）为G连接，f为L₁到L₂的函数，g为M₁到M₂的函数，因每个L及M为完全格，故由f或g构成的函数集合为单调函数空间，则得到一个G连接（L₁—>L₂, α, γ, M₁—>M₂），其中α(f)=α₂ ◦f ◦γ₁，γ(g)=γ₂◦ g◦ α₁
【应用】
当要做数据流分析的一个完全格L不满足升链条件时，除了直接对L运用加宽算子及变窄算子外，还怎么去计算近似它的最小不动点？这时伽罗瓦连接就派上用场了，先将L对应到另一个完全格M，即构造一个Galois连接或插入（L, α, γ, M），设A是L上的广义单调框架（不要求L满足升链条件，指定传递函数集合F为L到L的单调函数空间，即F本身也是完全格），其中f是L到L的单调函数，B是M上的广义单调框架，其中g是M到M的单调函数，保证g是由f衍生的函数的上近似即α◦f◦γ ⊑ g，及M满足升链条件。到了这里可以证明两个结论：
➀ lfp(f) ⊑ γ(lfp(g)) 和 α(lfp(f)) ⊑ lfp(g)
➁B的约束解(B₁, B₂)蕴含A的约束解(A₁, A₂)=(γ◦B₁, γ◦B₂)，下标1、2表示流图结点的入口、出口。接下来有两种方法可以计算近似L的最小不动点
1. 直接计算M上的最小不动点，然后应用上述结论➀，取lfp(f) = γ(lfp(g))
2. 构造M的上界算子（针对Galois连接）或加宽算子（针对Galois插入），满足 l₁ ∇ₗ l₂ = γ(α(l₁) ∇ₘ α(l₂))，可以证明左式为L上的一个加宽算子，取其lfp∇ₗ (f)。如果前面构造的是Galois插入，那么可以证明L和M两者的加宽算子精度是一样的，即lfp∇ₗ (f) = γ(lfp∇ₘ(α◦f◦γ ))
posted @
2023-09-06 22:42 春秋十二月 阅读(223) |
评论 (0) |
编辑 收藏定理：集合Z[n]由所有i=0,1,…, n-1整数组成，其中满足gcd(i,n)=1的元素与乘法模n操作形成了交换群G，且单位元为e=1。
证明：设a、b属于G，有gcd(a,n)=1，gcd(b,n)=1，则gcd(a*b,n)=gcd(b,n)=1，即(a*b) mod n封闭，显然单位元为1；根据扩展欧几里德算法得a*x+n*y=1，x为a的逆元，则1=gcd(a,n)=gcd(a*x,n)=gcd(x,n)，故x也在G中
posted @
2023-09-06 22:34 春秋十二月 阅读(247) |
评论 (0) |
编辑 收藏记输出为[G`, G, p, q, g]，其中p为大素数，G`为模p的有限循环整数群，阶为p-1；q为大素数，为G的阶，G为G`的子群（模亦是p），生成元为g（G`的一个元素），另外满足如下条件：
1. 1<q的位长<p的位长，p、q随机选取，p同余于1 mod q，即q整除p-1，q为p-1的素因子
2. 1<g<=p-1，随机选取，测试它的(p-1)/q次幂是否等于1 mod p，若等于则重新选取，直到不等于
3. 上面选定的g，遍历1到q的幂模p，就得到G的各元素
数学基础：一个有限群，对每个元素它的阶整除群的阶，它的群阶幂次方等于单位元；一个有限循环群，它的生成元个数为群阶的欧拉数，若群阶是素数，则所有非1的元素都是生成元
结论：这种计算子群的方法由于保证阶为素数且只要超过160位长，就可避免针对阶为合数的质因子分解并利用中国剩余定理求离散对数的已知最好攻击，具有中长期安全强度
posted @
2023-09-06 22:28 春秋十二月 阅读(295) |
评论 (0) |
编辑 收藏定理：令K[x]是由次数小于8、系数为0或1的多项式组成的环，m(x)=x^8+x^4+x^3+x+1为不可约多项式，则K[x]/(m(x))（模m(x)剩余类环）同构于元素个数为256的有限域F
证明：
1. 构造映射H: P->Z，P表示K[x]中的多项式，Z表示小于256的非负整数，定义函数h(p)=z(mod 256)。显然H为双射；依初等数论同余性质有h(p1+p2)=(z1+z2)mod 256=z1(mod 256)+z2(mod 256)=h(p1)+h(p2)，h(p1*p2)=z1*z2(mod 256)=z1(mod 256)*z2(mod 256)=h(p1)*h(p2)，故H保持加法乘法封闭性。这点保证支持任意明文/密文的运算
2. 由一元多项式环的性质得多项式乘法可以交换，即f(x)•g(x)=g(x)•f(x)，满足域的交换条件。其乘法单位元是常数项1，满足域的单位元条件
3. 因非零多项式f(x)与m(x)互素，由一元多项式环的互素定理知存在g(x)、k(x)使得f(x)•g(x)+m(x)•k(x)=1(系数模2)，即f(x)•g(x)模m(x)余1（这里1表示单位元），故f(x)存在逆元，由群定义知逆元必唯一，满足域的逆元条件。另aes规定零多项式的逆元为其自身。这点保证s盒及列混合操作可逆
posted @
2023-09-06 22:22 春秋十二月 阅读(1342) |
评论 (0) |
编辑 收藏posted @
2021-12-13 15:21 春秋十二月 阅读(635) |
评论 (0) |
编辑 收藏
由于实际使用中RSA公钥通常很短，而私钥和模位长度一样，导致解密(或签名)时大数指数模运算比较慢，故可使用中国剩余定理约简模数和解密指数，以加快运算
描述
x为密文，n为模，p和q为大素数且满足n=pq，d为私钥，设
x
p ≡ x mod p，x
q ≡ x mod q
(1)
d
p ≡ d mod (p-1)，d
q ≡ d mod (q-1)
(2)
y
p = x
p^d
p mod p，y
q = x
q^d
q mod q
(3)
则有 x
d ≡ ((qc
p)y
p + (pc
q)y
q) mod n，其中 c
p ≡ q
-1 mod p ， c
q ≡ p
-1 mod q
证明
由(1)式可得
x
pd ≡ x
d mod p，x
qd ≡ x
d mod q
(4)
根据中国剩余定理可得
x
d ≡ ((qc
p)x
pd + (pc
q)x
qd) mod n，下面只要证明y
p和x
pd一样同余于x
d模p，y
q和x
qd一样同余于x
d模q
根据
(2)式及费小马定理可得
x
p^d
p ≡ x
pd mod p，x
q^d
q ≡ x
qd mod q, 再结合(4)得
x
p^d
p ≡ x
d mod p，x
q^d
q ≡ x
d mod q，故
y
p = x
d mod p，y
q = x
d mod q 证毕
posted @
2021-10-01 17:32 春秋十二月 阅读(1289) |
评论 (0) |
编辑 收藏算法描述
如果对于任意0<=a<p和0<=b<q(p和q皆是素数)，那么当x<p*q时，存在一个唯一的x，使得x≡a mod p 且 x≡b mod q，则
x =(((a - b)*u) mod p)*q + b，其中u满足u*q≡1 mod p。
算法证明
1.先推导x的解
因x≡a mod p 且 x≡b mod q
故令x = k1*p + a 且 x = k2*q + b (1)
即 k1*p + a = k2*q + b
=> a - b = k2*q - k1*p (2)
又因u*q≡1 mod p，故令u*q = 1 + k3*p (3)
由(2)和(3)式
=> a - b = k2 * (1+k3*p)/u - k1*p
两边同时乘u
=>（a - b) * u = k2*(1+k3*p) - k1*p*u
两边同时模p
=> ((a - b) * u) mod p = (k2 mod p) mod p (4)
又因x < p*q，故b + k2*q < p*q
=> b <(p - k2) * q
因0<b<q，故p > k2
=> (k2 mod p) mod p = k2
故(4)式即
((a - b) * u) mod p = k2 (5)
将(5)代入(1)式可得
x = (((a - b)*u) mod p)*q + b
2. 再证明x是唯一解
假设x1是另一解，即 x1≡a mod p 且 x1≡b mod q，得
x1 - x ≡ 0 mod p 即 p | x1 - x
x1 - x ≡ 0 mod q 即 q | x1 - x
又因p和q皆为素数，故p*q | x1 - x，得
x1 - x ≡ 0 mod (p*q)
故 x1 mod (p*q) = x mod (p*q) 证毕
posted @
2021-09-19 16:01 春秋十二月 阅读(992) |
评论 (0) |
编辑 收藏