Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/rsa/common.py: 19%

1# Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu> 

2# 

3# Licensed under the Apache License, Version 2.0 (the "License"); 

4# you may not use this file except in compliance with the License. 

5# You may obtain a copy of the License at 

6# 

7# https://www.apache.org/licenses/LICENSE-2.0 

8# 

9# Unless required by applicable law or agreed to in writing, software 

10# distributed under the License is distributed on an "AS IS" BASIS, 

11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 

12# See the License for the specific language governing permissions and 

13# limitations under the License. 

14 

15"""Common functionality shared by several modules.""" 

16 

17import typing 

18 

19 

20class NotRelativePrimeError(ValueError): 

21 def __init__(self, a: int, b: int, d: int, msg: str = "") -> None: 

22 super().__init__(msg or "%d and %d are not relatively prime, divider=%i" % (a, b, d)) 

23 self.a = a 

24 self.b = b 

25 self.d = d 

26 

27 

28def bit_size(num: int) -> int: 

29 """ 

30 Number of bits needed to represent a integer excluding any prefix 

31 0 bits. 

32 

33 Usage:: 

34 

35 >>> bit_size(1023) 

36 10 

37 >>> bit_size(1024) 

38 11 

39 >>> bit_size(1025) 

40 11 

41 

42 :param num: 

43 Integer value. If num is 0, returns 0. Only the absolute value of the 

44 number is considered. Therefore, signed integers will be abs(num) 

45 before the number's bit length is determined. 

46 :returns: 

47 Returns the number of bits in the integer. 

48 """ 

49 

50 try: 

51 return num.bit_length() 

52 except AttributeError as ex: 

53 raise TypeError("bit_size(num) only supports integers, not %r" % type(num)) from ex 

54 

55 

56def byte_size(number: int) -> int: 

57 """ 

58 Returns the number of bytes required to hold a specific long number. 

59 

60 The number of bytes is rounded up. 

61 

62 Usage:: 

63 

64 >>> byte_size(1 << 1023) 

65 128 

66 >>> byte_size((1 << 1024) - 1) 

67 128 

68 >>> byte_size(1 << 1024) 

69 129 

70 

71 :param number: 

72 An unsigned integer 

73 :returns: 

74 The number of bytes required to hold a specific long number. 

75 """ 

76 if number == 0: 

77 return 1 

78 return ceil_div(bit_size(number), 8) 

79 

80 

81def ceil_div(num: int, div: int) -> int: 

82 """ 

83 Returns the ceiling function of a division between `num` and `div`. 

84 

85 Usage:: 

86 

87 >>> ceil_div(100, 7) 

88 15 

89 >>> ceil_div(100, 10) 

90 10 

91 >>> ceil_div(1, 4) 

92 1 

93 

94 :param num: Division's numerator, a number 

95 :param div: Division's divisor, a number 

96 

97 :return: Rounded up result of the division between the parameters. 

98 """ 

99 quanta, mod = divmod(num, div) 

100 if mod: 

101 quanta += 1 

102 return quanta 

103 

104 

105def extended_gcd(a: int, b: int) -> typing.Tuple[int, int, int]: 

106 """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb""" 

107 # r = gcd(a,b) i = multiplicitive inverse of a mod b 

108 # or j = multiplicitive inverse of b mod a 

109 # Neg return values for i or j are made positive mod b or a respectively 

110 # Iterateive Version is faster and uses much less stack space 

111 x = 0 

112 y = 1 

113 lx = 1 

114 ly = 0 

115 oa = a # Remember original a/b to remove 

116 ob = b # negative values from return results 

117 while b != 0: 

118 q = a // b 

119 (a, b) = (b, a % b) 

120 (x, lx) = ((lx - (q * x)), x) 

121 (y, ly) = ((ly - (q * y)), y) 

122 if lx < 0: 

123 lx += ob # If neg wrap modulo original b 

124 if ly < 0: 

125 ly += oa # If neg wrap modulo original a 

126 return a, lx, ly # Return only positive values 

127 

128 

129def inverse(x: int, n: int) -> int: 

130 """Returns the inverse of x % n under multiplication, a.k.a x^-1 (mod n) 

131 

132 >>> inverse(7, 4) 

133 3 

134 >>> (inverse(143, 4) * 143) % 4 

135 1 

136 """ 

137 

138 (divider, inv, _) = extended_gcd(x, n) 

139 

140 if divider != 1: 

141 raise NotRelativePrimeError(x, n, divider) 

142 

143 return inv 

144 

145 

146def crt(a_values: typing.Iterable[int], modulo_values: typing.Iterable[int]) -> int: 

147 """Chinese Remainder Theorem. 

148 

149 Calculates x such that x = a[i] (mod m[i]) for each i. 

150 

151 :param a_values: the a-values of the above equation 

152 :param modulo_values: the m-values of the above equation 

153 :returns: x such that x = a[i] (mod m[i]) for each i 

154 

155 

156 >>> crt([2, 3], [3, 5]) 

157 8 

158 

159 >>> crt([2, 3, 2], [3, 5, 7]) 

160 23 

161 

162 >>> crt([2, 3, 0], [7, 11, 15]) 

163 135 

164 """ 

165 

166 m = 1 

167 x = 0 

168 

169 for modulo in modulo_values: 

170 m *= modulo 

171 

172 for (m_i, a_i) in zip(modulo_values, a_values): 

173 M_i = m // m_i 

174 inv = inverse(M_i, m_i) 

175 

176 x = (x + a_i * M_i * inv) % m 

177 

178 return x 

179 

180 

181if __name__ == "__main__": 

182 import doctest 

183 

184 doctest.testmod()