Extra space above boxed multi-line equation

Use the empheq package

\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{empheq}
\begin{document}
\begin{empheq}[box=\fbox]{align*}
    &H(x) \colon \\
    &\qquad \textnormal{Select a random $|x|$-bit prime $q$.} \\
    &\qquad \textnormal{Let } r \in_R \mathbb{Z}^*_q \\
    &\qquad \textnormal{Output } \langle r, r^{h(x)} \bmod q \rangle
\end{empheq}
\end{document}

Resulting in

You can even make it a colorbox with

\begin{empheq}[box=\colorbox{yellow}]{align*}

Set \abovedisplayskip to 0pt:

\documentclass{article}
\usepackage{amsmath,amssymb}

\begin{document}

\fbox{\begin{minipage}{6cm}
\setlength\abovedisplayskip{0pt}
\begin{align*}
    &H(x) \colon \\
    &\qquad \textnormal{Select a random $|x|$-bit prime $q$.} \\
    &\qquad \textnormal{Let } r \in_R \mathbb{Z}^*_q \\
    &\qquad \textnormal{Output } \langle r, r^{h(x)} \bmod q \rangle
\end{align*}
\end{minipage}}

\end{document}

Just don't use align for this, which is a task for tabular

\fbox{\renewcommand{\arraystretch}{1.2}
  \begin{tabular}{l@{}l}
  \makebox[2em][l]{$H(x)$:}\\
  & Select a random $|x|$-bit prime $q$. \\
  & Let $r \in_R \mathbb{Z}^*_q$ \\
  & Output $\langle r, r^{h(x)} \bmod q \rangle$
  \end{tabular}}

and you don't even need to guess the width of the alignment.